by Lauff, V., Werner, F..
Series: 2000-36, Preprints
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.