Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

Для цитирования:

Постнова О. С., Тананко И. Е., Рогачко Е. С. Вычисление временных характеристик ациклической сети массового обслуживания с делением и слиянием требований // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2026. Т. 26, вып. 3. С. 448-458. DOI: 10.18500/1816-9791-2026-26-3-448-458, EDN: XUBEEY

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
31.08.2026
Полный текст:
скачать
(downloads: 17)
Язык публикации: 
русский
Рубрика: 
Информатика
Тип статьи: 
Научная статья
УДК: 
519.872
DOI: 
10.18500/1816-9791-2026-26-3-448-458
EDN: 
XUBEEY

Вычисление временных характеристик ациклической сети массового обслуживания с делением и слиянием требований

Авторы: 
Постнова Оксана Сергеевна, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Тананко Игорь Евстафьевич, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Рогачко Екатерина Сергеевна, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Рассматривается открытая ациклическая сеть массового обслуживания с делением и слиянием требований. При поступлении требования из источника в сеть оно делится на заданное постоянное число родственных фрагментов. Фрагменты переходят между системами сети независимо и друг от друга, и от фрагментов других требований. Покидая сеть обслуживания, все фрагменты поступают в систему, называемую системой сборки, в которой производится сборка требований из родственных фрагментов. Предлагается метод вычисления математического ожидания длительности сборки требований из фрагментов и математического ожидания длительности пребывания требований в сети. Для случая так называемого равномерного распределения нагрузки в сети массового обслуживания описывается вычисление математического ожидания длительности пребывания требований в сети. Равномерное распределение нагрузки определяется одинаковыми длинами маршрутов фрагментов требований в сети обслуживания, равными вероятностями этих маршрутов, а также одинаковыми интенсивностями обслуживания в системах сети, пропорциональными числу родственных фрагментов требований. Представлено сравнение численных результатов, полученных в ходе вычислительных экспериментов с использованием аналитической и имитационной моделей сети массового обслуживания с делением и слиянием требований. Результаты данной работы могут использоваться для оценки временных характеристик функционирования многопроцессорных систем, систем облачных вычислений и других стохастических систем, моделируемых сетями массового обслуживания с делением и слиянием требований.

Ключевые слова: 
сеть массового обслуживания с делением и слиянием требований
ациклическая сеть массового обслуживания
обслуживание фрагментов требований
длительность сборки требований
длительность пребывания требований в сети массового обслуживания
Список источников: 
  1. Thomasian A. Analysis of fork/join and related queueing systems // ACM Computing Surveys (CSUR). 2014. Vol. 47, iss. 2. Art. 17. P. 1–71. DOI: https://doi.org/10.1145/2628913
  2. Горбунова А. В., Зарядов И. С., Самуйлов К. Е., Сопин Э. С. Обзор систем параллельной обработки заявок // Вестник Российского университета дружбы народов. Серия: Математика. Информатика. Физика. 2017. Т. 25, № 4. С. 350–362. DOI: https://doi.org/10.22363/2312-9735-2017-25-4-350-362, EDN: ZVFIPZ
  3. Enganti P., Rosenkrantz T., Sun L., Wang Z., Che H., Jiang H. ForkMV: Mean-and-variance estimation of fork-join queuing networks for datacenter applications // IEEE International Conference on Networking, Architecture and Storage. 2022. P. 1–8. DOI: https://doi.org/10.1109/NAS55553.2022.9925531
  4. Flatto L., Hahn S. Two parallel queues created by arrivals with two demands I // SIAM Journal on Applied Mathematics. 1984. Vol. 44, iss. 5. P. 1041–1053. DOI: https://doi.org/10.1137/0144074
  5. Flatto L. Two parallel queues created by arrivals with two demands II // SIAM Journal on Applied Mathematics. 1985. Vol. 45, iss. 5. P. 861–878. DOI: https://doi.org/10.1137/0145052
  6. Ko S.-S., Serfozo R. F. Response times in M/M/s fork-join networks // Advances in Applied Probability. 2004. Vol. 36, iss. 3. P. 854–871. DOI: https://doi.org/10.1239/aap/1093962238
  7. Ko S.-S., Serfozo R. F. Sojourn times in G/M/1 fork-join networks // Naval Research Logistics. 2008. Vol. 55, iss. 5. P. 432–443. DOI: https://doi.org/10.1002/nav.20294
  8. Thomasian A., Tantawi A. N. Approximate solutions for M/G/1 fork/join synchronization // Proceedings of Winter Simulation Conference. 1994. P. 361–368. DOI: https://doi.org/10.1109/WSC.1994.717194
  9. Gorbunova A. V., Lebedev A. V. Correlations of the sojourn times of subtasks in fork-join queueing systems with M/M/1-type subsystems // Advances in Systems Science and Applications. 2024. Vol. 24, iss. 2. P. 1–18.
  10. Balsamo S., Donatiello L., van Dijk N. M. Bound performance models of heterogeneous parallel processing systems // IEEE Transactions on Parallel and Distributed Systems. 1998. Vol. 9, iss. 10. P. 1041–1056. DOI: https://doi.org/10.1109/71.730531
  11. Arns M. A tool for the analysis of hierarchical service-oriented extended open fork/join queueing networks // 1st International ICST Workshop on Tools for Solving Structured Markov Chains. 2010. P. 1–9. DOI: https://doi.org/10.4108/smctools.2007.1910
  12. Baccelli F., Makowski A. Simple computable bounds for the fork-join queue // Proceedings of Information Science and Systems Conference. 1985. P. 436–441.
  13. Schol D., Vlasiou M., Zwart B. Extreme values for the waiting time in large fork-join queues // Queueing Systems. 2025. Vol. 109. Art. 9. DOI: https://doi.org/10.1007/s11134-025-09937-2
  14. Осипов О. А., Тананко И. Е. Сети массового обслуживания произвольной топологии с делением и слиянием требований: случай бесконечноприборных систем обслуживания // Вестник Тверского государственного университета. Серия: Прикладная математика. 2017. № 4. С. 43–58. DOI: https://doi.org/10.26456/vtpmk188, EDN: ZXRLIF
  15. Baynat B., Dallery Y. An approximation method for general closed queuing networks with fork-join mechanisms // Journal of the Operational Research Society. 2000. Vol. 51, iss. 2. P. 198–208. DOI: https://doi.org/10.1057/palgrave.jors.2600885
  16. Baccelli F., Massey W., Towsley D. Acyclic fork-join queuing networks // Journal of the ACM. 1989. Vol. 36, iss. 3. P. 615–642. DOI: https://doi.org/10.1145/65950.65957
  17. Tancrez J.-S., Chevalie P., Sema P. A tight bound on the throughput of queueing networks with blocking // Analytical and Stochastic Modeling Techniques and Applications (ASMTA 2013) / eds. A. Dudin, K. de Turck. Berlin ; Heidelberg : Springer, 2013. P. 396–415. (Lecture Notes in Computer Science, vol. 7984). DOI: https://doi.org/10.1007/978-3-642-39408-9_28
  18. Dallery Y., Towsley D., Liu Z. Properties of fork/join queueing networks with blocking under various operating mechanisms // IEEE Transactions on Robotics and Automation. 1997. Vol. 13, iss. 4. P. 503–518. DOI: https://doi.org/10.1109/70.611303
  19. Xia C. H., Liu Z., Towsley D., Lelarge M. Scalability of fork/join queueing networks with blocking // ACM SIGMETRICS Performance Evaluation Review. 2007. Vol. 35, iss. 1. P. 133–144. DOI: https://doi.org/10.1145/1269899.1254898
  20. Yannopoulos E., Alfa A. S. A simple and quick approximation algorithm for tandem, split and merge queueing networks with blocking // INFOR: Information Systems and Operational Research. 1994. Vol. 32, iss. 4. P. 288–308. DOI: https://doi.org/10.1080/03155986.1994.11732258
  21. Осипов О. А. Анализ RQ-сети массового обслуживания с делением и слиянием требований // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2018. № 43. С. 49–55. DOI: https://doi.org/10.17223/19988605/43/6, EDN: XQWQHJ
  22. Marin A., Rossi S., Sottana M. Dynamic resource allocation in fork-join queues // ACM Transactions on Modeling and Performance Evaluation of Computing Systems. 2020. Vol. 5, iss. 1. P. 1–28. DOI: https://doi.org/10.1145/3372376
  23. Özkan E. Control of fork-join processing networks with multiple job types and parallel shared resources // Mathematics of Operations Research. 2021. Vol. 47, iss. 2. P. 1310–1334. DOI: https://doi.org/10.1287/moor.2021.1170
  24. Постнова О. С., Тананко И. Е., Рогачко Е. С. Приближенный анализ длительности пребывания требований в сети массового обслуживания с делением и слиянием требований // Управление большими системами. 2025. № 115. С. 33–51. EDN: HVKWYL
  25. Вентцель Е. С., Овчаров Л. А. Теория вероятностей и ее инженерные приложения. Москва : Наука, 1988. 480 c.
  26. He Q.-M. Fundamentals of matrix-analytic methods. New York : Springer Science+Business Media, 2014. 363 p. DOI: https://doi.org/10.1007/978-1-4614-7330-5
  27. Embrechts P., Klüppelberg C., Mikosch T. Modelling extremal events for insurance and finance. Berlin ; Heidelberg : Springer-Verlag, 1997. 648 p. (Stochastic Modelling and Applied Probability (SMAP, vol. 33)). DOI: https://doi.org/10.1007/978-3-642-33483-2
  28. Свидетельство о государственной регистрации программы для ЭВМ № 2025660299 Российская Федерация. Имитационная модель сетей массового обслуживания с делением и слиянием требований : № 2025619213 : заявл. 22.04.2025 : опубл. 22.04.2025 / О. С. Постнова, И. Е. Тананко ; заявитель федеральное государственное бюджетное образовательное учреждение высшего образования «Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского». EDN: KQEPPO
Поступила в редакцию: 
06.05.2026
Принята к публикации: 
11.06.2026
Опубликована: 
31.08.2026
  • 39 просмотров