Heuristic for no-wait flow shops with makespan minimization

Abstract

No-wait or constrained flow shops with makespan minimization are considered in this paper. An Objective Increment method is introduced to judge whether or not a new schedule is better than its parent. The judgment is made just by the makespan increment rather than by the traditional method to compute the whole makespan, and the time complexity of a heuristic can be decreased by one order. As a new schedule is usually generated by insertion or pair wise exchanging, objective increments are analysed for the fundamental operations. A composite heuristic is proposed for the problems considered. Experimental results show that the proposed approach outperforms the best existing algorithms with the least CPU time.

Keywords:

• Heuristic
• No-wait flow shop
• Scheduling
• Makespan

Acknowledgements

This work is supported by National Natural Science Foundation of China under Grants (Nos. 60504029 and 60672092), National Key Basic Research and Development Program of China (No. 2002 CB312205). The authors are grateful to the anonymous referees for their valuable suggestions and comments.