×

Quasi-birth-and-death processes, lattice path counting, and hypergeometric functions. (English) Zbl 1186.60087

The paper investigates the two-dimensional quasi-birth-and-death processes (QBD). Under the assumption that such a process is irreducible and ergodic its stationary probability vector exists and is given by virtue of a rate matrix \(R\). Determining explicit expressions for the elements of matrix \(R\) and a closely related matrix \(G\) with the aid of path decomposition, Bernoulli excursions, lattice path counting, and hypergeometric functions, is the main concern of this work. The main results are illustrated by an application to three classical queueing models: longest queue model, priority model and feedback model.
The authors believe that their contribution is three-fold: “(a) They introduce a class of QBD processes for which the \(R\) and \(G\) matrices can be explicitly determined; (b) Exact expressions for the fundamental matrix elements provide an explicit characterization of the probabilistic and dynamic behaviors of the stochastic process itself. (c) Their results provide an efficient alternative for computing the invariant distribution over those based on numerical algorithms.”

MSC:

60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60J25 Continuous-time Markov processes on general state spaces
60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramowitz, M. and Stegun, I. A. (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables . US Government Printing Office, Washington, D.C. · Zbl 0171.38503
[2] Adan, I. J. B. F. and Weiss, G. (2006). Analysis of a simple Markovian re-entrant line with infinite supply of work under the LBFS policy. \QS 54 , 169–183. · Zbl 1103.60076 · doi:10.1007/s11134-006-0065-4
[3] Adan, I. J. B. F. and van der Wal, J. (1998). Combining make to order and make to stock. OR Spektrum 20 , 73–81. · Zbl 0903.90047 · doi:10.1007/BF01539854
[4] Cobham, A. (1954). Priority assignment in waiting line problems. \OR 2 , 70–76.
[5] Cohen, J. W. (1987). A two-queue, one-server model with priority for the longer queue. \QS 2 , 261–283. · Zbl 0655.60090 · doi:10.1007/BF01158902
[6] Dunford, N. and Schwartz, J. T. (1958). Linear Operators. Part I: General Theory . John Wiley, New York. · Zbl 0635.47001
[7] Dunford, N. and Schwartz, J. T. (1963). Linear Operators. Part II: Spectral Theory. Self Adjoint Operators in Hilbert Space . John Wiley, New York. · Zbl 0128.34803
[8] Dunford, N. and Schwartz, J. T. (1971). Linear Operators. Part III: Spectral Operators . John Wiley, New York. · Zbl 0243.47001
[9] Flatto, L. (1989). The longer queue model. Prob. Eng. Inf. Sci. 3 , 537–559. · Zbl 1134.60395 · doi:10.1017/S0269964800001376
[10] Jaiswal, N. K. (1968). Priority Queues (Math. Sci. Eng. 50 ). Academic Press, London. · Zbl 0179.47904
[11] Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling . Society for Industrial and Applied Mathematics, Philadelphia, PA. · Zbl 0922.60001 · doi:10.1137/1.9780898719734
[12] van Leeuwaarden, J. S. H. and Winands, E. M. M. (2006). Quasi-birth-and-death processes with an explicit rate matrix. Stoch. Models 22 , 77–98. · Zbl 1115.60070 · doi:10.1080/15326340500481747
[13] Liu, D. and Zhao, Y. Q. (1997). Determination of explicit solutions for a general class of Markov processes. In Matrix-Analytic Methods in Stochastic Models (Lecture Notes Pure Appl. Math. 183 ), Dekker, New York, pp. 343–357. · Zbl 0872.60075
[14] Nelson, R. D. and Squillante, M. S. (1996). Stochastic analysis of affinity scheduling and load balancing in parallel processing systems. In Proc. 5th INFORMS Computer Science Technical Section Conference on Computer Science and Operations Research: Recent Advances in the Interface (January 1996).
[15] Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models . Johns Hopkins Press, Baltimore, MD. · Zbl 0469.60002
[16] Neuts, M. F. (1989). Structured Stochastic Matrices of M/G/1 Type and Their Applications . Marcel Dekker, New York. · Zbl 0695.60088
[17] Ramaswami, V. and Latouche, G. (1986). A general class of Markov processes with explicit matrix-geometric solutions. OR Spektrum 8 , 209–218. · Zbl 0612.60057 · doi:10.1007/BF01721131
[18] Schrage, L. E. (1967). The queue M/G/1 with feedback to lower priority queues. \MS 13 , 466–474.
[19] Squillante, M. S. (1998). Matrix-analytic methods in stochastic parallel-server scheduling models. In Advances in Matrix Analytic Methods for Stochastic Models , Notable, New Jersey, pp. 311–340.
[20] Squillante, M. S. (2005). Stochastic analysis of resource allocation in parallel processing systems. In Computer System Performance Modeling in Perspective: A Tribute to the Work of Prof. K. C. Sevcik , Imperial College Press, London, pp. 227–256.
[21] Squillante, M. S. and Nelson, R. D. (1991). Analysis of task migration in shared-memory multiprocessors. In Proc. ACM SIGMETRICS (May 1991), ACM Press, New York, pp. 143–155.
[22] Takács, L. (1991). A Bernoulli excursion and its various applications. ÅP 23 , 557–585. JSTOR: · Zbl 0738.60069 · doi:10.2307/1427622
[23] Tweedie, R. L. (1982). Operator-geometric stationary distributions for Markov chains, with application to queueing models. ÅP 14 , 368–391. JSTOR: · Zbl 0484.60072 · doi:10.2307/1426527
[24] Zheng, Y. and Zipkin, P. H. (1990). A queueing model to analyze the value of centralized inventory information. \OR 38 , 296–307. · Zbl 0735.90036 · doi:10.1287/opre.38.2.296
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.