Abstract
Optimizing the performance of general finite single-server acyclic queueing networks is a challenging problem and has been the subject of many studies. The version of the optimization problem treated here considers the minimization of the buffer areas and the service rates simultaneously with the maximization of the throughput. These are conflicting objectives, and the most appropriate methodology appears to be a multi-objective methodology. In fact, algorithms have previously been proposed, and the aim here is to show that the use of a mixed methodology can occasionally improve solutions without a significant increase in the computational costs. This paper shows that improvements in throughput can be achieved through a solution of a type of stochastic knapsack problem, which consists of redistributing the buffer spaces between the lines while preserving the overall capacity using a simulated annealing algorithm; that is, one objective is improved (the throughput) without worsening the other (the overall allocated capacity). A set of computational experiments are presented to demonstrate the effectiveness of the proposed approach. Additionally, some of the insights presented here may help scientists and practitioners in finite single-server queueing network planning.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Almeida, M.A.C., Cruz, F.R.B.: A note on Bayesian estimation of traffic intensity in single-server Markovian queues. Commun. Stati. Simul.Comput. 1–19 (2017a). https://doi.org/10.1080/03610918.2017.1353614 (in press)
Almeida, M.A.C., Cruz, F.R.B., Oliveira, F.L.P., de Souza G.: Bias correction for estimation of performance measures of a Markovian queue. Oper. Res. 1–20 (2017b) https://doi.org/10.1007/s12351-017-0351-4 (in press)
Alves, F.S.Q., Yehia, H.C., Pedrosa, L.A.C., Cruz, F.R.B., Kerbache, L.: Upper bounds on performance measures of heterogeneous \(M/M/c\) queues. Math. Probl. Eng. 2011, 18 (2011)
Bäck, T., Fogel, D., Michalewicz, Z. (eds.): Handbook of Evolutionary Computation. Institute of Physics Publishing and Oxford University Press, Oxford (1997)
Bertsimas, D., Tsitsiklis, J.: Simulated annealing. Stat. Sci. 8(1), 10–15 (1993)
Cerny, V.: Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J. Optim. Theory Appl. 45, 41–51 (1985)
Chaudhuri, K., Kothari, A., Pendavingh, R., Swaminathan, R., Tarjan, R., Zhou, Y.: Server allocation algorithms for tiered systems. Algorithmica 48(2), 129–146 (2007)
Cheah, J.Y., MacGregor Smith, J.: Generalized \(M/G/C/C\) state dependent queueing models and pedestrian traffic flows. Queueing Syst. 15(1), 365–386 (1994)
Chen, J., Hu, C., Ji, Z.: An improved ARED algorithm for congestion control of network transmission. Math. Probl. Eng. 2010, 14 (2010)
Cruz, F.R.B., MacGregor Smith, J., Queiroz, D.C.: Service and capacity allocation in \(M/G/C/C\) state dependent queueing networks. Comput. Oper. Res. 32(6), 1545–1563 (2005)
Cruz, F.R.B., Duarte, A.R., van Woensel, T.: Buffer allocation in general single-server queueing network. Comput. Oper. Res. 35(11), 3581–3598 (2008)
Cruz, F.R.B., van Woensel, T., MacGregor Smith, J., Lieckens, K.: On the system optimum of traffic assignment in \(M/G/c/c\) state-dependent queueing networks. Eur. J. Oper. Res. 201(1), 183–193 (2010)
Cruz, F.R.B., Kendall, G., While, L., Duarte, A.R., Brito, N.L.C.: Throughput maximization of queueing networks with simultaneous minimization of service rates and buffers. Math. Probl. Eng. 2012, 19 (2012)
Cruz, F.R.B., Quinino, R.C., Ho, L.L.: Bayesian estimation of traffic intensity based on queue length in a multi-server \(M/M/s\) queue. Commun. Stat. Simul. Comput. 46(9), 7319–7331 (2017)
de Bruin, A.M., van Rossum, A.C., Visser, M.C., Koole, G.M.: Modeling the emergency cardiac in-patient flow: an application of queuing theory. Health Care Manag. Sci. 10(2), 125–137 (2007)
Deb, K.: Multi-objective Optimisation using Evolutionary Algorithms. Wiley, New York (2001)
Deb, K., Agrawal, R.B.: Simulated binary crossover for continuous search space. Complex Syst. 9, 115–148 (1995)
Deb, K., Beyer, H.G.: Self-adaptive genetic algorithms with simulated binary crossover. Technical Report No. CI-61/99. Department of Computer Science/XI, University of Dortmund, Dortmund (1999)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Dijkstra, E.W.: A note on two problems in connection with graphs. Numer. Math. 1, 269–271 (1959)
Hajek, B.: Cooling schedules for optimal annealing. Math. Oper. Res. 13(2), 311–329 (1988)
Hu, X.B., Di Paolo, E.: An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem. In: IEEE Congress on Evolutionary Computation, CEC 2007, Singapore, pp. 55–62 (2007)
Huang, J., Li, R., An, J., Ntalasha, D., Yang, F., Li, K.: Energy-efficient resource utilization for heterogeneous embedded computing systems. IEEE Trans. Comput. 66(9), 1518–1531 (2017). https://doi.org/10.1109/TC.2017.2693186
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)
Kelton, D., Sadowski, R.P., Sadowski, D.A.: Simulation with Arena. MacGraw Hill College Div, New York (2001)
Kendall, D.G.: Stochastic processes occurring in the theory of queues and their analysis by the method of embedded Markov chains. Ann. Math. Stat. 24, 338–354 (1953)
Kerbache, L., MacGregor Smith, J.: The generalized expansion method for open finite queueing networks. Eur. J. Oper. Res. 32, 448–461 (1987)
Kimura, T.: A transform-free approximation for the finite capacity \(M/G/s\) queue. Oper. Res. 44(6), 984–988 (1996)
Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by simulated annealing. Science 4598, 671–680 (1983)
Lin, F.T.: Solving the knapsack problem with imprecise weight coefficients using genetic algorithms. Eur. J. Oper. Res. 185(1), 133–145 (2008)
MacGregor Smith, J.: \(M/G/c/K\) blocking probability models and system performance. Perform. Eval. 52(4), 237–267 (2003)
MacGregor Smith, J.: Optimal design and performance modelling of \(M/G/1/K\) queueing systems. Math. Comput. Model. 39(9–10), 1049–1081 (2004)
MacGregor Smith, J., Chikhale, N.: Buffer allocation for a class of nonlinear stochastic knapsack problem. Ann. Oper. Res. 58, 323–360 (1995)
MacGregor Smith, J., Cruz, F.R.B.: The buffer allocation problem for general finite buffer queueing networks. IIE Trans. 37(4), 343–365 (2005)
MacGregor Smith, J., Cruz, F.R.B., van Woensel, T.: Topological network design of general, finite, multi-server queueing networks. Eur. J. Oper. Res. 201(2), 427–441 (2010)
Menasce, D.A.: QoS issues in web services. IEEE Internet Comput. 06(6), 72–75 (2002)
Quinino, R.C., Cruz, F.R.B.: Bayesian sample sizes in an \(M/M/1\) queueing system. Int. J. Adv. Manuf. Technol. 88(1), 995–1002 (2017)
Spieckermann, S., Gutenschwager, K., Heinzel, H., Voß, S.: Simulation-based optimization in the automotive industry—a case study on body shop design. Simulation 75(5), 276–286 (2000)
Spinellis, D., Papadopoulos, C.T., MacGregor Smith, J.: Large production line optimization using simulated annealing. Int. J. Prod. Res. 38(3), 509–541 (2000)
van Woensel, T., Cruz, F.R.B.: Optimal routing in general finite multi-server queueing networks. PLoS ONE 9(7), e102,075 (2014)
Acknowledgements
This research has been partially funded by the Brazilian agencies CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico of the Ministry for Science and Technology), under Grant #304671/2014-2, and FAPEMIG (Fundação de Amparo à Pesquisa do Estado de Minas Gerais) under Grant #CEX-PPM-00564-17.
Funding
The Brazilian government funding agencies mentioned above had no role in the study.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that there are no conflicts of interest regarding the publication of this article.
Rights and permissions
About this article
Cite this article
Cruz, F.R.B., Duarte, A.R. & Souza, G.L. Multi-objective performance improvements of general finite single-server queueing networks. J Heuristics 24, 757–781 (2018). https://doi.org/10.1007/s10732-018-9379-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-018-9379-8