Informatics and Applications

2025, Volume 19, Issue 4, pp 35-42

HEURISTIC ONLINE LOAD BALANCING IN TWO-PHASE TANDEM QUEUES WITH DELAYS

M. G. Konovalov
R. V. Razumchik

Abstract

A single flow of customers arrives to the two-phase tandem queueing system. The first phase is the infinite-server queue which models the individual customer's delay. The second phase consists of N identical single server infinite capacity queues running in parallel. Upon arrival of a customer, the dispatcher must immediately decide which queue of the second phase will serve it. The dispatcher has certain a priori static information about the system and the incoming flow but the dynamic information about the queues arrives with a random delay.
A heuristic server allocation procedure is proposed that utilizes delayed information and the dispatcher's own decision history The algorithm is based on a combination of two techniques commonly used in dispatching problems: reserving queues for customers of a certain size and preferentially selecting servers with the shortest queue. The proposed procedure can be easily implemented in practice and does not require hardware changes. Numerical results comparing the new procedure with the most commonly used algorithms are presented.

[+] References (22)

Konovalov, M. G., and R. V. Razumchik. 2024. O dispetcherizatsii v odnom klasse dvukhfaznykh sistem massovogo obsluzhivaniya [On one problem of load balancing in two-phase tandem queues]. Informatika i ee Primeneniya - Inform. Appl. 18(4):52-58. doi: 10.14357/19922264240407. EDN: KGCBFL.
Moiseev, A., and A. Nazarov. 2016. Tandem of infinite- server queues with Markovian arrival process. Comm. Com. Inf Sc. 601:323-333. doi: 10.1007/978-3-319-30843- 2_34.
Dudin, A., and A. Nazarov. 2017. On a tandem queue with retrials and losses and state dependent arrival, service and retrial rates. Int. J. Operational Research 29(2):170-182. doi: 10.1504/IJOR.2017.10004611.
Pankratova, E., S. Moiseeva, and M. Farkhadov. 2022. Infinite-server resource queueing systems with different types ofMarkov-modulated Poisson process and renewal arrivals. Mathematics 10:2962. 16 p. doi: 10.3390/ math10162962.
Fedorova, E., I. Lapatin, O. Lizyura, A. Moiseev, A. Nazarov, and S. Paul. 2023. Queueing system with two phases ofservice and service rate degradation. Axioms 12(2):104. 19 p. doi: 10.3390/axioms12020104.
Moiseev, A. N., M. Shklennik, and E. Polin. 2023. Infinite-server queueing tandem with Markovian arrival process and service depending on its state. Ann. Oper Res. 326(1):261-279. doi: 10.1007/s10479-023-05318-1.
Lipshutz, D. 2019. Open problem-load balancing using delayed information. Stochastic Systems 9(3):305-306. doi: 10.1287/stsy.2019.0045.
Mitzenmacher, M. 2000. How useful is old information? IEEET. Parall. Distr. 11(1):6-20.doi: 10.1109/71.824633.
Atar, R., and D. Lipshutz. 2021. Heavy traffic limits for join-the-shortest-estimated- queue policy using delayed information. Math. Oper. Res. 46(1):268-300. doi: 10.1287/moor.2020.1056.
Novitzky, S., J. Pender, R. H. Rand, and E. Wesson. 2019. Nonlinear dynamics in queueing theory: Determining the size of oscillations in queues with delay. SIAM J. Appl. Dyn. Syst. 18(1):279-311. doi: 10.1137/18M1170637.
Schaerlaeckens, E. M. 2021. JIQ load balancing with delays. Eindhoven, Netherlands: Eindhoven University of Technology. Bachelor Thesis. 37 p.
Beraldi, R., C. Canali, R. Lancellotti, and G. P. Mattia. 2022. On the impact of stale information on distributed online load balancing protocols for edge computing. Comput. Netw. 210(5):108935. 14 p. doi: 10.1016/j.comnet.2022.108935.
Tahir, A., K. Cui, and H. Koeppl. 2023. Learning mean- field control for delayed information load balancing in large queuing systems. 51st Conference (International) on Parallel Processing Proceedings. New York, NY: ACM. Art. 42. 11 p. doi: 10.1145/3545008.3545025.
Konovalov, M. G., and R.V. Razumchik. 2015. Obzor modeley i algoritmov razmeshcheniya zadaniy v sistemakh s parallel'nym obsluzhivaniem [Methods and algorithms for job scheduling in systems with parallel service: A survey]. Informatika i ee Primeneniya - Inform. Appl. 9(4):56-67. doi: 10.14357/1992264150406. EDN: VEABIF
Kielanski, G., T. Hellemans, and B. Van Houdt. 2023. Join-Up-To(m): Improved hyperscalable load balancing. Queueing Syst. 105(3-4):291-316. doi: 10.1007/s11134- 023-09897-5.
Yildiz, M., A. Rolich, and A. Baiocchi. 2025. "Two- stagification": Job dispatching in large-scale clusters via a two-stage architecture. 23rd Mediterranean Communication and Computer Networking Conference Proceedings. Piscataway, NJ: IEEE. Art. 11103543. 6 p. doi: 10.1109/ MedComNet65822.2025.11103543.
Doncel, J. 2020. Performance balancing size- interval routing policies. INFOR 58(4):635-651. doi: 10.1080/03155986.2020.1743039.
Los, D., and T. Sauerwald. 2023. Balanced allocations in batches: The tower of two choices. 35th ACM Symposium on Parallelism in Algorithms and Architectures Proceedings. New York, NY: ACM. 51-61. doi: 10.1145/3558481.3591088.
Wang, Y., and D. Down. 2014. On resource pooling in SITA-like parallel server systems. 26th Teletraffic Congress (International) Proceedings. Piscataway, NJ: IEEE. Art. 6932947. 9 p. doi: 10.1109/ITC.2014.6932947.
Anselmi, J. 2020. Combining size-based load balancing with round-robin for scalable low latency. IEEE T. Parall. Distr. 31(4):886-896. doi: 10.1109/TPDS.2019.2950621.
Konovalov, M. G. 2007. Metody adaptivnoy obrabotki informatsii i ikh prilozheniya [Methods of adaptive information processing and their applications]. Moscow: IPI RAN. 212 p.
Liu, L., and J. G.C. Templeton. 1995. Departures in GRXn/Gn/infinity. Queueing Syst. 19(4):399-419. doi: 10.1007/BF01151931.

[+] About this article