Online Scheduling with Bounded Migration

arrive one by one are assigned to identical parallel machines with
the objective of minimizing the makespan. We generalize this
problem by allowing the current assignment to be changed whenever a
new job arrives, subject to the constraint that the total size of
moved jobs is bounded by beta times the size of the arriving job.

Our main result is a linear time `online approximation scheme', that
is, a family of online algorithms with competitive
ratio 1+epsilon and constant migration factor beta(epsilon),
for any fixed epsilon>0. This result is of particular importance
if considered in the context of sensitivity analysis: While a newly
arriving job may force a complete change of the entire structure of
an optimal schedule, only very limited `local' changes suffice to
preserve near-optimal solutions. We believe that this concept will
find wide application in its own right.

We also present simple deterministic online algorithms with
migration factors beta=2 and beta=4/3, respectively. Their
competitive ratio 3/2 beats the lower bound on the performance of
any online algorithm in the classical setting without migration. We
also present improved algorithms and similar results for closely
related problems. In particular, there is a short discussion of
corresponding results for the objective to
maximize the minimum load of a machine. The latter problem has an
application for configuring storage servers that was the original
motivation for this work.

Joint work with Peter Sanders and Naveen Sivadasan