×

Throughput maximization of queueing networks with simultaneous minimization of service rates and buffers. (English) Zbl 1264.90054

Summary: The throughput of an acyclic, general-service time queueing network was optimized, and the total number of buffers and the overall service rate was reduced. To satisfy these conflicting objectives, a multiobjective genetic algorithm was developed and employed. Thus, our method produced a set of efficient solutions for more than one objective in the objective function. A comprehensive set of computational experiments was conducted to determine the efficacy and efficiency of the proposed approach. Interesting insights obtained from the analysis of a complex network may assist practitioners in planning general-service queueing networks.

MSC:

90B22 Queues and service in operations research
90B10 Deterministic network models in operations research
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Li, E. Enginarlar, and S. M. Meerkov, “Conservation of filtering in manufacturing systems with unreliable machines and finished goods buffers,” Mathematical Problems in Engineering, vol. 2006, Article ID 27328, 12 pages, 2006. · Zbl 1200.91160
[2] A. B. Hu and S. M. Meerkov, “Lean buffering in serial production lines with Bernoullimachines,” Mathematical Problems in Engineering, vol. 2006, Article ID 17105, 24 pages, 2006. · Zbl 1200.91158
[3] A. M. A. Youssef and H. A. ElMaraghy, “Performance analysis of manufacturing systems composed of modular machines using the universal generating function,” Journal of Manufacturing Systems, vol. 27, no. 2, pp. 55-69, 2008.
[4] I. Dimitriou and C. Langaris, “A repairable queueing model with two-phase service, start-up times and retrial customers,” Computers and Operations Research, vol. 37, no. 7, pp. 1181-1190, 2010. · Zbl 1178.90090
[5] F. R. B. Cruz, F. S. Q. Alves, H. C. Yehia, L. A. C. Pedrosa, and L. Kerbache, “Upper bounds on performance measures of heterogeneous M/M/c queues,” Mathematical Problems in Engineering, vol. 2011, Article ID 702834, 18 pages, 2011. · Zbl 1235.90042
[6] J. H. Harris and S. G. Powell, “An algorithm for optimal buffer placement in reliable serial lines,” IIE Transactions, vol. 31, no. 4, pp. 287-302, 1999.
[7] R. Andriansyah, T. van Woensel, F. R. B. Cruz, and L. Duczmal, “Performance optimization of open zero-buffer multi-server queueing networks,” Computers and Operations Research, vol. 37, no. 8, pp. 1472-1487, 2010. · Zbl 1183.90109
[8] J. M. 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. · Zbl 1175.90114
[9] N. Koizumi, E. Kuno, and T. E. Smith, “Modeling patient flows using a queuing network with blocking,” Health Care Management Science, vol. 8, no. 1, pp. 49-60, 2005.
[10] A. M. de Bruin, A. C. van Rossum, M. C. Visser, and G. M. Koole, “Modeling the emergency cardiac in-patient flow: an application of queuing theory,” Health Care Management Science, vol. 10, no. 2, pp. 125-137, 2007.
[11] C. Osorio and M. Bierlaire, “An analytic finite capacity queueing network model capturing the propagation of congestion and blocking,” European Journal of Operational Research, vol. 196, no. 3, pp. 996-1007, 2009. · Zbl 1176.90129
[12] F. R. B. Cruz, J. M. Smith, and D. C. Queiroz, “Service and capacity allocation in M/G/c/c state-dependent queueing networks,” Computers and Operations Research, vol. 32, no. 6, pp. 1545-1563, 2005. · Zbl 1071.90014
[13] F. R. B. Cruz, T. van Woensel, J. M. 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. · Zbl 1177.90089
[14] 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, Article ID 54683, 17 pages, 2007. · Zbl 1169.68345
[15] J. Chen, C. Hu, and Z. Ji, “An improved ARED algorithm for congestion control of network transmission,” Mathematical Problems in Engineering, vol. 2010, Article ID 329035, 14 pages, 2010. · Zbl 1191.68096
[16] L. Tang, H.-S. Xi, J. Zhu, and B.-Q. Yin, “Modeling and optimization of m/g/1 -type queueing networks: an efficient sensitivity analysis approach,” Mathematical Problems in Engineering, vol. 2010, Article ID 130319, 16 pages, 2010. · Zbl 1195.90033
[17] G. M. Gontijo,, G. S. Atuncar, F. R. B. Cruz, and L. Kerbache, “Performance evaluation and dimensioning of GIX/M/c/N systems through kernel estimation,” Mathematical Problems in Engineering, vol. 2011, Article ID 348262, 20 pages, 2011. · Zbl 1235.90046
[18] 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. · Zbl 1124.68116
[19] D. A. Menascé, “QoS issues in web services,” IEEE Internet Computing, vol. 6, no. 6, pp. 72-75, 2002. · Zbl 05096759
[20] J. M. 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.
[21] D. G. Kendall, “Stochastic processes occurring in the theory of queues and their analysis by the method of imbedded Markov chains,” Annals Mathematical Statistics, vol. 24, pp. 338-354, 1953. · Zbl 0051.10505
[22] J. G. Shanthikumar and D. D. Yao, “Optimal server allocation in a systemofmulti-server stations,” Management Science, vol. 33, no. 9, pp. 1173-1180, 1987. · Zbl 0636.90034
[23] L. E. Meester and J. G. Shanthikumar, “Concavity of the throughput of tandem queueing systems with finite buffer storage space,” Advances in Applied Probability, vol. 22, no. 3, pp. 764-767, 1990. · Zbl 0713.60100
[24] 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. · Zbl 1268.05195
[25] F. R. B. Cruz, A. R. Duarte, and T. van Woensel, “Buffer allocation in general single-server queueing networks,” Computers and Operations Research, vol. 35, no. 11, pp. 3581-3598, 2008. · Zbl 1170.90361
[26] V. Chankong and Y. Y. Haimes, Multiobjective Decision Making: Theory and Methodology, Elsevier, Amsterdam, The Netherlands, 1983. · Zbl 0622.90002
[27] L. Kerbachea and J. M. Smith, “The generalized expansion method for open finite queueing networks,” European Journal of Operational Research, vol. 32, no. 3, pp. 448-461, 1987. · Zbl 0691.60088
[28] L. Kerbache and J. M. Smith, “Asymptotic behavior of the expansion method for open finite queueing networks,” Computers and Operations Research, vol. 15, no. 2, pp. 157-169, 1988. · Zbl 0662.60105
[29] L. Kerbache and J. M. 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. · Zbl 0971.90014
[30] E. G. Carrano, L. A. E. Soares, R. H. C. Takahashi, R. R. Saldanha, and O. M. Neto, “Electric distribution network multiobjective design using a problem-specific genetic algorithm,” IEEE Transactions on Power Delivery, vol. 21, no. 2, pp. 995-1005, 2006.
[31] J. M. 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. · Zbl 1112.90319
[32] T. Kimura, “A transform-free approximation for the finite capacity M/G/s queue,” Operations Research, vol. 44, no. 6, pp. 984-988, 1996. · Zbl 0879.90098
[33] J. M. Smith, “M/G/c/K blocking probability models and system performance,” Performance Evaluation, vol. 52, no. 4, pp. 237-267, 2003.
[34] D. Gross, J. F. Shortle, J. M. Thompson, and C. M. Harris, Fundamentals of Queueing Theory, Wiley-Interscience, New York, NY, USA, 4th edition, 2009. · Zbl 1151.60001
[35] J. Y. Cheah and J. M. Smith, “Generalized M/G/C/C state dependent queueing models and pedestrian traffic flows,” Queueing Systems, vol. 15, no. 1-4, pp. 365-386, 1994. · Zbl 0797.90028
[36] F. R. B. Cruz, P. C. Oliveira, and L. Duczmal, “State-dependent stochastic mobility model in mobile communication networks,” Simulation Modelling Practice and Theory, vol. 18, no. 3, pp. 348-365, 2010. · Zbl 05726095
[37] J. Labetoulle and G. Pujolle, “Isolation method in a network of queues,” IEEE Transactions on Software Engineering, vol. 6, no. 4, pp. 373-381, 1980. · Zbl 05341560
[38] K. Deb, Multi-Objective Optimisation Using Evolutionary Algorithms, Wiley, 2001. · Zbl 0970.90091
[39] C. A. Coello Coello, Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer, 2002. · Zbl 1130.90002
[40] F. T. Lin, “Solving the knapsack problem with imprecise weight coefficients using genetic algorithms,” European Journal of Operational Research, vol. 185, no. 1, pp. 133-145, 2008. · Zbl 1146.90483
[41] H. I. Calvete, C. Galé, and P. M. Mateo, “A new approach for solving linear bilevel problems using genetic algorithms,” European Journal of Operational Research, vol. 188, no. 1, pp. 14-28, 2008. · Zbl 1135.90023
[42] C. A. Coello Coello, “An updated survey of GA-based multiobjective optimization techniques,” in Proceedings of the ACM Computing Surveys, vol. 32, pp. 109-143, 2000.
[43] C. M. Fonseca and P. Fleming, “An overview of evolutionary algorithms in multiobjective optimization,” Evolutionary Computing, vol. 3, no. 1, pp. 1-16, 1995. · Zbl 05412786
[44] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002. · Zbl 05451853
[45] T. Bäck, D. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation, Institute of Physics Publishing and Oxford University Press, 1997. · Zbl 0883.68001
[46] X. B. Hu and E. Di Paolo, “An efficient Genetic Algorithm with uniform crossover for the multi-objective airport gate assignment problem,” in Proceedings of the IEEE Congress on Evolutionary Computation (CEC ’07), pp. 55-62, Singapore, September 2007.
[47] G. Sywerda, “Uniformcrossover in genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 2-9, Morgan Kaufmann Publishers, San Francisco, Calif, USA, 1989.
[48] K. Deb and R. B. Agrawal, “Simulated binary crossover for continuous search space,” Complex Systems, vol. 9, pp. 115-148, 1995. · Zbl 0843.68023
[49] K. Deb and H.-G. Beyer, “Self-adaptive genetic algorithms with simulated binary crossover,” Tech. Rep. CI-61/99, Department of Computer Science/XI, University of Dortmund, Dortmund, Germany, 1999.
[50] O. Rudenko and M. Schoenauer, “A steady performance stopping criterion for Pareto-based evolutionary algorithms,” in Proceedings of the 6th International Multi-Objective Programming and Goal Programming Conference, Hammamet, Tunisia, 2004.
[51] L. Martí, J. García, A. Berlanga, and J. M. Molina, “A cumulative evidential stopping criterion for multiobjective optimization evolutionary algorithms,” in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO ’07), pp. 2835-2842, ACM, New York, NY, USA, 2007.
[52] D. C. Montgomery, Design and Analysis of Experiments, John Wiley & Sons, New York, NY, USA, 6th edition, 2004.
[53] F. R. B. Cruz, T. van Woensel, and J. M. 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.
[54] R. Mathieu, L. Pittard, and G. Anandalingam, “Genetic algorithms based approach to bi-level linear programming,” Recherche Opérationnelle/Operations Research, vol. 28, no. 1, pp. 1-21, 1994. · Zbl 0857.90083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.