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 {m⁴, n⁴, r²}), where r is the number of nonzero tasks. The maximum number of preemptions introduced is 0(min {rn, rm, n³, m³}). 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.