zbMATH — the first resource for mathematics

Departures from many queues in series. (English) Zbl 0749.60090
Consider a series of \(n\) queues with a common service time distribution, and let \(D(k,n)\) denote the departure time of customer \(k\), assuming that initially \(k\) customers are placed in the first queue. The limiting behaviour of \(D(k,n)\) as \(n\to\infty\) is studied in various regimes for \(k\): if \(k\) is fixed, \((D(k,n)-n)/\sqrt n\) converges in distribution to a certain functional of \(k\)-dimensional Brownian motion; if \(k=k_ n\approx xn^{1-\varepsilon}\), \((D(k,n)-n)/\sqrt {nk}\) converges in probability to a constant independent of \(x\); and if \(k_ n\approx xn\), then \(D(k,n)/n\) converges in probability to a constant dependent on \(x\) (this result may be interpreted as a hydrodynamic limit). A basic observation is a duality between \(k\) and \(n\), which is obtained by expressing \(D(k,n)\) as the maximum partial sum of service times over paths of length \(k+n-1\) in a \(k\times n\) lattice of service times. The techniques involve weak convergence in function spaces, strong approximations and the subadditive ergodic theorem.

60K25 Queueing theory (aspects of probability theory)
60F17 Functional limit theorems; invariance principles
90B22 Queues and service in operations research
60J60 Diffusion processes
60F15 Strong limit theorems
Full Text: DOI