Performance analysis of rotation schedule and improved strategy for open shop problem to minimise makespan

Abstract

This article addresses the open shop scheduling problem with the objective to minimise the maximum completion time, or makespan. Both asymptotical analysis and worst case analysis are conducted for the heuristic, rotation schedule (RS) algorithm. In the asymptotical analysis, we prove that the RS algorithm is asymptotically equal to the optimal solution when the problem size is large enough. In the worst case analysis, we show that the tight worst case performance ratio of RS algorithm is equal to the machine number m. To accelerate the convergence of the RS algorithm for medium size problems, the improved version of the heuristic, the modified RS (MRS) algorithm is presented. At the end of this article, the asymptotical optimality of the RS algorithm and the practical effectiveness of the MRS algorithm are shown by numerical simulations.

Keywords:

• open shop problem
• makespan
• asymptotical analysis
• worst case analysis

Acknowledgements

We are grateful to the graduate student Qian Fang for testing the data. Especially, we would like to thank the editor-in-chief and the anonymous referees for providing constructive comments on an earlier version of this article. 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).