Title: Greed Works - Online Algorithms For Unrelated Machine Stochastic Scheduling,
Abstract: 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.