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

DOI10.1214/14-AAP1076zbMATH Open1328.60205arXiv1407.3837MaRDI QIDQ894810FDOQ894810

Authors: Amber L. Puha 

Publication date: 24 November 2015

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

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.

Full work available at URL: https://arxiv.org/abs/1407.3837

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
• Multiple channel queues in heavy traffic. I
• Weak convergence theorems for priority queues: preemptive-resume discipline
• Slowly varying functions and asymptotic relations
• A LIFO queue in heavy traffic
• Diffusion approximation for a processor sharing queue in heavy traffic.
• Fluid limits for shortest remaining processing time queues
• Diffusion limits for shortest remaining processing time queues
• A large-deviations analysis of the GI/GI/1 SRPT queue
• 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
• Technical Note—A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline
• Queues with equally heavy sojourn time and service requirement distributions
• A multiclass closed queueing network with unconventional heavy traffic behavior
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (14)

• Instability of SRPT, SERPT and SJF multiclass queueing 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
• A note on non-existence of diffusion limits for serve-the-longest-queue when the buffers are equal in size
• A Skorokhod map on measure-valued paths with applications to priority queues
• Fluid limits for earliest-deadline-first networks
• Fluid limits for shortest job first with aging
• Achievable performance of blind policies in heavy traffic
• Heavy-traffic analysis of sojourn time under the foreground-background scheduling policy
• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
• 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
• Diffusion limits for SRPT and LRPT queues via EDF approximations

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)