Zurück zu den Preprints des Jahres 2001


2001-01

Heuristics for Two-Machine Flow Shop Problems with Earliness and Tardiness Penalties

by Lauff, V., Werner, F..


Series: 2001-01, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
We consider a two-machine flow shop problem with a given comnon due date for all jobs. Penalties are assigned for both early and late completion of jobs, and the objective is the minimization of the total penalty costs. Based on some structural properties , we derive several
constructive and iterative algorithms. For asymmetric linear and quadratic penalty functions, these algorithms are compared relative to each other on problems with 40 and 200 jobs as well as with the exact solution for small problems with up to 20 jobs.

Keywords:
scheduling, flow shop, heuristics, nonregular performance measures

This paper was published in:
International Journal of Operations and Quantitative Management, Vol. 10, No. 2, 2004, 125 - 144.