在线可中断二台机器流水作业问题

运筹与管理 ›› 2011, Vol. 20 ›› Issue (5): 27-30.

在线可中断二台机器流水作业问题

杨名, 鲁习文, 汪磊扬

华东理工大学理学院数学系,上海 200237

收稿日期:2010-07-25 出版日期:2011-10-25
作者简介:杨名(1984-),男,博士研究生,主要研究方向:排序理论;鲁习文(1962-),男,湖北人,教授,博士生导师,主要研究方向:排序理论,优化理论与应用,数学模型。
基金资助:
国家自然科学基金资助项目资助(10771067);上海市自然科学基金资助项目资助(09ZR1407200)

Online Preemptive Scheduling of Two-machine Flow Shops

YANG Ming, LU Xi-wen, WANG Lei-yang

Dept. of Mathematics, East China University of Science and Technology, Shanghai 200237, China

Received:2010-07-25 Online:2011-10-25

摘要/Abstract

摘要： 本文研究了可中断的二台机器流水作业排序问题,目标函数为最小化最大完工时间,工件实时到达,工件信息在工件到达之前不可知。我们给出了该在线问题的下界,并对问题中只有两个到达时间的特殊情况给出了3/2竞争的在线算法。

关键词: 组合最优化, 流水作业, 在线算法, 可中断, 竞争比

Abstract: We investigate the problem of online preemptive scheduling of two-machine flow shops with the objective of minimizing the makespan. Jobs arrive independently over time and the information of a job is not known until its arrival. We present a lower bound of the problem. For the special case with only two arrival times we provide a algorithm which is -3/2 competitive.

Key words: combinatorial optimization, flow shop, online algorithm, preemptive, competitive ratio

中图分类号:

O223

杨名, 鲁习文, 汪磊扬. 在线可中断二台机器流水作业问题[J]. 运筹与管理, 2011, 20(5): 27-30.

YANG Ming, LU Xi-wen, WANG Lei-yang. Online Preemptive Scheduling of Two-machine Flow Shops[J]. Operations Research and Management Science, 2011, 20(5): 27-30.

[1]	苏兵, 任宏光, 周佳其, 陈光会, LIN Guo-hui. 可卸货的移动在线背包问题模型和算法[J]. 运筹与管理, 2021, 30(5): 1-5.
[2]	徐金红, 徐维军, 秦旭. 基于高斯分布的在线采购机制设计及竞争分析[J]. 运筹与管理, 2021, 30(3): 98-103.
[3]	林浩, 林澜. 一类二阶段指派问题[J]. 运筹与管理, 2021, 30(2): 97-101.
[4]	樊相宇, 林小果, 武小平. 环形路网上带有服务时长的在线TSP问题[J]. 运筹与管理, 2020, 29(6): 139-144.
[5]	马军平, 徐寅峰, 吴腾宇. 有服务时长和服务可选择性的快递车辆调度在线策略研究[J]. 运筹与管理, 2020, 29(1): 38-46.
[6]	徐维军, 董鹏翠, 彭子衿. 基于优惠合同的在线租赁策略设计[J]. 运筹与管理, 2019, 28(3): 183-190.
[7]	马卫民, 张颖, 李刚. 带有交易费用和持有成本的局内采购管理模型竞争分析[J]. 运筹与管理, 2018, 27(1): 171-177.
[8]	吴腾宇,徐寅峰. 带有配额的在线Nomadic旅行商问题[J]. 运筹与管理, 2016, 25(2): 1-6.
[9]	胡茂林,徐维军. 购买价格递减的在线租赁问题策略设计[J]. 运筹与管理, 2015, 24(5): 281-287.
[10]	胡丹, 农庆琴, 方奇志. 单位工件的平行机并行分批在线排序问题的算法[J]. 运筹与管理, 2015, 24(1): 137-141.
[11]	朱莹, 茹少峰, 张文明. 基于在线理论的股票算法交易策略研究[J]. 运筹与管理, 2015, 24(1): 222-230.
[12]	徐金红, 马银戌, 蒋微青. 统计信息下在线反向拍卖的竞争分析[J]. 运筹与管理, 2014, 23(4): 213-218.
[13]	汪磊扬. 考虑常数客户批运输的单机排序问题[J]. 运筹与管理, 2013, 22(5): 29-34.
[14]	马卫民, 徐博, 黄卉, 陈香堂. 双人合作的在线雪橇租赁问题[J]. 运筹与管理, 2013, 22(4): 12-19.
[15]	徐寅峰, 曹永峰, 郑斐峰. 单水库在线发电调度策略设计与分析[J]. 运筹与管理, 2011, 20(6): 82-87.