¹Huazhong University of Science and Technology, Wuhan, PR China

Correspondence: L Wang, C5–211, Huazhong University of Science and Technology, Wuhan 430074, People's Republic of China. E-mail: hustwanglei@sohu.com

Received April 2004; Accepted June 2005; Published online 23 November 2005.

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.