This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Nuyens, M. Articles by Zwart, B. Search for Related Content

Preventing Large Sojourn Times Using SMART Scheduling

Department of Mathematics, Vrije Universiteit Amsterdam, De Boelelaan 1081, 1081 HV Amsterdam, The Netherlands
Computer Science Department, California Institute of Technology, Pasadena, California 91125
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
misjanuyens{at}gmail.com
adamw{at}caltech.edu
bertzwart{at}gatech.edu

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.

Subject classifications: queues; priority; limit theorems; probability; stochastic model applications.
History: Received October 2005; revision received September 2006; accepted October 2006.