Heavy traffic analysis for EDF queues with reneging (Q535200): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: John P. Lehoczky / rank | |||
Property / author | |||
Property / author: Steven E. Shreve / rank | |||
Property / author | |||
Property / author: John P. Lehoczky / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Steven E. Shreve / rank | |||
Normal rank | |||
Property / review text | |||
The paper considers a single-server queue in which customers have deadlines and are served until their deadlines elapse. The performance of the system is measured by the fraction of reneged work, defined as the residual work not serviced due to elapsed deadlines. This quantity is shown to be minimized by an earliest-deadline-first scheduling policy. The main result of the paper is a heavy traffic convergence theorem. It is shown that the limit of the scaled workload process is a doubly reflected Brownian motion with lower barrier zero and upper barrier at the mean of the lead time distribution. It is also shown that, conditional on the limiting workload, the resulting limiting measure-valued workload process is the same limiting process as when customers are served to completion. | |||
Property / review text: The paper considers a single-server queue in which customers have deadlines and are served until their deadlines elapse. The performance of the system is measured by the fraction of reneged work, defined as the residual work not serviced due to elapsed deadlines. This quantity is shown to be minimized by an earliest-deadline-first scheduling policy. The main result of the paper is a heavy traffic convergence theorem. It is shown that the limit of the scaled workload process is a doubly reflected Brownian motion with lower barrier zero and upper barrier at the mean of the lead time distribution. It is also shown that, conditional on the limiting workload, the resulting limiting measure-valued workload process is the same limiting process as when customers are served to completion. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Oleg K. Zakusilo / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60K25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60G57 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60J65 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68M20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B22 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5886809 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
due dates | |||
Property / zbMATH Keywords: due dates / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
heavy traffic | |||
Property / zbMATH Keywords: heavy traffic / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
queueing | |||
Property / zbMATH Keywords: queueing / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
reneging | |||
Property / zbMATH Keywords: reneging / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
diffusion limits | |||
Property / zbMATH Keywords: diffusion limits / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
random measures | |||
Property / zbMATH Keywords: random measures / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
real-time queues | |||
Property / zbMATH Keywords: real-time queues / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1104.1047 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Applied Probability and Queues / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4269108 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Multiserver Queueing System with Impatient Customers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Stochastic discrete flow networks: Diffusion approximations and bottlenecks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3527603 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fluid Limits for Shortest Remaining Processing Time Queues / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Real-time queues in heavy traffic with earliest-deadline-first queue discipline / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convex duality and the Skorokhod problem. II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3721531 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Validity of heavy traffic steady-state approximations in generalized Jackson networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Diffusion approximation for a processor sharing queue in heavy traffic. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Heavy traffic limit for a processor sharing queue with soft deadlines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Diffusion limits for shortest remaining processing time queues / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Reflected Brownian motion on an orthant / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3808989 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multiple channel queues in heavy traffic. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4039796 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Law of large numbers limits for many-server queues / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5721605 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5332541 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5454115 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Earliest-deadline-first service in heavy-traffic acyclic networks. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Accuracy of state space collapse for earliest-deadline-first queues / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An explicit formula for the Skorokhod map on \([0,a]\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Double Skorokhod Map and Reneging Real-Time Queues / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the behavior of LIFO preemptive resume queues in heavy traffic / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3240992 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fluid and heavy traffic diffusion limits for a generalized processor sharing model / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3218851 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A diffusion approximation for a Markovian queue with reneging / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A diffusion approximation for a GI/GI/1 queue with balking or reneging / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Weak convergence theorems for priority queues: preemptive-resume discipline / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Stochastic-Process Limits / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Steady state approximations of limited processor sharing queues in heavy traffic / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 01:38, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Heavy traffic analysis for EDF queues with reneging |
scientific article |
Statements
Heavy traffic analysis for EDF queues with reneging (English)
0 references
11 May 2011
0 references
The paper considers a single-server queue in which customers have deadlines and are served until their deadlines elapse. The performance of the system is measured by the fraction of reneged work, defined as the residual work not serviced due to elapsed deadlines. This quantity is shown to be minimized by an earliest-deadline-first scheduling policy. The main result of the paper is a heavy traffic convergence theorem. It is shown that the limit of the scaled workload process is a doubly reflected Brownian motion with lower barrier zero and upper barrier at the mean of the lead time distribution. It is also shown that, conditional on the limiting workload, the resulting limiting measure-valued workload process is the same limiting process as when customers are served to completion.
0 references
due dates
0 references
heavy traffic
0 references
queueing
0 references
reneging
0 references
diffusion limits
0 references
random measures
0 references
real-time queues
0 references