Chromatic scheduling in a cyclic open shop

We consider the computational complexity of some problems of scheduling in a cyclic open shop, which is a variation of a standard open shop system. In particular, we show that the problem of scheduling is NP-hard for a 3-processor system and polynomial for a 2-processor one. Moreover, we prove that the problem of determining if a given shop can be scheduled in 3 time units is polynomially solvable. 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.