Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling

György Dósa (), M. Grazia Speranza () and Zsolt Tuza ()
Additional contact information
György Dósa: University of Pannonia
M. Grazia Speranza: University of Brescia
Zsolt Tuza: University of Pannonia

Journal of Combinatorial Optimization, 2011, vol. 21, issue 4, No 5, 458-480

Abstract: Abstract We consider semi on-line scheduling on two uniform machines. The speed of the slow machine is normalized to 1 while the speed of the fast machine is assumed to be s≥1. Jobs of size J 1,J 2,… arrive one at a time, and each J i (i≥1) has to be assigned to one of the machines before J i+1 arrives. The assignment cannot be changed later. The processing time of the ith job is J i on the slow machine and J i /s on the fast one. The objective is to minimize the makespan. We study both the case where the only information known in advance is the total size ∑i≥1 J i of the jobs and the case where the only information known in advance is the optimum makespan. For each of these two cases, we almost completely determine the best possible competitive ratio of semi on-line algorithms compared to the off-line optimum, as a function of s in the range $1\le s

Keywords: Semi on-line scheduling; Uniform machines; Competitive analysis (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9265-2 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:21:y:2011:i:4:d:10.1007_s10878-009-9265-2

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

DOI: 10.1007/s10878-009-9265-2

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