Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling

This paper considers minimizing the makespan in the fixed, 3-machine, assembly-type flowshop scheduling (AFS) problem. Since this problem has been proved strongly NP-complete, this paper proposes a series of heuristic algorithms based on the basic idea of Johnson's algorithm, Gupta's idea, the theorem newly provided in this paper, and worst/ difficult case analyses. Numerical experiments show that the proposed heuristic algorithms can solve all of the worst cases which cannot be solved by the existing heuristic algorithms, and can solve all of the 90,000 instances generated randomly, meaning that the proposed algorithms are powerful enough to solve the fixed, 3-machine, AFS problem. (C) 2003 Published by Elsevier Science B.V.