Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision

Yong Wu, Min Ji and Qifan Yang

International Journal of Production Economics, 2012, vol. 135, issue 1, 367-371

Abstract: This paper investigates semi-online scheduling problems on two parallel identical machines under a grade of service (GoS) provision. We consider two different semi-online versions where the optimal offline value of the instance is known in advance or the largest processing time of all jobs is known in advance. Respectively for the two semi-online models, two algorithms with competitive ratios of 3/2 and (5+1)/2 are shown to be optimal.

Keywords: Scheduling; Semi-online; Grade of service; Two machines; Competitive ratio (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527311003501
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:135:y:2012:i:1:p:367-371

DOI: 10.1016/j.ijpe.2011.07.021

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 ().