Zurück zu den Preprints des Jahres 1999


1999-01

Local Search Heuristics for Two-Stage Flow Shop Problems with Secondary Criterion

by Gupta, J.N.D., Hennig, K., Werner, F..


Series: 1999-01, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
The 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. In the comparison we 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.

Keywords:
flow shop scheduling, secondary criterion, local search, tabu search, threshold accepting, simulated annealing, multi-lever search, empirical evaluation

This paper was published in:
Computers and Operations Research, Vol. 29, No. 2, 2002, 123 - 149.