Makespan minimization in online scheduling with machine eligibility

Kangbok Lee (), Joseph Leung () and Michael Pinedo ()

Annals of Operations Research, 2013, vol. 204, issue 1, 189-222

Abstract: In this paper we provide a survey of online scheduling in parallel machine environments with machine eligibility constraints and the makespan as objective function. We first give a brief overview of the different parallel machine environments and then survey the various types of machine eligibility constraints, including tree-hierarchical processing sets, Grade of Service processing sets, interval processing sets, and nested processing sets. We furthermore describe the relationships between the various different types of processing sets. We proceed with describing two basic online scheduling paradigms, namely online over list and online over time. For each one of the two paradigms we survey all the results that have been recorded in the literature with regard to each type of machine eligibility constraints. We obtain also several extensions in various directions. In the concluding section we describe the most important open problems in this particular area. Copyright Springer Science+Business Media New York 2013

Keywords: Parallel machine scheduling; Eligibility constraint; Tree-hierarchical and GoS processing sets; Interval and nested processing sets; Online and semi-online scheduling; Offline scheduling; Makespan; Competitive ratio (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-012-1271-6 (text/html)
Access to full text is restricted to subscribers.

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:spr:annopr:v:204:y:2013:i:1:p:189-222:10.1007/s10479-012-1271-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-012-1271-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().