Post-processing Improvements in Multi-objective Optimization of General Single-server Finite Queueing Networks
Keywords:
Queueing networks, Conflicting objectives, Buffer allocation, Particle swarm optimizationAbstract
An alternative mathematical programming formulation is considered for a mixed-integer optimization problem in queueing networks. The sum of the blocking probabilities of a general service time, single server, and the finite, acyclic queueing network is minimized, and so are the total buffer sizes and the overall service rates. A multi-objective genetic algorithm (MOGA) and a particle swarm optimization (MOPSO) algorithm are combined to solve this difficult stochastic problem. The derived algorithm produces a set of efficient solutions for multiple objectives in the objective function. The implementation of the optimization algorithms is dependent on the generalized expansion method (GEM), a classical tool used to evaluate the performance of finite queueing networks. We carried out a set of computational experiments to attest to the efficacy and efficiency of the proposed approach. In addition, we present a comparative analysis of the solutions before and after post-processing. Insights obtained from the study of complex queue networks may assist the planning of these types of queueing networks.
Downloads
References
J. MacGregor Smith and F. R. B. Cruz, “The buffer allocation problem for general finite buffer queueing networks,” IIE Transactions, vol. 37, no. 4, pp. 343–365, 2005.
G. L. Souza, A. R. Duarte, G. J. P. Moreira, and F. R. B. Cruz, “A novel formulation for multi-objective optimization of general finite single-server queueing networks,” in IEEE Congress on Evolutionary Computation (CEC), pp. 1–8, 2020.
F. R. B. Cruz, A. R. Duarte, and T. van Woensel, “Buffer allocation in general single-server queueing networks,” Computers & Operations Research, vol. 35, no. 11, pp. 3581–3598, 2008.
F. R. B. Cruz, A. R. Duarte, and G. L. Souza, “Multi-objective performance improvements of general finite single-server queueing networks,” Journal of Heuristics, vol. 24, no. 5, pp. 757–781, 2018.
S. Yelkenci Kose and O. Kilincci, “A multi-objective hybrid evolutionary approach for buffer allocation in open serial production lines,” Journal of Intelligent Manufacturing, vol. 31, no. 1, pp. 33–51, 2020.
I. Zennaro, S. Finco, R. Aldrighetti, and D. Battini, “Buffer size evaluation in a bottle plant production system: a comparison between different solving methods,” International Journal of Services and Operations Management, vol. 42, no. 4, pp. 500–524, 2022.
J. MacGregor Smith, “Simultaneous buffer and service rate allocation in open finite queueing networks,” IISE Transactions, vol. 50, no. 3, pp. 203–216, 2018.
J. O. Hernández-Vázquez, S. Hernández-González, J. A. Jiménez-García, M. D. Hernández-Ripalda, and J. I. Hernández-Vázquez, “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, vol. 16, no. 4, pp. 447–458, 2019.
J. MacGregor Smith, F. R. B. Cruz, and T. van Woensel, “Topological network design of general, finite, multi-server queueing networks,” European Journal of Operational Research, vol. 201, no. 2, pp. 427–441, 2010.
E. Almehdawe, B. Jewkes, and Q.-M. He, “Optimization in a two-stage multi-server service system with customer priorities,” Journal of the Operational Research Society, vol. 70, no. 2, pp. 326–337, 2019.
A. Ingolfsson, E. Almehdawe, A. Pedram, and M. Tran, “Comparison of fluid approximations for service systems with state-dependent service rates and return probabilities,” European Journal of Operational Research, vol. 283, no. 2, pp. 562–575, 2020.
F. R. B. Cruz, T. Van Woensel, J. MacGregor Smith, and K. Lieckens, “On the system optimum of traffic assignment in M/G/c/c state-dependent queueing networks,” European Journal of Operational Research, vol. 201, no. 1, pp. 183–193, 2010.
R. Khalid, M. K. M. Nawawi, L. A. Kawsar, N. A. Ghani, A. A. Kamil, and A. Mustafa, “Optimal routing of pedestrian flow in a complex topological network with multiple entrances and exits,” International Journal of Systems Science, vol. 51, no. 8, pp. 1325–1352, 2020.
J. Liu, L. Hu, X. Xu, and J. Wu, “A queuing network simulation optimization method for coordination control of passenger flow in urban rail transit stations,” Neural Computing and Applications, vol. 33, no. 17, pp. 10935–10959, 2021.
N. U. Ahmed and X. H. Ouyang, “Suboptimal RED feedback control for buffered TCP flow dynamics in computer network,” Mathematical Problems in Engineering, vol. 2007, no. Article ID 54683, p. 17 pages, 2007.
J. Chen, C. Hu, and Z. Ji, “An improved ARED algorithm for congestion control of network transmission,” Mathematical Problems in Engineering, vol. 2010, no. Article ID 329035, p. 17 pages, 2010.
V. Inzillo, F. De Rango, and A. A. Quintana, “A self clocked fair queuing MAC approach limiting deafness and round robin issues in directional MANET,” in 2019 Wireless Days (WD), pp. 1–6, IEEE, 2019.
E. Pourjavad and E. Almehdawe, “Optimization of the technician routing and scheduling problem for a telecommunication industry,” Annals of Operations Research, vol. 315, no. 1, pp. 371–395, 2022.
K. Chaudhuri, A. Kothari, R. Pendavingh, R. Swaminathan, R. Tarjan, and Y. Zhou, “Server allocation algorithms for tiered systems,” Algorithmica, vol. 48, no. 2, pp. 129–146, 2007.
D. A. Menascé, “QoS issues in web services,” IEEE Internet Computing, vol. 6, no. 6, pp. 72–75, 2002.
F. R. B. Cruz, G. Kendall, L. While, A. R. Duarte, and N. C. L. Brito, “Throughput maximization of queueing networks with simultaneous minimization of service rates and buffers,” Mathematical Problems in Engineering, vol. 2012, no. Article ID 692593, p. 19 pages, 2012.
K. Deb, Multi-objective optimisation using evolutionary algorithms. New York, NY: John Wiley & Sons, Inc., 2001.
C. A. Coello Coello, G. B. Lamont, D. A. Van Veldhuizen, et al., Evolutionary algorithms for solving multi-objective problems, vol. 5. Springer, 2007.
W. Leong and G. G. Yen, “PSO-based multiobjective optimization with dynamic population size and adaptive local archives,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 38, no. 5, pp. 1270–1293, 2008.
V. Hajipour and S. H. R. Pasandideh, “Proposing an adaptive particle swarm optimization for a novel bi-objective queuing facility location model,” Economic Computation and Economic Cybernetics Studies and Research, vol. 46, no. 3, pp. 223–240, 2012.
M. Sharafi and T. Y. ELMekkawy, “Multi-objective optimal design of hybrid renewable energy systems using PSO-simulation based approach,” Renewable Energy, vol. 68, pp. 67–79, 2014.
W. Deng, H. Zhao, X. Yang, J. Xiong, M. Sun, and B. Li, “Study on an improved adaptive PSO algorithm for solving multi-objective gate assignment,” Applied Soft Computing, vol. 59, pp. 288–302, 2017.
P. Azimi and A. Asadollahi, “Developing a new bi-objective functions model for a hierarchical location-allocation problem using the queuing theory and mathematical programming,” Journal of Optimization in Industrial Engineering, vol. 12, no. 2, pp. 149–154, 2019.
D. R. X. Oliveira, G. J. P. Moreira, A. R. Duarte, A. L. F. Cançado, and E. Luz, “Spatial cluster analysis using particle swarm optimization and dispersion function,” Communications in Statistics - Simulation and Computation, pp. 1–18, 2019.
J. MacGregor Smith, F. R. B. Cruz, and T. van Woensel, “Optimal server allocation in general, finite, multi-server queueing networks,” Applied Stochastic Models in Business & Industry, vol. 26, no. 6, pp. 705–736, 2010.
J. MacGregor Smith, “Optimal workload allocation in closed queueing networks with state dependent queues,” Annals of Operations Research, vol. 231, no. 1, pp. 157–183, 2015.
A. R. Duarte, “The server allocation problem for Markovian queueing networks,” International Journal of Services and Operations Management, vol. (to appear), pp. 1–16, 2022.
H. S. R. Martins, F. R. B. Cruz, A. R. Duarte, and F. L. P. Oliveira, “Modeling and optimization of buffers and servers in finite queueing networks,” OPSEARCH, vol. 56, no. 1, pp. 123–150, 2019.
L. Kerbache and J. MacGregor Smith, “Multi-objective routing within large scale facilities using open finite queueing networks,” European Journal of Operational Research, vol. 121, no. 1, pp. 105–123, 2000.
F. R. B. Cruz, “Optimizing the throughput, service rate, and buffer allocation in finite queueing networks,” Electronic Notes in Discrete Mathematics, vol. 35, pp. 163 – 168, 2009. LAGOS’09 - V Latin-American Algorithms, Graphs and Optimization Symposium.
T. van Woensel, R. Andriansyah, F. R. B. Cruz, J. MacGregor Smith, and L. Kerbache, “Allocation in general multi-server queueing networks,” International Transactions in Operational Research, vol. 17, no. 2, pp. 257–286, 2010.
T. van Woensel, R. Andriansyah, F. R. B. Cruz, J. MacGregor Smith, and L. Kerbache, “Buffer and server allocation in general multi-server queueing networks,” International Transactions in Operational Research, vol. 17, no. 2, pp. 257–286, 2010.
R. Andriansyah, T. van Woensel, F. R. B. Cruz, and L. Duczmal, “Performance optimization of open zero-buffer multi-server queueing networks,” Computers & Operations Research, vol. 37, no. 8, pp. 1472–1487, 2010.
F. R. B. Cruz, T. van Woensel, and J. MacGregor Smith, “Buffer and throughput trade-offs in M/G/1/K queueing networks: A bi-criteria approach,” International Journal of Production Economics, vol. 125, no. 2, pp. 224–234, 2010.
T. van Woensel and F. R. B. Cruz, “Optimal routing in general finite multi-server queueing networks,” PLoS ONE, vol. 9, p. e102075, July 2014.
J. MacGregor Smith, “Optimal design and performance modelling of M/G/1/k queueing systems,” Mathematical and Computer Modelling, vol. 39, no. 9-10, pp. 1049–1081, 2004.
T. Kimura, “A transform-free approximation for the finite capacity M/G/s queue,” Operations Research, vol. 44, no. 6, pp. 984–988, 1996.
J. MacGregor Smith, “M/G/c/k blocking probability models and system performance,” Performance Evaluation, vol. 52, no. 4, pp. 237–267, 2003.
D. Gross, J. F. Shortle, J. M. Thompson, and C. M. Harris, Fundamentals of queueing theory. New York, NY: Wiley - Interscience, 4th edition ed., 2009.
L. Kerbache and J. MacGregor Smith, “The generalized expansion method for open finite queueing networks,” European Journal of Operational Research, vol. 32, pp. 448–461, 1987.
J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings, IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948, 1995.
C. A. Coello Coello and M. S. Lechuga, “MOPSO: A proposal for multiple objective particle swarm optimization,” in Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No.02TH8600), vol. 2, pp. 1051–1056, 2002.
V. Trivedi, P. Varshney, and M. Ramteke, “A simplified multi-objective particle swarm optimization algorithm,” Swarm Intelligence, vol. 14, no. 2, pp. 83–116, 2020.
Z. Fan, T. Wang, Z. Cheng, G. Li, and F. Gu, “An improved multiobjective particle swarm optimization algorithm using minimum distance of point to line,” Shock and Vibration, vol. 2017, pp. 1–16, 2017.
C. Jia and H. Zhu, “An improved multiobjective particle swarm optimization based on culture algorithms,” Algorithms, vol. 10, no. 2, p. 46, 2017.
X. Zhao, Y. Jin, H. Ji, J. Geng, X. Liang, and R. Jin, “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, pp. 412–415, 2013.
S. Jiang, Y.-S. Ong, J. Zhang, and L. Feng, “Consistencies and contradictions of performance metrics in multiobjective optimization,” IEEE transactions on cybernetics, vol. 44, no. 12, pp. 2391–2404, 2014.
K. Deb, S. Agarwal, A. Pratap, and T. Meyarivan, “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II,” in International Conference on Parallel Problem Solving from Nature, pp. 849–858, Springer, 2000.
E. Zitzler and L. Thiele, “Multiobjective optimization using evolutionary algorithms—a comparative case study,” in International conference on parallel problem solving from nature, pp. 292–301, Springer, 1998.
