Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2012 | Published
Journal Article Open

Is Tail-Optimal Scheduling Possible?


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.

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.

Attached Files

Published - 1249.full.pdf


Files (177.9 kB)
Name Size Download all
177.9 kB Preview Download

Additional details

August 22, 2023
October 20, 2023