Abstract
To investigate the quality of heavy-traffic approximations for queues with many servers, we consider the steady-state number of waiting customers in an M/D/s queue as s→∞. In the Halfin-Whitt regime, it is well known that this random variable converges to the supremum of a Gaussian random walk. This paper develops methods that yield more accurate results in terms of series expansions and inequalities for the probability of an empty queue, and the mean and variance of the queue length distribution. This quantifies the relationship between the limiting system and the queue with a small or moderate number of servers. The main idea is to view the M/D/s queue through the prism of the Gaussian random walk: as for the standard Gaussian random walk, we provide scalable series expansions involving terms that include the Riemann zeta function.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions, 9th edn. Dover, New York (1970)
Asmussen, S.: Applied Probability and Queues, 2nd edn. Springer, New York (2003)
Barndorff-Nielsen, O.E., Cox, D.R.: Asymptotic Techniques for Use in Statistics. Chapman and Hall, London (1990)
Borst, S., Mandelbaum, A., Reiman, M.: Dimensioning large call centers. Oper. Res. 52, 17–34 (2004)
Blanchet, J., Glynn, P.: Complete corrected diffusion approximations for the maximum of a random walk. Ann. Appl. Probab. 16, 951–983 (2006)
Chang, J.T., Peres, Y.: Ladder heights, Gaussian random walks and the Riemann zeta function. Ann. Probab. 25, 787–802 (1997)
Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the Lambert W function. Adv. Comput. Math. 5, 329–359 (1996)
De Bruijn, N.G.: Asymptotic Methods in Analysis. Dover, New York (1981)
Erdélyi, A., Magnus, W., Oberhettinger, F., Tricomi, F.G.: Higher Transcendental Functions, vol. I. McGraw-Hill, New York (1953)
Franx, G.J.: A simple solution for the M/D/c waiting time distribution. Oper. Res. Lett. 29, 221–229 (2001)
Gans, N., Koole, G., Mandelbaum, A.: Telephone call centers: tutorial, review and research prospects. Manuf. Serv. Oper. Manag. 5, 79–141 (2003)
Halfin, S., Whitt, W.: Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29, 567–588 (1981)
Janssen, A.J.E.M., van Leeuwaarden, J.S.H.: On Lerch’s transcendent and the Gaussian random walk. Ann. Appl. Probab. 17, 421–439 (2007)
Janssen, A.J.E.M., van Leeuwaarden, J.S.H.: Cumulants of the maximum of the Gaussian random walk. Stoch. Process. Appl. 117, 1928–1959 (2007)
Janssen, A.J.E.M., van Leeuwaarden, J.S.H., Zwart, B.: Refining square root staffing by expanding Erlang C. Oper. Res. (2008, under revision)
Jeffrey, D.J., Hare, D.E.G., Corless, R.M.: Unwinding the branches of the Lambert W function. Math. Sci. 21, 1–7 (1996)
Jagerman, D.: Some properties of the Erlang loss function. Bell Syst. Tech. J. 53, 525–551 (1974)
Jelenković, P., Mandelbaum, A., Momčilovic, P.: Heavy traffic limits for queues with many deterministic servers. Queueing Syst. 47, 53–69 (2004)
Jensen, J.L.: Saddlepoint Approximations. Clarendon Press, Oxford (1995)
Mandelbaum, A., Momčilovic, P.: Queues with many servers: The virtual waiting-time process in the QED regime (2005)
Mandelbaum, A.: http://iew3.technion.ac.il/serveng/References/references.html
Michel, R.: On Berry-Esseen bounds for the compound Poisson distribution. Insur. Math. Econ. 13, 35–37 (1993)
Olver, F.W.J.: Asymptotics and Special Functions. Academic, New York (1974)
Puhalskii, A., Reiman, M.: The multiclass GI/PH/N queue in the Halfin-Whitt regime. Adv. Appl. Probab. 32, 564–595 (2000)
Reed, J.: The G/GI/N queue in the Halfin-Whitt regime. Preprint (2006)
Siegmund, D.: Corrected diffusion approximations in certain random walk problems. Adv. Appl. Probab. 11, 701–719 (1979)
Spitzer, F.L.: A combinatorial lemma and its application to probability theory. Trans. Am. Math. Soc. 82, 323–339 (1956)
Szegö, G.: Über eine Eigenschaft der Exponentialreihe. Sitzungsber. Berl. Math. Ges. 22, 50–64 (1922)
Szegö, G.: Orthogonal Polynomials, 4th edn. American Mathematical Society, Providence (1975)
Temme, N.M.: The uniform asymptotic expansion of a class of integrals related to cumulative distribution functions. SIAM J. Math. Anal. 13, 239–253 (1982)
Temme, N.M.: Special Functions. Wiley, New York (1996)
Tijms, H.C.: Stochastic Models: An Algorithmic Approach. Wiley, New York (1994)
van Leeuwaarden, J.S.H.: Queueing models for cable access networks. Ph.D. thesis, Eindhoven University of Technology, The Netherlands (2005)
Watson, G.N.: An expansion related to Stirling’s formula, derived by the method of steepest descent. Q. J. Pure Appl. Math. 48, 1–18 (1920)
Whitt, W.: Heavy traffic limit theorems for the G/H *2 /n/m queue. Math. Oper. Res. 30, 1–27 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Janssen, A.J.E.M., van Leeuwaarden, J.S.H. & Zwart, B. Corrected asymptotics for a multi-server queue in the Halfin-Whitt regime. Queueing Syst 58, 261–301 (2008). https://doi.org/10.1007/s11134-008-9070-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-008-9070-0
Keywords
- M/D/s queue
- Halfin-Whitt scaling
- Gaussian random walk
- All-time maximum
- Riemann zeta function
- Lerch’s transcendent
- Spitzer’s identity
- Queues in heavy traffic
- Lambert W Function
- Corrected diffusion approximation