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(n^3)$. 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 LP-solution 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.