Is Tail-Optimal Scheduling Possible?

• 成果类型: Article
• 署名作者: Wierman, Adam; Zwart, Bert
• 署名单位: California Institute of Technology; California Institute of Technology; Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1086
• 发表日期: 2012
• 页码: 1249-1257
• 关键词: processor-sharing queues; large-deviations; sojourn times; asymptotics; discipline; distributions

摘要

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.