Performance Bounds and Suboptimal Policies for Multi-Class Queue

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.

References

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, 2004, vol. 14, no. 3, pp. 1084-1134. DOI: 10.1214/105051604000000233
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, pp. 1127-1133.
3. Kebarighotbi A., Cassandras C.G. Optimal Scheduling of Parallel Queues with Stochastic Flow Models: The cmu-rule Revisited. IFAC Proceedings Volumes, 2011, no. 44, pp. 8223-8228.
4. Shanthikumar J., Yao D. Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling Control. Operations Research, 1992, vol. 40, no. 2, pp. 293-299. DOI: 10.1287/opre.40.3.S293
5. Meyn S., Tweedie R. Markov Chains and Stochastic Stability. London, Springer, 1993. DOI: 10.1007/978-1-4471-3267-7
6. Puterman M.L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. New Jersey, John Wiley and Sons, 2009.
7. Schweitzer P.J., Seidmann A. Generalized Polynomial Approximations in Markovian Decision Processes. Journal of Mathematical Analysis and Applications, 1985, vol. 110, pp. 568-582. DOI: 10.1016/0022-247X(85)90317-8
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, pp. 1710-1728. DOI: 10.1002/rnc.1665
9. Osipova N., Ayesta U., Avrachenkov K. Optimal Policy for Multi-Class Scheduling in a Single Server Queue. 21st International Teletraffic Congress, 2009, p. 10951139.
10. Jia Li, Zhang H.M. Bounding Queuing System Performance with Variational Theory. Transportation Research Procedia, 2015, no. 7, pp. 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, pp. 278-295. DOI: 10.1016/j.is.2015.03.010
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, pp. 12-26. DOI: 10.1016/j.simpat.2012.05.010
13. Casale G., Sansottera A., Cremonesi P. Compact Markov-Modulated Models for Multiclass Trace Fitting. European Journal of Operational Research, 2016, vol. 255, no. 3, pp. 822-833. DOI: 10.1016/j.ejor.2016.06.005
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, 2011, vol. 60, no. 7, pp. 524-529. DOI: 10.1016/j.sysconle.2011.04.010
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, pp. 823-839. DOI: 10.1016/j.apm.2017.01.044
16. Kleinrock L. Queueing Systems. Volume II: Computer Applications. New Jersey, John Wiley and Sons, 1976.
17. Ching-Tarng Hsieh, Lam S.S. Two Classes of Performance Bounds for Closed Queueing Networks. Performance Evaluation, 1987, vol. 7, no. 1, pp. 3-30. DOI: 10.1016/0166-5316(87)90054-X
18. Koukopoulos D., Mavronicolas M., Spirakis P. Performance and Stability Bounds for Dynamic Networks. Journal of Parallel and Distributed Computing, 2007, vol. 67, no. 4, pp. 386-399. DOI: 10.1016/j.jpdc.2006.11.005