Local search heuristics for two-stage flow shop problems with secondary criterion

This paper develops and compares different local search heuristics for the two-stage flow shop problem with makespan minimization as the primary criterion and the minimization of either the total flow time, total weighted flow time, or total weighted tardiness as the secondary criterion. We investigate several variants of simulated annealing, threshold accepting, tabu search, and multi-level search algorithms. The influence of the parameters of these heuristics and the starting solution are empirically analyzed. The proposed heuristic algorithms are empirically evaluated and found to be relatively more effective in finding better quality solutions than the existing algorithms.Scope and purposeTraditional research to solve multi-stage scheduling problems has focused on single criterion. However, in industrial scheduling practices, managers develop schedules based on multi-criteria. Scheduling problems involving multiple criteria require significantly more effort in finding acceptable solutions and hence have not received much attention in the literature. This paper considers one such multiple criteria scheduling problem, namely, the two-machine flow shop problem where the primary criterion is the minimization of makespan and the secondary criterion is one of the three most popular performance measures, namely, the total flow time, total weighted flow time, or total weighted tardiness. Based on the principles of local search, development of heuristic algorithms, that can be adapted for several multi-criteria scheduling problems, is discussed. Using the example of the two-machine flow shop problem with secondary criterion, computational experiments are used to evaluate the utility of the proposed algorithms for solving scheduling problems with a secondary criterion.