Is Tail-Optimal Scheduling Possible?

Adam Wierman () and Bert Zwart ()
Additional contact information
Adam Wierman: Department of Computer Science, California Institute of Technology, Pasadena, California 91125
Bert Zwart: VU University Amsterdam, Eurandom, Georgia Institute of Technology, and CWI Amsterdam, 1098 XG Amsterdam, The Netherlands

Operations Research, 2012, vol. 60, issue 5, 1249-1257

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.

Keywords: scheduling; queueing; large deviations; competitive analysis (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1086 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:5:p:1249-1257

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().