The cyclic compact open-shop scheduling problem (Q686491)

We consider a variation of the classical nonpreemptive open shop scheduling problem. For the normal open shop, finding whether a schedule exists in \(T\) time units is NP-complete. The main difference with the classical model is that we consider so- called periodical or cyclic schedules; this means that the schedule obtained is repeated periodically. If the length of a period is \(k\) time units, then a job which is on a processor during the first \(p\) time units of a period and the last \(q\) time units of a period is considered as being processed without preemptions on that processor during \(q+ p\) consecutive time units. Such scheduling problems are sometimes called cylindrical (instead of cyclic); this name stems frm the fact that we take the processor schedules (and the job schedules) for one period and make a cylinder by gluing together the \(t= 0\) and \(t= k\) axes. Cyclic problems occur more and more frequently in automated production systems; some types of cyclic problems are discussed. Another difference from the classical models is that we consider compact schedules only. In a cyclic schedule, this means that if we consider the cylinder representing the job (processor) schedules in each period, each job (processor) at most one idle time interval on the cylinder. We give a complete formulation of the cyclic compact open shop scheduling problem and derive a graph-theoretic model. A characterization in terms of graphs is given for problems which have cyclic schedules with some additional requirements.