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.