Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/17774
Title: A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines
Authors: Ng, CT 
Cheng, TCE 
Bandalouski, AM
Kovalyov, MY
Lam, SS
Keywords: cargo loading/unloading
Fixed interval scheduling
Interval graph
Maximum weight clique
Issue Date: 2014
Publisher: Palgrave Macmillan
Source: Journal of the Operational Research Society, 2014, v. 65, no. 10, p. 1571-1579 How to cite?
Journal: Journal of the Operational Research Society 
Abstract: We study the problem of scheduling n non-preemptive jobs on m unrelated parallel machines. Each machine can process a specified subset of the jobs. If a job is assigned to a machine, then it occupies a specified time interval on the machine. Each assignment of a job to a machine yields a value. The objective is to find a subset of the jobs and their feasible assignments to the machines such that the total value is maximized. The problem is NP-hard in the strong sense. We reduce the problem to finding a maximum weight clique in a graph and survey available solution methods. Furthermore, based on the peculiar properties of graphs, we propose an exact solution algorithm and five heuristics. We conduct computer experiments to assess the performance of our and other existing heuristics. The computational results show that our heuristics outperform the existing heuristics.
URI: http://hdl.handle.net/10397/17774
ISSN: 0160-5682
EISSN: 1476-9360
DOI: 10.1057/jors.2013.109
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Sep 23, 2017

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
0
Citations as of Sep 24, 2017

Page view(s)

75
Last Week
3
Last month
Checked on Sep 25, 2017

Google ScholarTM

Check

Altmetric



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