American Institute of Mathematical Sciences

Advanced
2011, 1(4): 691-711. doi: 10.3934/naco.2011.1.691

Kronecker product-forms of steady-state probabilities with $C_k$/$C_m$/$1$ by matrix polynomial approaches

Hsin-Yi Liu 1, and  Hsing Paul Luh 1,

1. 

Department of Mathematical Science, National Chengchi University, Taipei, Taiwan, Taiwan

Received  June 2011 Revised  August 2011 Published  November 2011

In this paper, we analyze a single server queueing system $C_k/C_m/1$. We construct a general solution space of vector product-forms for steady-state probability and express it in terms of singularities and vectors of the fundamental matrix polynomial $\textbf{Q}(\omega)$. It is shown that there is a strong relation between the singularities of $\textbf{Q}(\omega)$ and the roots of the characteristic polynomial involving the Laplace transforms of the inter-arrival and service times distributions. Thus, some steady-state probabilities may be written as a linear combination of vectors derived in expression of these roots. In this paper, we focus on solving a set of equations of matrix polynomials in the case of multiple roots. As a result, we give a closed-form solution of unboundary steady-state probabilities of $C_k/C_m/1$, thereupon considerably reducing the computational complexity of solving a complicated problem in a general queueing model.
Keywords: Matrix polynomials, quasi-birth-and-death process, phase-type distributions.
Mathematics Subject Classification: Primary: 15A16, 60K25, 40C0.
Citation: Hsin-Yi Liu, Hsing Paul Luh. Kronecker product-forms of steady-state probabilities with $C_k$/$C_m$/$1$ by matrix polynomial approaches. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 691-711. doi: 10.3934/naco.2011.1.691
References:
[1]

R. Bellman, "Introduction to Matrix Analysis," MacGraw-Hill, London, 1960. Google Scholar

[2]

D. Bertsimas, An analytic approach to a general class of G/G/s queueing systems, Operations Research, 38 (1990), 139-155. doi: 10.1287/opre.38.1.139.  Google Scholar

[3]

F. De Terán, F. M. Dopico and J. Moro, Low rank perturbation of Weierstrass structure, SIAM J. Matrix Anal. Appl., 30 (2008), 538-547.  Google Scholar

[4]

R. V. Evans, Geometric distribution in some two-dimensional queueing systems, Operations Research, 15 (1967), 830-846. doi: 10.1287/opre.15.5.830.  Google Scholar

[5]

H. R. Gail, S. L. Hantler and B. A. Taylor, Matrix-geometric invariant measures for G/M/1 type Markov chains, Commun. Statist.-Stochastic Models, 14 (1998), 537-569.  Google Scholar

[6]

H. R. Gail, S. L. Hantler and B. A. Taylor, Spectral analysis of M/G/1 and G/M/1 Type Markov chains, Advanced Applied Probability, 28 (1996), 114-165. doi: 10.2307/1427915.  Google Scholar

[7]

H. R. Gail, S. L. Hantler, M. Sidi and B. A. Taylor, Linear independence of root equations for M/G/1 type Markov chains, Queueing Systems, 20 (1995), 321-339. doi: 10.1007/BF01245323.  Google Scholar

[8]

I. C. Gohberg, P. Lancaster and L. Rodman, "Matrix Polynomials," Academic Press, New York, 1982.  Google Scholar

[9]

M. F. Neuts, "Matrix-Geometric Solutions in Stochastic Models," The John Hopkins University Press, 1981.  Google Scholar

[10]

W. K. Grassmann, Real eigenvalues of certain tridiagonal matrix polynomials with queueing applications, Linear Algebra and Its Applications, 342 (2002), 93-106. doi: 10.1016/S0024-3795(01)00462-1.  Google Scholar

[11]

W. K. Grassmann and J. Tavakoli, A tandem queue with movable server: an eigenvalue approach, SIAM J. Matrix Anal. Appl, 24 (2002), 465-474.  Google Scholar

[12]

W. K. Grassmann and S. Drekic, An analytical solution for a tandem queue with blocking, Queueing Systems, 36 (2000), 221-235. doi: 10.1023/A:1019139405059.  Google Scholar

[13]

R. A. Horn and C. R. Johnson, "Topics in Matrix Analysis," Cambridge University Press, 1999. Google Scholar

[14]

J. Y. Le Boudec, Steady-state probabilities of the PH/PH/1 queue, Queueing Systems, 3 (1988), 73-88. doi: 10.1007/BF01159088.  Google Scholar

[15]

