00-36

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

by Lauff, V.; Werner, F.

 

Preprint series: 00-36, Preprints

The paper is published: Computers & Operations Research, Vol. 31, 2004, 317 - 345.

MSC:
90B35 Scheduling theory, See also {68M20}

 

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.