On-line load balancing

The setup for our problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a dierent level of service, and once assigned can not 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 competitive ratio of the on-line greedy algorithm for this problem, namel