Preemptive parallel‐machine scheduling with a common server to minimize makespan. (14th September 2017)

• Record Type: Journal Article
• Authors: Cheng, T.C.E.; Kravchenko, Svetlana A.; Lin, Bertrand M.T.
• Is Part Of: Naval research logistics. Volume 64:Number 5(2017)
• Page Start: 388
• Page End: 398
• Publication Date: 2017-09-14
• Subjects: scheduling -- parallel machines -- common server -- makespan -- preemption; Logistics, Naval -- Periodicals; Supplies and stores -- Periodicals; 359.07
• DOI: 10.1002/nav.21762
• Languages: English
• ISSNs: 0894-069X

Abstract

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. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 388–398, 2017