A Note on Open Shop Preemptive Schedules

The problem of preemptively scheduling a set of n independent jobs on an m processor open shop is discussed. An algorithm to construct preemptive schedules with minimum-maximum finishing time is presented. The worst case time complexity is 0(r + min {m4, n4, r2}), where r is the number of nonzero tasks. The maximum number of preemptions introduced is 0(min {rn, rm, n3, m3}). The algorithm is best possible for open shops with a fixed number of processors or jobs. In this case the maximum number of preemptions introduced is bounded by some fixed constant.