Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/13882
Title: Fixed interval scheduling : models, applications, computational complexity and algorithms
Authors: Kovalyov, MY
Ng, CT 
Cheng, TCE 
Keywords: Discrete starting times
Interval graph
Interval scheduling
k-coloring
k-track assignment
Maximum weight clique
Maximum weight independent set
Issue Date: 2007
Publisher: Elsevier
Source: European journal of operational research, 2007, v. 178, no. 2, p. 331-342 How to cite?
Journal: European journal of operational research 
Abstract: The defining characteristic of fixed interval scheduling problems is that each job has a finite number of fixed processing intervals. A job can be processed only in one of its intervals on one of the available machines, or is not processed at all. A decision has to be made about a subset of the jobs to be processed and their assignment to the processing intervals such that the intervals on the same machine do not intersect. These problems arise naturally in different real-life operations planning situations, including the assignment of transports to loading/unloading terminals, work planning for personnel, computer wiring, bandwidth allocation of communication channels, printed circuit board manufacturing, gene identification and examining computer memory structures. We present a general formulation of the interval scheduling problem, show its relations to cognate problems in graph theory, and survey existing models, results on computational complexity and solution algorithms.
URI: http://hdl.handle.net/10397/13882
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2006.01.049
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

93
Last Week
1
Last month
4
Citations as of Sep 20, 2018

WEB OF SCIENCETM
Citations

84
Last Week
0
Last month
2
Citations as of Sep 17, 2018

Page view(s)

109
Last Week
0
Last month
Citations as of Sep 24, 2018

Google ScholarTM

Check

Altmetric


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