Improved bounds for on-line load balancing

We consider the following load balancing problem. Jobs arrive on-line and m ust be assigned to one of m machines thereby increasing the load on that ma chine by a certain weight. Jobs also depart on-line. The goal is to minimiz e the maximum load on any machine, the load being defined as the sum of the weights of the jobs assigned to the machine divided by the machine capacit y. The scheduler also has the option of preempting a job and reassigning it to another machine. Whenever a job is assigned or reassigned to a machine, the on-line algorithm incurs a reassignment cost depending on the job. For arbitrary reassignment costs and identical machines, we present an on-line algorithm with a competitive ratio of 3.5981 against current load, i.e., t he maximum load at any time is less than 3.5981 times the lowest achievable load at that time. Our algorithm also incurs a reassignment cost less than 6.8285 times the cost of assigning all the jobs. For arbitrary reassignmen t costs and related machines we present an algorithm with a competitive rat io of 32 and a reassignment factor of 79.4. We also describe algorithms wit h better performance guarantees for some special cases of the problem.