by Shakhlevich, N.V., Sotskov, Y.N., Werner, F..
Series: 1997-14, Preprints
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
Shop-scheduling, polynomial algorithm, NP -hard problem
This paper was published in:
Annals of Operations Research 92, 1999, 281 - 304.