Skip to main content
SpringerLink
Log in

A survey of retrial queueing systems

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Retrial queueing systems have been extensively studied because of their applications in telephone systems, call centers, telecommunication networks, computer systems, and in daily life. This survey deals with various retrial queueing models. The main focus of this survey is to show analytic results for queue length distributions, waiting time distributions, and tail asymptotics for the queue length and waiting time distributions. This survey also considers the stability analysis of retrial queueing models.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  • Anderson, W. J. (1991). Continuous-time markov chains: An applications-oriented approach. Berlin: Springer.

    Book  Google Scholar 

  • Artalejo, J. R. (1999a). A classified bibliography of research on retrial queues: Progress in 1990–1999. Top, 7, 187–211.

  • Artalejo, J. R. (1999b). Accessible bibliography on retrial queues. Mathematical and Computer Modelling, 30, 1–6.

  • Artalejo, J. R. (2010). Accessible bibliography on retrial queues: Progress in 2000–2009. Mathematical and Computer Modelling, 51, 1071–1081.

    Article  Google Scholar 

  • Artalejo, J. R., & Chakravarthy, S. R. (2006a). Algorithmic analysis of the \(\mathit{MAP}/\mathit{PH}/1\) retrial queue. Top, 14, 293–332.

    Article  Google Scholar 

  • Artalejo, J. R., & Chakravarthy, S. R. (2006b). Computational analysis of the maximal queue length in the \(\mathit{MAP}/M/c\) retrial queue. Applied Mathematics and Computation, 183, 1399–1409.

  • Artalejo, J. R., Chakravarthy, S. R., & Lopez-Herrero, M. J. (2007). The busy period and the waiting time analysis of a \(\mathit{MAP}/M/c\) queue with finite retrial group. Stochastic Analysis and Applications, 25, 445–469.

    Article  Google Scholar 

  • Artalejo, J. R., Falin, G. I., & Lopez-Herrero, M. J. (2002). A second order analysis of the waiting time in the \(M/G/1\) retrial queue. Asia-Pacific Journal of Operational Research, 19, 131–148.

    Google Scholar 

  • Artalejo, J. R., & Gómez-Corral, A. (2005). Waiting time in the \(M/M/c\) queue with finite retrial group. Bulletin of Kerala Mathematics Association, 2, 1–17.

    Google Scholar 

  • Artalejo, J. R., & Gómez-Corral, A. (2007). Waiting time analysis of the \(M/G/1\) queue with finite retrial group. Naval Research Logistics, 54, 524–529.

    Article  Google Scholar 

  • Artalejo, J. R., & Gómez-Corral, A. (2008). Retrial queueing systems. Berlin: Springer.

    Book  Google Scholar 

  • Artalejo, J. R., & Phung-Duc, T. (2013). Single server retrial queues with two way communication. Applied Mathematical Modelling, 37, 1811–1822.

    Article  Google Scholar 

  • Avrachenkov, K., Nain, P., & Yechiali, U. (2014). A retrial system with two input streams and two orbit queues. Queueing Systems, 77, 1–31.

    Article  Google Scholar 

  • Bramson, M. (2008). Stability of Queueing Networks. Berlin: Springer.

    Google Scholar 

  • Breuer, L., Dudin, A., & Klimenok, V. (2002). A retrial \(\mathit{BMAP}/\mathit{PH}/N\) system. Queueing Systems, 40, 433–457.

    Article  Google Scholar 

  • Chen, H., & Yao, D. D. (2001). Fundamentals of Queueing Networks. Berlin: Springer.

    Book  Google Scholar 

  • Choi, B. D., & Chang, Y. (1999). Single server retrial queues with priority calls. Mathematical and Computer Modelling, 30, 7–32.

    Article  Google Scholar 

  • Choi, B. D., Han, D. H., & Falin, G. I. (1993). On the virtual waiting time for an M/G/l retrial queue with two types of calls. Journal of Applied Mathametic and Stochastic Analysis, 6, 11–24.

    Article  Google Scholar 

  • Choi, B. D., & Kim, B. (2004). Non-ergodicity criteria for denumerable continuous time Markov processes. Operations Research Letters, 32, 575–580.

    Google Scholar 

  • Choi, B. D., & Park, K. K. (1990). The M/G/1 retrial queue with Bernoulli schedule. Queueing Systems, 7, 219–227.

    Article  Google Scholar 

  • Choo, Q. H., & Conolly, B. (1979). New results in the theory of repeated orders queueing systems. Journal of Applied Probability, 16, 631–640.

    Article  Google Scholar 

  • Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid models. The Annals of Applied Probability, 5, 49–77.

    Article  Google Scholar 

  • Deul, N. (1980). Stationary conditions for multi-server queueing systems with repeated calls. Elektronische Informationsverarbeitung und Kybernetik, 16, 607–613.

    Google Scholar 

  • Diamond, J., & Alfa, A. S. (1998). The \(\mathit{MAP}/\mathit{PH}/1\) retrial queue. Stochastic Models, 14, 1151–1177.

    Article  Google Scholar 

  • Dudin, A., & Klimenok, V. (1999). Queueing system \(\mathit{BMAP}/G/1\) with repeated calls. Mathematical and Computer Modelling, 30, 115–128.

    Article  Google Scholar 

  • Erdélyi, A. (1953). Higher transcendental functions (Vol. 1). New York: McGraw-Hill.

    Google Scholar 

  • Falin, G. I. (1976). Aggregate arrival of customers in a one-line system with repeated calls. Ukrainian Mathematical Journal, 28, 437–440.

    Article  Google Scholar 

  • Falin, G. I. (1977). On the waiting time in a single-channel queueing system with secondary calls. Moscow University Computational Mathematics and Cybernetics, 4, 83–87.

    Google Scholar 

  • Falin, G. I. (1983a). Calculation of probability characteristics of a multiline system with repeated calls. Moscow University Computational Mathematics and Cybernetics, 1, 43–49.

    Google Scholar 

  • Falin, G. I. (1983b). the influence of inhomogeneity of the composition of subscribers on the functioning of telephone systems with repeated calls. Engineering Cybernetics, 21, 78–82.

    Google Scholar 

  • Falin, G. I. (1984). On sufficient conditions for ergodicity of multichannel queueing systems with repeated calls. Advances in Applied Probability, 16, 447–448.

    Article  Google Scholar 

  • Falin, G. I. (1987). The ergodicity of multilinear queueing systems with repeated calls. Sov. J. Comput. Syst. Sci., 25, 60–65.

    Google Scholar 

  • Falin, G. I. (1988). On a multiclass batch arrival retrial queue. Advances in Applied Probability, 20, 483–487.

    Article  Google Scholar 

  • Falin, G. I. (1990). A survey of retrial queues. Queueing Systems, 7, 127–168.

    Article  Google Scholar 

  • Falin, G. I., Artalejo, J. R., & Martin, M. (1993). On the single server retrial queue with priority customers. Queueing Systems, 14, 439–455.

    Article  Google Scholar 

  • Falin, G. I., & Fricker, C. (1991). On the virtual waiting time in an \(M/G/1\) retrial queue. Journal of Applied Probability, 28, 446–460.

    Article  Google Scholar 

  • Falin, G. I., & Templeton, J. G. C. (1997). Retrial Queues. London: Chapman & Hall.

    Book  Google Scholar 

  • Fayolle, G., Malyshev, V. A., & Menshikov, M. V. (1995). Topics in the constructive theory of countable markov chains. Cambridge: Cambridge University Press.

    Book  Google Scholar 

  • Foster, F. G. (1953). On stochastic matrices associated with certain queueing processes. Annals of Mathematical Statistics, 24, 355–360.

    Article  Google Scholar 

  • Gómez-Corral, A. (2006). A bibliographical guide to the analysis of retrial queues through matrix analytic techniques. Annals of Operations Research, 141, 163–191.

    Article  Google Scholar 

  • Gómez-Corral, A., & Ramalhoto, M. F. (1999). The stationary distribution of a Markovian process arising in the theory of multiserver retrial queueing systems. Mathematical and Computer Modelling, 30, 141–158.

    Article  Google Scholar 

  • Hanschke, T. (1987). Explicit formulas for the characteristics of the \(M/M/2/2\) queue with repeated attempts. Journal of Applied Probability, 24, 486–494.

    Article  Google Scholar 

  • Hanschke, T. (1999). A matrix continued fraction algorithm for the multiserver repeated order queue. Mathematical and Computer Modelling, 30, 159–170.

    Article  Google Scholar 

  • He, Q.-M., Li, H., & Zhao, Y. Q. (2000). Ergodicity of the \(\mathit{BMAP}/\mathit{PH}/s/s+K\) retrial queue with PH-retrial times. Queueing Systems, 35, 323–347.

    Article  Google Scholar 

  • Jonin, G. L., & Sedol, J. J. (1970). Investigation of telephone systems in the case of repeated calls. Latvian Mathematical Yearbook, 7, 71–83.

    Google Scholar 

  • Kaplan, M. (1979). A sufficient condition for nonergodicity of a Markov chain. IEEE Transactions on Information Theory, IT–25, 470–471.

    Article  Google Scholar 

  • Keilson, J., Cozzolino, J., & Young, H. (1968). A service system with unfilled requests repeated. Operations Research, 16, 1126–1137.

    Article  Google Scholar 

  • Kim, B. (2011). Stability of a retrial queueing network with different classes of customers and restricted resource polling. Journal of Industrial and Management Optimization, 7, 753–765.

    Article  Google Scholar 

  • Kim, J. (2015). Tail asymptotics for the queue size distribution in an \(M^X/G/1\) retrial queue. Journal of Applied Mathematics & Informatics, 33, 185–191.

    Article  Google Scholar 

  • Kim, B., & Kim, J. (2011). Higher moments of the waiting time distribution in \(M/G/1\) retrial queues. Operations Research Letters, 39, 224–228.

    Article  Google Scholar 

  • Kim, B., & Kim, J. (2012). Exact tail asymptotics for the \(M/M/m\) retrial queue with nonpersistent customers. Operations Research Letters, 40, 537–540.

    Article  Google Scholar 

  • Kim, J., & Kim, B. (2013a). Waiting time distribution in an \(M/\mathit{PH}/1\) retrial queue. Performance Evaluation, 70, 286–299.

    Article  Google Scholar 

  • Kim, J., & Kim, J. (2013b). Waiting time distribution in the \(M/M/m\) retrial queue. Bulletin of the Korean Mathematical Society, 50, 1659–1671.

    Article  Google Scholar 

  • Kim, B., & Kim, J. (2015a). Stability of a two-class and two-server retrial queueing system. Performance Evaluation, 88–89, 1–17.

    Google Scholar 

  • Kim, B., & Kim, J. (2015b). Analysis of the \(M^{X}/G/1\) retrial queue. Annals of Operations Research. doi:10.1007/s10479-015-1921-6.

  • Kim, B., & Kim, J. (2015c). Waiting time distributions in an \(M/G/1\) retrial queue with two classes of customers. Annals of Operations Research. doi:10.1007/s10479-015-1979-1.

  • Kim, B., & Lee, I. (2008). Tests for nonergodicity of denumerable continuous time Markov processes. Computers and Mathematics with Applications, 55, 1310–1321.

    Article  Google Scholar 

  • Kim, B., Kim, J., & Kim, J. (2010a). Tail asymptotics for the queue size distribution in the \(\mathit{MAP}/G/1\) retrial queue. Queueing Systems, 66, 79–94.

    Article  Google Scholar 

  • Kim, J., Kim, B., & Kim, J. (2010b). Moments of the queue size distribution in the \(\mathit{MAP}/G/1\) retrial queue. Computers & Operations Research, 37, 1212–1219.

    Article  Google Scholar 

  • Kim, J., Kim, J., & Kim, B. (2010c). Regularly varying tail of the waiting time distribution in \(M/G/1\) retrial queue. Queueing Systems, 65, 365–383.

    Article  Google Scholar 

  • Kim, J., Kim, J., & Kim, B. (2012). Tail asymptotics of the queue size distribution in the \(M/M/m\) retrial queue. Journal of Computational and Applied Mathematics, 236, 3445–3460.

    Article  Google Scholar 

  • Kim, J., Kim, B., & Ko, S.-S. (2007). Tail asymptotics for the queue size distribution in an \(M/G/1\) retrial queue. Journal of Applied Probability, 44, 1111–1118.

    Article  Google Scholar 

  • Klimenok, V. I. (2001). A multiserver retrial queueing system with batch Markov arrival process. Automation and Remote Control, 62, 1312–1322.

    Article  Google Scholar 

  • Kulkarni, V. G. (1982). Letters to the editor. Journal of Applied Probability, 19, 901–905.

    Article  Google Scholar 

  • Kulkarni, V. G. (1983). On queueing systems with retrials. Journal of Applied Probability, 20, 380–389.

    Article  Google Scholar 

  • Kulkarni, V. G. (1986). Expected waiting times in a multiclass batch arrival retrial queue. Journal of Applied Probability, 23, 144–154.

    Article  Google Scholar 

  • Kulkarni, V. G., & Liang, H. M. (1997). Retrial queues revisited. In J. H. Dshalalow (Ed.), Frontiers in queueing: Models and applications in science and engineering (pp. 19–34). Boca Raton: CRC Press.

    Google Scholar 

  • Liang, H. M., & Kulkarni, V. G. (1993). Stability condition for a single-server retrial queue. Advances in Applied Probability, 25, 690–701.

    Article  Google Scholar 

  • Liu, B., Wang, X., & Zhao, Y. Q. (2012). Tail asymptotics for \(M/M/c\) retrial queues with nonpersistent customers. Operational Research: An International Journal, 12, 173–188.

    Article  Google Scholar 

  • Liu, B., & Zhao, Y. Q. (2010). Analyzing retrial queues by censoring. Queueing Systems, 64, 203–225.

    Article  Google Scholar 

  • Lucantoni, D. M. (1991). New results on the single server queue with a batch Markovian arrival process. Communications in Statistics. Stochastic Models, 7, 1–46.

    Article  Google Scholar 

  • Masuyama, H. (2014). Subexponential tail equivalence of the stationary queue length distributions of \(\mathit{BMAP}/GI/1\) queues with and without retrials, arXiv:1310.4608v3.

  • Neuts, M. F. (1989). Structured stochastic matrices of M/G/1 type and their applications. New York: Marcel Dekker.

    Google Scholar 

  • Neuts, M. F., & Rao, B. M. (1990). Numerical investigation of a multiserver retrial model. Queueing Systems, 7, 169–190.

    Article  Google Scholar 

  • Nobel, R. D., & Tijms, H. C. (2006). Waiting-time probabilities in the \(M/G/1\) retrial queue. Statistica Neerlandica, 60, 73–78.

    Article  Google Scholar 

  • Pakes, A. G. (1969). Some conditions for ergodicity and recurrence of Markov chains. Operations Research, 17, 1058–1061.

    Article  Google Scholar 

  • Phung-Duc, T., Masuyama, H., Kasahara, S., & Takahashi, Y. (2009). \(M/M/3/3\) and \(M/M/4/4\) retrial queues. Journal of Industrial and Management Optimization, 5, 431–451.

    Article  Google Scholar 

  • Phung-Duc, T., Masuyama, H., Kasahara, S., & Takahashi, Y. (2013). A matrix continued fraction approach to multiserver retrial queues. Annals of Operations Research, 202, 161–183.

    Article  Google Scholar 

  • Reuter, G. E. H. (1961). Competition processes. In Proceedings of the Fourth Berkeley symposium on mathematical statistics andprobability , Vol. 2, pp. 421–430.

  • Rodrigo, A., Vázquez, M., & Falin, G. I. (1998). A new Markovian description of the \(M/G/1\) retrial queue. European Journal of Operational Research, 104, 231–240.

    Article  Google Scholar 

  • Seneta, E. (1981). Nonnegative matrices and Markov chains. Berlin: Springer.

    Book  Google Scholar 

  • Sennott, L. I. (1985). Tests for the nonergodicity of multidimensional Markov chains. Operations Research, 33, 161–167.

    Article  Google Scholar 

  • Sennott, L. I., Humblet, P. A., & Tweedie, R. L. (1983). Mean drifts and the non-ergodicity of Markov chains. Operations Research, 31, 783–789.

    Article  Google Scholar 

  • Shang, W., Liu, L., & Li, Q.-L. (2006). Tail asymptotics for the queue length in an \(M/G/1\) retrial queue. Queueing Systems, 52, 193–198.

    Article  Google Scholar 

  • Tweedie, R. L. (1975). Sufficient conditions for regularity, recurrence and ergodicity of Markov processes. Mathematical Proceedings of the Cambridge Philosophical Society, 78, 125–136.

    Article  Google Scholar 

  • Tweedie, R. L. (1981). Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov processes. Journal of Applied Probability, 18, 122–130.

    Article  Google Scholar 

  • Yamamuro, K. (2012). The queue length in an \(M/G/1\) batch arrival retrial queue. Queueing Systems, 70, 187–205.

    Article  Google Scholar 

  • Yang, T., Posner, M. J. M., & Templeton, J. G. C. (1990). The \(M/G/1\) retrial queue with nonpersistent customers. Queueing Systems, 7, 209–218.

    Article  Google Scholar 

  • Yang, T., Posner, M. J. M., Templeton, J. G. C., & Li, H. (1994). An approximation method for the \(M/G/1\) retrial queue with general retrial times. European Journal of Operational Research, 76, 552–562.

    Article  Google Scholar 

  • Yang, T., & Templeton, J. G. C. (1987). A survey on retrial queues. Queueing Systems, 2, 201–233.

    Article  Google Scholar 

Download references

Acknowledgments

We are grateful to the reviewers for their valuable comments and suggestions, which improved this paper. J. Kim’s research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2014R1A1A4A01003813). B. Kim’s research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. 2014R1A2A2A01005831).

Author information

Authors and Affiliations

  1. Department of Mathematics Education, Chungbuk National University, 1 Chungdae-ro, Seowon-gu, Cheongju, Chungbuk, 28644, Korea

    Jeongsim Kim

  2. Department of Mathematics, Korea University, 145 Anam-ro, Seongbuk-gu, Seoul, 02841, Korea

    Bara Kim

Authors
  1. Jeongsim Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bara Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bara Kim.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kim, J., Kim, B. A survey of retrial queueing systems. Ann Oper Res 247, 3–36 (2016). https://doi.org/10.1007/s10479-015-2038-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-015-2038-7

Keywords

Mathematics Subject Classification

Search

Navigation