Premium
Preemptive parallel‐machine scheduling with a common server to minimize makespan
Author(s) -
Cheng T.C.E.,
Kravchenko Svetlana A.,
Lin Bertrand M.T.
Publication year - 2017
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21762
Subject(s) - preemption , job shop scheduling , unary operation , computer science , scheduling (production processes) , time complexity , parallel computing , heuristic , distributed computing , mathematical optimization , algorithm , mathematics , operating system , discrete mathematics , artificial intelligence , schedule
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. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 388–398, 2017