Bounds on the rate of convergence for one class of inhomogeneous Markovian queueing models with possible batch arrivals and services

Zeifman, A. ; Razumchik, R. ; Satin, Y. ; Kiseleva, K. ; Korotysheva, A. ; Korolev, V.

International Journal of Applied Mathematics and Computer Science, Tome 28 (2018) no. 1, pp. 141-154.

Résumé

In this paper we present a method for the computation of convergence bounds for four classes of multiserver queueing systems, described by inhomogeneous Markov chains. Specifically, we consider an inhomogeneous M/M/S queueing system with possible state-dependent arrival and service intensities, and additionally possible batch arrivals and batch service. A unified approach based on a logarithmic norm of linear operators for obtaining sharp upper and lower bounds on the rate of convergence and corresponding sharp perturbation bounds is described. As a side effect, we show, by virtue of numerical examples, that the approach based on a logarithmic norm can also be used to approximate limiting characteristics (the idle probability and the mean number of customers in the system) of the systems considered with a given approximation error.

Détail

Keywords: inhomogeneous birth process, inhomogeneous death process, weak ergodicity, rate of convergence, sharp bounds, logarithmic norm, forward Kolmogorov system
Mots-clés : proces narodzin, proces śmierci, stopień konwergencji, norma logarytmiczna, system Kołmogorowa

Bibliographie

[1] Almasi, B., Roszik, J. and Sztrik, J. (2005). Homogeneous finite-source retrial queues with server subject to breakdowns and repairs, Mathematical and Computer Modelling 42(5): 673–682.

[2] Chen, A., Pollett, P., Li, J. and Zhang, H. (2010). Markovian bulk-arrival and bulk-service queues with state-dependent control, Queueing Systems 64(3): 267–304.

[3] Daleckij, J. and Krein,M. (1974). Stability of Solutions of Differential Equations in Banach Space, American Mathematical Society, Providence, RI.

[4] Doorn, E.V., Zeifman, A. and Panfilova, T. (2010). Bounds and asymptotics for the rate of convergence of birth-death processes, Theory of Probability and Its Applications 54(1): 97–113.

[5] Granovsky, B. and Zeifman, A. (2000). The n-limit of spectral gap of a class of birthdeath Markov chains, Applied Stochastic Models in Business and Industry 16(4): 235–248.

[6] Granovsky, B. and Zeifman, A. (2004). Nonstationary queues: Estimation of the rate of convergence, Queueing Systems 46(3–4): 363–388.

[7] Gudkova, I., Korotysheva, A., Zeifman, A., Shilova, G., Korolev, V., Shorgin, S. and Razumchik, R. (2016). Modeling and analyzing licensed shared access operation for 5g network as an inhomogeneous queue with catastrophes, 2016 8th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), Lisbon, Portugal, pp. 282–287.

[8] Kamiński, M. (2015). Symbolic computing in probabilistic and stochastic analysis, International Journal of Applied Mathematics and Computer Science 25(4): 961–973, DOI: 10.1515/amcs-2015-0069.

[9] Kartashov, N. (1985). Criteria for uniform ergodicity and strong stability of Markov chains with a common phase space, Theory of Probability and Mathematical Statistics 30(30): 71–89.

[10] Kartashov, N. (1996). Strong Stable Markov Chains, VSP, Utrecht.

[11] Kim, C., Dudin, A., Dudin, S. and Dudina, O. (2014). Analysis of an MMAP/PH1, PH2/N/∞ queueing system operating in a random environment, International Journal of Applied Mathematics and Computer Science 24(3): 485–501, DOI: 10.2478/amcs-2014-0036.

[12] Li, J. and Zhang, L. (2016). Decay property of stopped Markovian bulk-arriving queues with c-servers, Stochastic Models 32(4): 674–686.

[13] Mitrophanov, A. (2003). Stability and exponential convergence of continuous-time Markov chains, Journal of Applied Probability 40(4): 970–979.

