  We consider the problem of makespan minimization on unrelated machines when
job sizes are stochastic. The goal is to find a fixed assignment of jobs to
machines, to minimize the expected value of the maximum load over all the
machines. For the identical machines special case when the size of a job is the
same across all machines, a constant-factor approximation algorithm has long
been known. Our main result is the first constant-factor approximation
algorithm for the general case of unrelated machines. This is achieved by (i)
formulating a lower bound using an exponential-size linear program that is
efficiently computable, and (ii) rounding this linear program while satisfying
only a specific subset of the constraints that still suffice to bound the
expected makespan. We also consider two generalizations. The first is the
budgeted makespan minimization problem, where the goal is to minimize the
expected makespan subject to scheduling a target number (or reward) of jobs. We
extend our main result to obtain a constant-factor approximation algorithm for
this problem. The second problem involves $q$-norm objectives, where we want to
minimize the expected q-norm of the machine loads. Here we give an $O(q/\log
q)$-approximation algorithm, which is a constant-factor approximation for any
fixed $q$.
