New Challenges on Scheduling Theory

Co-authorsChristopher Y. Crutchfield, Zoran Dzunic, David R. Karger, and Jacob H. Scott

This talk presents improved approximation algorithms for the problem of "multiprocessor scheduling under uncertainty" (SUU), in which the execution of each job may fail probabilistically. This problem is motivated by the increasing use of distributed computing to handle large, computationally intensive tasks. In the SUU problem we are given n unit-length jobs and m machines, a directed acyclic graph of precedence constraints among jobs, and unrelated failure probabilities q_ij for each job j when executed on machine i for a single timestep. Our goal is to find a schedule that minimizes the expected makespan.

Lin and Rajaraman [SPAA 07] gave the first approximations for this NP-hard problem for the special cases of independent jobs, precedence constraints forming disjoint chains, and precedence constraints forming trees. Our results include several asymptotically better approximations. In particular, we improve upon the previously best O( log n)-approximation for independent jobs, giving an O( log log (u))-approximation, where u=min(m,n). We also have an O( log (n+m) log log (u))-approximation algorithm for precedence constraints that form disjoint chains (improving on the previously best bound by a ( log (n) / log log (n))² factor when n=m^Θ(1).

Our techniques include reducing SUU to a problem in "stochastic scheduling", where machines must process a set of jobs with randomly distributed lengths. Our algorithms for SUU also apply to standard problem in this stochastic setting, giving the first approximation algorithms for preemptive stochastic scheduling on unrelated machines.