@article{Vakhania2023, 
author = {Nodari Vakhania},
title = {On preemptive scheduling on unrelated machines using linear programming},
year = {2023},
journal = {AIMS Mathematics},
volume = {8},
number = {3},
pages = {7061-7082},
keywords = {scheduling, linear programming, release time, time complexity, unrelated machines},
url = {https://www.sciopen.com/article/10.3934/math.2023356},
doi = {10.3934/math.2023356},
abstract = {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.}
}