Zurück zu den Preprints des Jahres 2000


On the Complexity and Some Properties of Multi-Stage Scheduling Problems with Earliness and Tardiness Penalties

by Lauff, V., Werner, F..

Series: 2000-36, Preprints

90B35 Scheduling theory, deterministic

In this paper, the complexity and some other properties of several multi-stage problems
with a non-regular performance measure are investigated. Mainly, we deal with two-machine problems.
It is shown that the two-machine flow shop problem with intermediate storage costs defined in this paper
is NP-hard in the strong sense for d = 0 as well as for a non-restrictive due date. We prove similar results
for the two-machine open shop problem. In absence of intermediate storage costs, the
open shop and the job shop problem are ploynomially solvable for a non-restrictive due date.

scheduling, flow shop, non-regular criterion, common due date

This paper was published in:
Computers & Operations Research, Vol. 31, 2004, 317 - 345.