Heavy traffic analysis for EDF queues with reneging

DOI10.1214/10-AAP681zbMATH Open1220.60053arXiv1104.1047OpenAlexW3098977136MaRDI QIDQ535200FDOQ535200

Authors: Łukasz Kruk, Kavita Ramanan, John P. Lehoczky, Steven Shreve 

Publication date: 11 May 2011

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

Abstract: This paper presents a heavy-traffic analysis of the behavior of a single-server queue under an Earliest-Deadline-First (EDF) scheduling policy in which customers have deadlines and are served only until their deadlines elapse. The performance of the system is measured by the fraction of reneged work (the residual work lost due to elapsed deadlines) which is shown to be minimized by the EDF policy. The evolution of the lead time distribution of customers in queue is described by a measure-valued process. The heavy traffic limit of this (properly scaled) process is shown to be a deterministic function of the limit of the scaled workload process which, in turn, is identified to be a doubly reflected Brownian motion. This paper complements previous work by Doytchinov, Lehoczky and Shreve on the EDF discipline in which customers are served to completion even after their deadlines elapse. The fraction of reneged work in a heavily loaded system and the fraction of late work in the corresponding system without reneging are compared using explicit formulas based on the heavy traffic approximations. The formulas are validated by simulation results.

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

Recommendations

• Earliest-deadline-first service in heavy-traffic acyclic networks.
• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• Fluid limits for earliest-deadline-first networks
• Diffusion approximation for a \(G/G/1\) EDF queue with unbounded lead times
• Accuracy of state space collapse for earliest-deadline-first queues

zbMATH Keywords

queueingdue datesdiffusion limitsrandom measuresheavy trafficrenegingreal-time queues

Mathematics Subject Classification ID

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) Brownian motion (60J65) Random measures (60G57)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Applied Probability and Queues
• Stochastic-Process Limits
• Title not available (Why is that?)
• Multiple channel queues in heavy traffic. I
• Law of large numbers limits for many-server queues
• Reflected Brownian motion on an orthant
• Stochastic discrete flow networks: Diffusion approximations and bottlenecks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex duality and the Skorokhod problem. II
• Weak convergence theorems for priority queues: preemptive-resume discipline
• A diffusion approximation for a GI/GI/1 queue with balking or reneging
• Title not available (Why is that?)
• A multiserver queueing system with impatient customers
• Earliest-deadline-first service in heavy-traffic acyclic networks.
• Title not available (Why is that?)
• A diffusion approximation for a Markovian queue with reneging
• Fluid and heavy traffic diffusion limits for a generalized processor sharing model
• Validity of heavy traffic steady-state approximations in generalized Jackson networks
• Diffusion approximation for a processor sharing queue in heavy traffic.
• An explicit formula for the Skorokhod map on \([0,a]\)
• Heavy traffic limit for a processor sharing queue with soft deadlines
• Fluid limits for shortest remaining processing time queues
• Diffusion limits for shortest remaining processing time queues
• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• Fluid limit of a heavily loaded EDF queue with impatient customers
• Steady state approximations of limited processor sharing queues in heavy traffic
• On the behavior of LIFO preemptive resume queues in heavy traffic
• Double Skorokhod Map and Reneging Real-Time Queues
• Diffusion approximation for a \(G/G/1\) EDF queue with unbounded lead times
• Accuracy of state space collapse for earliest-deadline-first queues

Cited In (28)

• Ergodicity of an SPDE associated with a many-server queue
• Accuracy of state space collapse for earliest-deadline-first queues
• Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits
• Fuzzy testing of operating performance index based on confidence intervals
• Real-time queues in heavy traffic with earliest-deadline-first queue discipline
• Diffusion approximation for a \(G/G/1\) EDF queue with unbounded lead times
• Law of large numbers for the many-server earliest-deadline-first queue
• A Skorokhod map on measure-valued paths with applications to priority queues
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• Personalized queues: the customer view, via a fluid model of serving least-patient first
• Developing a performance index with a Poisson process and an exponential distribution for operations management and continuous improvement
• Fluid limits for earliest-deadline-first networks
• Impact of priority sequencing decisions on on-time probability and expected tardiness of orders in make-to-order production systems with external due-dates
• Multiple-input heavy-traffic real-time queues.
• Fluid limits for shortest job first with aging
• The GI/GI/m queues with reneging in heavy traffic
• SDEs with two reflecting barriers driven by semimartingales and processes with bounded \(p\)-variation
• Replicate to the shortest queues
• Minimality of EDF networks with resource sharing
• Loss ratio of the EDF scheduling policy with early discarding technique
• Edge minimality of EDF resource sharing networks
• Fluid Limits of G/G/1+G Queues Under the Nonpreemptive Earliest-Deadline-First Discipline
• SDEs with two reflecting barriers driven by optional processes with regulated trajectories
• Stability of linear EDF networks with resource sharing
• Diffusion approximations for open Jackson networks with reneging
• Processor-shared buffers with reneging
• On queues with impatience: stability, and the optimality of earliest deadline first
• Diffusive limits of Lipschitz functionals of Poisson measures

This page was built for publication: Heavy traffic analysis for EDF queues with reneging

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