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

Обложка

Цитировать

Полный текст

Аннотация

Предлагается новый подход к оценке квантилей распределения времени отклика системы массового обслуживания с разделением и параллельным обслуживанием заявок, для обозначения которой в англоязычной литературе используется термин fork-join. Рассматривается классический вариант данной системы с пуассоновским входным потоком и экспоненциальными временами обслуживания на однородных приборах. Заявки при поступлении в систему мгновенно разделяются на фиксированное число подзаявок и отправляются на обслуживание в соответствующие подсистемы с накопителем неограниченной емкости и одним прибором. Заявка считается обслуженной после обслуживания всех ее компонентов. Данная система позволяет смоделировать множество реальных процессов, для которых с целью увеличения эффективности характерно разделение крупных задач на более мелкие составляющие, например, системы параллельных или распределенных вычислений. Сложность анализа систем заключается в наличии зависимости между временами пребывания подзаявок, что значительно затрудняет анализ всех показателей производительности таких систем. Основным вкладом статьи является подход к~определению квантилей распределения времени отклика, оценка которых является не менее ценной по сравнению с оценкой среднего значения времени отклика. При этом вычислению математического ожидания посвящено гораздо большее количество работ в данной области, что объясняется в том числе сложностью проведения подобного анализа даже для данной характеристики, а оценка квантилей представляется еще более трудоемкой задачей.

Об авторах

Анастасия Владимировна Горбунова

ФГБУН Институт проблем управления им. В.А. Трапезникова РАН

Email: avgorbunova@list.ru
Москва

Алексей Викторович Лебедев

Московский государственный университет имени~М.В.~Ломоносова

Email: avlebed@yandex.ru
Москва

Список литературы

  1. ARMONY M., ISRAELIT S., MANDELBAUM A.,MARMOR Y.N. et al. Patient flow in hospitals: a data-based queueing-science perspective // Stochastic Systems. –2015. – Vol. 5, No. 1. – P. 146–194.
  2. BACCELLI F., MAKOWSKI A.M. Queueing models forsystems with synchronization constraints // Proc. of the IEEE. –1989. – Vol. 77, No. 1. – P. 138–161.
  3. BARON O., KRASS D., SHERZER E., SENDEROVICH A.Can machines solve general queueing problems? // WinterSimulation Conference (WSC) – 2022. – P. 2830–2841.
  4. CHOCRON E., COHEN I., FEIGIN P. Delay predictionfor managing multiclass service systems: An investigation ofqueueing theory and machine learning approaches // IEEETrans. on Engineering Management. – 2022. — P. 1–11.
  5. DIELEMAN A., BERKHOUT A., HEIDERGOTT B. A neuralnetwork approach to performance analysis of tandem lines:The value of analytical knowledge // Computers & OperationsResearch. – 2023. – Vol. 152. – P. 106–124.
  6. ENGANTI P., ROSENKRANTZ T., SUN L., WANG Z. et al.ForkMV: Mean-and-Variance Estimation of Fork-Join QueuingNetworks for Datacenter Applications // IEEE Int. Conf. onNetworking, Architecture and Storage (NAS). – 2022. – P. 1–8.
  7. GALLIEN J., WEIN L.M. A simple and effective componentprocurement policy for stochastic assembly Systems // QueueingSystems. – 2001. – Vol. 38. – P. 221–248.
  8. GORBUNOVA A.V., LEBEDEV A.V. Bivariate distributionsof maximum remaining service times in fork-join infinite-serverqueues // Probl. Inf. Transm. – 2020. –Vol. 56, No. 1. – P. 73–90. – DOI: https://doi.org/10.1134/S003294602001007X.
  9. GORBUNOVA A.V., LEBEDEV A.V. Nonlinearapproximation of characteristics of a fork–join queueingsystem with Pareto service as a model of parallel structureof data processing // Mathematics and Computers inSimulation. – 2023. – Vol. 214. – P. 409–428. – DOI:https://doi.org/10.1016/j.matcom.2023.07.029.
  10. GORBUNOVA A.V., LEBEDEV A.V. On estimating thecharacteristics of a fork-join queueing system with Poissoninput and exponential service times // Advances in SystemsScience and Applications. – 2023. – Vol. 23, No. 2. –P. 99–114. – DOI: https://doi.org/10.25728/assa.2023.23.2.1351.
  11. GORBUNOVA A.V., VISHNEVSKY V.M. Estimating theresponse time of a cloud computing system with the helpof neural networks // Advances in Systems Science andApplications. – 2020. – Vol. 20, No. 3. – P. 105–112.
  12. JIANG L., GIACHETTI R.E. A queueing network model toanalyze the impact of parallelization of care on patient cycletime // Health Care Management Science. – 2008. – Vol. 11. –P. 248–261.
  13. LEBEDEV A.V. Upper bound for the expected minimum ofdependent random variables with known Kendall’s tau // Theoryof Probability and Its Applications. – 2019. – Vol. 64, No. 3. –P. 465—473.
  14. LEBEDEV A.V. On the Interrelation between DependenceCoefficients of Bivariate Extreme Value Copulas // MarkovProc. Relat. Fields. – 2019. – Vol. 25, No. 4. – P. 639–648.
  15. NELSEN R.B. An introduction to copulas. – Springer Science& Business Media, 2007. – 272 p.
  16. NELSON R., TANTAWI A.N. Approximate analysis offork/join synchronization in parallel queues // IEEE Trans.Comput. – 1988. – Vol. 37, No. 6. – P. 739–743.
  17. NGUYEN M., ALESAWI S., LI S., CHE S. et al. Ablack-box fork-join latency prediction model for data-intensiveapplications // IEEE Trans. on Parallel and DistributedSystems. – 2020. – Vol. 31, No. 9. – P. 1983–2000.
  18. QIU ZH., PEREZ J.F., HARRISON P.G. Beyond the meanin fork-join queues: Efficient approximation for response-timetails // Performance Evaluation. – 2015. – Vol. 91. – P. 99–116.
  19. VISHNEVSKY V.M., GORBUNOVA A.V. Application ofmachine learning methods to solving problems of queuingtheory // Communications in Computer and InformationScience. – 2022. – Vol. 1605. – P. 304–316. – DOI:https://doi.org/10.1007/978-3-031-09331-9_24.
  20. SCHOL D., VLASIOU M., ZWART B. Large fork-joinqueues with nearly deterministic arrival and service times //Mathematics of Operations Research. – 2022. – Vol. 47, No. 2. –P. 1335–1364. – DOI: https://doi.org/10.1287/moor.2021.1171.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать


Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-NonCommercial 4.0 International License.

Согласие на обработку персональных данных

 

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