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

 An ergodic control problem for many-server multiclass queueing systems with cross-trained servers
 Anup Biswas, Indian Institute of Science Education and Research-Pune

 Abstract 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, 35J60Keywords: 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
 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.

### References

[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