H. Luh, Matrix product-form solutions of stationary probabilities in tandem queues, Journal of the Operations Research, 42 (1999), 436-656.  Google Scholar

[16]

A. Van De Liefvoort, The waiting-time distribution and its moments of the PH/PH/1 queue, Operations Research Letters, 9 (1990), 261-269. doi: 10.1016/0167-6377(90)90071-C.  Google Scholar

[17]

V. Wallace, "The Solution of Quasi Birth and Death Processes arising from Multiple Access Computer Systems," Ph. D. diss., Systems Engineering Laboratory, University of Michigan, Tech. Report N 07742-6-T, 1969. Google Scholar

show all references

References:
[1]

R. Bellman, "Introduction to Matrix Analysis," MacGraw-Hill, London, 1960. Google Scholar

[2]

D. Bertsimas, An analytic approach to a general class of G/G/s queueing systems, Operations Research, 38 (1990), 139-155. doi: 10.1287/opre.38.1.139.  Google Scholar

[3]

F. De Terán, F. M. Dopico and J. Moro, Low rank perturbation of Weierstrass structure, SIAM J. Matrix Anal. Appl., 30 (2008), 538-547.  Google Scholar

[4]

R. V. Evans, Geometric distribution in some two-dimensional queueing systems, Operations Research, 15 (1967), 830-846. doi: 10.1287/opre.15.5.830.  Google Scholar

[5]

H. R. Gail, S. L. Hantler and B. A. Taylor, Matrix-geometric invariant measures for G/M/1 type Markov chains, Commun. Statist.-Stochastic Models, 14 (1998), 537-569.  Google Scholar

[6]

H. R. Gail, S. L. Hantler and B. A. Taylor, Spectral analysis of M/G/1 and G/M/1 Type Markov chains, Advanced Applied Probability, 28 (1996), 114-165. doi: 10.2307/1427915.  Google Scholar

[7]

H. R. Gail, S. L. Hantler, M. Sidi and B. A. Taylor, Linear independence of root equations for M/G/1 type Markov chains, Queueing Systems, 20 (1995), 321-339. doi: 10.1007/BF01245323.  Google Scholar

[8]

I. C. Gohberg, P. Lancaster and L. Rodman, "Matrix Polynomials," Academic Press, New York, 1982.  Google Scholar

[9]

M. F. Neuts, "Matrix-Geometric Solutions in Stochastic Models," The John Hopkins University Press, 1981.  Google Scholar

[10]

W. K. Grassmann, Real eigenvalues of certain tridiagonal matrix polynomials with queueing applications, Linear Algebra and Its Applications, 342 (2002), 93-106. doi: 10.1016/S0024-3795(01)00462-1.  Google Scholar

[11]

W. K. Grassmann and J. Tavakoli, A tandem queue with movable server: an eigenvalue approach, SIAM J. Matrix Anal. Appl, 24 (2002), 465-474.  Google Scholar

[12]

W. K. Grassmann and S. Drekic, An analytical solution for a tandem queue with blocking, Queueing Systems, 36 (2000), 221-235. doi: 10.1023/A:1019139405059.  Google Scholar

[13]

R. A. Horn and C. R. Johnson, "Topics in Matrix Analysis," Cambridge University Press, 1999. Google Scholar

[14]

J. Y. Le Boudec, Steady-state probabilities of the PH/PH/1 queue, Queueing Systems, 3 (1988), 73-88. doi: 10.1007/BF01159088.  Google Scholar

[15]

H. Luh, Matrix product-form solutions of stationary probabilities in tandem queues, Journal of the Operations Research, 42 (1999), 436-656.  Google Scholar

[16]

A. Van De Liefvoort, The waiting-time distribution and its moments of the PH/PH/1 queue, Operations Research Letters, 9 (1990), 261-269. doi: 10.1016/0167-6377(90)90071-C.  Google Scholar

[17]

V. Wallace, "The Solution of Quasi Birth and Death Processes arising from Multiple Access Computer Systems," Ph. D. diss., Systems Engineering Laboratory, University of Michigan, Tech. Report N 07742-6-T, 1969. Google Scholar

[1]

Sung-Seok Ko. A nonhomogeneous quasi-birth-death process approach for an $ (s, S) $ policy for a perishable inventory system with retrial demands. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1415-1433. doi: 10.3934/jimo.2019009
[2]

Michiel De Muynck, Herwig Bruneel, Sabine Wittevrongel. Analysis of a discrete-time queue with general service demands and phase-type service capacities. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1901-1926. doi: 10.3934/jimo.2017024
[3]

