The Load Rebalancing Problem

In the classical load balancing or multiprocessor scheduling prob-lem, we are given a sequence of jobs of varying sizes and are asked to assign each job to one of the m empty processors. A typical ob-jective is to minimize makespan, the load on the heaviest loaded processor. Since in most real world scenarios the load is a dynamic measure, the initial assignment may be not remain optimal with time. Motivated by such considerations in a variety of systems, we formulate the problem of load rebalancing — given a possibly sub-optimal assignment of jobs to processors, relocate a set of the jobs so as to decrease the makespan. Specifically, the goal is to achieve the best possible makespan under the constraint that no more than k jobs are relocated. We also consider a generalization of this prob-lem where there is an arbitrary cost function associated with each job relocation. Since the problem is clearly NP-hard, we focus on approximation algorithms. We construct a sophisticated algorithm which achieves a 1.5-approximation, with near linear running time. We also show that the problem has a PTAS, resolving the com-plexity issue. Finally, we investigate the approximability of several extensions of the rebalancing model