97-14
Shop-Scheduling Problems with Fixed and Non-Fixed Machine Orders of the Jobs
by Shakhlevich, N.V.; Sotskov, Y.N.; Werner, F.
Preprint series: 97-14, Preprints
The paper is published: Annals of Operations Research 92, 1999, 281 - 304.
Abstract: 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 arbitraryorder (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 fixedmachine orders and one may have an arbitrary machine order). We answerall other remaining open questions on the complexity status of mixed-shopproblems with the makespan criterion by presenting different polynomial andpseudopolynomial algorithms.
Keywords: Shop-scheduling, polynomial algorithm, NP -hard problem
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.