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(kn,n), where kn.. as n... The case of kn=[xn] corresponds to a hydrodynamic limit.