Online Load Balancing on Related Machines

We give a constant-competitive algorithm for the problem of assigning jobs online to machines with non-uniform speed (called related machines) so as to optimize any l(q)-norm of the machine loads. Previously, such a result was only known for the special case of the makespan, or l(infinity). norm. We also extend these results to obtain tight bounds for the problem of vector scheduling on related machines, where no results were previously known even for the makespan norm. To obtain our results, we employ a convex relaxation of the l(q)-norm objective and use a continuous greedy algorithm to solve this convex program online. To round the fractional solution, we then use a novel restructuring of the instance that we call machine smoothing. This is a generic tool that reduces a problem on related machines to a set of problem instances on identical machines, and we hope it will be useful in other settings with non-uniform machine speeds as well.