Chromatic scheduling in a cyclic open shop

We also consider another variation of a cyclic open shop--a compact open shop. For this system we prove that the problem of minimizing Cmax for 2-processor system and the problem of determining if there exists a legal schedule are NP-hard. Moreover, we give polynomial time algorithms for determining if Cmax⩽3 in a general case and for determining if Cmax⩽4 in the case of zero-unit time tasks.