On-line and semi-online scheduling for flow shop problems on two machines

Abstract

We investigate the on-line and semi-online scheduling for flow shop problems on two machines with the objective to minimize the makespan. Several lower bounds for the problems with and without preemption are derived. For some special cases of semi-online version, we provide two on-line algorithms with a competitive ratio of . Finally we give a lower bound for the problem with unavailable time interval on the first machine. And for the problem with the interval on the second machine, we show that no on-line algorithm has a constant competitive ratio.

Keywords:

• scheduling
• on-line
• flow shop
• lower bound
• algorithm

Acknowledgements

The authors thank two anonymous referees whose comments helped improve this article. This research was supported by Grant No. 09ZR1407200 of the Science Foundation of Shanghai and the National Natural Science Foundation of China (No. 11071072).