Academic Journals Database
Disseminating quality controlled scientific knowledge

Diffusion limits for shortest remaining processing time queues

Author(s): H. Christian Gromoll | Łukasz Kruk | Amber L. Puha

Journal: Stochastic Systems
ISSN 1946-5238

Volume: 1;
Issue: 1;
Start page: 1;
Date: 2011;
Original page

Keywords: Heavy traffic | ueueing | shortest remaining processing time | diffusion limit

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.

HR software für Hotellerie

Automatische Erstellung
von Personaldokumente
und Anmeldungen bei Behörden

RPA Switzerland

Robotic Process Automation Switzerland