Stochastic Scheduling on Unrelated Machines

Motivated by problems in distributed computing, this thesis presents the first non-trivial polynomial time approximation algorithms for an important class of machine scheduling problems. We study the family of preemptive minimum makespan schedul-ing problems where jobs have stochastic processing requirements and provide the first approximation algorithms for these problems when machines have unrelated speeds. We show a series of algorithms that apply given increasingly general classes of prece-dence constraints on jobs. Letting nand m be, respectively, the number of jobs and machines in an instance, when jobs need an exponentially distributed amount of processing, we give: • An O(log log min {m, n})-approximation algorithm when jobs are independent; • An 0 (log(n + m) log log min {m, n})-approximation algorithm when precedence constraints form disjoint chains; and, • An O(log n log(n + m) log log min {m, n})-approximation algorithm when prece-dence constraints form a directed forest