Many-server queues with customer abandonment: A survey of diffusion and fluid approximations

Abstract

The performance of a call center is sensitive to customer abandonment. In this survey paper, we focus on G / GI / n + GI parallel-server queues that serve as a building block to model call center operations. Such a queue has a general arrival process (the G), independent and identically distributed (iid) service times with a general distribution (the first GI), and iid patience times with a general distribution (the +GI). Following the square-root safety staffing rule, this queue can be operated in the quality- and efficiency-driven (QED) regime, which is characterized by large customer volume, the waiting times being a fraction of the service times, only a small fraction of customers abandoning the system, and high server utilization. Operational efficiency is the central target in a system whose staffing costs dominate other expenses. If a moderate fraction of customer abandonment is allowed, such a system should be operated in an overloaded regime known as the efficiency-driven (ED) regime. We survey recent results on the many-server queues that are operated in the QED and ED regimes. These results include the performance insensitivity to patience time distributions and diffusion and fluid approximate models as practical tools for performance analysis.

Keywords

Heavy traffic / square-root safety staffing / quality- and efficiency-driven regime / efficiency-driven regime / piecewise OU process

References

[1] Aksin Z., Armony M., Mehrotra V.. The modern call center: a multidisciplinary perspective on operations management research. Production and Operations Management, 2007, 16: 665-688.

[2] Atar R., Giat C., Shimkin N.. The cµ/θ rule for many-server queues with abandonment. Operations Research, 2010, 58: 1427-1439.

[3] Atar R., Giat C., Shimkin N.. On the asymptotic optimality of the cµ/θ rule under ergodic cost. Queueing Systems, 2011, 67: 127-144.

[4] Baccelli F., Boyer P., Hébuterne G.. Single-server queues with impatient customers. Advances in Applied Probability, 1984, 16: 887-905.

[5] Bassamboo A., Harrison J. M., Zeevi A.. Dynamic routing and admission control in high-volume service systems: asymptotic analysis via multi-scale fluid limits. Queueing Systems, 2005, 51: 249-285.

[6] Bassamboo A., Harrison J. M., Zeevi A.. Design and control of a large call center: asymptotic analysis of an LP-based method. Operations Research, 2006, 54: 419-435.

[7] Bassamboo A., Randhawa R. S.. On the accuracy of fluid models for capacity sizing in queueing systems with impatient customers. Operations Research, 2010, 58: 1398-1413.

[8] Bhattacharya P.P., Ephremides A.. Stochastic monotonicity properties of multiserver queues with impatient customers. Journal of Applied Probability, 1991, 28: 673-682.

[9] Billingsley P.. Convergence of Probability Measures, 1999, 2nd ed. New York: Wiley.

[10] Boxma O.J., de Waal P.R.. Labetouille J., Roberts J.W.. Multiserver queues with impatient customers. The fundamental role of teletraffic in the evolution of telecommunications networks (Proc. ITC-14), 1994, Amsterdam: North-Holland 743-756.

[11] Brandt A., Brandt M.. On the M(n)/M (n)/ s queue with impatient calls. Performance Evaluation, 1999, 35: 1-18.

[12] Brandt A., Brandt M.. Asymptotic results and a Markovian approximation for the M(n)/M (n)/ s GI + system. Queueing Systems, 2002, 41: 73-94.

[13] Brockmeyer E., Halstrøm H.L., Jensen A.. The life and works of A.K. Erlang. Transactions of the Danish Academy of Technical Sciences, 1948, 1948: 1-277.

[14] Brown L., Gans N., Mandelbaum A., Sakov A., Shen H., Zeltyn S., Zhao L.. Statistical analysis of a telephone call center: a queueing-science perspective. Journal of the American Statistical Association, 2005, 100: 36-50.

[15] Browne S., Whitt W.. Dshalalow J.. Piecewise-linear diffusion processes. Advances in queueing, 1995, Boca Raton, FL: CRC Press 463-480.

[16] Cox D.R., Oakes D.. Analysis of Survival Data, 1984, London: Monographs on Statistics and Applied Probability, Chapman & Hall

[17] Dai J.G., He S.. Customer abandonment in many-server queues. Mathematics of Operations Research, 2010, 35: 347-362.

[18] Dai J.G., He S., Tezcan T.. Many-server diffusion limits for G/Ph/n + GI queues. Annals of Applied Probability, 2010, 20: 1854-1890.

[19] Dai J.G., Tezcan T.. Optimal control of parallel server systems with many servers in heavy traffic. Queueing Systems, 2008, 59: 95-134.

[20] Dieker A.B., Gao X.. Positive recurrence of piecewise Ornstein-Uhlenbeck processes and common quadratic Lyapunov functions, 2011, Atlanta, GA: School of Industrial and Systems Engineering, Georgia Institute of Technology

[21] Gans N., Koole G., Mandelbaum A.. Telephone call centers: tutorial, review, and research prospects. Manufacturing & Service Operations Management, 2003, 5: 79-141.

[22] Garnett O., Mandelbaum A., Reiman M.. Designing a call center with impatient customers. Manufacturing & Service Operations Management, 2002, 4: 208-227.

