An optimal semi-online algorithm for 2-machine scheduling with an availability constraint

Hongying Li () and Chunjie Su
Additional contact information
Hongying Li: East China University of Science and Technology
Chunjie Su: East China University of Science and Technology

Journal of Combinatorial Optimization, 2011, vol. 22, issue 2, No 3, 153-165

Abstract: Abstract This paper considers a problem of semi-online scheduling jobs on two identical parallel machines with objective to minimize the makespan. We assume there is an unavailable period [B,F] on one machine and the largest job processing time P max is known in advance. After comparing B with P max we consider three cases, and we show a lower bound of the problem are 3/2, 4/3 and $(\sqrt{5}+1)/2$ , respectively. We further present an optimal algorithm and prove its competitive ratio reaches the lower bound.

Keywords: Scheduling; Semi-online; Availability; Algorithm; Competitive ratio (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9280-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:22:y:2011:i:2:d:10.1007_s10878-009-9280-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9280-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().