Zurück zu den Preprints des Jahres 1997


Shop-Scheduling Problems with Fixed and Non-Fixed Machine Orders of the Jobs

by Shakhlevich, N.V., Sotskov, Y.N., Werner, F..

Series: 1997-14, Preprints

90B35 Scheduling theory, deterministic

The paper deals with the determination of an optimal schedule
for the so-called mixed-shop problem when the makespan has to be mini-
mized. In such a problem, some jobs have fixed machine orders (as in the job-
shop), while the operations of the other jobs may be processed in arbitrary
order (as in the open-shop). We prove binary NP -hardness of the preemp-
tive problem case with three machines and three jobs (two jobs have fixed
machine orders and one may have an arbitrary machine order). We answer
all other remaining open questions on the complexity status of mixed-shop
problems with the makespan criterion by presenting different polynomial and
pseudopolynomial algorithms.

Shop-scheduling, polynomial algorithm, NP -hard problem

This paper was published in:
Annals of Operations Research 92, 1999, 281 - 304.