On the exact bounds of SPT for scheduling on parallel machines with availability constraints

Zhiyi Tan, Yong Chen and An Zhang

International Journal of Production Economics, 2013, vol. 146, issue 1, 293-299

Abstract: This paper considers the scheduling problems with the objective of minimizing the total completion time on two parallel identical machines with given unavailable periods. The jobs are assumed to be nonresumable. If there is one unavailable period on one of the two machines, we prove that SPT has a tight worst-case ratio of 3/2. If there is one unavailable period on each machine, and the unavailable periods on two machines do not overlap, we prove that SPT has a worst-case ratio of 2, which is the smallest possible worst-case ratio that an polynomial time algorithm can have unless P=NP.

Keywords: Scheduling; Worst-case ratio; Parallel machines; Total completion time; Availability constraints (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527313003253
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: https://EconPapers.repec.org/RePEc:eee:proeco:v:146:y:2013:i:1:p:293-299

DOI: 10.1016/j.ijpe.2013.07.013

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().