A Robust PTAS for Machine Covering and Packing

Minimizing the makespan or maximizing the minimum machine load are two of the most important and fundamental parallel machine scheduling problems. In an online scenario, jobs are consecutively added and/or deleted and the goal is to always maintain a (close to) optimal assignment of jobs to machines. The reassignment of a job induces a cost proportional to its size and the total cost for reassigning jobs must preferably be bounded by a constant r times the total size of added or deleted jobs. Our main result is that, for any e > 0, one can always maintain a (1 + e)-competitive solution for some constant reassignment factor r(e). For the minimum makespan problem this is the first improvement of the (2+e)-competitive algorithm with constant reassignment factor published in 1996 by Andrews, Goemans, and Zhang.