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

Page view(s)

22
Citations as of Dec 16, 2018

Google ScholarTM

Check

Altmetric


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