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.
Citation: Nodari Vakhania. On preemptive scheduling on unrelated machines using linear programming[J]. AIMS Mathematics, 2023, 8(3): 7061-7082. doi: 10.3934/math.2023356
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.
| [1] |
T. Gonzalez, S. Sahni, Preemptive scheduling of uniform processor systems, J. Assoc. Comput. Mach., 25 (1978), 92–101. https://doi.org/10.1145/322047.322055 doi: 10.1145/322047.322055
|
| [2] | J. Labetoulle, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Preemptive scheduling of uniform machines subject to release dates, In: Progress in combinatorial optimization, New York: Academic Press, 245–261, 1984. https://doi.org/10.1016/B978-0-12-566780-7.50020-9 |
| [3] |
E. L. Lawler, J. Labetoulle, On preemptive scheduling of unrelated parallel processors by linear programming, J. Assoc. Comput. Mach., 25 (1978), 612–619. https://doi.org/10.1145/322092.322101 doi: 10.1145/322092.322101
|
| [4] |
C. N. Potts, Analysis of a linear programming heuristic for scheduling unrelated parallel machines, Discrete Appl. Math., 10 (1985), 155–164. https://doi.org/10.1016/0166-218X(85)90009-5 doi: 10.1016/0166-218X(85)90009-5
|
| [5] |
J. K. Lenstra, D. B. Shmoys, E. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Math. Program., 46 (1990), 259–271. https://doi.org/10.1007/BF01585745 doi: 10.1007/BF01585745
|
| [6] |
E. Shchepin, N. Vakhania, An optimal rounding gives a better approximation for scheduling unrelated machines, Oper. Res. Lett., 33 (2005), 127–133. https://doi.org/10.1016/j.orl.2004.05.004 doi: 10.1016/j.orl.2004.05.004
|
| [7] |
T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time, J. Assoc. Comput. Mach., 23 (1976), 665–679. https://doi.org/10.1145/321978.321985 doi: 10.1145/321978.321985
|
| [8] |
T. Gonzalez, E. L. Lawler, S. Sahni, Optimal preemptive scheduling of two unrelated processors, ORSA J. Comput., 2 (1990), 209–301. https://doi.org/10.1287/ijoc.2.3.219 doi: 10.1287/ijoc.2.3.219
|
| [9] |
E. Shchepin, N. Vakhania, On the geometry, preemptions and complexity of multiprocessor and open shop scheduling, Ann. Oper. Res., 159 (2008), 183–213. https://doi.org/10.1007/s10479-007-0266-1 doi: 10.1007/s10479-007-0266-1
|
| [10] |
M. Foumani, K. Smith-Miles, The impact of various carbon reduction policies on green flowshop scheduling, Appl. Energ., 249 (2019), 300–315. https://doi.org/10.1016/j.apenergy.2019.04.155 doi: 10.1016/j.apenergy.2019.04.155
|
| [11] |
G. L. Gong, Q. W. Deng, X. R. Gong, D. Huang, A non-dominated ensemble fitness ranking algorithm for multi-objective flexible job-shop scheduling problem considering worker flexibility and green factors, Knowl. Based Syst., 231 (2021), 107430. https://doi.org/10.1016/j.knosys.2021.107430 doi: 10.1016/j.knosys.2021.107430
|
Figures(6) / Tables(4)
Nodari Vakhania. On preemptive scheduling on unrelated machines using linear programming[J]. AIMS Mathematics, 2023, 8(3): 7061-7082. doi: 10.3934/math.2023356
DownLoad: