What is it about?

The paper deals with the determination of an optimal schedule for the so‐called mixed‐shopproblem when the makespan has to be minimized. In such a problem, some jobs have fixed machine orders, while the operations of the other jobs may be processed in arbitrary order. We prove binary NP‐hardness of the preemptive problem 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.

Featured Image