New heuristics for flow shop problem to minimize makespan

Abstract

This paper investigates the flow shop problem with the objective to minimize makespan. New algorithms are designed: one is off-line heuristic, Single Job First, for problem F_m∥C_max; and the other is on-line heuristic, Dynamic Single Job First (DSJF), for problem F_m|r_i|C_max and its on-line version. It is proved that the two heuristics are asymptotically optimal when the size of the problem is large enough. In addition, the asymptotical optimality of First-Come, First-Served manner is obtained as a byproduct of the asymptotical analysis of DSJF heuristic. At the end of the paper, a new lower bound with performance guarantee is provided for problem F_m∥C_max, and computational experiments show the effectiveness of these heuristic algorithms.

Keywords:

• scheduling
• flow shop problem
• makespan
• performance analysis of algorithm

Acknowledgements

We are grateful to the graduate students Qian Fang and Meng Su for testing the data. And especially, we would express our appreciation to the anonymous referee for his constructive comments that helped us to improve an earlier version of this paper. This research is partly supported by National Natural Science Foundation for Distinguished Young Scholars of China (Grant No. 70425003), National 863 High-Tech Research and Development Program of China (Grant No. 2006AA04Z174) and National Natural Science Foundation of China (Grant No. 60674084).