2023-03-01
On the complexity of scheduling unrelated parallel machines with limited preemptions
Publication
Publication
Operations Research Letters , Volume 51 - Issue 2 p. 187- 189
We consider the problem of finding a minimum-length preemptive schedule for n jobs on m parallel machines. The problem is solvable in polynomial time, whether the machines are identical, uniform or unrelated. For identical or uniform machines, it is easy to obtain an optimal schedule in which the portion of a job that is assigned to a single machine is processed without interruption. We show that imposing this condition in the case of unrelated machines makes the problem NP-hard.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1016/j.orl.2023.02.004 | |
| Operations Research Letters | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Lenstra, J. K., & Vakhania, N. (2023). On the complexity of scheduling unrelated parallel machines with limited preemptions. Operations Research Letters, 51(2), 187–189. doi:10.1016/j.orl.2023.02.004 |
|
