Abstract
We consider parallel-machine scheduling with a common server and job preemption to minimize the makespan. While the non-preemptive version of the problem is strongly NP-hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP-hard even if there is a fixed number of machines. We give a pseudo-polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP-hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases.
Original language | English |
---|---|
Pages (from-to) | 388-398 |
Number of pages | 11 |
Journal | Naval Research Logistics |
Volume | 64 |
Issue number | 5 |
DOIs | |
State | Published - Aug 2017 |
Keywords
- common server
- makespan
- parallel machines
- preemption
- scheduling