Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-22T17:59:43.367Z Has data issue: false hasContentIssue false
  • English
  • Français

Markov processes whose steady state distribution is matrix-exponential with an application to the GI/PH/1 queue

Published online by Cambridge University Press:  01 July 2016

Bhaskar Sengupta
Bhaskar Sengupta*
Affiliation:
AT & T Bell Laboratories, Holmdel
*
∗Postal address: HO 3L-309, AT & T Bell Laboratories, Holmdel, NJ 07733, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper is concerned with a bivariate Markov process {Xt, Nt; t ≧ 0} with a special structure. The process Xt may either increase linearly or have jump (downward) discontinuities. The process Xt takes values in [0,∞) and Nt takes a finite number of values. With these and additional assumptions, we show that the steady state joint probability distribution of {Xt, Nt; t ≧ 0} has a matrix-exponential form. A rate matrix T (which is crucial in determining the joint distribution) is the solution of a non-linear matrix integral equation. The work in this paper is a continuous analog of matrix-geometric methods, which have gained widespread use of late. Using this theory, we present a new and considerably simplified characterization of the waiting time and queue length distributions in a GI/PH/1 queue. Finally, we show that the Markov process can be used to study an inventory system subject to seasonal fluctuations in supply and demand.

Keywords

BIVARIATE MARKOV PROCESS
Type
Research Article
Information
Advances in Applied Probability , Volume 21 , Issue 1 , March 1989 , pp. 159 - 180
Copyright
Copyright © Applied Probability Trust 1989 

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

Bellman, R. (1960) Introduction to Matrix Analysis. McGraw-Hill, New York.Google Scholar
Cohen, J. W. (1982) The Single Server Queue. North-Holland, Amsterdam.Google Scholar
Doshi, B. T., Talman, A. and Van Der Duyn Schouten, F. (1978) The average cost in a single commodity production-inventory system with two switch-over levels. Management Sci. 24, 1078–1086.CrossRefGoogle Scholar
Frame, J. S. (1964a) Matrix functions and applications, part IV: Matrix function and constituent matrices. IEEE Spectrum 1 (6), 123–131.CrossRefGoogle Scholar
Frame, J. S. (1964b) Matrix functions and applications, part V: Similarity reductions by rational or orthogonal matrices. IEEE Spectrum 1 (7), 103–116.CrossRefGoogle Scholar
Franklin, J. N. (1968) Matrix Theory. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Gani, J. and Prabhu, N. U. (1957) Stationary distributions of the negative exponential type for the infinite dam, J. R. Statist. Soc. 19, 342–351.Google Scholar
Gross, D. and Harris, C. M. (1974) Fundamentals of Queueing Theory. Wiley, New York.Google Scholar
Keilson, J. (1979) Markov Chain Models–Rarity and Exponentiality. Springer-Verlag, New York.CrossRefGoogle Scholar
Lucantoni, D. M. and Ramaswami, V. (1985) Efficient algorithms for solving the non-linear matrix equations arising in phase type queues. Stoch. Models 1, 29–51.CrossRefGoogle Scholar
Marcus, M. and Minc, H. (1964) A Survey of Matrix Theory & Matrix Inequalities. Allyn & Bacon, Boston.Google Scholar
Moler, C. and Van Loan, C. (1978) Nineteen dubious ways to compute the exponential of a matrix. SIAM Rev. 20, 801–836.CrossRefGoogle Scholar
Neuts, M. F. (1978) Markov chains with applications to queueing theory, which have a matrix-geometric invariant probability vector. Adv. Appl. Prob. 10, 125–212.CrossRefGoogle Scholar
Neuts, M. F. (1981) Matrix Geometric Solutions for Stochastic Models. John Hopkins University Press, Baltimore.Google Scholar
Ramaswami, V. (1985) Non-linear matrix equations in applied probability: Solution techniques and open problems. SIAM Rev. Google Scholar
Seneta, E. (1980) Non-negative Matrices and Markov Chains. Springer Verlag, New York.Google Scholar
Sengupta, B. (1988) The semi-Markovian queue: theory and applications. Submitted.Google Scholar
Tweedie, R. L. (1976) Criteria for classifying general Markov chains. Adv. Appl. Prob. 8, 737–771.CrossRefGoogle Scholar
Tweedie, R. L. (1982) Operator geometric stationary distributions for Markov chains with application to queueing models. Adv. Appl. Prob. 14, 368–391.CrossRefGoogle Scholar
Ward, R. C. (1977) Numerical computation of the matrix exponential with accuracy estimate. SIAM J. Numer. Anal. 14, 600–610.CrossRefGoogle Scholar