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

Alexander Zeifman; Rostislav Razumchik; Yacov Satin; Ksenia Kiseleva; Anna Korotysheva; Victor Korolev

doi:10.2478/amcs-2018-0011

.blurhash-client-img { display: none !important; }

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

International Journal of Applied Mathematics and Computer Science

Volume 28 (2018): Issue 1 (March 2018)

By: Alexander Zeifman, Rostislav Razumchik, Yacov Satin, Ksenia Kiseleva, Anna Korotysheva and Victor Korolev

Open Access

|Mar 2018

Abstract

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.

References

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.10.1016/j.mcm.2004.02.046
Search in Google Scholar Back to article
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.10.1007/s11134-009-9162-5
Open DOI Search in Google Scholar Back to article
Daleckij, J. and Krein,M. (1974). Stability of Solutions of Differential Equations in Banach Space, American Mathematical Society, Providence, RI.
Search in Google Scholar Back to article
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.10.1137/S0040585X97984097
Search in Google Scholar Back to article
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.10.1002/1526-4025(200010/12)16:4<;235::AID-ASMB415>3.0.CO;2-S
Search in Google Scholar Back to article
Granovsky, B. and Zeifman, A. (2004). Nonstationary queues: Estimation of the rate of convergence, Queueing Systems 46(3-4): 363-388.10.1023/B:QUES.0000027991.19758.b4
Open DOI Search in Google Scholar Back to article
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.10.1109/ICUMT.2016.7765372
Search in Google Scholar Back to article
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.10.1515/amcs-2015-0069
Open DOI Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Kartashov, N. (1996). Strong Stable Markov Chains, VSP, Utrecht. 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.10.2478/amcs-2014-0036
Open DOI Search in Google Scholar Back to article
Li, J. and Zhang, L. (2016). Decay property of stopped Markovian bulk-arriving queues with c-servers, Stochastic Models 32(4): 674-686.10.1080/15326349.2016.1196374
Search in Google Scholar Back to article
Mitrophanov, A. (2003). Stability and exponential convergence of continuous-time Markov chains, Journal of Applied Probability 40(4): 970-979.10.1239/jap/1067436094
Open DOI Search in Google Scholar Back to article
Mitrophanov, A. (2004). The spectral GAP and perturbation bounds for reversible continuous-time Markov chains, Journal of Applied Probability 41(4): 1219-1222.10.1239/jap/1101840568
Open DOI Search in Google Scholar Back to article
Mitrophanov, A. (2005a). Ergodicity coefficient and perturbation bounds for continuous-time Markov chains, Mathematical Inequalities & Applications 8(1): 159-168.10.7153/mia-08-15
Open DOI Search in Google Scholar Back to article
Mitrophanov, A. (2005b). Sensitivity and convergence of uniformly ergodic Markov chains, Journal of Applied Probability 42(4): 1003-1014.10.1239/jap/1134587812
Open DOI Search in Google Scholar Back to article
Moiseev, A. and Nazarov, A. (2016a). Queueing network MAP − (GI/∞)K with high-rate arrivals, European Journal of Operational Research 254(1): 161-168.10.1016/j.ejor.2016.04.011
Search in Google Scholar Back to article
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.10.1007/978-3-319-30843-2_34
Search in Google Scholar Back to article
Nelson, R., Towsley, D. and Tantawi, A. (1987). Performance analysis of parallel processing systems, ACM SIGMETRICS Performance Evaluation Review 15(1): 93-94.10.1145/29904.29916
Search in Google Scholar Back to article
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.10.1137/S0040585X97986151
Search in Google Scholar Back to article
Schwarz, J., Selinka, G. and Stolletz, R. (2016). Performance analysis of time-dependent queueing systems: Survey and classification, Omega 63: 170-189.10.1016/j.omega.2015.10.013
Search in Google Scholar Back to article
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.10.1287/mnsc.37.3.307
Open DOI Search in Google Scholar Back to article
Whitt, W. (2015). Stabilizing performance in a single-server queue with time-varying arrival rate, Queueing Systems 81(4): 341-378.10.1007/s11134-015-9462-x
Search in Google Scholar Back to article
Zeifman, A. (1995a). On the estimation of probabilities for birth and death processes, Journal of Applied Probability 32(3): 623-634.10.2307/3215117
Open DOI Search in Google Scholar Back to article
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.10.1016/0304-4149(95)00028-6
Search in Google Scholar Back to article
Zeifman, A. and Korolev, V. (2014). On perturbation bounds for continuous-time Markov chains, Statistics & Probability Letters 88: 66-72.10.1016/j.spl.2014.01.031
Open DOI Search in Google Scholar Back to article
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.10.1016/j.spl.2015.04.013
Search in Google Scholar Back to article
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.10.1007/s11134-013-9388-0
Open DOI Search in Google Scholar Back to article
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).10.1137/S0040585X97T988320
Search in Google Scholar Back to article
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.10.7148/2016-0676
Search in Google Scholar Back to article
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.10.1007/s11134-006-4353-9
Open DOI Search in Google Scholar Back to article
Zeifman, A., Satin, Y., Korolev, V. and Shorgin, S. (2014b). n 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.10.2478/amcs-2014-0037
Open DOI Search in Google Scholar Back to article
Zeifman, A., Satin, Y. and Panfilova, T. (2013). Limiting characteristics for finite birthdeath-catastrophe processes, Mathematical Biosciences 245(1): 96-102.10.1016/j.mbs.2013.02.00923458510
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/amcs-2018-0011 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X

Journal RSS Feed

Language: English

Page range: 141 - 154

Submitted on: Apr 24, 2017

Accepted on: Aug 9, 2017

Published on: Mar 31, 2018

Published by: University of Zielona Góra

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

inhomogeneous birth and death processes,

forward Kolmogorov system

Related subjects:

Mathematics,

Applied mathematics

© 2018 Alexander Zeifman, Rostislav Razumchik, Yacov Satin, Ksenia Kiseleva, Anna Korotysheva, Victor Korolev, published by University of Zielona Góra
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 28 (2018): Issue 1 (March 2018)