A novel method for generating the optimal routing matrix of queuing networks with batch service

封面

如何引用文章

全文:

详细

In this paper, we consider a large-scale open queuing network. The arrival process in the queueing network is Poissonian. Сustomer transitions between nodes are described by the routing matrix. Each node consists of a single server and an infinite waiting queue. Customers are served as a unique batch of a given size with exponentially distributed service time. After the completion of service, customers are routed between nodes one at a time, independently of each other. We assume that, at any node, the number of destinations is much larger than the batch size. We also assume that the transition probabilities of customers between nodes are comparable. In this paper, we propose a method for generating the optimal routing matrix that provides the minimum average sojourn times in each node. We also provide a condition for relative arrival rates, under which the queuing network topology is radial (star-shaped), and expressions for optimal input rates to nodes. Finally, examples of the optimal routing matrix for different values of the overall input rate and in case of link failures are presented.

作者简介

Nadezhda Sergeeva

Saratov State University

ORCID iD: 0000-0001-6125-7078
SPIN 代码: 3960-0429
Astrahanskaya str., 83, Saratov, Russia

Michele Pagano

University of Pisa

ORCID iD: 0000-0003-1706-4994
Scopus 作者 ID: 57200499634
ул. Дж. Карузо, 16

Igor Tananko

Saratov State University

ORCID iD: 0000-0001-8960-9709
SPIN 代码: 8132-3706
Scopus 作者 ID: 56636512100
Researcher ID: D-9834-2013
Astrahanskaya str., 83, Saratov, Russia

Elena Stankevich

Saratov State University

ORCID iD: 0000-0003-0630-4550
SPIN 代码: 4119-6338
Astrahanskaya str., 83, Saratov, Russia

参考

  1. Башарин Г. П., Бочаров П. П., Коган Я. А. Анализ очередей в вычислительных сетях: Теория и методы расчета. Москва : Наука, 1989. 334 с.
  2. Вишневский В. М. Теоретические основы проектирования компьютерных сетей. Москва : Техносфера, 2003. 506 с.
  3. Митрофанов Ю. И. Анализ сетей массового обслуживания. Саратов : Научная книга, 2005. 175 с.
  4. Рыков В. В. Управляемые системы массового обслуживания // Итоги науки и техники. Серия: Теория вероятностей. Математическая стататистика. Теория кибернетики. 1975. Вып. 12. C. 43–153.
  5. Papadimitriou C. H., Tsitsiklis J. N. The complexity of optimal queueing network control // Mathematics of Operations Research, 1999. Vol. 24, iss. 2. P. 293–305. https://doi.org/10.1287/moor.24.2.293
  6. Neely M. J. Stochastic network optimization with application to communication and queueing systems. Cham : Springer, 2010. 199 p. https://doi.org/10.2200/S00271ED1V01Y201006CNT007
  7. Neale J. J., Duenyas I. Control of a batch processing machine serving compatible job families // IIE Transactions. 2003. Vol. 35, iss. 8. P. 699–710. https://doi.org/10.1080/07408170304347
  8. Makis V. Optimal control of a batch service queueing system with bounded waiting time // Kybernetika. 1985. Vol. 21, iss. 4. P. 262–271.
  9. Grippa P., Schilcher U., Bettstetter C. On access control in cabin-based transport systems // IEEE Transactions on Intelligent Transportation Systems. 2019. Vol. 20, iss. 6. P. 2149–2156. https://doi.org/10.1109/TITS.2018.2864551
  10. Zeng Y., Xia C. H. Optimal bulking threshold of batch service queues // Journal of Applied Probability. 2017. Vol. 54, iss. 2. P. 409–423. https://doi.org/10.1017/jpr.2017.8
  11. Bountali O., Economou A. Equilibrium joining strategies in batch service queueing system // European Journal of Operational Research. 2017. Vol. 260, iss. 3. P. 1142–1151. https://doi.org/10.1016/j.ejor.2017.01.024
  12. Deb R. K., Serfozo R. F. Optimal Control of Batch Service Queues // Advances in Applied Probability. 1973. Vol. 5, iss. 2. P. 340–361. https://doi.org/10.2307/1426040
  13. Rabta B., Reiner G. Batch sizes optimisation by means of queueing network decomposition and genetic algorithm // International Journal of Production Research. 2012. Vol. 50, iss. 10. P. 2720–2731. https://doi.org/10.1080/00207543.2011.588618
  14. Mitici M., Goseling J., van Ommeren J.-K., Graaf M., Boucherie R. J. On a tandem queue with batch service and its applications in wireless sensor networks // Queueing Systems. 2017. Vol. 87. P. 81–93. https://doi.org/10.1007/s11134-017-9534-1
  15. Xia C. H., Michailidis G., Bambos N., Glynn P. W. Optimal control of parallel queues with batch service // Probability in the Engineering and Informational Sciences. 2002. Vol. 16, iss. 3. P. 289–307. https://doi.org/10.1017/S0269964802163029
  16. Yu A.-L., Zhang H.-Y., Chen Q.-X., Mao N., Xi Sh.-H. Buffer allocation in a flow shop with capacitated batch transports // Journal of the Operational Research Society. 2022. Vol. 73, iss. 4. P. 888–904. https://doi.org/10.1080/01605682.2020.1866957
  17. Hopp W. J., Spearman M. L., Chayet S., Donohue K. L., Gel E. S. Using an optimized queueing network model to support wafer fab design // IIE Transactions. 2002. Vol. 34, iss. 2. P. 119–130. https://doi.org/10.1080/07408170208928855
  18. Kar S., Rehrmann R., Mukhopadhyay A., Alt B., Ciucu F., Koeppl H., Binnig C., Rizk A. On the throughput optimization in large-scale batch-processing systems // Performance Evaluation. 2020. Vol. 144. Art. 102142. https://doi.org/10.1016/j.peva.2020.102142
  19. Stankevich E., Tananko I., Pagano M. Optimization of open queuing networks with batch services // Mathematics. 2022. Vol. 10, iss. 16. Art. 3027. https://doi.org/10.3390/math10163027
  20. Pagano M., Tananko I., Stankevich E. On the optimal input rate in queues with batch service // Axioms. 2023. Vol. 12, iss. 7. Art. 656. https://doi.org/10.3390/axioms12070656
  21. Станкевич Е. П., Тананко И. Е., Пагано М. Анализ системы массового обслуживания с групповым обслуживанием требований // Компьютерные науки и информационные технологии : материалы Междунар. науч. конф. (Саратов, 18–20 ноября 2021 г.) / под ред. В. А. Твердохлебова. Саратов : Научная книга, 2021. С. 148–151.

补充文件

附件文件
动作
1. JATS XML
下载


Creative Commons License
此作品已接受知识共享署名 4.0国际许可协议的许可

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

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») на элемент с текстом «Принять и продолжить».