Geodesic
Performance bounds and suboptimal policies for multi-class queue
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 12 (2019) no. 1, pp. 44-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, we consider a general class of a queuing system with multiple job types and flexible service facility. We use a stochastic control policy to determine the performance loss in multi-class M/M/1 queue. The considered system is originally a Markov decision processes (MDP). The author showed how to compute performance bounds for the stochastic control policy of MDP with an average cost criteria. In practice, many authors used heuristic control policies due to some hardness in computing and running mathematically optimal policies. The authors found bounds on performance in order to an optimal policy where the goal of this job is to compute the difference of optimality and a specific policy. In other words, this study shows that, the optimal bounds of the average queue length for any non-idling policies can be found by a factor of service rates.
Keywords: queueing system, multiple job classes, stochastic control policy. 
@article{VYURU_2019_12_1_a3,
     author = {A. Madankan},
     title = {Performance bounds and suboptimal policies for multi-class queue},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {44--54},
     year = {2019},
     volume = {12},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2019_12_1_a3/}
}
TY  - JOUR
AU  - A. Madankan
TI  - Performance bounds and suboptimal policies for multi-class queue
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2019
SP  - 44
EP  - 54
VL  - 12
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURU_2019_12_1_a3/
LA  - en
ID  - VYURU_2019_12_1_a3
ER  - 
%0 Journal Article
%A A. Madankan
%T Performance bounds and suboptimal policies for multi-class queue
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2019
%P 44-54
%V 12
%N 1
%U http://geodesic.mathdoc.fr/item/VYURU_2019_12_1_a3/
%G en
%F VYURU_2019_12_1_a3
A. Madankan. Performance bounds and suboptimal policies for multi-class queue. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 12 (2019) no. 1, pp. 44-54. http://geodesic.mathdoc.fr/item/VYURU_2019_12_1_a3/

[1] Atar R., Mandelbaum A., Reiman M. I., “Schesuling a Multi-Class Queue with Many Exponentioal Servers: Asymptotic Optimality in Heavy Traffic”, The Annals of Applied Probability, 14:3 (2004), 1084–1134 | DOI | MR | Zbl

[2] Regan K., Boutilier C., “Robust Policy Computation in Reward-Uncertain MDPs Using Nondominated Policies”, Twenty-Fourth AAAI Conference on Artificial Intelligence (Atlanta, July, 2010), 1127–1133

[3] Kebarighotbi A., Cassandras C. G., “Optimal Scheduling of Parallel Queues with Stochastic Flow Models: The $c\mu$-rule Revisited”, IFAC Proceedings Volumes, 44 (2011), 8223–8228 | DOI | MR

[4] Shanthikumar J., Yao D., “Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling Control”, Operations Research, 40:2 (1992), 293–299 | DOI | MR

[5] Meyn S., Tweedie R., Markov Chains and Stochastic Stability, Springer, London, 1993 | DOI | MR | Zbl

[6] Puterman M. L., Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley and Sons, New Jersey, 2009 | MR

[7] Schweitzer P. J., Seidmann A., “Generalized Polynomial Approximations in Markovian Decision Processes”, Journal of Mathematical Analysis and Applications, 110 (1985), 568–582 | DOI | MR | Zbl

[8] Yang Wang, Boyd S., “Performance Bounds and Sub-Optimal Policies for Linear Stochastic Control via LMIs”, International Journal of Robust and Nonlinear Control, 2011, no. 21, 1710–1728 | DOI | MR | Zbl

[9] Osipova N., Ayesta U., Avrachenkov K., “Optimal Policy for Multi-Class Scheduling in a Single Server Queue”, 21st International Teletraffic Congress (2009), 10951139

[10] Jia Li, Zhang H. M., “Bounding Queuing System Performance with Variational Theory”, Transportation Research Procedia, 2015, no. 7, 519–535

[11] Senderovich A., Weidlich M., Gal A., Mandelbaum A., “Queue Mining for Delay Prediction in Multi-Class Service Processes”, Information Systems, 2015, no. 53, 278–295 | DOI

[12] Huang Qing, Chakravarthy S. R., “Analytical and Simulation Modeling of a Multi-Server Queue with Markovian Arrivals and Priority Services”, Simulation Modelling Practice and Theory, 2012, no. 28, 12–26 | DOI

[13] Casale G., Sansottera A., Cremonesi P., “Compact Markov-Modulated Models for Multiclass Trace Fitting”, European Journal of Operational Research, 255:3 (2016), 822–833 | DOI | MR | Zbl

[14] Lefeber E., Lammer S., Rooda J. E., “Optimal Control of a Deterministic Multiclass Queuing System For Which Several Queues Can Be Served Simultaneously”, Systems and Control Letters, 60:7 (2011), 524–529 | DOI | MR | Zbl

[15] Walraevens J., Bruneel H., Fiems D., Wittevrongel S., “Delay Analysis of Multiclass Queues with Correlated Train Arrivals and a Hybrid Priority/Fifo Scheduling Discipline”, Applied Mathematical Modelling, 2017, no. 45, 823–839 | DOI | MR

[16] Kleinrock L., Queueing Systems, v. II, Computer Applications, John Wiley and Sons, New Jersey, 1976 | MR | Zbl

[17] Ching-Tarng Hsieh, Lam S. S., “Two Classes of Performance Bounds for Closed Queueing Networks”, Performance Evaluation, 7:1 (1987), 3–30 | DOI | MR | Zbl

[18] Koukopoulos D., Mavronicolas M., Spirakis P., “Performance and Stability Bounds for Dynamic Networks”, Journal of Parallel and Distributed Computing, 67:4 (2007), 386–399 | DOI | Zbl