Departures from Many Queues in Series

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(kₙ,n), where kₙ → ∞ as n → ∞. The case of kₙ = xn corresponds to a hydrodynamic limit.