  This paper presents improved approximation algorithms for the problem of
multiprocessor scheduling under uncertainty, or 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 G 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, which is the expected time at which all jobs complete.
  Lin and Rajaraman 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. In this paper, we present
asymptotically better approximation algorithms. In particular, we give an
O(loglog min(m,n))-approximation for independent jobs (improving on the
previously best O(log n)-approximation). We also give an O(log(n+m) loglog
min(m,n))-approximation algorithm for precedence constraints that form disjoint
chains (improving on the previously best
O(log(n)log(m)log(n+m)/loglog(n+m))-approximation by a (log n/loglog n)^2
factor when n = poly(m). Our algorithm for precedence constraints forming
chains can also be used as a component for precedence constraints forming
trees, yielding a similar improvement over the previously best algorithms for
trees.
