Optimal robust algorithms for preemptive scheduling

jobs is to be assigned to machines such that any job can be
split into parts arbitrarily and distributed among the machines,
under the condition that its part cannot be processed in parallel
on different machines. Given the goal of minimizing the makespan,
this problem is known to be polynomially solvable even for the
most general model of unrelated machines.
Robust algorithms receive one piece of input at a time. They may
change a small portion of the solution as an additional part of
the input is revealed. The capacity of change is based on the
size of the new input. For scheduling problems, the maximum
ratio between the size of the jobs (or parts of jobs) which may be
re-scheduled upon the arrival of a new job j, and the size of
j, is called "migration factor".
We design an optimal algorithm with migration factor 1-1/m for
identical machines, and show that an algorithm of smaller
migration factor cannot be optimal. We further discuss
uniformly related machines and identical machines with restricted
assignment. Joint work with Asaf Levin.