Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems open journal systems 

An ergodic control problem for many-server multiclass queueing systems with cross-trained servers

Anup Biswas, Indian Institute of Science Education and Research-Pune

A \(M/M/N+M\) 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.

AMS 2000 subject classifications: Primary 93E20; Secondary 60H30, 35J60

Keywords: Multi-class Markovian queues, reneging/abandonment, Halfin-Whitt (QED) regime, heavy-traffic, long time-average control, scheduling control, stable Markov optimal control, Hamilton-Jacobi-Bellman equation, asymptotic optimality

Creative Common LOGO

Full Text: PDF

Biswas, Anup, An ergodic control problem for many-server multiclass queueing systems with cross-trained servers, Stochastic Systems, 8, (2018), 1-46 (electronic). DOI: 10.1214/15-SSY209.


[1]     Aliprantis, C. D. and Border, K. C. (2006). Infinite dimensional analysis, Third ed. Springer, Berlin A hitchhiker’s guide. MR2378491 (2008m:46001)

[2]     Arapostathis, A., Biswas, A. and Pang, G. (2015). Ergodic control of multi-class M∕M∕N + M queues in the Halfin-Whitt regime. Ann. Appl. Probab. 25 3511–3570. 10.1214/14-AAP1081 MR3404643

[3]     Arapostathis, A., Borkar, V. S. and Ghosh, M. K. (2012). Ergodic control of diffusion processes. Encyclopedia of Mathematics and its Applications 143. Cambridge University Press, Cambridge. MR2884272

[4]     Arapostathis, A. and Pang, G. (2016). Ergodic diffusion control of multiclass multi-pool networks in the Halfin-Whitt regime. Ann. Appl. Probab. 26 3110–3153. 10.1214/16-AAP1171 MR3563203

[5]     Arapostathis, A. and Pang, G. (2017). Infinite Horizon Average Optimality of the N-network Queueing Model in the Halfin-Whitt Regime. Preprint.

[6]     Armony, M. (2005). Dynamic routing in large-scale service systems with heterogeneous servers. Queueing Syst. 51 287–329. 10.1007/s11134-005-3760-7 MR2189596

[7]     Atar, R. (2005). Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic. Ann. Appl. Probab. 15 2606–2650. MR2187306

[8]     Atar, R. and Biswas, A. (2014). Control of the multiclass G∕G∕1 queue in the moderate deviation regime. Ann. Appl. Probab. 24 2033–2069. 10.1214/13-AAP971 MR3226171

[9]     Atar, R., Giat, C. and Shimkin, N. (2010). The cμ∕θ rule for many-server queues with abandonment. Oper. Res. 58 1427–1439. MR2560545

[10]     Atar, R., Giat, C. and Shimkin, N. (2011). On the asymptotic optimality of the cμ∕θ rule under ergodic cost. Queueing Syst. 67 127–144. MR2771197

[11]     Atar, R., Mandelbaum, A. and Reiman, M. I. (2004). Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic. Ann. Appl. Probab. 14 1084–1134. MR2071417

[12]     Atar, R., Mandelbaum, A. and Shaikhet, G. (2009). Simplified control problems for multiclass many-server queueing systems. Math. Oper. Res. 34 795–812. 10.1287/moor.1090.0404 MR2573496

[13]     Biswas, A. (2014). Risk-sensitive control for the multiclass many-server queues in the moderate deviation regime. Math. Oper. Res. 39 908–929. 10.1287/moor.2013.0632 MR3247010

[14]     Biswas, A., Ishii, H., Saha, S. and Wang, L. (2017). On viscosity solution of HJB equations with state constraints and reflection control. SIAM J. Control Optim. 55 365–396. 10.1137/15M103830X MR3606413

[15]     Budhiraja, A., Ghosh, A. P. and Lee, C. (2011). Ergodic rate control problem for single class queueing networks. SIAM J. Control Optim. 49 1570–1606. 10.1137/09077463X MR2817491 (2012e:60231)

[16]     Dai, J. G. and Tezcan, T. (2008). Optimal control of parallel server systems with many servers in heavy traffic. Queueing Syst. 59 95–134. MR2430811

[17]     Dai, J. G. and Tezcan, T. (2011). State space collapse in many-server diffusion limits of parallel server systems. Math. Oper. Res. 36 271–320. 10.1287/moor.1110.0494 MR2828761

[18]     Gilbarg, D. and Trudinger, N. S. (1983). Elliptic partial differential equations of second order, second ed. Grundlehren der Mathematischen Wissenschaften 224. Springer-Verlag, Berlin. MR0737190

[19]     Gurvich, I. and Whitt, W. (2009). Queue-and-idleness-ratio controls in many-server service systems. Math. Oper. Res. 34 363–396. 10.1287/moor.1080.0366 MR2554064

[20]     Harrison, J. M. and Zeevi, A. (2004). Dynamic scheduling of a multiclass queue in the Halfin-Whitt heavy traffic regime. Oper. Res. 52 243–257. MR2066399

[21]     Ichihara, N. and Sheu, S.-J. (2013). Large time behavior of solutions of Hamilton-Jacobi-Bellman equations with quadratic nonlinearity in gradients. SIAM J. Math. Anal. 45 279–306. MR3032978

[22]     Iravani, S. M. R., Kolfal, B. and Oyen, M. P. V. (2007). Call-Center Labor Cross-Training: It’s a Small World after All. Management Science 53 1102–1112.

[23]     Kallenberg, O. (2002). Foundations of modern probability, second ed. Probability and its Applications (New York). Springer-Verlag, New York. MR1876169

[24]     Kim, J. and Ward, A. R. (2013). Dynamic scheduling of a GI∕GI∕1 + GI queue with multiple customer classes. Queueing Syst. 75 339–384. MR3110643

[25]     Krantz, S. G. (2001). Function theory of several complex variables. AMS Chelsea Publishing, Providence, RI Reprint of the 1992 edition. MR1846625 (2002e:32001)

[26]     Mandelbaum, A. and Stolyar, A. L. (2004). Scheduling flexible servers with convex delay costs: heavy-traffic optimality of the generalized -rule. Oper. Res. 52 836–855. MR2104141

[27]     Pang, G., Talreja, R. and Whitt, W. (2007). Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surv. 4 193–267. MR2368951

[28]     Ramanan, K. and Reiman, M. I. (2003). Fluid and heavy traffic diffusion limits for a generalized processor sharing model. Ann. Appl. Probab. 13 100–139. 10.1214/aoap/1042765664 MR1951995 (2004b:60220)

[29]     Ramanan, K. and Reiman, M. I. (2008). The heavy traffic limit of an unbalanced generalized processor sharing model. Ann. Appl. Probab. 18 22–58. 10.1214/07-AAP438 MR2380890 (2009b:60287)

[30]     Sznajder, R. and Filar, J. A. (1992). Some comments on a theorem of Hardy and Littlewood. J. Optim. Theory Appl. 75 201–208. 10.1007/BF00939913 MR1189274 (93i:90110)

[31]     van Mieghem, J. A. (1995). Dynamic scheduling with convex delay costs: the generalized rule. Ann. Appl. Probab. 5 809–833. MR1359830

[32]     Ward, A. R. and Armony, M. (2013). Blind fair routing in large-scale service systems with heterogeneous customers and servers. Oper. Res. 61 228–243. 10.1287/opre.1120.1129 MR3042753

[33]     Yosida, K. (1980). Functional analysis, sixth ed. Grundlehren der Mathematischen Wissenschaften 123. Springer-Verlag, Berlin. MR0617913

Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238