Diffusion limits for shortest remaining processing time queues
From MaRDI portal
Abstract: 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.
Recommendations
- Diffusion limits of limited processor sharing queues
- Refining diffusion approximations for queues
- Fluid and diffusion limits for transient sojourn times of processor sharing queues with time varying rates
- scientific article; zbMATH DE number 7529536
- On some diffusion approximations to queueing systems
- Fluid limits for shortest remaining processing time queues
- scientific article; zbMATH DE number 1096972
- Queue with limited volume, a diffusion approximation approach
Cites work
- scientific article; zbMATH DE number 3125504 (Why is no real title available?)
- scientific article; zbMATH DE number 3922340 (Why is no real title available?)
- scientific article; zbMATH DE number 3950174 (Why is no real title available?)
- scientific article; zbMATH DE number 3951715 (Why is no real title available?)
- scientific article; zbMATH DE number 3274494 (Why is no real title available?)
- A large-deviations analysis of the GI/GI/1 SRPT queue
- Fluid limits for shortest remaining processing time queues
- Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
- Multi-layered round robin routing for parallel servers
- Multiple channel queues in heavy traffic. I
- Queues with equally heavy sojourn time and service requirement distributions
- Technical Note—A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline
- The Queue M/G/1 with the Shortest Remaining Processing Time Discipline
- The steady-state appearance of the M/G/1 queue under the discipline of shortest remaining processing time
- Weak convergence theorems for priority queues: preemptive-resume discipline
Cited in
(17)- SEH: size estimate hedging for single-server queues
- Instability of SRPT, SERPT and SJF multiclass queueing networks
- SRPT applied to bandwidth-sharing networks
- Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits
- Fluid limits for shortest remaining processing time queues
- A fluid approximation for a matching model with general reneging distributions
- The SRPT service policy with frequency scaling: modeling, evaluation and optimization
- A Skorokhod map on measure-valued paths with applications to priority queues
- Heavy traffic scaling limits for shortest remaining processing time queues with light tailed processing time distributions
- Fluid limits for shortest job first with aging
- Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling
- On the average sojourn time under \(M/M/1/\)SRPT
- Heavy traffic analysis for EDF queues with reneging
- Fluid limits for multiple-input shortest remaining processing time queues
- Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions
- Invariance of fluid limits for the shortest remaining processing time and shortest job first policies
- Diffusion limits for SRPT and LRPT queues via EDF approximations
This page was built for publication: Diffusion limits for shortest remaining processing time queues
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168838)
