On-Line Load Balancing of Temporary Tasks

✍ Scribed by Yossi Azar; Bala Kalyanasundaram; Serge Plotkin; Kirk R Pruhs; Orli Waarts

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 181 KB
• Volume: 22
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1995.0799

✦ Synopsis

O n -competitive algorithm. In addition, trying to overcome the ⍀ n lower bound for the case of unknown task duration, this paper initiates a study of the Ž load balancing problem for tasks with known duration i.e., the duration of a task . Ž . becomes known upon its arrival . For this case we show an O log nT -competitive algorithm, where T is the ratio of the maximum possible duration of a task to the minimum possible duration of a task. The paper explores an alternative way to ' Ž . overcome the ⍀ n bound; it considers the related machines case with unknown task duration. In the related machines case, a task can be executed by any machine and the increase in load depends on the speed of the machine and the weight of the task. For this case the paper gives a 20-competitive algorithm and shows a Ž . lower bound of 3 y o 1 on the competitive ratio.