{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/45633"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/45633","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions","abstract":"We study the problem of scheduling jobs on a two-machine distributed server, where the job size distribution is heavy-tailed. We focus on two distributions, for which we prove that the performance of the optimal size-independent policy is asymptotically worse than that of a simple size-dependent policy. First, we consider a simple distribution where incoming jobs can only be of two possible sizes. The motivation is that with two largely different sizes, the simple distribution captures the important aspects of a heavy tail. Second, we extend to a bounded Pareto distribution, which has an actual heavy tail. For both cases, we analyze the performance with regards to slowdown (waiting time divided by job size) for several size-independent and size-dependent policies. We see that the size-dependent policies perform better, and then go on to prove that even the best size-independent policy cannot achieve the same performance. We conclude that as we increase the variance of our job size distribution, the gap between size-independent and size-dependent policies grows.","abstract_html":"We study the problem of scheduling jobs on a two-machine distributed server, where the job size distribution is heavy-tailed. We focus on two distributions, for which we prove that the performance of the optimal size-independent policy is asymptotically worse than that of a simple size-dependent policy. First, we consider a simple distribution where incoming jobs can only be of two possible sizes. The motivation is that with two largely different sizes, the simple distribution captures the important aspects of a heavy tail. Second, we extend to a bounded Pareto distribution, which has an actual heavy tail. For both cases, we analyze the performance with regards to slowdown (waiting time divided by job size) for several size-independent and size-dependent policies. We see that the size-dependent policies perform better, and then go on to prove that even the best size-independent policy cannot achieve the same performance. We conclude that as we increase the variance of our job size distribution, the gap between size-independent and size-dependent policies grows.","abstract_has_math":false,"creators":["Nham, John (John T.)"],"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":["John N. Tsitsiklis and Sudhendu Rai."],"committee_chairs":[],"committee_members":[],"year":2008,"date_issued":"2008","date_published":"2008","updated_at":"2026-07-22T22:21:07Z","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/45633","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["John N. Tsitsiklis and Sudhendu Rai."]},{"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":["Nham, John (John T.)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-06-25T20:36:42Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-06-25T20:36:42Z"]},{"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/45633"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Includes bibliographical references (p. 47-48)."]},{"key":"dc:description.abstract","label":"Abstract","values":["We study the problem of scheduling jobs on a two-machine distributed server, where the job size distribution is heavy-tailed. We focus on two distributions, for which we prove that the performance of the optimal size-independent policy is asymptotically worse than that of a simple size-dependent policy. First, we consider a simple distribution where incoming jobs can only be of two possible sizes. The motivation is that with two largely different sizes, the simple distribution captures the important aspects of a heavy tail. Second, we extend to a bounded Pareto distribution, which has an actual heavy tail. For both cases, we analyze the performance with regards to slowdown (waiting time divided by job size) for several size-independent and size-dependent policies. We see that the size-dependent policies perform better, and then go on to prove that even the best size-independent policy cannot achieve the same performance. We conclude that as we increase the variance of our job size distribution, the gap between size-independent and size-dependent policies grows."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions"]}]}],"canonical_facts":{"dc:contributor.advisor":["John N. Tsitsiklis and Sudhendu Rai."],"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":["Nham, John (John T.)"],"dc:date.accessioned":["2009-06-25T20:36:42Z"],"dc:date.available":["2009-06-25T20:36:42Z"],"dc:date.issued":["2008"],"dc:description":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.","This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.","Includes bibliographical references (p. 47-48)."],"dc:description.abstract":["We study the problem of scheduling jobs on a two-machine distributed server, where the job size distribution is heavy-tailed. We focus on two distributions, for which we prove that the performance of the optimal size-independent policy is asymptotically worse than that of a simple size-dependent policy. First, we consider a simple distribution where incoming jobs can only be of two possible sizes. The motivation is that with two largely different sizes, the simple distribution captures the important aspects of a heavy tail. Second, we extend to a bounded Pareto distribution, which has an actual heavy tail. For both cases, we analyze the performance with regards to slowdown (waiting time divided by job size) for several size-independent and size-dependent policies. We see that the size-dependent policies perform better, and then go on to prove that even the best size-independent policy cannot achieve the same performance. We conclude that as we increase the variance of our job size distribution, the gap between size-independent and size-dependent policies grows."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/45633"],"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":["Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:07Z"}