To Pool or Not to Pool: Queueing Design for Large-Scale Service Systems

References

• Amari SV, Misra RB (1997) Closed-form expressions for distribution of sum of exponential random variables. IEEE Trans. Reliability 46(4):519–522.Crossref, Google Scholar
• Aras AK, Chen X, Liu Y (2018) Many-server Gaussian limits for overloaded non-Markovian queues with customer abandonment. Queueing Systems 89(1–2):81–125.Crossref, Google Scholar
• Armony M, Roels G, Song H (2018) Pooling queues with strategic servers: The effects of customer ownership. Working paper, New York University, New York.Google Scholar
• Armony M, Israelit S, Mandelbaum A, Marmor YN, Tseytlin Y, Yom-Tov GB (2015) On patient flow in hospitals: A data-based queueing-science perspective. Stochastic Systems 5(1):146–194.Link, Google Scholar
• Avi-Itzhak B, Levy H (2004) On measuring fairness in queues. Adv. Appl. Probab. 36(3):919–936.Crossref, Google Scholar
• Avi-Itzhak B, Levy H, Raz D (2008) Quantifying fairness in queuing systems. Principles, approaches, and applicability. Probab. Engrg. Inform. Sci. 22(4):495–517.Crossref, Google Scholar
• Banerjee S, Mukherjee D (2019) Join-the-shortest queue diffusion limit in Halfin–Whitt regime: Tail asymptotics and scaling of extrema. Ann. Appl. Probab. 29(2):1262–1309.Crossref, Google Scholar
• Baron O, Milner J (2009) Staffing to maximize profit for call centers with alternate service-level agreements. Oper. Res. 57(3):685–700.Link, Google Scholar
• Billingsley P (1999) Convergence of Probability Measures, 2nd ed. (John Wiley & Sons, New York).Crossref, Google Scholar
• Braverman A (2020) Steady-state analysis of the join-the-shortest-queue model in the Halfin–Whitt regime. Math. Oper. Res. 45(3):1069–1103.Google Scholar
• Chen H, Ye HQ (2012) Asymptotic optimality of balanced routing. Oper. Res. 60(1):163–179.Link, Google Scholar
• Dai JG, He S, Tezcan T (2010) Many-server diffusion limits for G/Ph/n+GI queues. Ann. Appl. Probab. 20(5):1854–1890.Crossref, Google Scholar
• Ding Y, Park E, Nagarajan M, Grafstein E (2019) Patient prioritization in emergency department triage systems: An empirical study of Canadian Triage and Acuity Scale (CTAS). Manufacturing Service Oper. Management 21(4):723–741.Link, Google Scholar
• Eschenfeldt P, Gamarnik D (2018) Join the shortest queue with many servers. The heavy-traffic asymptotics. Math. Oper. Res. 43(3):867–886.Link, Google Scholar
• Foschini G, Salz J (1978) A basic dynamic routing problem and diffusion. IEEE Trans. Comm. 26(3):320–327.Crossref, Google Scholar
• Garnett O, Mandelbaum A, Reiman M (2002) Designing a call center with impatient customers. Manufacturing Service Oper. Management 4(3):208–227.Link, Google Scholar
• Gupta V, Walton N (2019) Load balancing in the nondegenerate slowdown regime. Oper. Res. 67(1):281–294.Link, Google Scholar
• Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3):567–588.Link, Google Scholar
• He S (2020) Diffusion approximation for efficiency-driven queues when customers are patient. Oper. Res. 68(4):1265–1284.Link, Google Scholar
• He S, Sim M, Zhang M (2019) Data-driven patient scheduling in emergency departments: A hybrid robust–stochastic approach. Management Sci. 65(9):4123–4140.Link, Google Scholar
• Huang J, Mandelbaum A, Zhang H, Zhang J (2017) Refined models for efficiency-driven queues with applications to delay announcements and staffing. Oper. Res. 65(5):1380–1397.Link, Google Scholar
• Jouini O, Dallery Y, Nait-Abdallah R (2008) Analysis of the impact of team-based organizations in call center management. Management Sci. 54(2):400–414.Link, Google Scholar
• Kang W, Ramanan K (2012) Asymptotic approximations for stationary distributions of many-server queues with abandonment. Ann. Appl. Probab. 22(2):477–521.Crossref, Google Scholar
• Kingman JFC (1962) The effect of queue discipline on waiting time variance. Proc. Cambridge Philos. Soc. 58(1):163–164.Crossref, Google Scholar
• Kleinrock L (1976) Computer Applications, Volume II: Queueing Systems (John Wiley & Sons, New York).Google Scholar
• Koole G (2013) Call Center Optimization (MG books, Amsterdam).Google Scholar
• Liu Y (2018) Staffing to stabilize the tail probability of delay in service systems with time-varying demand. Oper. Res. 66(2):514–534.Link, Google Scholar
• Liu Y, Whitt W (2012) The Gt/GI/st+GI many-server fluid queue. Queueing Systems 71(4):405–444.Crossref, Google Scholar
• Liu Y, Whitt W (2014) Many-server heavy-traffic limit for queues with time-varying parameters. Ann. Appl. Probab. 24(1):378–421.Crossref, Google Scholar
• Lu Y, Xie Q, Kliot G, Geller A, Larus JR, Greenberg A (2011) Join-idle-queue: A novel load balancing algorithm for dynamically scalable web services. Performance Evaluation 68(11):1056–1071.Crossref, Google Scholar
• Mandelbaum A, Reiman MI (1998) On pooling in queueing networks. Management Sci. 44(7):971–981.Link, Google Scholar
• Mandelbaum A, Zeltyn S (2009) Staffing many-server queues with impatient customers: Constraint satisfaction in call centers. Oper. Res. 57(5):1189–1205.Link, Google Scholar
• Mandelbaum A, Sakov A, Zeltyn S (2001) Empirical analysis of a call center. Working paper, Technion–Israel Institute of Technology, Haifa.Google Scholar
• Milner JM, Olsen TL (2008) Service-level agreements in call centers: Perils and prescriptions. Management Sci. 54(2):238–252.Link, Google Scholar
• Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans. Parallel Distributed Systems 12(10):1094–1104.Crossref, Google Scholar
• Mukherjee D, Borst SC, van Leeuwaarden JSH, Whiting PA (2016) Universality of load balancing schemes on the diffusion scale. J. Appl. Probab. 53(4):1111–1124.Crossref, Google Scholar
• Mukherjee D, Borst SC, van Leeuwaarden JSH, Whiting PA (2020) Asymptotic optimality of power-of-d load balancing in large-scale systems. Math. Oper. Res., ePub ahead of print January 20, https://doi.org/10.1287/moor.2019.1042.Link, Google Scholar
• Raz D, Avi-Itzhak B, Levy H (2005) Fair operation of multi-server and multi-queue systems. SIGMETRICS Performance Evaluation Rev. 33(1):382–383.Crossref, Google Scholar
• Raz D, Levy H, Avi-Itzhak B (2004) A resource-allocation queueing fairness measure. SIGMETRICS Performance Evaluation Rev. 32(1):130–141.Crossref, Google Scholar
• Reiman MI (1984) Some diffusion approximations with state space collapse. Baccelli F, Fayolle G, eds. Modelling and Performance Evaluation Methodology, Lecture Notes in Control and Information Sciences, Vol. 60 (Springer, Berlin), 209–240.Crossref, Google Scholar
• Rothkopf MH, Rech P (1987) Perspectives on queues: Combining queues is not always beneficial. Oper. Res. 35(6):906–909.Link, Google Scholar
• Shi P, Chou MC, Dai JG, Ding D, Sim J (2016) Models and insights for hospital inpatient operations: Time-dependent ED boarding time. Management Sci. 62(1):1–28.Link, Google Scholar
• Shunko M, Niederhoff J, Rosokha Y (2018) Humans are not machines: The behavioral impact of queueing design on service time. Management Sci. 64(1):453–473.Link, Google Scholar
• Smith DR, Whitt W (1981) Resource sharing for efficiency in traffic systems. Bell System Tech. J. 60(1):39–55.Crossref, Google Scholar
• Song H, Tucker AL, Murrell KL (2015) The diseconomies of queue pooling: An empirical investigation of emergency department length of stay. Management Sci. 61(12):3032–3053.Link, Google Scholar
• Stolyar AL (2015) Pull-based load distribution in large-scale heterogeneous service systems. Queueing Systems 80(4):341–361.Crossref, Google Scholar
• Sunar N, Tu Y, Ziya S (2018) Pooled versus dedicated queues when customers are delay-sensitive. Working paper, University of North Carolina at Chapel Hill, Chapel Hill.Google Scholar
• Wang J, Zhou YP (2018) Impact of queue configuration on service time: Evidence from a supermarket. Management Sci. 64(7):3055–3075.Link, Google Scholar
• Ward AR (2012) Asymptotic analysis of queueing systems with reneging: A survey of results for FIFO, single class models. Surveys Oper. Res. Management Sci. 17(1):1–14.Crossref, Google Scholar
• Weber RR (1978) On the optimal assignment of customers to parallel servers. J. Appl. Probab. 15(2):406–413.Crossref, Google Scholar
• Whitt W (1986) Deciding which queue to join: Some counterexamples. Oper. Res. 34(1):55–62.Link, Google Scholar
• Whitt W (1999) Partitioning customers into service groups. Management Sci. 45(11):1579–1592.Link, Google Scholar
• Whitt W (2004) Efficiency-driven heavy-traffic approximations for many-server queues with abandonments. Management Sci. 50(10):1449–1461.Link, Google Scholar
• Whitt W (2006) Fluid models for multiserver queues with abandonments. Oper. Res. 54(1):37–54.Link, Google Scholar
• Winston W (1977) Optimality of the shortest line discipline. J. Appl. Probab. 14(1):181–189.Crossref, Google Scholar
• Ying L, Srikant R, Kang X (2017) The power of slightly more than one sample in randomized load balancing. Math. Oper. Res. 42(3):692–722.Link, Google Scholar
• Zeltyn S, Mandelbaum A (2005) Call centers with impatient customers: Many-server asymptotics of the M/M/n+G queue. Queueing Systems 51(3–4):361–402.Crossref, Google Scholar
• Zhang H, Wang R (1989) Heavy traffic limit theorems for a queueing system in which customers join the shortest line. Adv. Appl. Probab. 21(2):451–469.Crossref, Google Scholar
• Zhang H, Hsu G-H, Wang R (1995) Heavy traffic limit theorems for a sequence of shortest queueing systems. Queueing Systems 21(1–2):217–238.Crossref, Google Scholar