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+√(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 δ≥ 1. This implies improved competitive ratios for unrelated machines but may also be of independent interest.
READ FULL TEXT