00-36
On the Complexity and Some Properties of Multi-Stage Scheduling Problems with Earliness and Tardiness Penalties
Preprint series: 00-36, Preprints
The paper is published: Computers & Operations Research, Vol. 31, 2004, 317 - 345.
Abstract: 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.
Keywords: scheduling, flow shop, non-regular criterion, common due date
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.