CaltechAUTHORS
  A Caltech Library Service

Preventing Large Sojourn Times Using SMART Scheduling

Nuyens, Misja and Wierman, Adam and Zwart, Bert (2008) Preventing Large Sojourn Times Using SMART Scheduling. Operations Research, 56 (1). pp. 88-101. ISSN 0030-364X. https://resolver.caltech.edu/CaltechAUTHORS:20170408-151537902

[img] PDF - Accepted Version
See Usage Policy.

296Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170408-151537902

Abstract

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1287/opre.1070.0504DOIArticle
http://www.jstor.org/stable/25147170JSTORArticle
Additional Information:© 2008 INFORMS. Received October 2005; revisions received June 2006, September 2006; accepted October 2006. Published Online: February 1, 2008. The authors thank the referees for their suggestions and comments, which have improved the presentation and readability of the paper.
Subject Keywords:queues; priority; limit theorems; probability; stochastic model applications
Issue or Number:1
Record Number:CaltechAUTHORS:20170408-151537902
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170408-151537902
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:76051
Collection:CaltechAUTHORS
Deposited By: 1Science Import
Deposited On:05 May 2017 23:39
Last Modified:03 Oct 2019 16:57

Repository Staff Only: item control page