Preventing large sojourn times using SMART scheduling
成果类型：
Article
署名作者：
Nuyens, Misja; Wierman, Adam; Zwart, Bert
署名单位：
Vrije Universiteit Amsterdam; California Institute of Technology; University System of Georgia; Georgia Institute of Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1070.0504
发表日期：
2008
页码：
88-101
关键词：
摘要：
Recently, the so-called class of SMART scheduling policies has been introduced to formalize the common heuristic of biasing toward small jobs. We study the tail of the sojourn-time (response-time) distribution under both SMART policies and the foreground-background policy (FB) in the GI/GI/1 queue. We prove that these policies behave very well under heavy-tailed service times. Specifically, we show that the sojourn-time tail under all SMART policies and FB is similar to that of the service-time tail, up to a constant, which makes the SMART class superior to first-come-first-served (FCFS). In contrast, for light-tailed service times, we prove that the sojourn-time tail under FB and SMART is larger than that under FCFS. However, we show that the sojourn-time tail for a job of size y under FB and all SMART policies still outperforms FCFS as long as y is not too large.