Combining Single-pass and Multiple-pass Heuristics for Group Flexible Flow-shop Scheduling Problems

This paper focuses on solving the group flexible flow-shop scheduling problem with more than two machine centers, which have the same number of parallel machines. The problem is solved at two levels, one for the job sequence in each group, and the other for the group sequence. One single-pass heuristic, the Palmer procedure, and two multiple-pass heuristics, the CDS and the LN procedures, are combined to solve it. Multiple-pass heuristics in general need more computation time but get a better solution than single-pass ones. Four heuristic algorithms, each with a single-pass heuristic (the Palmer heuristic) and a multiple-pass one (the CDS or LN heuristic) are then proposed and a comparative analysis is then made among them. Experiments are also made to analyze the performance of these four algorithms.