On preemptive scheduling on unrelated machines using linear programming

We consider a basic preemptive scheduling problem where n non-simultaneously released jobs are to be processed by m unrelated parallel machines so as to minimize maximum job completion time. An optimal LP-solution has been used to construct an optimal preemptive schedule for simultaneously released jobs in time O(n3). We propose fast O(m) time algorithm that finds an optimal schedule in case the above LP-solution possesses small enough number of non-zero elements. We propose another linear program for non-simultaneously released jobs and show how an optimal schedule can be constructed also in time O(m) from the optimal solution to that linear program. Based on another stronger linear program formulation, we extend the earlier known schedule construction procedure for non-simultaneously released jobs. The procedure is important, in particular, because there may exist no optimal schedule that agrees with an optimal LP-solution. An optimal LPsolution imposes a number of preemptions, and additional preemptions may occur during the schedule construction process, a job might be forced to be split on the same machine. We show that if no job split is allowed, even a restricted version of the problem on three unrelated machines is NP-hard. As a result, we obtain that, given an optimal LP-solution, it is NP-hard to find an optimal schedule that agrees with that LP-solution. As another side result, we obtain that it is NP-hard to find an optimal schedule with at most m - 1 preemptions.

Automated summary

This paper addresses a basic preemptive scheduling problem where non-simultaneously released jobs are processed by unrelated parallel machines. A fast algorithm is proposed that finds an optimal schedule when the Linear Programming (LP) solution has a small number of non-zero elements. Another linear program is introduced for non-simultaneously released jobs, and an optimal schedule can be constructed from the optimal solution to this linear program. The importance of the procedure lies in the fact that there may exist no optimal schedule that agrees with an optimal LP-solution.