View article

We study the problem of scheduling a set of jobs on machines with stochastic job processing times when no preemptions are allowed and with a weighted sum of expected completion times objective. Our model allows for “unrelated” machines: the distributions of processing times may vary across both jobs and machines. We study static routing policies, which assign (or “route”) each job to a particular machine at the start of the problem and then sequence jobs on each machine according to the weighted shortest expected processing time rule. We discuss how to obtain a good routing of jobs to machines by solving a convex quadratic optimization problem that has variables and depends only on the job processing distributions through their expected values. Our main result is an additive performance bound on the suboptimality of this static routing policy relative to an optimal adaptive, nonanticipative …