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

摘要

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