Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/45633 |
| _version_ | 1811074801047961600 |
|---|---|
| author | Nham, John (John T.) |
| author2 | John N. Tsitsiklis and Sudhendu Rai. |
| author_facet | John N. Tsitsiklis and Sudhendu Rai. Nham, John (John T.) |
| author_sort | Nham, John (John T.) |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. |
| first_indexed | 2024-09-23T09:55:42Z |
| format | Thesis |
| id | mit-1721.1/45633 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:55:42Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/456332019-04-11T02:54:00Z Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions Size-independent versus size-dependent policies in scheduling heavy-tailed distributions Nham, John (John T.) John N. Tsitsiklis and Sudhendu Rai. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. 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). 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. by John Nham. M.Eng. 2009-06-25T20:36:42Z 2009-06-25T20:36:42Z 2008 2008 Thesis http://hdl.handle.net/1721.1/45633 355813783 eng 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. http://dspace.mit.edu/handle/1721.1/7582 48 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Nham, John (John T.) Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions |
| title | Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions |
| title_full | Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions |
| title_fullStr | Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions |
| title_full_unstemmed | Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions |
| title_short | Size-independent vs. size-dependent policies in scheduling heavy-tailed distributions |
| title_sort | size independent vs size dependent policies in scheduling heavy tailed distributions |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/45633 |
| work_keys_str_mv | AT nhamjohnjohnt sizeindependentvssizedependentpoliciesinschedulingheavytaileddistributions AT nhamjohnjohnt sizeindependentversussizedependentpoliciesinschedulingheavytaileddistributions |