Preemptive open shop scheduling with multiprocessors: polynomial cases and applications

This paper addresses a multiprocessor generalization of the preemp-tive open-shop scheduling problem. The set of processors is partitioned into two groups and the operations of the jobs may require either sin-gle processors in either group or simultaneously all processors from the same group. We consider two variants depending on whether pre-emptions are allowed at any fractional time point or only at integral time points. We shall show that the former problem can be solved in polynomial time, and provide sufficient conditions under which the latter problem is tractable. Applications to course scheduling and hy-pergraph edge coloring are also discussed