[23] Grassmann W.K.. Is the fact that the emperor wears no clothes a subject worthy of publication?. Interfaces, 1986, 16: 43-51.

[24] Grassmann W.K.. Finding the right number of servers in real-world queuing systems. Interfaces, 1988, 18: 94-104.

[25] Gross D., Harris C.M.. Fundamentals of Queueing Theory, 1985, New York: Wiley.

[26] Gurvich I., Whitt W.. Queue-and-idleness-ratio controls in many-server service systems. Mathematics of Operations Research, 2009, 34: 363-396.

[27] Haln S., Whitt W.. Heavy-traffic limits for queues with many exponential servers. Operations Research, 1981, 29: 567-588.

[28] Harrison J.M., Zeevi A.. Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime. Operations Research, 2004, 52: 243-257.

[29] He S., Dai J.G.. Many-server queues with customer abandonment: numerical analysis of their diffusion models, 2011, Atlanta, GA: School of Industrial and Systems Engineering, Georgia Institute of Technology

[30] Kang W., Ramanan K.. Fluid limits of many-server queues with reneging. Annals of Applied Probability, 2010, 20: 2204-2260.

[31] Kaspi H., Ramanan K.. Law of large numbers limits for many-server queues. Annals of Applied Probability, 2011, 21: 33-114.

[32] Koçağa Y.L., Ward A.R.. Admission control for a multi-server queue with abandonment. Queueing Systems, 2010, 65: 275-323.

[33] Kolesar P.. Comment on “Is the fact that the emperor wears no clothes a subject worthy of publication?”. Interfaces, 1986, 16: 50-5.

[34] Liu, Y. and Whitt, W. (2011). The G _t / GI / s _t + GI _t many-server fluid queue. Preprint

[35] Mandelbaum A., Momčilović P.. Queues with many servers and impatient customers. Mathematics of Operations Research, 2012, 37: 41-65.

[36] Mandelbaum A., Zeltyn S.. The impact of customers’ patience on delay and abandonment: some empirically-driven experiments with the M / M / n + G queue. OR Spectrum, 2004, 26: 377-411.

[37] Mandelbaum A., Zeltyn S.. Spath D., Fähnrich K.-P.. Service engineering in action: the Palm/Erlang-A queue with applications to call centers. Advances in services innovations, 2007, Berlin: Springer 17-45.

[38] Mandelbaum A., Zeltyn S.. Staffing many-server queues with impatient customers: constraint satisfaction in call centers. Operations Research, 2009, 57: 1189-1205.

[39] Neuts M.F.. Matrix-Geometric Solutions in Stochastic Models: An Algorithm Approach, 1981, Baltimore, MD: The John Hopkins University Press

[40] Newell G.F.. Approximate Stochastic Behavior of n-Server Service Systems with Large n, 1973, Berlin: Springer-Verlag.

[41] Newell, G.F. (1982). Applications of Queueing Theory. Chapman-Hall

[42] Palm C.. Etude des delais d’attente. Erisson Technics, 1937, 5: 37-56.

[43] Palm, C. (1946). Special issue of teletrafikteknik. Tekniska Meddelanden från Kungliga Telegrafstyrelsen, 4

[44] Puhalskii A.A., Reiman M.I.. The multiclass GI / PH / N queue in the Halfin-Whitt regime. Advances in Applied Probability, 2000, 32: 564-595.

[45] Reed J., Tezcan T.. Hazard rate scaling for the GI / M / n + GI queue, 2009, New York: Stern School of Business, New York University

[46] Reed J.E., Ward A.R.. Approximating the GI / GI / 1 + GI queue with a nonlinear drift diffusion: hazard rate scaling in heavy traffic. Mathematics of Operations Research, 2008, 33: 606-644.

[47] Stanford R.E.. Reneging phenomena in single channel queues. Mathematics of Operations Research, 1979, 4: 162-178.

[48] Talreja R., Whitt W.. Heavy-traffic limits for waiting times in many-server queues with abandonment. Annals of Applied Probability, 2009, 19: 2137-2175.

[49] Tezcan T., Dai J.G.. Dynamic control of N-systems with many servers: asymptotic optimality of a static priority policy in heavy traffic. Operations Research, 2010, 58: 94-110.

[50] Whitt W.. Understanding the efficiency of multi-server service systems. Management Science, 1992, 38: 708-723.

[51] Whitt W.. Eciency-driven heavy-traffic approximations for many-server queues with abandonments. Management Science, 2004, 50: 1449-1461.

[52] Whitt W.. Heavy-traffic limits for the G/H ₂ ^*/n/m queue. Mathematics of Operations Research, 2005, 30: 1-27.

[53] Whitt W.. Fluid models for multiserver queues with abandonments. Operations Research, 2006, 54: 37-54.

[54] Zeltyn S., Mandelbaum A.. Call centers with impatient customers: many-server asymptotics of the M / M / n + G + queue. Queueing Systems, 2005, 51: 361-402.

[55] Zhang J.. Fluid models of multi-server queues with abandonment, 2009, Hong Kong: Department of Industrial Engineering and Logistics Management, Hong Kong University of Science and Technology