Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-01-09T23:34:23.818Z Has data issue: false hasContentIssue false
  • English
  • Français

Moment formulas for the Markov renewal branching process

Published online by Cambridge University Press:  01 July 2016

Marcel F. Neuts
Marcel F. Neuts*
Affiliation:
Purdue University
Get access Rights & Permissions [Opens in a new window]

Abstract

There are many queueing models in which there appears a semi-Markov matrix G(·), whose entries are absorption-time distributions in a Markov renewal branching process. The role of G(·) is similar to that of the busy period in the simple M/G/1 model. The computation of various quantities associated with G(·) is however much more complicated. The moment matrices, and particularly the mean matrix of G(·), are essential in the construction of general and mathematically well-justified algorithms for the steady-state distributions of such queues.

This paper discusses the moment matrices of G(·) and algorithms for their numerical computation. Its contents are basic to the algorithmic solutions to several queueing models, which are to be presented in follow-up papers.

Keywords

MARKOV RENEWAL BRANCHING PROCESSBUSY PERIODMOMENTSCOMPUTATIONAL PROBABILITY
Type
Research Article
Information
Advances in Applied Probability , Volume 8 , Issue 4 , December 1976 , pp. 690 - 711
Copyright
Copyright © Applied Probability Trust 1976 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Carson, C. C. (1975) Computational methods for single server queues with interarrival and service time distributions of phase type. Ph.D. Thesis, Purdue University.Google Scholar
[2] Çinlar, E. (1967) Time dependence of queues with semi-Markovian services. J. Appl. Prob. 4, 356–364.CrossRefGoogle Scholar
[3] Karlin, S. (1969) A First Course in Stochastic Processes. Academic Press, New York and London.Google Scholar
[4] Kemeny, J. and Snell, J. L. (1960) Finite Markov Chains. Van Nostrand, Princeton, N.J.Google Scholar
[5] Marcus, M. and Minc, H. (1964) A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, Boston.Google Scholar
[6] Neuts, M. F. (1966) The single server queue with Poisson input and semi-Markov service times. J. Appl. Prob. 3, 202–230.CrossRefGoogle Scholar
[7] Neuts, M. F. (1968) Two queues in series with a finite intermediate waitingroom. J. Appl. Prob. 5, 123–142.CrossRefGoogle Scholar
[8] Neuts, M. F. (1970) Two servers in series, treated in terms of a Markov renewal branching process. Adv. Appl. Prob. 2, 110–149.CrossRefGoogle Scholar
[9] Neuts, M. F. (1971) A queue subject to extraneous phase changes. Adv. Appl. Prob. 3, 78–119.CrossRefGoogle Scholar
[10] Neuts, M. F. and Purdue, P. (1971) Multivariate semi-Markov matrices. J. Austral. Math. Soc. 13, 107–113.CrossRefGoogle Scholar
[11] Neuts, M. F. (1974) The Markov renewal branching process. Proc. Conf. on Math. Methods in the Theory of Queues, Kalamazoo MI, Springer Verlag, New York, 1–21.Google Scholar
[12] Neuts, M. F. (1976) The effect of change-over times on the M/G/1 queue with several types of customers. Purdue Mimeo Series No. 441, Dept. of Statistics, Purdue University.Google Scholar
[13] Neuts, M. F. (1976) Some explicit formulas for the steady-state behavior of the queue with semi-Markovian service times. Purdue Mimeo Series No. 444, Dept. of Statistics, Purdue University.Google Scholar
[14] Ortega, J. M. and Rheinboldt, W. C. (1970) Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York and London.Google Scholar
[15] Purdue, P. (1972) On the use of analytic matric functions in queueing theory. Ph.D. Thesis, Purdue University.Google Scholar
[16] Purdue, P. (1973) Non-linear matrix integral equations of Volterra type in queueing theory. J. Appl. Prob. 10, 644–651.CrossRefGoogle Scholar
[17] Purdue, P. (1974) The M/M/1 queue in a Markovian environment. Operat. Res. 22, 562–569.CrossRefGoogle Scholar
[18] Purdue, P. (1975) A queue with Poisson input and semi-Markov service times: busy period analysis. J. Appl. Prob. 12, 353–357.CrossRefGoogle Scholar
[19] Wallace, V. (1969) The solution of quasi birth and death processes arising from multiple access computer systems. Ph. D. Thesis, University of Michigan, Ann Arbor, Technical Report 07742–6–T.Google Scholar
[20] Yechiali, U. (1973) A queueing-type birth-and-death process defined on a continuous-time Markov chain. Operat. Res. 21, 604–609.CrossRefGoogle Scholar