Generalized truncated methods for an efficient solution of retrial systems. (English) Zbl 1162.90007

Summary: We are concerned with the analytic solution of multiserver retrial queues including the impatience phenomenon. As there are not closed-form solutions to these systems, approximate methods are required. We propose two different generalized truncated methods to effectively solve this type of systems. The methods proposed are based on the homogenization of the state space beyond a given number of users in the retrial orbit. We compare the proposed methods with the most well-known methods appeared in the literature in a wide range of scenarios. We conclude that the proposed methods generally outperform previous proposals in terms of accuracy for the most common performance parameters used in retrial systems with a moderated growth in the computational cost.


90B22 Queues and service in operations research
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI EuDML


[1] G. Jonin and J. Sedol, “Telephone systems with repeated calls,” in Proceedings of the 6th International Teletraffic Congress (ITC ’70), pp. 435.1-435.5, Munich, Germany, September 1970.
[2] P. Tran-Gia and M. Mandjes, “Modeling of customer retrial phenomenon in cellular mobile networks,” IEEE Journal on Selected Areas in Communications, vol. 15, no. 8, pp. 1406-1414, 1997.
[3] E. Onur, H. Deli\cc, C. Ersoy, and M. U. \cCa\uglayan, “Measurement-based replanning of cell capacities in GSM networks,” Computer Networks, vol. 39, no. 6, pp. 749-767, 2002.
[4] T. Bonald and J. W. Roberts, “Congestion at flow level and the impact of user behaviour,” Computer Networks, vol. 42, no. 4, pp. 521-536, 2003. · Zbl 1059.68013
[5] B. D. Choi, Y. W. Shin, and W. C. Ahn, “Retrial queues with collision arising from unslotted CMSA/CD protocol,” Queueing Systems, vol. 11, no. 4, pp. 335-356, 1992. · Zbl 0762.60088
[6] A. Mandelbaum, “Call centers (centres), research bibliography with abstracts,” Tech. Rep., Faculty of Industrial Engineering and Management Technion-Israel Institute of Technology, Technion City, Israel, 2004, http://ie.technion.ac.il/serveng/.
[7] M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, vol. 2 of Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University, Baltimore, Md, USA, 1981. · Zbl 0469.60002
[8] L. Bright and P. G. Taylor, “Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes,” Communications in Statistics. Stochastic Models, vol. 11, no. 3, pp. 497-525, 1995. · Zbl 0837.60081
[9] G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, ASA-SIAM Series on Statistics and Applied Probability 5, SIAM, Philadelphia, Pa, USA, 1999. · Zbl 0922.60001
[10] J. R. Artalejo and M. Pozo, “Numerical calculation of the stationary distribution of the main multiserver retrial queue,” Annals of Operations Research, vol. 116, no. 1-4, pp. 41-56, 2002. · Zbl 1013.90038
[11] M. F. Neuts and B. M. Rao, “Numerical investigation of a multiserver retrial model,” Queueing Systems, vol. 7, no. 2, pp. 169-189, 1990. · Zbl 0711.60094
[12] G. Falin and J. Templeton, Retrial Queues, Chapman & Hall/CRC, Boca Raton, Fla, USA, 1997. · Zbl 0944.60005
[13] B. S. Greenberg and R. W. Wolff, “An upper bound on the performance of queues with returning customers,” Journal of Applied Probability, vol. 24, no. 2, pp. 466-475, 1987. · Zbl 0626.60092
[14] R. I. Wilkinson, “Theories for toll traffic engineering in the USA,” The Bell System Technical Journal, vol. 35, no. 2, pp. 421-514, 1956.
[15] S. N. Stepanov, “Markov models with retrials: the calculation of stationary performance measures based on the concept of truncation,” Mathematical and Computer Modelling, vol. 30, no. 3-4, pp. 207-228, 1999. · Zbl 1042.60547
[16] A. A. Fredericks and G. A. Reisner, “Approximations to stochastic service systems, with an application to a retrial model,” The Bell System Technical Journal, vol. 58, no. 3, pp. 557-576, 1979. · Zbl 0402.90043
[17] M. A. Marsan, G. de Carolis, E. Leonardi, R. Lo Cigno, and M. Meo, “Efficient estimation of call blocking probabilities in cellular mobile telephony networks with customer retrials,” IEEE Journal on Selected Areas in Communications, vol. 19, no. 2, pp. 332-346, 2001.
[18] M. J. Doménech-Benlloch, J. M. Giménez-Guzmán, J. Martínez-Bauset, and V. Casares-Giner, “Efficient and accurate methodology for solving multiserver retrial systems,” Electronics Letters, vol. 41, no. 17, pp. 967-969, 2005.
[19] G. I. Falin, “Calculation of probability characteristics of a multiline system with repeat calls,” Moscow University Computational Mathematics and Cybernetics, no. 1, pp. 43-49, 1983. · Zbl 0534.90035
[20] V. V. Anisimov and J. R. Artalejo, “Approximation of multiserver retrial queues by means of generalized truncated models,” Top, vol. 10, no. 1, pp. 51-66, 2002. · Zbl 1015.60085
[21] D. P. Gaver, P. A. Jacobs, and G. Latouche, “Finite birth-and-death models in randomly changing environments,” Advances in Applied Probability, vol. 16, no. 4, pp. 715-731, 1984. · Zbl 0554.60079
[22] L. D. Servi, “Algorithmic solutions to two-dimensional birth-death processes with application to capacity planning,” Telecommunication Systems, vol. 21, no. 2-4, pp. 205-212, 2002.
[23] J. Ye and S.-Q. Li, “Folding algorithm: a computational method for finite QBD processes with level-dependent transitions,” IEEE Transactions on Communications, vol. 42, no. 234, part 1, pp. 625-639, 1994.
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.