IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v56y2008i1p88-101.html
   My bibliography  Save this article

Preventing Large Sojourn Times Using SMART Scheduling

Author

Listed:
  • Misja Nuyens

    (Department of Mathematics, Vrije Universiteit Amsterdam, De Boelelaan 1081, 1081 HV Amsterdam, The Netherlands)

  • Adam Wierman

    (Computer Science Department, California Institute of Technology, Pasadena, California 91125)

  • Bert Zwart

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

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.

Suggested Citation

  • Misja Nuyens & Adam Wierman & Bert Zwart, 2008. "Preventing Large Sojourn Times Using SMART Scheduling," Operations Research, INFORMS, vol. 56(1), pages 88-101, February.
    • Handle: RePEc:inm:oropre:v:56:y:2008:i:1:p:88-101
    DOI: 10.1287/opre.1070.0504
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1070.0504
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1070.0504?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. P. Jelenković & P. Momčilović, 2003. "Large Deviation Analysis of Subexponential Waiting Times in a Processor-Sharing Queue," Mathematics of Operations Research, INFORMS, vol. 28(3), pages 587-608, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Adam Wierman & Bert Zwart, 2012. "Is Tail-Optimal Scheduling Possible?," Operations Research, INFORMS, vol. 60(5), pages 1249-1257, October.
    2. Samuli Aalto & Ziv Scully, 2023. "Minimizing the mean slowdown in the M/G/1 queue," Queueing Systems: Theory and Applications, Springer, vol. 104(3), pages 187-210, August.
    3. Predrag Jelenković & Xiaozhu Kang & Jian Tan, 2009. "Heavy-tailed limits for medium size jobs and comparison scheduling," Annals of Operations Research, Springer, vol. 170(1), pages 133-159, September.
    4. Bo Zhang & Bert Zwart, 2013. "Steady-State Analysis for Multiserver Queues Under Size Interval Task Assignment in the Quality-Driven Regime," Mathematics of Operations Research, INFORMS, vol. 38(3), pages 504-525, August.
    5. Nikhil Bansal & Bart Kamphorst & Bert Zwart, 2018. "Achievable Performance of Blind Policies in Heavy Traffic," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 949-964, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mihalis G. Markakis & Eytan Modiano & John N. Tsitsiklis, 2018. "Delay Analysis of the Max-Weight Policy Under Heavy-Tailed Traffic via Fluid Approximations," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 460-493, May.
    2. Predrag R. Jelenković & Petar Momčilović, 2004. "Large Deviations of Square Root Insensitive Random Sums," Mathematics of Operations Research, INFORMS, vol. 29(2), pages 398-406, May.
    3. Predrag Jelenković & Xiaozhu Kang & Jian Tan, 2009. "Heavy-tailed limits for medium size jobs and comparison scheduling," Annals of Operations Research, Springer, vol. 170(1), pages 133-159, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:56:y:2008:i:1:p:88-101. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.