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 crite rion and the minimization of either the total flow time, total weighted flo w time, or total weighted tardiness as the secondary criterion. We investig ate several variants of simulated annealing, threshold accepting, tabu sear ch, and multi-level search algorithms. The influence of the parameters of t hese heuristics and the starting solution are empirically analyzed. The pro posed heuristic algorithms are empirically evaluated and found to be relati vely more effective in finding better quality solutions than the existing a lgorithms. Scope and purpose Traditional research to solve multi-stage scheduling problems has focused o n single criterion. However, in industrial scheduling practices, managers d evelop schedules based on multi-criteria. Scheduling problems involving mul tiple criteria require significantly more effort in finding acceptable solu tions and hence have not received much attention in the literature. This pa per considers one such multiple criteria scheduling problem, namely, the tw o-machine flow shop problem where the primary criterion is the minimization of makespan and the secondary criterion is one of the three most popular p erformance measures, namely, the total flow time, total weighted flow time, or total weighted tardiness. Based on the principles of local search, deve lopment of heuristic algorithms, that can be adapted for several multicrite ria 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 schedul ing problems with a secondary criterion. (C) 2001 Elsevier Science Ltd. All rights reserved.