{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/45750"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/45750","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Approximation algorithms for stochastic scheduling on unrelated machines","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Scott, Jacob (Jacob Healy)"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["David R. Karger."],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008","date_published":"2008","updated_at":"2026-07-22T22:21:48Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/45750","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["David R. Karger."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Scott, Jacob (Jacob Healy)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-06-30T16:11:21Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-06-30T16:11:21Z"]},{"key":"dc:date.issued","label":"Date","values":["2008"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/45750"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.","Includes bibliographical references (p. 59-60)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Approximation algorithms for stochastic scheduling on unrelated machines"]}]}],"canonical_facts":{"dc:contributor.advisor":["David R. Karger."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Scott, Jacob (Jacob Healy)"],"dc:date.accessioned":["2009-06-30T16:11:21Z"],"dc:date.available":["2009-06-30T16:11:21Z"],"dc:date.issued":["2008"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.","Includes bibliographical references (p. 59-60)."],"dc:description.abstract":["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."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/45750"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Approximation algorithms for stochastic scheduling on unrelated machines"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:48Z"}