Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 15A16, 60K25, 40C05.


    \begin{equation} \\ \end{equation}
  • [1]

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


    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.


    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.


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


    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.


    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.


    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.


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


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


    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.


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


    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.


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


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


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


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(74) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint