Investigation of Tandem Queuing Systems Using Machine Learning Methods

Capa

Citar

Texto integral

Resumo

This paper considers tandem queuing systems with limited buffer sizes in each phase. The system handles an incoming correlated MAP flow and the service time obeys a PH-distribution. Models of such systems and methods for their investigation are briefly reviewed from the historical perspective. According to the review, the problem statement presented below, the methods proposed for solving this problem, and the corresponding results are novel. An accurate algorithm for calculating the performance characteristics of low-dimensional tandem queuing systems is described, including an estimate of the algorithm’s complexity. An approach using both machine learning and simulation modeling is suggested for the investigation of high-dimensional tandem queuing systems. Numerical analysis results are provided to show the effectiveness of machine learning methods for estimating the performance of tandem queuing systems.

Sobre autores

V. Vishnevsky

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: vishn@inbox.ru
Moscow, Russia

A. Larionov

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: larioandr@gmail.com
Moscow, Russia

A. Mukhtarov

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: mukhtarov.amir.a@gmail.com
Moscow, Russia

A. Sokolov

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: aleksandr.sokolov@phystech.edu
Moscow, Russia

Bibliografia

  1. Khayyati, S., Tan, B. Supervised-Learning-Based Approximation Method for Multi-server Queueing Networks under Different Service Disciplines with Correlated Interarrival and Service Times // International Journal of Production Research. – 2022. – Vol. 60, no. 17. – P. 5176–5200. – DOI: https://doi.org/10.1080/00207543.2021.1951448.
  2. Kumar, B.K., Sankar, R., Krishnan, R.N., Rukmani, R. Performance Analysis of Multi-processor Two-Stage Tandem Call Center Retrial Queues with Non-Reliable Processors // Methodology and Computing in Applied Probability. – 2022. – Vol. 24, no. 1. – P. 95–142. – DOI: https://doi.org/10.1007/s11009-020-09842-6.
  3. Oblakova, A., Al Hanbali, A., Boucherie, R.J., et al. An Analytical Model for a Tandem of Two Traffic-Light Intersections under Semi-actuated and Fixed Control // Transportation Research Interdisciplinary Perspectives. – 2022. – Vol. 16, no. 3. – Art. no. 100715. – DOI: https://doi.org/10.1016/j.trip.2022.100715.
  4. Rovetto, C., Cruz, E., Nuñez, I., et al. Minimizing Intersection Waiting Time: Proposal of a Queue Network Model Using Kendall’s Notation in Panama City // Applied Sciences. – 2023. – Vol. 13, no. 18. – Art. no. 10030. – DOI: https://doi.org/3390/app131810030.
  5. Pershin, O.Y., Mukhtarov, A.A., Vishnevsky, V.M., Larionov, A.A. Optimal Placement of Base Stations in Integrated Design of Wireless Networks // Programming and Computer Software. – 2023. – Vol. 49, suppl. 2. – P. S82–S90. – DOI: https://doi.org/10.1134/S0361768823100055.
  6. Vishnevsky, V., Krishnamoorthy, A., Kozyrev, D., Larionov, A. Review of Methodology and Design of Broadband Wireless Networks with Linear Topology // Indian Journal of Pure and Applied Mathematics. – 2016. – Vol. 47, no. 2. – P. 329–342. – DOI: https://doi.org/10.1007/s13226-016-0190-7.
  7. Gnedenko, B.W., König, D. Handbuch der Bedienungstheorie II. – Berlin: De Gruyter, 1984. – 608 p. – DOI: https://doi.org/1515/9783112614747.
  8. Neuts, M.F. Two Queues in Series with a Finite, Intermediate Waitingroom // Journal of Applied Probability. – 1968. – Vol. 5, no. 1. – P. 123–142. – DOI: https://doi.org/10.2307/3212081.
  9. Dieleman, N.A., Berkhout, J., and Heidergott, B. A Neural Network Approach to Performance Analysis of Tandem Lines: The Value of Analytical Knowledge // Computers and Operations Research. – 2023. – Vol. 152, no. 3. – Art. no. 106124. – DOI: https://doi.org/10.1016/j.cor.2022.106124 .
  10. Dudin, S.A., Dudin, A.N., Dudina, O.S., Chakravarthy, S.R. Analysis of a Tandem Queuing System with Blocking and Group Service in the Second Node // International Journal of Systems Science: Operations and Logistics. – 2023. – Vol. 10, no. 1. – Art. no. 2235270. – DOI: https://doi.org/10.1080/23302674.2023.2235270.
  11. Dudin, S.A., Dudina, O.S., Dudin, A.N. Analysis of Tandem Queue with Multi-Server Stages and Group Service at the Second Stage // Axioms. – 2024. – Vol. 13, no. 4. – art. no. 214. – DOI: https://doi.org/10.3390/axioms13040214.
  12. Bocharov, P.P., Manzo, R., Pechinkin, A.V. Analysis of a Two-Phase Queueing System with a Markov Arrival Process and Losses // Journal of Mathematical Sciences. – 2005. – Vol. 131, no. 3. – Р. 5606–5613. – DOI: https://doi.org/10.1007/s10958-005-0432-4.
  13. Kim, C.S., Klimenok, V., Taramin, O. A Tandem Retrial Queueing System with Two Markovian Flows and Reservation of Channels // Computers and Operations Research. – 2010. – Vol. 37, no. 7. – P. 1238–1246. – DOI: https://doi.org/10.1016/j.cor.2009.03.030.
  14. Kim, C., Klimenok, V.I., Dudin, A.N. Priority Tandem Aueueing System with Retrials and Reservation of Channels as a Model of Call Center // Computers and Industrial Engineering. – 2016. – Vol. 96. – P. 61–71. – DOI: https://doi.org/10.1016/j.cie.2016.03.012.
  15. Klimenok, V., Breuer, L., Tsarenkov, G., Dudin, A. The BMAP/G/1/–>·/PH/1/M Tandem Queue with Losses // Performance Evaluation. – 2005. – Vol. 61, no. 1. – P. 17–40. – DOI: https://doi.org/10.1016/j.peva.2004.09.001.
  16. Lian, Z., Liu, L. A Tandem Network with MAP Inputs // Operations Research Letters. – 2008. – Vol. 36, no. 2. – P. 189–195. – DOI: https://doi.org/10.1016/j.orl.2007.04.004.
  17. Vishnevskii, V.M., Dudin, A.N. Queueing Systems with Correlated Arrival Flows and Their Applications to Modeling Telecommunication Networks // Automation and Remote Control. – 2017. – Vol. 78, no. 8. – P. 1361–1403. – DOI: https://doi.org/10.1134/S000511791708001X.
  18. Dudin, A.N., Klimenok, V.I., Vishnevsky, V.M. The Theory of Queuing Systems with Correlated Flows // Cham: Springer, 2020. – 410 p.
  19. Bruell, S.C., Balbo, G., Afshari, P.V. Mean Value Analysis of Mixed, Multiple Class BCMP Networks with Load Dependent Service Stations // Performance Evaluation. – 1984. – Vol. 4, iss. 4. – P. 241–260. – DOI: https://doi.org/10.1016/0166-5316(84)90010-5.
  20. Vishnevsky, V., Klimenok, V., Sokolov, A., Larionov, A. Performance Evaluation of the Priority Multi-server System MMAP/PH/M/N Using Machine Learning Mmethods // Mathematics. – 2021. – Vol. 9, no. 24. – Art. no. 3236. – DOI: https://doi.org/10.3390/math9243236.
  21. Klimenok, V., Dudin, A., Vishnevsky, V. On the Stationary Distribution of Tandem Queue Consisting of a Finite Number of Stations // Communications in Computer and Information Science. – 2012. – Vol. 291. – P. 383–392. – DOI: https://doi.org/10.1007/978-3-642-31217-5_40.
  22. Palomo, S., Pender, J. Learning the Tandem Network Lindley Recursion // Proceedings of 2021 Winter Simulation Conference (WSC). – Phoenix, 2021. – P. 1–12. –DOI: https://doi.org/10.1109/WSC52266.2021.9715530.
  23. Rabta, B. A Review of Decomposition Methods for Open Queueing Networks // Rapid Modelling for Increasing Competitiveness. Ed. by G. Reiner – London: Springer2009. – P. 25–42. – DOI: https://doi.org/10.1007/978-1-84882-748-6_3.
  24. Vishnevsky, V., Larionov, A., Roman, I., Semenova, O. Estimation of IEEE 802.11 DCF Access Performance in Wireless Networks with Linear Topology Using PH Service Time Approximations and MAP Input // Proceedings of 11th IEEE International Conference on Application of Information and Communication Technologies. – Moscow, 2017. – P. 1–5. –DOI: https://doi.org/10.1109/ICAICT.2017.8687247.
  25. Gorbunova, A.V., Vishnevsky, V.M., Larionov, A.A. Evaluation of the End-to-End Delay of a Multiphase Queuing System Using Artificial Neural Networks // Lecture Notes in Computer Science . – Cham: Springer, 2021. – Vol. 12563. – P 631–642. – DOI: https://doi.org/10.1007/978-3-030-66471-8_48.
  26. Kudou, T., Nii, S., Okuda, T. A Performance Evaluation of Tandem Queueing Systems by Machine Learning // Proceedings of 2022 IEEE International Conference on Consumer Electronics. – Taiwan, 2022. – P. 389–390. – DOI: https://doi.org/10.1109/ICCE-Taiwan55306.2022.9869030.
  27. Kudou, T., Okuda, T. A Time Series Analysis of Single Server Queueing Systems by Using Machine Learning // Proceedings of 2023 International Conference on Consumer Electronics. – Taiwan, 2023. – P. 327–328. – DOI: https://doi.org/10.1109/ICCE-Taiwan58799.2023.10226861.
  28. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. – М: Техносфера, 2003. – 512 с. [Vishnevsky, V.M. Theoretical foundations of computer network design. Technosphera, Moscow. – 2003. – 512 p. (In Russian)]
  29. Vishnevsky, V.M., Klimenok, V.I., Sokolov, A.M., Larionov, A.A. Investigation of the Fork–Join System with Markovian Arrival Process Arrivals and Phase-Type Service Time Distribution Using Machine Learning Methods // Mathematics. –2024. – Vol. 12, no. 5. – Art. no. 659. – DOI: https://doi.org/10.3390/math12050659.
  30. Efrosinin, D., Vishnevsky, V., Stepanova, N. Optimal Scheduling in General Multi-Queue System by Combining Simulation and Neural Network Techniques // Sensors. – 2023. – Vol. 23, no. 12. – Art. no. 5479. – DOI: https://doi.org/3390/s23125479.
  31. Telek, M., Heindl, A. Matching Moments For Acyclic Discrete And Continuous Phase-Type Distributions Of Second Order // International Journal of Simulation Systems, Science and Technology. – 2002. – Vol. 3, no. 3. – P. 47–57.
  32. Johnson, M.A., Taaffe, M.R. Matching Moments to Phase Distributions: Mixtures of Erlang Distributions of Common Order // Communications in Statistics. Stochastic Models. – 1989. – Vol. 5, no. 4. – P. 711–743. – DOI: https://doi.org/1080/15326348908807131.
  33. Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J. Classification and Regression Trees. – New York: Chapman and Hall, 1984. – 368 p. – DOI: https://doi.org/10.1201/
  34. Demidova, L.A., Usachev, P.O. Development and Approbation of the Improved CART Algorithm Version // Journal of Phy­sics: Conference Series. – 2020. – Vol. 1479. – Art. no. 012085. – DOI: https://doi.org/10.1088/1742-6596/1479/1/012085.
  35. Gordon, A.D., Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J. Classification and Regression Trees // Biometrics. – 1984. – Vol. 40, no. 3. – P. 874. – DOI: https://doi.org/10.2307/2530946.
  36. Loh, W.Y. Classification and Regression Trees // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. – 2011. – Vol. 1, no. 1. – P. 14–23. – DOI: https://doi.org/10.1002/widm.8.
  37. Friedman, J.H. Stochastic Gradient Boosting // Computational Statistics and Data Analysis. – 2002. – Vol. 38, no. 4. – P. 367–378. – DOI: https://doi.org/10.1016/S0167-9473(01)00065-2.
  38. Kingma, D.P., Ba, J.L. Adam: A Method for Stochastic Pptimization // arXiv:1412.6980. – 2014. – URL: http://arxiv.org/abs/1412.6980.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar


Creative Commons License
Este artigo é disponível sob a Licença Creative Commons Atribuição 4.0 Internacional.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».