Real-time queues in heavy traffic with earliest-deadline-first queue discipline

DOI10.1214/aoap/1015345295zbMath1015.60086OpenAlexW2025585405MaRDI QIDQ1872459

Bogdan Doytchinov, Steven E. Shreve, John P. Lehoczky

Publication date: 6 May 2003

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

Full work available at URL: https://doi.org/10.1214/aoap/1015345295

zbMATH Keywords

queueingheavy trafficdue datesdiffusion limitsrandom measures

Mathematics Subject Classification ID

Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22) Brownian motion (60J65) Random measures (60G57)

Related Items (33)

Multiple-input heavy-traffic real-time queues. ⋮ Diffusion approximation for a processor sharing queue in heavy traffic. ⋮ Earliest-deadline-first service in heavy-traffic acyclic networks. ⋮ Fluid Limits of G/G/1+G Queues Under the Nonpreemptive Earliest-Deadline-First Discipline ⋮ Law of large numbers for the many-server earliest-deadline-first queue ⋮ A functional central limit theorem for the \(M/GI/\infty \) queue ⋮ Personalized queues: the customer view, via a fluid model of serving least-patient first ⋮ On the optimal allocation of service to impatient tasks ⋮ On queues with impatience: stability, and the optimality of earliest deadline first ⋮ Edge minimality of EDF resource sharing networks ⋮ Limiting distribution for a simple model of order book dynamics ⋮ Markovian online matching algorithms on large bipartite random graphs ⋮ Impact of priority sequencing decisions on on-time probability and expected tardiness of orders in make-to-order production systems with external due-dates ⋮ Fluid limits for earliest-deadline-first networks ⋮ Stability of linear EDF networks with resource sharing ⋮ SCHEDULING IMPATIENT JOBS IN A CLEARING SYSTEM WITH INSIGHTS ON PATIENT TRIAGE IN MASS CASUALTY INCIDENTS ⋮ Continuity and monotonicity of solutions to a greedy maximization problem ⋮ Control of end-to-end delay tails in a multiclass network: LWDF discipline optimality ⋮ Heavy traffic limit for a processor sharing queue with soft deadlines ⋮ An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system ⋮ Ergodicity of an SPDE associated with a many-server queue ⋮ A Skorokhod map on measure-valued paths with applications to priority queues ⋮ An \(\mathsf{EDF}\)-based restricted-migration scheduling algorithm for multiprocessor soft real-time systems ⋮ Tardiness bounds under global EDF scheduling on a multiprocessor ⋮ Heavy traffic analysis for EDF queues with reneging ⋮ Diffusion limits of limited processor sharing queues ⋮ Accuracy of state space collapse for earliest-deadline-first queues ⋮ Stability of preemptive EDF queueing networks ⋮ On the optimality of the earliest due date rule in stochastic scheduling and in queueing ⋮ A diffusion approximation for a GI/GI/1 queue with balking or reneging ⋮ Simulation of multidimensional diffusions with sticky boundaries via Markov chain approximation ⋮ Minimal and Locally Edge Minimal Fluid Models for Resource-Sharing Networks ⋮ Heavy traffic analysis for single-server SRPT and LRPT queues via EDF diffusion limits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Brownian models of multiclass queueing networks: Current status and open problems
• Polling systems with zero switchover times: A heavy-traffic averaging principle
• Dynamic scheduling with convex delay costs: The generalized \(c\mu\) rule
• A Heavy Traffic Limit Theorem for Networks of Queues with Multiple Customer Types
• Heavy Traffic Analysis of Dynamic Cyclic Policies: A Unified Treatment of the Single Machine Scheduling Problem
• A multiclass feedback queue in heavy traffic
• A limit theorem for priority queues in heavy traffic
• Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Closed Network
• Scheduling Networks of Queues: Heavy Traffic Analysis of a Two-Station Network with Controllable Inputs
• A performance analysis of minimum laxity and earliest deadline scheduling in a real-time system
• On some limit theorems for the GI/G/1 queue
• Weak convergence theorems for priority queues: preemptive-resume discipline
• Multiple channel queues in heavy traffic. I
• The virtual waiting time of the GI/G/1 queue in heavy traffic
• Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment

This page was built for publication: Real-time queues in heavy traffic with earliest-deadline-first queue discipline