О новом подходе к оценке квантилей времени отклика системы с разделением и параллельным обслуживанием заявок
- Авторы: Горбунова А.В.1, Лебедев А.В.2
-
Учреждения:
- ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
- Московский государственный университет имени~М.В.~Ломоносова
- Выпуск: № 108 (2024)
- Страницы: 6-21
- Раздел: Системный анализ
- URL: https://journal-vniispk.ru/1819-2440/article/view/284351
- DOI: https://doi.org/10.25728/ubs.2024.108.1
- ID: 284351
Цитировать
Полный текст
Аннотация
Предлагается новый подход к оценке квантилей распределения времени отклика системы массового обслуживания с разделением и параллельным обслуживанием заявок, для обозначения которой в англоязычной литературе используется термин fork-join. Рассматривается классический вариант данной системы с пуассоновским входным потоком и экспоненциальными временами обслуживания на однородных приборах. Заявки при поступлении в систему мгновенно разделяются на фиксированное число подзаявок и отправляются на обслуживание в соответствующие подсистемы с накопителем неограниченной емкости и одним прибором. Заявка считается обслуженной после обслуживания всех ее компонентов. Данная система позволяет смоделировать множество реальных процессов, для которых с целью увеличения эффективности характерно разделение крупных задач на более мелкие составляющие, например, системы параллельных или распределенных вычислений. Сложность анализа систем заключается в наличии зависимости между временами пребывания подзаявок, что значительно затрудняет анализ всех показателей производительности таких систем. Основным вкладом статьи является подход к~определению квантилей распределения времени отклика, оценка которых является не менее ценной по сравнению с оценкой среднего значения времени отклика. При этом вычислению математического ожидания посвящено гораздо большее количество работ в данной области, что объясняется в том числе сложностью проведения подобного анализа даже для данной характеристики, а оценка квантилей представляется еще более трудоемкой задачей.
Об авторах
Анастасия Владимировна Горбунова
ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
Email: avgorbunova@list.ru
Москва
Алексей Викторович Лебедев
Московский государственный университет имени~М.В.~Ломоносова
Email: avlebed@yandex.ru
Москва
Список литературы
- 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.
- BACCELLI F., MAKOWSKI A.M. Queueing models forsystems with synchronization constraints // Proc. of the IEEE. –1989. – Vol. 77, No. 1. – P. 138–161.
- BARON O., KRASS D., SHERZER E., SENDEROVICH A.Can machines solve general queueing problems? // WinterSimulation Conference (WSC) – 2022. – P. 2830–2841.
- 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.
- 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.
- 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.
- GALLIEN J., WEIN L.M. A simple and effective componentprocurement policy for stochastic assembly Systems // QueueingSystems. – 2001. – Vol. 38. – P. 221–248.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- LEBEDEV A.V. On the Interrelation between DependenceCoefficients of Bivariate Extreme Value Copulas // MarkovProc. Relat. Fields. – 2019. – Vol. 25, No. 4. – P. 639–648.
- NELSEN R.B. An introduction to copulas. – Springer Science& Business Media, 2007. – 272 p.
- NELSON R., TANTAWI A.N. Approximate analysis offork/join synchronization in parallel queues // IEEE Trans.Comput. – 1988. – Vol. 37, No. 6. – P. 739–743.
- 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.
- 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.
- 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.
- 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.
Дополнительные файлы
