English

运筹学学报

• 运筹学 • 上一篇    下一篇

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

 杨名, 鲁习文   

  • 收稿日期: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

PDF

1519

摘要： 本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间，工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形，并给出了性能比为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