Departures from Many Queues in Series

P. W. Glynn and W. Whitt

Annals of Applied Probability, Vol.1,  546-572 (1991)

We consider a series of n single-server queues, each with unlimited waiting space and the first-in first-out service discipline. Initially, the system is empty; then k customers are placed in the first queue. The service times of all the customers at all the queues are i.i.d. with a general distribution. We are interested in the time D(k,n) required for all k customers to complete service from all n queues. In particular, we investigate the limiting behavior of D(k,n) as n->∞ and/or k ->∞. There is a duality implying that D(k,n) is distributed the same as D(n,k) so that results for large n are equivalent to results for large k. A previous heavy-traffic limit theorem implies that D(k,n) satisfies an invariance principle as n ->∞, converging after normalization to a functional of k-dimensional Brownian motion. We use the subadditive ergodic theorem and a strong approximation to describe the limiting behavior of D(kn,n), where kn ->∞ as n ->∞. The case of kn = [xn] corresponds to a hydrodynamic limit.