Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/76059
Title: Preemptive parallel-machine scheduling with a common server to minimize makespan
Authors: Cheng, TCE 
Kravchenko, SA
Lin, BMT
Keywords: Scheduling
Parallel machines
Common server
Makespan
Preemption
Issue Date: 2017
Publisher: John Wiley & Sons
Source: Naval research logistics, 2017, v. 64, no. 5, p. 388-398 How to cite?
Journal: Naval research logistics 
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.
URI: http://hdl.handle.net/10397/76059
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.21762
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.