A local search method for permutation flow shop scheduling

Abstract

It is well known that a local search method, a widely used approach for solving the permutation flow shop scheduling problem, can easily be trapped at a local optimum. In this paper, we propose two escape-from-trap procedures to move away from local optima. Computational experiments carried out on a standard set of instances show that this heuristic algorithm generally outperforms an effective approximation algorithm.

Keywords:

• heuristics
• local search
• escape-from-trap
• flow shop sequencing

Acknowledgements

This research was supported by the National Natural Science Foundation of China under grant no. 10471051 and partially supported by the National Basic Research Program of China under grant no. 2004CB318000.