[14] Mitrophanov, A. (2004). The spectral GAP and perturbation bounds for reversible continuous-time Markov chains, Journal of Applied Probability 41(4): 1219–1222.

[15] Mitrophanov, A. (2005a). Ergodicity coefficient and perturbation bounds for continuous-time Markov chains, Mathematical Inequalities Applications 8(1): 159–168.

[16] Mitrophanov, A. (2005b). Sensitivity and convergence of uniformly ergodic Markov chains, Journal of Applied Probability 42(4): 1003–1014.

[17] Moiseev, A. and Nazarov, A. (2016a). Queueing network MAP − (GI/∞)K with high-rate arrivals, European Journal of Operational Research 254(1): 161–168.

[18] Moiseev, A. and Nazarov, A. (2016b). Tandem of infinite-server queues with Markovian arrival process, Distributed Computer and Communication Networks: 18th International Conference, DCCN 2015, Moscow, Russia, pp. 323–333.

[19] Nelson, R., Towsley, D. and Tantawi, A. (1987). Performance analysis of parallel processing systems, ACM SIGMETRICS Performance Evaluation Review 15(1): 93–94.

[20] Satin, Y., Zeifman, A. and Korotysheva, A. (2013). On the rate of convergence and truncations for a class of Markovian queueing systems, Theory of Probability Its Applications 57(3): 529–539.

[21] Schwarz, J., Selinka, G. and Stolletz, R. (2016). Performance analysis of time-dependent queueing systems: Survey and classification, Omega 63: 170–189.

[22] Whitt, W. (1991). The pointwise stationary approximation for Mt/Mt/s queues is asymptotically correct as the rates increase, Management Science 37(3): 307–314.

[23] Whitt, W. (2015). Stabilizing performance in a single-server queue with time-varying arrival rate, Queueing Systems 81(4): 341–378.

[24] Zeifman, A. (1995a). On the estimation of probabilities for birth and death processes, Journal of Applied Probability 32(3): 623–634.

[25] Zeifman, A. (1995b). Upper and lower bounds on the rate of convergence for nonhomogeneous birth and death processes, Stochastic Processes and Their Applications 59(1): 157–173.

[26] Zeifman, A. and Korolev, V. (2014). On perturbation bounds for continuous-time Markov chains, Statistics Probability Letters 88: 66–72.

[27] Zeifman, A. and Korolev, V. (2015). Two-sided bounds on the rate of convergence for continuous-time finite inhomogeneous Markov chains, Statistics Probability Letters 103: 30–36.

[28] Zeifman, A., Korolev, V., Satin, Y., Korotysheva, A. and Bening, V. (2014a). Perturbation bounds and truncations for a class of Markovian queues, Queueing Systems 76(2): 205–221.

[29] Zeifman, A., Korotysheva, A., Korolev, V. and Satin, Y. (2016a). Truncation bounds for approximations of inhomogeneous continuous-time Markov chains, Probability Theory and Its Applications 61(3): 563–569, (in Russian).

[30] Zeifman, A., Korotysheva, A., Satin, Y., Shilova, G., Razumchik, R., Korolev, V. and Shorgin, S. (2016b). Uniform in time bounds for “no-wait” probability in queues of Mt/Mt/S type, Proceedings of the 30th European Conference on Modelling and Simulation, ECMS 2016, Regensburg, Germany, pp. 676–684.

[31] Zeifman, A., Leorato, S., Orsingher, E., Satin, Y. and Shilova, G. (2006). Some universal limits for nonhomogeneous birth and death processes, Queueing Systems 52(2): 139–151.

[32] Zeifman, A., Satin, Y., Korolev, V. and Shorgin, S. (2014b). On truncations for weakly ergodic inhomogeneous birth and death processes, International Journal of Applied Mathematics and Computer Science 24(3): 503–518, DOI: 10.2478/amcs-2014-0037.

[33] Zeifman, A., Satin, Y. and Panfilova, T. (2013). Limiting characteristics for finite birthdeath-catastrophe processes, Mathematical Biosciences 245(1): 96–102.