A large-deviations analysis of the GI/GI/1 SRPT queue

2005/05/23 by Misja Nuyens, Bert Zwart, Nuyens, Misja +1 · 1 citation
Business, Management and Accounting · Engineering · Mathematics · #60F10 #60K25 (primary) #90B22 (secondary) #Advanced Queuing Theory Analysis #Advanced Wireless Network Optimization #FOS: Mathematics #Probability (math.PR) #Reliability and Maintenance Optimization #math.PR #msc:60F10 #msc:60K25 #msc:90B22

paper · pdf · doi:10.48550/arxiv.math/0505450

22 pages

arxiv created 2005/05/23 · openalex publication_date 2005/05/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a GI/GI/1 queue with the shortest remaining processing time discipline (SRPT) and light-tailed service times. Our interest is focused on the tail behavior of the sojourn-time distribution. We obtain a general expression for its large-deviations decay rate. The value of this decay rate critically depends on whether there is mass in the endpoint of the service-time distribution or not. An auxiliary priority queue, for which we obtain some new results, plays an important role in our analysis. We apply our SRPT-results to compare SRPT with FIFO from a large-deviations point of view.

Cited by

• The Gittins Index: A Design Principle for Decision-Making Under Uncertainty

Related

• On the steady-state probability of delay and large negative deviations for the GI/GI/n queue in the Halfin-Whitt regime
• Large deviations analysis for the M/H₂/n + M queue in the Halfin-Whitt regime
• Heavy-tailed queues in the Halfin-Whitt regime
• Moderate deviations of many--server queues, idempotent processes and quasipotentials
• On Gaussian Limits and Large Deviations for Queues Fed by High Intensity Randomly Scattered Traffic