Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/25960
Title: Scheduling parallel machines with inclusive processing set restrictions
Authors: Ou, J
Leung, JYT
Li, CL 
Keywords: Parallel machines
Polynomial time approximation scheme
Scheduling
Worst-case analysis
Issue Date: 2008
Publisher: John Wiley & Sons
Source: Naval research logistics, 2008, v. 55, no. 4, p. 328-338 How to cite?
Journal: Naval research logistics 
Abstract: We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst-case performance ratio of 4/3 + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature.
URI: http://hdl.handle.net/10397/25960
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.20286
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

50
Last Week
1
Last month
0
Citations as of Dec 1, 2017

WEB OF SCIENCETM
Citations

49
Last Week
1
Last month
0
Citations as of Oct 18, 2017

Page view(s)

54
Last Week
1
Last month
Checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric



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