Heavy traffic analysis for EDF queues with reneging
From MaRDI portal
(Redirected from Publication:535200)
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.
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
Cites work
- scientific article; zbMATH DE number 3885030 (Why is no real title available?)
- scientific article; zbMATH DE number 3125504 (Why is no real title available?)
- scientific article; zbMATH DE number 3951715 (Why is no real title available?)
- scientific article; zbMATH DE number 4078444 (Why is no real title available?)
- scientific article; zbMATH DE number 192908 (Why is no real title available?)
- scientific article; zbMATH DE number 1354815 (Why is no real title available?)
- scientific article; zbMATH DE number 3206641 (Why is no real title available?)
- scientific article; zbMATH DE number 3185400 (Why is no real title available?)
- A diffusion approximation for a GI/GI/1 queue with balking or reneging
- A diffusion approximation for a Markovian queue with reneging
- A multiserver queueing system with impatient customers
- Accuracy of state space collapse for earliest-deadline-first queues
- An explicit formula for the Skorokhod map on \([0,a]\)
- Applied Probability and Queues
- Convex duality and the Skorokhod problem. II
- Diffusion approximation for a \(G/G/1\) EDF queue with unbounded lead times
- Diffusion approximation for a processor sharing queue in heavy traffic.
- Diffusion limits for shortest remaining processing time queues
- Double Skorokhod Map and Reneging Real-Time Queues
- Earliest-deadline-first service in heavy-traffic acyclic networks.
- Fluid and heavy traffic diffusion limits for a generalized processor sharing model
- Fluid limit of a heavily loaded EDF queue with impatient customers
- Fluid limits for shortest remaining processing time queues
- Heavy traffic limit for a processor sharing queue with soft deadlines
- Law of large numbers limits for many-server queues
- Multiple channel queues in heavy traffic. I
- On the behavior of LIFO preemptive resume queues in heavy traffic
- Real-time queues in heavy traffic with earliest-deadline-first queue discipline
- Reflected Brownian motion on an orthant
- Steady state approximations of limited processor sharing queues in heavy traffic
- Stochastic discrete flow networks: Diffusion approximations and bottlenecks
- Stochastic-Process Limits
- Validity of heavy traffic steady-state approximations in generalized Jackson networks
- Weak convergence theorems for priority queues: preemptive-resume discipline
Cited in
(28)- Diffusive limits of Lipschitz functionals of Poisson measures
- 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
- Law of large numbers for the many-server earliest-deadline-first queue
- Diffusion approximation for a \(G/G/1\) EDF queue with unbounded lead times
- A Skorokhod map on measure-valued paths with applications to priority queues
- 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
- Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
- 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
- Diffusion approximations for open Jackson networks with reneging
- Stability of linear EDF networks with resource sharing
- Processor-shared buffers with reneging
- On queues with impatience: stability, and the optimality of earliest deadline first
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)
