A Diffusion Approximation for the G/GI/n/m Queue
- 1 December 2004
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 52 (6), 922-941
- https://doi.org/10.1287/opre.1040.0136
Abstract
We develop a diffusion approximation for the queue-length stochastic process in the G/GI/n/m queueing model (having a general arrival process, independent and identically distributed service times with a general distribution, n servers, and m extra waiting spaces). We use the steady-state distribution of that diffusion process to obtain approximations for steady-state performance measures of the queueing model, focusing especially upon the steady-state delay probability. The approximations are based on heavy-traffic limits in which n tends to infinity as the traffic intensity increases. Thus, the approximations are intended for large n. For the GI/M/n/∞ special case, Halfin and Whitt (1981) showed that scaled versions of the queue-length process converge to a diffusion process when the traffic intensity ρn approaches 1 with (1 – ρn)√n → β for 0 < β < ∞. A companion paper, Whitt (2005), extends that limit to a special class of G/GI/n/mn models in which the number of waiting places depends on n and the service-time distribution is a mixture of an exponential distribution with probability p and a unit point mass at 0 with probability 1 – p. Finite waiting rooms are treated by incorporating the additional limit mn/√n → κ for 0 < κ ≤ ∞. The approximation for the more general G/GI/n/m model developed here is consistent with those heavy-traffic limits. Heavy-traffic limits for the GI/PH/n/∞ model with phase-type service-time distributions established by Puhalskii and Reiman (2000) imply that our approximating process is not asymptotically correct for nonexponential phase-type service-time distributions, but nevertheless, the heuristic diffusion approximation developed here yields useful approximations for key performance measures such as the steady-state delay probability. The accuracy is confirmed by making comparisons with exact numerical results and simulations.This publication has 34 references indexed in Scilit:
- The multiclass GI/PH/N queue in the Halfin-Whitt regimeAdvances in Applied Probability, 2000
- Equivalence relations in the approximations for the M/G/s/s + r queueMathematical and Computer Modelling, 2000
- Fitting mixtures of exponentials to long-tail distributions to analyze network performance modelsPerformance Evaluation, 1998
- Simulation run lengths to estimate blocking probabilitiesACM Transactions on Modeling and Computer Simulation, 1996
- AnM/M/s-consistent diffusion model for theGI/G/s queueQueueing Systems, 1995
- APPROXIMATIONS FOR THE GI/G/m QUEUEProduction and Operations Management, 1993
- The Brownian approximation for rate-control throttles and the G/G/1/C queueDiscrete Event Dynamic Systems, 1992
- Comparisons of multi-server queues with finite waiting roomsCommunications in Statistics. Stochastic Models, 1992
- Comparison conjectures about the M/G/s queueOperations Research Letters, 1983
- Approximations in finite-capacity multi-server queues by Poisson arrivalsJournal of Applied Probability, 1978