ONLINE LOAD BALANCING

The setup for our problem consists of n servers that must complete a s et of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned cannot be re assigned. We make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. The on -line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized . In this paper we derive matching upper and lower bounds for the comp etitive ratio of the on-line greedy algorithm for this problem, namely , [(3n)2/3/2](1 + o(1)), and derive a lower bound, OMEGA(n1/2), for an y other deterministic or randomized on-line algorithm.