Paper Info
Title
Semi-online scheduling on two uniform processors
Abstract
In this paper we consider the problem of semi-online scheduling on two uniform processors, in the case where the total sum of the tasks is known in advance. Tasks arrive one at a time and have to be assigned to one of the two processors before the next one arrives. The assignment cannot be changed later. The objective is the minimization of the makespan. Assume that the speed of the fast processor is s, while the speed of the slow one is normalized to 1. As a function of s, we derive general lower bounds on the competitive ratio achievable with respect to offline optimum, and design on-line algorithms with guaranteed upper bound on their competitive ratio. The algorithms presented for s=3 are optimal, as well as for s=1 and for 1+174@?s@?1+32.
Year
DOI
Venue
2008
10.1016/j.tcs.2007.12.005
Theor. Comput. Sci.
Keywords
DocType
Volume
total sum,fast processor,competitive ratio,on-line algorithm,general lower bound,uniform processor,Competitive analysis,Semi-online scheduling,Uniform processors,semi-online scheduling
Journal
393
Issue
ISSN
Citations 
1-3
Theoretical Computer Science
16
PageRank 
References 
Authors
1.01
12
3
Name
Order
Citations
PageRank
Enrico Angelelli129120.58
Maria Grazia Speranza2121777.86
Zsolt Tuza31889262.52