Scheduling parallel machines with inclusive processing set restrictions and job release times

Li, Chung-Lun and Xiuli Wang

European Journal of Operational Research, 2010, vol. 200, issue 3, pages 702-710

Abstract: We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with 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. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.

Keywords: Scheduling; Parallel; machines; Release; times; Worst-case; analysis; Polynomial; time; approximation; scheme (search for similar items in EconPapers)
Date: 2010

Downloads: (external link)
http://www.sciencedirect.com/science/article/B6VCT ... 743f6d239a72ff2b8f62
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:eee:ejores:v:200:y:2010:i:3:p:702-710

Access Statistics for this article

European Journal of Operational Research is edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Series data maintained by Heidi Boesdal ().