Simulating Stochastic Scheduling Policies on Unrelated Machines

We investigate the competitive performance bounds of a purely combinatorial, online algorithm for stochastic and non-preemptive scheduling on unrelated machines. Several simulation experiments with different instances are executed and the performance is investigated from a computational perspective. The performance of this online algorithm is compared to an offline LP relaxation based algorithm and the WSEPT rule, both on average and in worst case. Finally, the random LP-relaxation based policy is derandomized and the effects on the performance of this algorithm are investigated