On-line Load Balancing of Temporary Tasks

This paper considers the non-preemptive on-line load balancing problem where tasks have limited duration in time. Upon arrival, each task has to be immediately assigned to one of the machines, increasing the load on this machine for the duration of the task by an amount that depends on both the machine and the task. The goal is to minimize the maximum load. Azar, Broder and Karlin studied the unknown duration case where the duration of a task is not known upon its arrival [4]. They focused on the special case in which for each task there is a subset of machines capable of executing it, and the increase in load due to assigning the task to one of these machines depends only on the task and not on the machine. For this case, they showed an O(n 2=3 )-competitive algorithm, and an \Omega\Gamma p n) lower bound on the competitive ratio, where n is the number of the machines. This paper closes the gap by giving an O( p n)-competitive algorithm. In addition, trying to overcome the\Omega..