Approximation algorithms for stochastic scheduling on unrelated machines

Motivated by problems in distributed computing, this thesis presents the first nontrivial polynomial time approximation algorithms for an important class of machine scheduling problems. We study the family of preemptive minimum makespan scheduling 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 precedence constraints on jobs. Letting n and 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 precedence constraints form a directed forest. Very simple modifications allow our algorithms to apply to more general distributions, at the cost of slightly worse approximation ratios. Our O(log log n)-approximation algorithm for independent jobs holds when we allow restarting instead of preemption. Here jobs may switch machines, but lose all previous processing if they do so. We also consider problems in the framework of scheduling under uncertainty. This model considers jobs that require unit processing on machines with identical speeds. However, after processing a job to completion, a machine has an (unrelated) probability of failing and leaving the job uncompleted. This difficulty is offset by allowing multiple machines to process a job simultaneously. We prove that this model is equivalent to a slightly modified version of the family of problems described above and provide approximation algorithms for analogous problems with identical ratios.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Scott, Jacob (Jacob Healy)

Advisor dc:contributor.advisor

• David R. Karger.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/45750

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/45750