Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T09:16:26.141Z Has data issue: false hasContentIssue false
  • English
  • Français

New perspectives on the Erlang-A queue

Part of: Sequential methods Special processes Operations research and management science

Published online by Cambridge University Press:  22 July 2019

Andrew Daw  and
Jamol Pender
Andrew Daw*
Affiliation:
Cornell University
Jamol Pender*
Affiliation:
Cornell University
*
*Postal address: School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853-3801, USA.
*Postal address: School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853-3801, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

The nonstationary Erlang-A queue is a fundamental queueing model that is used to describe the dynamic behavior of large-scale multiserver service systems that may experience customer abandonments, such as call centers, hospitals, and urban mobility systems. In this paper we develop novel approximations to all of its transient and steady state moments, the moment generating function, and the cumulant generating function. We also provide precise bounds for the difference of our approximations and the true model. More importantly, we show that our approximations have explicit stochastic representations as shifted Poisson random variables. Moreover, we are also able to show that our approximations and bounds also hold for nonstationary Erlang-B and Erlang-C queueing models under certain stability conditions.

Keywords

Multiserver queueabandonmentdynamical systemasymptoticstime-varying ratemoments, fluid limitErlang-A queuefunctional forward equationmoment generating function

MSC classification

Primary: 60K25: Queueing theory
Secondary: 90B22: Queues and service 62L20: Stochastic approximation
Type
Original Article
Information
Advances in Applied Probability , Volume 51 , Issue 1 , March 2019 , pp. 268 - 299
Copyright
© Applied Probability Trust 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baccelli, F. and Hebuterne, G. (1981). On queues with impatient customers. In Performance, ed. Kylstra, F. J., North-Holland, pp. 159–179.Google Scholar
Borst, S., Mandelbaum, A. and Reiman, M. I. (2004). Dimensioning large call centers. Operat. Res. 52, 17–34.CrossRefGoogle Scholar
Boxma, O. J. and de Waal, P. R. (1994). Multiserver queues with impatient customers. Teletraffic Sci. Eng. 1, 743–756.CrossRefGoogle Scholar
Braverman, A., Dai, J. G. and Feng, J. (2016). Stein’s method for steady-state diffusion approximations: an introduction through the Erlang-A and Erlang-C models. Stoch. Systems 6, 301–366.CrossRefGoogle Scholar
Brown, L. et al. (2005). Statistical analysis of a telephone call center: a queueing-science perspective. J. Amer. Statist. Assoc. 100, 36–50.CrossRefGoogle Scholar
Daw, A. and Pender, J. (2018). Queues driven by Hawkes processes. Stoch. Systems 8, 192–229.CrossRefGoogle Scholar
Dong, J., Feldman, P. and Yom-Tov, G. B. (2015). Service systems with slowdowns: potential failures and proposed solutions. Operat. Res. 63, 305–324.CrossRefGoogle Scholar
Eick, S. G., Massey, W. A. and Whitt, W. (1993). M t/G/∞ queues with sinusoidal arrival rates. Manag. Sci. 39, 241–252.CrossRefGoogle Scholar
Engblom, S. and Pender, J. (2014). Approximations for the moments of nonstationary and state dependent birth-death queues. Preprint. Available at https://arxiv.org/abs/1406.6164.Google Scholar
Feldman, Z., Mandelbaum, A., Massey, W. A. and Whitt, W. (2008). Staffing of time-varying queues to achieve time-stable performance. Manag. Sci. 54, 324–338.CrossRefGoogle Scholar
Ferragut, A. and Paganini, F. (2012). Content dynamics in P2P networks from queueing and fluid perspectives. In Proc. 24th Internat. Teletraffic Congress, IEEE, p. 11.Google Scholar
Fralix, B. H. (2013). On the time-dependent moments of Markovian queues with reneging. Queueing Systems 75, 149–168.CrossRefGoogle Scholar
Garnett, O., Mandelbaum, A. and Reiman, M. (2002). Designing a call center with impatient customers. Manufacturing Service Operat. Manag. 4, 208–227.CrossRefGoogle Scholar
Gurvich, I., Huang, J. and Mandelbaum, A. (2014). Excursion-based universal approximations for the Erlang-A queue in steady-state. Math. Operat. Res. 39, 325–373.CrossRefGoogle Scholar
Hale, J. K. and Verduyn Lunel, S. M. (2013). Introduction to Functional Differential Equations, Vol. 99. Springer.Google Scholar
Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Operat. Res. 29, 567–588.CrossRefGoogle Scholar
Hampshire, R. C. and Massey, W. A. (2010). Dynamic optimization with applications to dynamic rate queues. INFORMS Tutorials Operat. Res. 2010, 208–247.Google Scholar
Hampshire, R. C., Jennings, O. B. and Massey, W. A. (2009). A time-varying call center design via Lagrangian mechanics. Prob. Eng. Inf. Sci. 23, 231–259.CrossRefGoogle Scholar
Hampshire, R. C., Massey, W. A. and Wang, Q. (2009). Dynamic pricing to control loss systems with quality of service targets. Prob. Eng. Inf. Sci. 23, 357–383.CrossRefGoogle Scholar
Knessl, C. and van Leeuwaarden, J. S. H. (2015). Transient analysis of the Erlang-A model. Math. Meth. Operat. Res. 82, 143–173.CrossRefGoogle ScholarPubMed
Ko, Y. M. and Pender, J. (2017). Diffusion limits for the (MAP t/Ph t/∞)N queueing network. Operat. Res. Lett. 45, 248–253.CrossRefGoogle Scholar
Ko, Y. M. and Pender, J. (2018). Strong approximations for time-varying infinite-server queues with non-renewal arrival and service processes. Stoch. Models 34, 186–206.CrossRefGoogle Scholar
Koops, D. T., Boxma, O. J. and Mandjes, M. R. H. (2017). Networks of ⋅/G/∞ queues with shot-noise-driven arrival intensities. Queueing Systems 86, 301–325.CrossRefGoogle Scholar
Koops, D. T., Saxena, M., Boxma, O. J. and Mandjes, M. (2018). Infinite-server queues with Hawkes input. J. Appl. Prob. 55, 920–943.CrossRefGoogle Scholar
Mandelbaum, A. and Zeltyn, S. (2004). The impact of customers’ patience on delay and abandonment: Some empirically-driven experiments with the M/M/n+G queue. OR Spektrum 26, 377–411.CrossRefGoogle Scholar
Mandelbaum, A. and Zeltyn, S. (2007). Service engineering in action: The Palm/Erlang-A queue, with applications to call centers. In Advances in Services Innovations. Springer, Berlin, pp. 17–45.CrossRefGoogle Scholar
Mandelbaum, A., Massey, W. A. and Reiman, M. I. (1998). Strong approximations for Markovian service networks. Queueing Systems Theory Appl. 30, 149–201.CrossRefGoogle Scholar
Mandelbaum, A. et al. (2002). Queue lengths and waiting times for multiserver queues with abandonment and retrials. Telecommun. Systems 21, 149–171.CrossRefGoogle Scholar
Massey, W. A. (2002). The analysis of queues with time-varying rates for telecommunication models. Telecommun. Systems 21, 173–204.CrossRefGoogle Scholar
Massey, W. A. and Pender, J. (2013). Gaussian skewness approximation for dynamic rate multi-server queues with abandonment. Queueing Systems 75, 243–277.CrossRefGoogle Scholar
Massey, W. A. and Pender, J. (2018). Dynamic rate Erlang-A queues. Queueing Systems 89, 127–164.CrossRefGoogle Scholar
Matis, T. I. and Feldman, R. M. (2001). Transient analysis of state-dependent queueing networks via cumulant functions. J. Appl. Prob. 38, 841–859.CrossRefGoogle Scholar
Niyirora, J. and Pender, J. (2016). Optimal staffing in nonstationary service centers with constraints. Naval Res. Logistics 63, 615–630.CrossRefGoogle Scholar
Palm, C. (1953). Methods of judging the annoyance caused by congestion. Tele 4, 189–208.Google Scholar
Pender, J. (2014). Gram Charlier expansion for time varying multiserver queues with abandonment. SIAM J. Appl. Math. 74, 1238–1265.CrossRefGoogle Scholar
Pender, J. and Ko, Y. M. (2017). Approximations for the queue length distributions of time-varying many-server queues. INFORMS J. Computing 29, 688–704.CrossRefGoogle Scholar
Pender, J. and Phung-Duc, T. (2016). A law of large numbers for M/M/c/Delayoff-setup queues with nonstationary arrivals. In Lecture Notes in Computer Science, Springer, pp. 253–268.Google Scholar
Reed, J. E. and Ward, A. R. (2008). Approximating the GI/GI/1+GI queue with a nonlinear drift diffusion: Hazard rate scaling in heavy traffic. Math. Operat. Res. 33, 606–644.CrossRefGoogle Scholar
Shimkin, N. and Mandelbaum, A. (2004). Rational abandonment from tele-queues: nonlinear waiting costs with heterogeneous preferences. Queueing Systems 47, 117–146.CrossRefGoogle Scholar
Talreja, R. and Whitt, W. (2009). Heavy-traffic limits for waiting times in many-server queues with abandonment. Ann. Appl. Prob. 19, 2137–2175.CrossRefGoogle Scholar
van Leeuwaarden, J. S. H. and Knessl, C. (2012). Spectral gap of the Erlang A model in the Halfin-Whitt regime. Stoch. Systems 2, 149–207.CrossRefGoogle Scholar
Ward, A. R. and Glynn, P. W. (2003). A diffusion approximation for a Markovian queue with reneging. Queueing Systems 43, 103–128.CrossRefGoogle Scholar
Ward, A. R. and Glynn, P. W. (2005). A diffusion approximation for a GI/GI/1 queue with balking or reneging. Queueing Systems 50, 371–400.CrossRefGoogle Scholar
Whitt, W. (2006). Sensitivity of performance in the Erlang-A queueing model to changes in the model parameters. Operat. Res. 54, 247–260.CrossRefGoogle Scholar
Yom-Tov, G. B. and Mandelbaum, A. (2014). Erlang-R: A time-varying queue with reentrant customers, in support of healthcare staffing. Manufacturing Service Operat. Manag. 16, 283–299.CrossRefGoogle Scholar
Zeltyn, S. and Mandelbaum, A. (2005). Call centers with impatient customers: Many-server asymptotics of the M/M/n+ G queue. Queueing Systems 51, 361–402.Google Scholar
Zhang, B., Van Leeuwaarden, J. S. H. and Zwart, B. (2012). Staffing call centers with impatient customers: Refinements to many-server asymptotics. Operat. Res. 60, 461–474.CrossRefGoogle Scholar
Zohar, E., Mandelbaum, A. and Shimkin, N. (2002). Adaptive behavior of impatient customers in tele-queues: theory and empirical support. Manag. Sci. 48, 566–583.CrossRefGoogle Scholar
Pender, J. (2016). Sampling the functional kolmogorov forward equations for nonstationary queueing networks. INFORMS J. Computing 29.Google Scholar