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

Read the Original

This page is a summary of: , Annals of Operations Research, January 1999, Springer Science + Business Media,
DOI: 10.1023/a:1018943016617.
You can read the full text:

Read

Contributors

The following have contributed to this page