An Improved Greedy Algorithm for Stochastic Online Scheduling on Unrelated Machines

Most practical scheduling applications involve some uncertainty about the arriving times and lengths of the jobs. Stochastic online scheduling is a well-established model capturing this. Here the arrivals occur online, while the processing times are random. For this model, Gupta, Moseley, Uetz, and Xie recently devised an efficient policy for non-preemptive scheduling on unrelated machines with the objective to minimize the expected total weighted completion time. We improve upon this policy by adroitly combining greedy job assignment with $α_j$-point scheduling on each machine. In this way we obtain a $(3+\sqrt 5)(2+Δ)$-competitive deterministic and an $(8+4Δ)$-competitive randomized stochastic online scheduling policy, where $Δ$ is an upper bound on the squared coefficients of variation of the processing times. We also give constant performance guarantees for these policies within the class of all fixed-assignment policies. The $α_j$-point scheduling on a single machine can be enhanced when the upper bound $Δ$ is known a priori or the processing times are known to be $δ$-NBUE for some $δ\ge 1$. This implies improved competitive ratios for unrelated machines but may also be of independent interest.