(1) Ecole Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland;(2) Computer and Automation Institute, Kende str. 13–17, 1111 Budapest, Hungary;(3) Faculty of Business Administration, Memorial University, St. John’s, NL, Canada
Abstract:
This paper addresses a multiprocessor generalization of the preemptive open-shop scheduling problem. The set of processors
is partitioned into two groups and the operations of the jobs may require either single processors in either group or simultaneously
all processors from the same group. We consider two variants depending on whether preemptions are allowed at any fractional
time points or only at integer time points. We reduce the former problem to solving a linear program in strongly polynomial
time, while a restricted version of the second problem is solved by rounding techniques. Applications to course scheduling
and hypergraph edge coloring are also discussed.