有使用限制的二台机器流水作业问题

运筹学学报 ›› 2011, Vol. 15 ›› Issue (3): 62-69.

有使用限制的二台机器流水作业问题

^{杨名, 鲁习文}

收稿日期:2011-05-19 修回日期:2011-07-12 出版日期:2011-09-20 发布日期:2011-09-29
通讯作者: 鲁习文 E-mail:xwlu@ecust.edu.cn

Two-Machine Flow Shop Problems with Availability Constraints

YANG Ming, LU Xi-Wen

Received:2011-05-19 Revised:2011-07-12 Online:2011-09-20 Published:2011-09-29
Contact: Xiwen Lu E-mail:xwlu@ecust.edu.cn

摘要/Abstract

摘要： 本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间，工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形，并给出了性能比为3/2的近似算法。同时我们还考虑了在第二台机器上存在一个不可用时间段情况下的半在线问题，给出了一个竞争比为3/2的半在线算法。

关键词: 竞争比排序, 流水作业, 使用限制, 近似算法, 竞争比

Abstract: We investigate the problems for two-machine flow shop scheduling with availability constraints. A resumable scenario is assumed, i.e., if a job cannot be finished before the interval it is continued after the machine becomes available again. The objective is to minimize the makespan. We first consider an approximate case of the problem with several availability constraints on both machines, present an algorithm with performance ratio of 3/2. Then we give an algorithm with competitive ratio of 3/2 for the semi-online problem with an availability constraint on the second machine.

Key words: scheduling, flow shop, availability constraint, approximation algorithm, competitive ratio

杨名, 鲁习文. 有使用限制的二台机器流水作业问题[J]. 运筹学学报, 2011, 15(3): 62-69.

YANG Ming, LU Xi-Wen. Two-Machine Flow Shop Problems with Availability Constraints[J]. Operations Research Transactions, 2011, 15(3): 62-69.

[1]	吴弘一, 王冬, 万龙, 罗文昌. 嵌套加工型限制下的混合分批平行机排序问题的近似算法[J]. 运筹学学报（中英文）, 2026, 30(1): 188-196.
[2]	夏倩, 张新功. 具有前瞻区间和不相容工件族的两台流水车间在线排序问题[J]. 运筹学学报（中英文）, 2025, 29(4): 103-111.
[3]	靳凯媛, 郑斐峰, 刘明. 考虑订单类型和准备时间的批处理机在线调度模型研究[J]. 运筹学学报（中英文）, 2025, 29(4): 231-240.
[4]	袁园, 兰艳, 韩鑫. 带有维护窗口的调度问题的综述[J]. 运筹学学报（中英文）, 2025, 29(1): 1-18.
[5]	高洁, 邹娟, 隋玉康, 张玉忠. 带有退化维护活动和工件可拒绝的非同类机排序问题[J]. 运筹学学报, 2023, 27(3): 137-149.
[6]	袁藩, 徐大川, 张冬梅. k-均值问题的差分隐私算法综述[J]. 运筹学学报（中英文）, 2022, 26(3): 1-16.
[7]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.
[8]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[9]	代宇波, 段懿红, 刘龙城, 王子豪. 一类一维在线单位聚类问题的随机近似算法[J]. 运筹学学报, 2022, 26(3): 143-150.
[10]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[11]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[12]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[13]	刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报（中英文）, 2022, 26(1): 99-112.
[14]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量k-均值问题的局部搜索算法[J]. 运筹学学报（中英文）, 2022, 26(1): 113-124.
[15]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.