Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling

DOI10.1214/14-AAP1076MaRDI QIDQ894810zbMATH OpenFDO

Authors Amber L. Puha

Publication date 24 November 2015

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.3837, https://projecteuclid.org/euclid.aoap/1443703777

zbMATH Keywords

queueingheavy trafficdiffusion limitshortest remaining processing timenonstandard scaling

Mathematics Subject Classification ID

Diffusion processes (60J60) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Functional limit theorems; invariance principles (60F17) Random measures (60G57)

Abstract: We develop a heavy traffic diffusion limit theorem under nonstandard spatial scaling for the queue length process in a single server queue employing shortest remaining processing time (SRPT). For processing time distributions with unbounded support, it has been shown that standard diffusion scaling yields an identically zero limit. We specify an alternative spatial scaling that produces a nonzero limit. Our model allows for renewal arrivals and i.i.d. processing times satisfying a rapid variation condition. We add a corrective spatial scale factor to standard diffusion scaling, and specify conditions under which the sequence of unconventionally scaled queue length processes converges in distribution to the same nonzero reflected Brownian motion to which the sequence of conventionally scaled workload processes converges. Consequently, this corrective spatial scale factor characterizes the order of magnitude difference between the queue length and workload processes of SRPT queues in heavy traffic. It is determined by the processing time distribution such that the rate at which it tends to infinity depends on the rate at which the tail of the processing time distribution tends to zero. For Weibull processing time distributions, we restate this result in a manner that makes the resulting state space collapse more apparent.

Recommendations

• Diffusion limits for shortest remaining processing time queues
• Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions
• Diffusion limits for SRPT and LRPT queues via EDF approximations
• Fluid limits for shortest remaining processing time queues
• Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits

Cites work

• 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 4000257 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• A LIFO queue in heavy traffic
• A large-deviations analysis of the GI/GI/1 SRPT queue
• A multiclass closed queueing network with unconventional heavy traffic behavior
• Diffusion approximation for a processor sharing queue in heavy traffic.
• Diffusion limits for shortest remaining processing time queues
• Fluid limits for shortest remaining processing time queues
• Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
• Multiple channel queues in heavy traffic. I
• Queues with equally heavy sojourn time and service requirement distributions
• Slowly varying functions and asymptotic relations
• 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

(14)

• Fluid limits for shortest job first with aging
• Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits
• A note on non-existence of diffusion limits for serve-the-longest-queue when the buffers are equal in size
• Diffusion limits for SRPT and LRPT queues via EDF approximations
• Instability of SRPT, SERPT and SJF multiclass queueing networks
• A fluid approximation for a matching model with general reneging distributions
• Fluid limits for earliest-deadline-first networks
• Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions
• Achievable performance of blind policies in heavy traffic
• Heavy-traffic analysis of sojourn time under the foreground-background scheduling policy
• Fluid limits for shortest remaining processing time queues
• Fluid limits for multiple-input shortest remaining processing time queues
• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
• A Skorokhod map on measure-valued paths with applications to priority queues

This page was built for publication: Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894810)