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 $\Delta$ on the squared coefficient of variation of the jobs' processing times. They are $4+2\Delta$ when there are no release dates, and $12+6\Delta$ when jobs are released over time. For the special case of deterministic processing times, without and with release times, this paper shows that the same combinatorial greedy algorithm has a competitive ratio of 4 and 6, respectively. 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.