An ergodic control problem for many-server multiclass queueing systems with cross-trained servers. (English) Zbl 1382.93036

Summary: A Markovian queueing network is considered with \(d\) independent customer classes and \(d\) server pools in Halfin-Whitt regime. Class i customers has priority for service in pool \(i\) for \(i = 1, \ldots, d\), and may access some other pool if the pool has an idle server and all the servers in pool \(i\) are busy. We formulate an ergodic control problem where the running cost is given by a non-negative convex function with polynomial growth. We show that the limiting controlled diffusion is modelled by an action space which depends on the state variable. We provide a complete analysis for the limiting ergodic control problem and establish asymptotic convergence of the value functions for the queueing model.


93E20 Optimal stochastic control
90B22 Queues and service in operations research
60K25 Queueing theory (aspects of probability theory)
60H30 Applications of stochastic analysis (to PDEs, etc.)
35J60 Nonlinear elliptic equations
Full Text: DOI arXiv Euclid


[1] Aliprantis, CD., Border, KC. (2006)Infinite Dimensional Analysis: A Hitchhiker’s Guide, Third ed. (Springer, Berlin). · Zbl 1156.46001
[2] Arapostathis, A., Pang, G. (2016) Ergodic diffusion control of multiclass multi-pool networks in the Halfin-Whitt regime.Ann. Appl. Probab.26(5):3110-3153. · Zbl 1351.60120
[3] Arapostathis, A., Pang, G. (2017) Infinite horizon average optimality of theN-network queueing model in the Halfin-Whitt regime. Preprint arXiv:1602.03275.
[4] Arapostathis, A., Biswas, A., Pang, G. (2015) Ergodic control of multi-classM/M/N+Mqueues in the Halfin-Whitt regime.Ann. Appl. Probab.25(6):3511-3570. · Zbl 1330.60108
[5] Arapostathis, A., Borkar, VS., Ghosh, MK. (2012)Ergodic Control of Diffusion Processes.Encyclopedia of Mathematics and Its Applications, Vol. 143 (Cambridge University Press, UK, Cambridge).
[6] Armony, M. (2005) Dynamic routing in large-scale service systems with heterogeneous servers.Queueing Syst.51(3-4):287-329. · Zbl 1094.60058
[7] Atar, R. (2005) Scheduling control for queueing systems with many servers: Asymptotic optimality in heavy traffic.Ann. Appl. Probab.15(4):2606-2650. · Zbl 1098.60083
[8] Atar, R., Biswas, A. (2014) Control of the multiclassG/G/1 queue in the moderate deviation regime.Ann. Appl. Probab.24(5):2033-2069. · Zbl 1306.60131
[9] Atar, R., Giat, C., Shimkin, N. (2010) Thecμ/θrule for many-server queues with abandonment.Oper. Res.58(5):1427-1439. · Zbl 1233.90107
[10] Atar, R., Giat, C., Shimkin, N. (2011) On the asymptotic optimality of thecμ/θrule under ergodic cost.Queueing Syst.67(2):127-144. · Zbl 1217.90063
[11] Atar, R., Mandelbaum, A., Reiman, MI. (2004) Scheduling a multi class queue with many exponential servers: Asymptotic optimality in heavy traffic.Ann. Appl. Probab.14(3):1084-1134. · Zbl 1049.60079
[12] Atar, R., Mandelbaum, A., Shaikhet, G. (2009) Simplified control problems for multiclass many-server queueing systems.Math. Oper. Res.34(4):795-812. · Zbl 1213.60142
[13] Biswas, A. (2014) Risk-sensitive control for the multiclass many-server queues in the moderate deviation regime.Math. Oper. Res.39(3):908-929. · Zbl 1315.60097
[14] Biswas, A., Ishii, H., Saha, S., Wang, L. (2017) On viscosity solution of hjb equations with state constraints and reflection control.SIAM J. Control Optim.55(1):365-396. · Zbl 1354.93172
[15] Budhiraja, A., Ghosh, AP., Lee, C. (2011) Ergodic rate control problem for single class queueing networks.SIAM J. Control Optim.49(4):1570-1606. MR2817491 (2012e:60231). · Zbl 1226.93138
[16] Dai, JG., Tezcan, T. (2008) Optimal control of parallel server systems with many servers in heavy traffic.Queueing Syst.59(2):95-134. · Zbl 1167.90446
[17] Dai, JG., Tezcan, T. (2011) State space collapse in many-server diffusion limits of parallel server systems.Math. Oper. Res.36(2):271-320. · Zbl 1239.60084
[18] Gilbarg, D., Trudinger, NS. (1983)Elliptic Partial Differential Equations of Second Order.Grundlehren der Mathematischen Wissenschaften, Second ed., Vol. 224 (Springer, Berlin). · Zbl 0562.35001
[19] Gurvich, I., Whitt, W. (2009) Queue-and-idleness-ratio controls in many-server service systems.Math. Oper. Res.34(2):363-396. · Zbl 1213.60149
[20] Harrison, JM., Zeevi, A. (2004) Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime.Oper. Res.52(2):243-257. · Zbl 1165.90474
[21] Ichihara, N., Sheu, S-J. (2013) Large time behavior of solutions of Hamilton-Jacobi-Bellman equations with quadratic nonlinearity in gradients.SIAM J. Math. Anal.45(1):279-306. · Zbl 1264.35043
[22] Iravani, SMR., Kolfal, B., Oyen, MPV. (2007) Call-center labor cross-training: It’s a small world after all.Management Sci.53(7):1102-1112. · Zbl 1232.91581
[23] Kallenberg, O. (2002)Foundations of Modern Probability.Probability and Its Applications, Second ed. (Springer, New York).
[24] Kim, J., Ward, AR. (2013) Dynamic scheduling of aGI/GI/1 +GIqueue with multiple customer classes.Queueing Syst.75(2-4):339-384.
[25] Krantz, SG. (2001)Function Theory of Several Complex Variables(AMS Chelsea Publishing, Providence, RI). RI Reprint of the 1992 edition. MR1846625 (2002e:32001).
[26] Mandelbaum, A., Stolyar, AL. (2004) Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalizedcμ-rule.Oper. Res.52(6):836-855. · Zbl 1165.90402
[27] Pang, G., Talreja, R., Whitt, W. (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues.Probab. Surv.4:193-267. · Zbl 1189.60067
[28] Ramanan, K., Reiman, MI. (2003) Fluid and heavy traffic diffusion limits for a generalized processor sharing model.Ann. Appl. Probab.13(1):100-139. MR1951995 (2004b:60220). · Zbl 1016.60083
[29] Ramanan, K., Reiman, MI. (2008) The heavy traffic limit of an unbalanced generalized processor sharing model.Ann. Appl. Probab.18(1):22-58. MR2380890 (2009b:60287). · Zbl 1144.60056
[30] Sznajder, R., Filar, JA. (1992) Some comments on a theorem of Hardy and Littlewood.J. Optim. Theory Appl.75(1):201-208. MR1189274 (93i:90110). · Zbl 0795.90085
[31] van Mieghem, JA. (1995) Dynamic scheduling with convex delay costs: The generalizedcμrule.Ann. Appl. Probab.5(3):809-833. · Zbl 0843.90047
[32] Ward, AR., Armony, M. (2013) Blind fair routing in large-scale service systems with heterogeneous customers and servers.Oper. Res.61(1):228-243. MR3042753 · Zbl 1267.90042
[33] Yosida, K. (1980)Functional Analysis.Grundlehren der Mathematischen Wissenschaften, Sixth ed., Vol. 123 (Springer-Verlag, Berlin). · Zbl 0435.46002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.