Greed Works - Online Algorithms For Unrelated Machine Stochastic Scheduling

This paper establishes the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. The algorithm introduced in this paper is based on a purely combinatorial assignment of jobs to machines, hence it also works online. The performance bounds are of the same order of magnitude as those of earlier work, and depend linearly on an upper bound on the squared coefficient of variation of the jobs' processing times. They are 4+2 when there are no release dates, and 72+36 when there are release dates. Bounds on the performance of combinatorial algorithms for problems with unrelated machines were previously unknown, even when processing times are not stochastic. For the special case of deterministic processing times and without release times, the performance bound equals 4, which is tight. As to the technical contribution, the paper shows for the first time how dual fitting techniques can be used for stochastic and nonpreemptive scheduling problems.