Is tail-optimal scheduling possible?

A.C. Wierman, B. Zwart

Research output: Contribution to journalArticleAcademicpeer-review

35 Citations (Scopus)
2 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1249-1257
JournalOperations Research
Volume60
Issue number5
DOIs
Publication statusPublished - 2012

Fingerprint

Dive into the research topics of 'Is tail-optimal scheduling possible?'. Together they form a unique fingerprint.

Cite this