Semi-online scheduling with GoS eligibility constraints

Kangbok Lee, Hark-Chin Hwang and Kyungkuk Lim

International Journal of Production Economics, 2014, vol. 153, issue C, 204-214

Abstract: We consider semi-online scheduling problems on parallel machines to minimize the makespan subject to Grade of Service (GoS) eligibility constraints with different prior information: (1) the known total processing time, (2) the known largest processing time, (3) the known both total and largest processing times and (4) the known optimal makespan. For semi-online problems with different numbers of machines and information, we present a unified algorithm. Then we provide lower bounds of the competitive ratio for any algorithm and prove the competitive ratio of the proposed algorithm.

Keywords: Semi-online scheduling; Grade of Service (GoS); Unified algorithm; Competitive ratio; Lower bound example (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527314000711
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:153:y:2014:i:c:p:204-214

DOI: 10.1016/j.ijpe.2014.03.001

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