Load Balancing for Response Time

A centralized scheduler must assign tasks to servers, processing on-line a sequence of task arrivals and departures. Each task runs for an unknown length of time, but comes with a weight that measures resource utilization per unit time. The response time of a server is the sum of the weights of the tasks assigned to it. The goal is to minimize the maximum response time, i.e., load, of any server. Previous papers on online load balancing have generally concentrated only on keeping the current maximum load on an on-line server bounded by some function of the maximum off-line load ever seen. Our goal is to keep the current maximum load on an on-line server bounded by a function of the current off-line load. Thus our algorithms are not skewed by transient peaks, and provide bounded response time at all point in the run. To achieve this, the scheduler must occasionally reassign tasks, in an attempt to decrease the maximum load. We study several variants of load balancing, including identica..