Zhenquan Zhang, Meiling Chen, Jiajun Zhang, Tianshou Zhou. Analysis of non-Markovian effects in generalized birth-death models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3717-3735. doi: 10.3934/dcdsb.2020254
[4]

Jacek Banasiak, Marcin Moszyński. Dynamics of birth-and-death processes with proliferation - stability and chaos. Discrete & Continuous Dynamical Systems, 2011, 29 (1) : 67-79. doi: 10.3934/dcds.2011.29.67
[5]

Hilla Behar, Alexandra Agranovich, Yoram Louzoun. Diffusion rate determines balance between extinction and proliferation in birth-death processes. Mathematical Biosciences & Engineering, 2013, 10 (3) : 523-550. doi: 10.3934/mbe.2013.10.523
[6]

Jacek Banasiak, Mustapha Mokhtar-Kharroubi. Universality of dishonesty of substochastic semigroups: Shattering fragmentation and explosive birth-and-death processes. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 529-542. doi: 10.3934/dcdsb.2005.5.529
[7]

Genni Fragnelli, A. Idrissi, L. Maniar. The asymptotic behavior of a population equation with diffusion and delayed birth process. Discrete & Continuous Dynamical Systems - B, 2007, 7 (4) : 735-754. doi: 10.3934/dcdsb.2007.7.735
[8]

Jacques Henry. For which objective is birth process an optimal feedback in age structured population dynamics?. Discrete & Continuous Dynamical Systems - B, 2007, 8 (1) : 107-114. doi: 10.3934/dcdsb.2007.8.107
[9]

Xianlong Fu, Dongmei Zhu. Stability results for a size-structured population model with delayed birth process. Discrete & Continuous Dynamical Systems - B, 2013, 18 (1) : 109-131. doi: 10.3934/dcdsb.2013.18.109
[10]

Abdon E. Choque-Rivero, Iván Area. A Favard type theorem for Hurwitz polynomials. Discrete & Continuous Dynamical Systems - B, 2020, 25 (2) : 529-544. doi: 10.3934/dcdsb.2019252
[11]

Evgeny L. Korotyaev. Estimates for solutions of KDV on the phase space of periodic distributions in terms of action variables. Discrete & Continuous Dynamical Systems, 2011, 30 (1) : 219-225. doi: 10.3934/dcds.2011.30.219
[12]

Dongxue Yan, Xianlong Fu. Asymptotic analysis of a spatially and size-structured population model with delayed birth process. Communications on Pure & Applied Analysis, 2016, 15 (2) : 637-655. doi: 10.3934/cpaa.2016.15.637
[13]

Dongxue Yan, Yu Cao, Xianlong Fu. Asymptotic analysis of a size-structured cannibalism population model with delayed birth process. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1975-1998. doi: 10.3934/dcdsb.2016032
[14]

Dongxue Yan, Xianlong Fu. Long-time behavior of a size-structured population model with diffusion and delayed birth process. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021030
[15]

Purshottam N. Agrawal, Thakur Ashok K. Sinha, Avinash Sharma. Convergence of derivative of Szász type operators involving Charlier polynomials. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021016
[16]

V. S. Manoranjan, Hong-Ming Yin, R. Showalter. On two-phase Stefan problem arising from a microwave heating process. Discrete & Continuous Dynamical Systems, 2006, 15 (4) : 1155-1168. doi: 10.3934/dcds.2006.15.1155
[17]

Yuzhou Tian, Yulin Zhao. Global phase portraits and bifurcation diagrams for reversible equivariant Hamiltonian systems of linear plus quartic homogeneous polynomials. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 2941-2956. doi: 10.3934/dcdsb.2020214
[18]

Victor Meng Hwee Ong, David J. Nott, Taeryon Choi, Ajay Jasra. Flexible online multivariate regression with variational Bayes and the matrix-variate Dirichlet process. Foundations of Data Science, 2019, 1 (2) : 129-156. doi: 10.3934/fods.2019006
[19]

Sang-Gyun Youn. On the Sobolev embedding properties for compact matrix quantum groups of Kac type. Communications on Pure & Applied Analysis, 2020, 19 (6) : 3341-3366. doi: 10.3934/cpaa.2020148
[20]

Miloud Moussai. Application of the bernstein polynomials for solving the nonlinear fractional type Volterra integro-differential equation with caputo fractional derivatives. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021021

 Impact Factor: 

Tools

Metrics

  • PDF downloads (54)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy