Optimal resource allocation in networks of general single-server finite queues
DOI:
https://doi.org/10.5753/jbcs.2026.5178Keywords:
Multi-objective optimization, Particle swarm optimization, Buffer allocation, Service rate allocation, Queueing networksAbstract
This study simultaneously considers minimizing the total buffer allocation and the overall service rates in the network while maximizing its throughput. Some algorithms have already been proposed in the literature, but the discussion of efficient alternatives is relevant. We develop a novel approach to multi-objective particle swarm optimization (MO-PSO). We apply this approach to an acyclic, general single-server finite queueing network to optimize throughput. This algorithm was specifically tailored to address the problem, which involves mixed-integer variables and constraints that depend on the current solution, since service rates cannot fall below arrival rates. The proposed approach simultaneously decreases the total buffer allocation and the overall service rate. Consequently, our method yields a suboptimal Pareto set for these conflicting objectives. We conducted a computational and experimental study to verify the effectiveness of the proposed approach and to compare it with previously proposed solutions. The insights gained can enhance the design of queue networks.
Downloads
References
Almehdawe, E., Jewkes, B., and He, Q.-M. (2019). Optimization in a two-stage multi-server service system with customer priorities. Journal of the Operational Research Society, 70(2):326-337. DOI: 10.1080/01605682.2018.1438762.
Coello Coello, C. A. and Lechuga, M. S. (2002). MOPSO: A proposal for multiple objective particle swarm optimization. In Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No.02TH8600), volume 2, pages 1051-1056. DOI: 10.1109/CEC.2002.1004388.
Cruz, F. R. B. (2009). Optimizing the throughput, service rate, and buffer allocation in finite queueing networks. Electronic Notes in Discrete Mathematics, 35:163-168. LAGOS'09 - V Latin-American Algorithms, Graphs and Optimization Symposium. DOI: 10.1016/j.endm.2009.11.028.
Cruz, F. R. B., Duarte, A. R., and Souza, G. L. (2018). Multi-objective performance improvements of general finite single-server queueing networks. Journal of Heuristics, 24(5):757-781. DOI: 10.1007/s10732-018-9379-8.
Cruz, F. R. B., Duarte, A. R., and van Woensel, T. (2008). Buffer allocation in general single-server queueing networks. Computers & Operations Research, 35(11):3581-3598. DOI: 10.1016/j.cor.2007.03.004.
Cruz, F. R. B., Kendall, G., While, L., Duarte, A. R., and Brito, N. C. L. (2012). Throughput maximization of queueing networks with simultaneous minimization of service rates and buffers. Mathematical Problems in Engineering, 2012(Article ID 692593):19 pages. DOI: 10.1155/2012/692593.
Cruz, F. R. B., van Woensel, T., and MacGregor Smith, J. (2010). Buffer and throughput trade-offs in M/G/1/K queueing networks: A bi-criteria approach. International Journal of Production Economics, 125(2):224-234. DOI: 10.1016/j.ijpe.2010.02.017.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182-197. DOI: 10.1109/4235.996017.
Duarte, A. R. (2024). The server allocation problem for Markovian queueing networks. International Journal of Services and Operations Management, 48(2):256-271. DOI: 10.1504/IJSOM.2024.138931.
Fan, Z., Wang, T., Cheng, Z., Li, G., and Gu, F. (2017). An improved multiobjective particle swarm optimization algorithm using minimum distance of point to line. Shock and Vibration, 2017:1-16. DOI: 10.1155/2017/8204867.
Gross, D., Shortle, J. F., Thompson, J. M., and Harris, C. M. (2009). Fundamentals of queueing theory. Wiley - Interscience, New York, NY, fourth edition. DOI: 10.1002/9781119453765.
Hernández-Vázquez, J. O., Hernández-González, S., Jiménez-García, J. A., Hernández-Ripalda, M. D., and Hernández-Vázquez, J. I. (2019). Enfoque híbrido metaheurístico AG-RS para el problema de asignación del buffer que minimiza el inventario en proceso en líneas de producción abiertas en serie. Revista Iberoamericana de Automática e Informática Industrial, 16(4):447-458. DOI: 10.4995/riai.2019.10883.
Ingolfsson, A., Almehdawe, E., Pedram, A., and Tran, M. (2020). Comparison of fluid approximations for service systems with state-dependent service rates and return probabilities. European Journal of Operational Research, 283(2):562-575. DOI: 10.1016/j.ejor.2019.11.041.
Inzillo, V., De Rango, F., and Quintana, A. A. (2019). A self clocked fair queuing MAC approach limiting deafness and round robin issues in directional MANET. In 2019 Wireless Days (WD), pages 1-6. IEEE. DOI: 10.1109/WD.2019.8734263.
Kassoul, K., Cheikhrouhou, N., and Zufferey, N. (2022). Buffer allocation design for unreliable production lines using genetic algorithm and finite perturbation analysis. International Journal of Production Research, 60(10):3001-3017. DOI: 10.1080/00207543.2021.1909169.
Kennedy, J. and Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN'95 - International Conference on Neural Networks, volume 4, pages 1942-1948. DOI: 10.1109/ICNN.1995.488968.
Kerbache, L. and MacGregor Smith, J. (1987). The generalized expansion method for open finite queueing networks. European Journal of Operational Research, 32:448-461. DOI: 10.1016/S0377-2217(87)80012-7.
Kerbache, L. and MacGregor Smith, J. (1988). Asymptotic behavior of the expansion method for open finite queueing networks. Computers & Operations Research, 15(2):157-169. DOI: 10.1016/0305-0548(88)90008-1.
Khalid, R., Nawawi, M. K. M., Kawsar, L. A., Ghani, N. A., Kamil, A. A., and Mustafa, A. (2020). Optimal routing of pedestrian flow in a complex topological network with multiple entrances and exits. International Journal of Systems Science, 51(8):1325-1352. DOI: 10.1080/00207721.2020.1756524.
Kimura, T. (1996). A transform-free approximation for the finite capacity M/G/s queue. Operations Research, 44(6):984-988. DOI: 10.1287/opre.44.6.984.
Kose, S. Y. and Kilincci, O. (2020). A multi-objective hybrid evolutionary approach for buffer allocation in open serial production lines. Journal of Intelligent Manufacturing, 31(1):33-51. DOI: 10.1007/s10845-018-1435-6.
Liu, J., Hu, L., Xu, X., and Wu, J. (2021). A queuing network simulation optimization method for coordination control of passenger flow in urban rail transit stations. Neural Computing and Applications, 33(17):10935-10959. DOI: 10.1007/s00521-020-05580-5.
MacGregor Smith, J. (2003). M/G/c/k blocking probability models and system performance. Performance Evaluation, 52(4):237-267. DOI: 10.1016/S0166-5316(02)00190-6.
MacGregor Smith, J. (2004). Optimal design and performance modelling of M/G/1/k queueing systems. Mathematical and Computer Modelling, 39(9-10):1049-1081. DOI: 10.1016/S0895-7177(04)90534-1.
MacGregor Smith, J. (2015). Optimal workload allocation in closed queueing networks with state dependent queues. Annals of Operations Research, 231(1):157-183. DOI: 10.1007/s10479-013-1418-0.
MacGregor Smith, J. (2018). Simultaneous buffer and service rate allocation in open finite queueing networks. IISE Transactions, 50(3):203-216. DOI: 10.1080/24725854.2017.1300359.
MacGregor Smith, J. and Cruz, F. R. B. (2005). The buffer allocation problem for general finite buffer queueing networks. IIE Transactions, 37(4):343-365. DOI: 10.1080/07408170590916986.
Martins, H. S. R., Cruz, F. R. B., Duarte, A. R., and Oliveira, F. L. P. (2019). Modeling and optimization of buffers and servers in finite queueing networks. OPSEARCH, 56(1):123-150. DOI: 10.1007/s12597-019-00362-7.
Pourjavad, E. and Almehdawe, E. (2022). Optimization of the technician routing and scheduling problem for a telecommunication industry. Annals of Operations Research, 315(1):371-395. DOI: 10.1007/s10479-022-04658-8.
Souza, G. L., Duarte, A. R., Moreira, G. J. P., and Cruz, F. R. B. (2020). A novel formulation for multi-objective optimization of general finite single-server queueing networks. In IEEE Congress on Evolutionary Computation (CEC), pages 1-8. DOI: 10.1109/CEC48606.2020.9185827.
Souza, G. L., Duarte, A. R., Moreira, G. J. P., and Cruz, F. R. B. (2023). Post-processing improvements in multi-objective optimization of general single-server finite queueing networks. IEEE Latin America Transactions, 21(3):381-388. DOI: 10.1109/TLA.2023.10068841.
Trivedi, V., Varshney, P., and Ramteke, M. (2020). A simplified multi-objective particle swarm optimization algorithm. Swarm Intelligence, 14(2):83-116. DOI: 10.1007/s11721-019-00170-1.
Xi, S., MacGregor Smith, J., Chen, Q., Mao, N., Zhang, H., and Yu, A. (2022). Simultaneous machine selection and buffer allocation in large unbalanced series-parallel production lines. International Journal of Production Research, 60(7):2103-2125. DOI: 10.1080/00207543.2021.1884306.
Zennaro, I., Finco, S., Aldrighetti, R., and Battini, D. (2022). Buffer size evaluation in a bottle plant production system: a comparison between different solving methods. International Journal of Services and Operations Management, 42(4):500-524. DOI: 10.1504/IJSOM.2022.124990.
Zhao, X., Jin, Y., Ji, H., Geng, J., Liang, X., and Jin, R. (2013). An improved mixed-integer multi-objective particle swarm optimization and its application in antenna array design. In 5th IEEE International Symposium on Microwave, Antenna, Propagation and EMC Technologies for Wireless Communications, pages 412-415. DOI: 10.1109/MAPE.2013.6689835.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Gabriel L. Souza, Anderson R. Duarte, Frederico R. B. Cruz, Gladston J. P. Moreira
This work is licensed under a Creative Commons Attribution 4.0 International License.
