For citation:
Sergeeva N. V., Pagano M., Tananko I. E., Stankevich E. P. A novel method for generating the optimal routing matrix of queuing networks with batch service. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2025, vol. 25, iss. 1, pp. 128-139. DOI: 10.18500/1816-9791-2025-25-1-128-139, EDN: ULANGK
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.
- Basharin G. P., Bocharov P. P., Kogan Ya. A. Analiz ocheredey v vychislitel’nykh setyakh : Teoriya i metody rascheta [Analysis of queues in computer networks: Theory and calculation methods]. Moscow, Nauka, 1989. 334 p. (in Russian).
- Vishnevskiy V. M. Teoreticheskie osnovy proektirovaniya komp’yuternykh setey [Theoretical foundations of computer network design]. Moscow, Tekhnosfera, 2003. 506 p. (in Russian).
- Mitrofanov Yu. I. Analiz setey massovogo obsluzhivaniya [Analysis of queuing networks]. Saratov, Nauchnaya kniga, 2005. 175 p. (in Russian).
- Rykov V. V. Controlled queuing systems. Itogi Nauki i Tekhniki. Seriya: Teoriya Veroyatnostei. Matematicheskaya Statistika. Teoreticheskaya Kibernetika [Results of Science and Technology. Series: Probability Theory. Mathematical Statistics. Theoretical Cybernetics], 1975, iss. 12, pp. 43–153 (in Russian).
- Papadimitriou C. H., Tsitsiklis J. N. The complexity of optimal queueing network control. Mathematics of Operations Research, 1999, vol. 24, iss. 2, pp. 293–305. https://doi.org/10.1287/moor.24.2.293
- Neely M. J. Stochastic network optimization with application to communication and queueing systems. Springer Cham, 2010. 199 p. https://doi.org/10.2200/S00271ED1V01Y201006CNT007
- Neale J. J., Duenyas I. Control of a batch processing machine serving compatible job families. IIE Transactions, 2003, vol. 35, iss. 8, pp. 699–710. https://doi.org/10.1080/07408170304347
- Makis V. Optimal control of a batch service queueing system with bounded waiting time. Kybernetika, 1985, vol. 21, iss. 4, pp. 262–271.
- 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, pp. 2149–2156. https://doi.org/10.1109/TITS.2018.2864551
- Zeng Y., Xia C. H. Optimal bulking threshold of batch service queues. Journal of Applied Probability, 2017, vol. 54, iss. 2, pp. 409–423. https://doi.org/10.1017/jpr.2017.8
- Bountali O., Economou A. Equilibrium joining strategies in batch service queueing system. European Journal of Operational Research, 2017, vol. 260, iss. 3, pp. 1142–1151. https://doi.org/10.1016/j.ejor.2017.01.024
- Deb R. K., Serfozo R. F. Optimal control of batch service queues. Advances in Applied Probability, 1973, vol. 5, iss. 2, pp. 340–361. https://doi.org/10.2307/1426040
- 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, pp. 2720–2731. https://doi.org/10.1080/00207543.2011.588618
- 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, pp. 81–93. https://doi.org/10.1007/s11134-017-9534-1
- 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, pp. 289–307. https://doi.org/10.1017/S0269964802163029
- 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, pp. 888–904. https://doi.org/10.1080/01605682.2020.1866957
- 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, pp. 119–130. https://doi.org/10.1080/07408170208928855
- 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
- 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
- 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
- Stankevich E. P., Tananko I. E., Pagano M. Analysis of queueing system with batch service. In: Tverdokhlebov V. A. (ed.) Komp’yuternye nauki i informatsionnye tekhnologii [Computer Science and Information Technologies]: Proceedings of the International Scientific Conference. Saratov, November 18–20, 2021. Saratov, Nauchnaya kniga, 2021, pp. 148–151 (in Russian).
- 250 reads