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 consider simulated annealing, threshold accepting, tabu search, and multi-level search. The latter type of algorithms are characterized by the use of different neighbourhoods within the search. In the comparison we also include a genetic algorithm from the literature. In this paper we analyze the influence of the parameters of these heuristics and the starting solution. The algorithms have been tested on problems with up to 80 jobs. (orig.)Available from TIB Hannover: RR 4487(1999,1) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman