Performance Bounds and Suboptimal Policies for Multi-Class Queue

В этой статье рассматривается общий класс системы массового обслуживания с несколькими типами заданий и гибкими возможностями обслуживания. Используется стохастическая стратегия управления для определения потери производительности в многоклассовой очереди M/M/1. Рассматриваемая система изначально представляет собой марковский процесс принятия решений. В работе показано, как рассчитать границы производительности для стратегии стохастического управления марковского процесса принятия решения с критериями средней стоимости. На практике многие исследователи использовали эвристические стратегии управления из-за некоторой сложности в вычислениях и использовании математически оптимальных стратегий. Цель данной работы заключается в расчете разницы между оптимальной и конкретной стратегий, а также в нахождении границы производительности для оптимальной стратегии. Другими словами, это исследование показывает, что оптимальные границы средней длины очереди для любых стратегий без простоя можно найти с помощью коэффициента скорости обслуживания.

Ключевые слова

система массового обслуживания; многоклассовые задачи; стратегия стохастического контроля.

Литература

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