CaltechAUTHORS
  A Caltech Library Service

Is Tail-Optimal Scheduling Possible?

Wierman, Adam and Zwart, Bert (2012) Is Tail-Optimal Scheduling Possible? Operations Research, 60 (5). pp. 1249-1257. ISSN 0030-364X. https://resolver.caltech.edu/CaltechAUTHORS:20121221-104528945

[img]
Preview
PDF - Published Version
See Usage Policy.

173Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20121221-104528945

Abstract

This paper focuses on the competitive analysis of scheduling disciplines in a large deviations setting. Although there are policies that are known to optimize the sojourn time tail under a large class of heavy-tailed job sizes (e.g., processor sharing and shortest remaining processing time) and there are policies known to optimize the sojourn time tail in the case of light-tailed job sizes (e.g., first come first served), no policies are known that can optimize the sojourn time tail across both light- and heavy-tailed job size distributions. We prove that no such work-conserving, nonanticipatory, nonlearning policy exists, and thus that a policy must learn (or know) the job size distribution in order to optimize the sojourn time tail.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1287/opre.1120.1086 DOIArticle
http://or.journal.informs.org/content/60/5/1249PublisherArticle
Additional Information:© 2012 INFORMS. Received August 2009; revisions received April 2011, February 2012; accepted April 2012. Published online in Articles in Advance October 9, 2012. Adam Wierman’s research is partly supported by the National Science Foundation Computing and Communication Foundations [Grant 0830511], Microsoft Research, and the Okawa Foundation. Bert Zwart’s research is partly supported by the National Science Foundation [Grants 0727400 and 0805979], an IBM faculty award, and a VIDI grant from the Netherlands Organisation for Scientific Research.
Funders:
Funding AgencyGrant Number
NSFCCF-0830511
Microsoft ResearchUNSPECIFIED
Okawa FoundationUNSPECIFIED
NSF0727400
NSF0805979
IBMUNSPECIFIED
Netherlands Organisation for Scientific Research (NWO) VIDI GrantUNSPECIFIED
Subject Keywords:scheduling; queueing; large deviations; competitive analysis
Issue or Number:5
Record Number:CaltechAUTHORS:20121221-104528945
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20121221-104528945
Official Citation:Adam Wierman and Bert Zwart Is Tail-Optimal Scheduling Possible? Operations Research September/October 2012 60:1249-1257; doi:10.1287/opre.1120.1086.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:36098
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:05 Feb 2013 20:17
Last Modified:03 Oct 2019 04:34

Repository Staff Only: item control page