Diffusion limits for shortest remaining processing time queues
We present a heavy traffic analysis for a single server queue with renewal arrivals and generally distributed i.i.d. service times, in which the server employs the Shortest Remaining Processing Time (SRPT) policy. Under typical heavy traffic assumptions, we prove a diffusion limit theorem for a meas...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2011-01-01
|
| Series: | Stochastic Systems |
| Subjects: | |
| Online Access: | http://www.i-journals.org/ssy/viewarticle.php?id=16&layout=abstract |
| _version_ | 1811340680386052096 |
|---|---|
| author | Amber L. Puha Łukasz Kruk H. Christian Gromoll |
| author_facet | Amber L. Puha Łukasz Kruk H. Christian Gromoll |
| author_sort | Amber L. Puha |
| collection | DOAJ |
| description | We present a heavy traffic analysis for a single server queue with renewal arrivals and generally distributed i.i.d. service times, in which the server employs the Shortest Remaining Processing Time (SRPT) policy. Under typical heavy traffic assumptions, we prove a diffusion limit theorem for a measure-valued state descriptor, from which we conclude a similar theorem for the queue length process. These results allow us to make some observations on the queue length optimality of SRPT. In particular, they provide the sharpest illustration of the well-known tension between queue length optimality and quality of service for this policy. |
| first_indexed | 2024-04-13T18:45:29Z |
| format | Article |
| id | doaj.art-a97b069995554d5d9020374e3d2016ed |
| institution | Directory Open Access Journal |
| issn | 1946-5238 |
| language | English |
| last_indexed | 2024-04-13T18:45:29Z |
| publishDate | 2011-01-01 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | Article |
| series | Stochastic Systems |
| spelling | doaj.art-a97b069995554d5d9020374e3d2016ed2022-12-22T02:34:35ZengInstitute for Operations Research and the Management Sciences (INFORMS)Stochastic Systems1946-52382011-01-0111116Diffusion limits for shortest remaining processing time queuesAmber L. PuhaŁukasz KrukH. Christian GromollWe present a heavy traffic analysis for a single server queue with renewal arrivals and generally distributed i.i.d. service times, in which the server employs the Shortest Remaining Processing Time (SRPT) policy. Under typical heavy traffic assumptions, we prove a diffusion limit theorem for a measure-valued state descriptor, from which we conclude a similar theorem for the queue length process. These results allow us to make some observations on the queue length optimality of SRPT. In particular, they provide the sharpest illustration of the well-known tension between queue length optimality and quality of service for this policy.http://www.i-journals.org/ssy/viewarticle.php?id=16&layout=abstractHeavy trafficueueingshortest remaining processing timediffusion limit |
| spellingShingle | Amber L. Puha Łukasz Kruk H. Christian Gromoll Diffusion limits for shortest remaining processing time queues Stochastic Systems Heavy traffic ueueing shortest remaining processing time diffusion limit |
| title | Diffusion limits for shortest remaining processing time queues |
| title_full | Diffusion limits for shortest remaining processing time queues |
| title_fullStr | Diffusion limits for shortest remaining processing time queues |
| title_full_unstemmed | Diffusion limits for shortest remaining processing time queues |
| title_short | Diffusion limits for shortest remaining processing time queues |
| title_sort | diffusion limits for shortest remaining processing time queues |
| topic | Heavy traffic ueueing shortest remaining processing time diffusion limit |
| url | http://www.i-journals.org/ssy/viewarticle.php?id=16&layout=abstract |
| work_keys_str_mv | AT amberlpuha diffusionlimitsforshortestremainingprocessingtimequeues AT łukaszkruk diffusionlimitsforshortestremainingprocessingtimequeues AT hchristiangromoll diffusionlimitsforshortestremainingprocessingtimequeues |