This paper presents a heavy traffic analysis of the behavior of multi-class acyclic queueing networks in which the customers have deadlines. We assume the queueing system consists of J stations, and there are K different customer classes. Customers from each class arrive to the network according to independent renewal processes. The customers from each class are assigned a random deadline drawn from a deadline distribution associated with that class and they move from station to station according to a fixed acyclic route. The customers at a given node are processed according to the earliest-deadline-first (EDF) queue discipline. At any time, the customers of each type at each node have a lead time, the time until their deadline lapses. We model these lead times as a random counting measure on the real line. Under heavy traffic conditions and suitable scaling, it is proved that the measure-valued lead-time process converges to a deterministic function of the workload process. A two-station example is worked out in detail, and simulation results are presented to illustrate the predictive value of the theory. This work is a generalization of Doytchinov, Lehoczky and Shreve [Ann. Appl. Probab. 11 (2001) 332–379], which developed these results for the single queue case.
Publié le : 2004-08-14
Classification:
Acyclic networks,
due dates,
heavy traffic,
queueing,
diffusion limits,
random measures.,
60K25,
60G57,
60J65,
68M20
@article{1089736287,
author = {Kruk, \L ukasz and Lehoczky, John and Shreve, Steven and Yeung, Shu-Ngai},
title = {Earliest-deadline-first service in heavy-traffic acyclic networks},
journal = {Ann. Appl. Probab.},
volume = {14},
number = {1},
year = {2004},
pages = { 1306-1352},
language = {en},
url = {http://dml.mathdoc.fr/item/1089736287}
}
Kruk, Łukasz; Lehoczky, John; Shreve, Steven; Yeung, Shu-Ngai. Earliest-deadline-first service in heavy-traffic acyclic networks. Ann. Appl. Probab., Tome 14 (2004) no. 1, pp. 1306-1352. http://gdmltest.u-ga.fr/item/1089736287/