Departures from Many Queues in Series

Glynn, Peter W. ; Whitt, Ward

Ann. Appl. Probab., Tome 1 (1991) no. 4, p. 546-572 / Harvested from Project Euclid

Résumé

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 \rightarrow \infty$ and/or $k \rightarrow \infty$. 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 \rightarrow \infty$, 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,n)$, where $k_n \rightarrow \infty$ as $n \rightarrow \infty$. The case of $k_n = \lbrack xn \rbrack$ corresponds to a hydrodynamic limit.

Détail

Publié le : 1991-11-14
Classification:  Tandem queues,  queues in series,  queueing networks,  departure process,  transient behavior,  reflected Brownian motion,  limit theorems,  invariance principle,  strong approximation,  subadditive ergodic theorem,  large deviations,  interacting particle systems,  hydrodynamic limit,  60K25,  60F17,  90B22,  60J60,  60F15