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 r...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2023-01-01
|
| Series: | AIMS Mathematics |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/math.2023356?viewType=HTML |
| _version_ | 1797936880917938176 |
|---|---|
| author | Nodari Vakhania |
| author_facet | Nodari Vakhania |
| author_sort | Nodari Vakhania |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T18:36:07Z |
| format | Article |
| id | doaj.art-31c340937c1a406fb47c90e195d232c0 |
| institution | Directory Open Access Journal |
| issn | 2473-6988 |
| language | English |
| last_indexed | 2024-04-10T18:36:07Z |
| publishDate | 2023-01-01 |
| publisher | AIMS Press |
| record_format | Article |
| series | AIMS Mathematics |
| spelling | doaj.art-31c340937c1a406fb47c90e195d232c02023-02-02T01:12:41ZengAIMS PressAIMS Mathematics2473-69882023-01-01837061708210.3934/math.2023356On preemptive scheduling on unrelated machines using linear programmingNodari Vakhania0Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Cuernavaca, Morelos, MéxicoWe 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.https://www.aimspress.com/article/doi/10.3934/math.2023356?viewType=HTMLschedulingunrelated machinesrelease timelinear programmingtime complexity |
| spellingShingle | Nodari Vakhania On preemptive scheduling on unrelated machines using linear programming AIMS Mathematics scheduling unrelated machines release time linear programming time complexity |
| title | On preemptive scheduling on unrelated machines using linear programming |
| title_full | On preemptive scheduling on unrelated machines using linear programming |
| title_fullStr | On preemptive scheduling on unrelated machines using linear programming |
| title_full_unstemmed | On preemptive scheduling on unrelated machines using linear programming |
| title_short | On preemptive scheduling on unrelated machines using linear programming |
| title_sort | on preemptive scheduling on unrelated machines using linear programming |
| topic | scheduling unrelated machines release time linear programming time complexity |
| url | https://www.aimspress.com/article/doi/10.3934/math.2023356?viewType=HTML |
| work_keys_str_mv | AT nodarivakhania onpreemptiveschedulingonunrelatedmachinesusinglinearprogramming |