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

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

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