Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality

Scheduling problems have a deep and well-developed literature in both operations research and computer science. Stochastic scheduling problems with many jobs are notoriously difficult, and optimal policies may require constant tracking of the elapsed time of all jobs in process. When the processors (or “machines”) are identical, a policy that simply schedules jobs in fixed order of job weight to expected processing time—the WSEPT rule—is asymptotically optimal when the number of jobs is large. Much less understood is the case with specialized (or “unrelated”) machines (i.e., each job’s processing distribution may vary across machines). In “Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality,” Balseiro, Brown, and Chen study stochastic scheduling with unrelated machines. The authors study a simple static routing policy that (i) assigns jobs to machines up front and (ii) schedules the jobs on each machine in the WSEPT order. This static routing policy depends only on job processing times through their expected values and is easy to compute with a single convex optimization problem. The authors explicitly characterize the performance loss of this static routing policy relative to an optimal scheduling policy; this result implies that this static routing policy is asymptotically optimal in the regime of many jobs.