  We study stochastic combinatorial optimization problems where the objective
is to minimize the expected maximum load (a.k.a.\ the makespan). In this
framework, we have a set of $n$ tasks and $m$ resources, where each task $j$
uses some subset of the resources. Tasks have random sizes $X_j$, and our goal
is to non-adaptively select $t$ tasks to minimize the expected maximum load
over all resources, where the load on any resource $i$ is the total size of all
selected tasks that use $i$. For example, when resources are points and tasks
are intervals in a line, we obtain an $O(\log\log m)$-approximation algorithm.
Our technique is also applicable to other problems with some geometric
structure in the relation between tasks and resources; e.g., packing paths,
rectangles, and "fat" objects. Our approach uses a strong LP relaxation using
the cumulant generating functions of the random variables. We also show that
this LP has an $\Omega(\log^* m)$ integrality gap, even for the problem of
selecting intervals on a line; here $\log^* m$ is the iterated logarithm
function.
