UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers

Dong, J; Ibrahim, R; (2021) SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers. Management Science 10.1287/mnsc.2021.4110. (In press). Green open access

[thumbnail of Ibrahim_On the SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers.pdf]
Preview
Text
Ibrahim_On the SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers.pdf - Accepted Version

Download (321kB) | Preview

Abstract

The shortest-remaining-processing-time (SRPT) scheduling policy has been extensively studied, for more than 50 years, in single-server queues with infinitely patient jobs. Yet, much less is known about its performance in multiserver queues. In this paper, we present the first theoretical analysis of SRPT in multiserver queues with abandonment. In particular, we consider the M/GI/s+GI queue and demonstrate that, in the many-sever overloaded regime, performance in the SRPT queue is equivalent, asymptotically in steady state, to a preemptive two-class priority queue where customers with short service times (below a threshold) are served without wait, and customers with long service times (above a threshold) eventually abandon without service. We prove that the SRPT discipline maximizes, asymptotically, the system throughput, among all scheduling disciplines. We also compare the performance of the SRPT policy to blind policies and study the effects of the patience-time and service-time distributions.

Type: Article
Title: SRPT Scheduling Discipline in Many-Server Queues with Impatient Customers
Open access status: An open access version is available from UCL Discovery
DOI: 10.1287/mnsc.2021.4110
Publisher version: https://doi.org/10.1287/mnsc.2021.4110
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > UCL School of Management
URI: https://discovery.ucl.ac.uk/id/eprint/10140016
Downloads since deposit
44Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item