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

Hsin-Yi  Liu; Hsing Paul Luh

doi:10.3934/naco.2011.1.691

Article Contents

2011, Volume 1, Issue 4: 691-711. Doi: 10.3934/naco.2011.1.691

This issue Previous Article Analysis of the statistical time-access fairness index of one-bit feedback fair scheduler Next Article On the stationary LCFS-PR single-server queue: A characterization via stochastic intensity

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

Received: June 2011

Revised: August 2011

Published: November 2011

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 15A16, 60K25, 40C05.

Citation:

Related Papers

Cited by

References

[1]	R. Bellman, "Introduction to Matrix Analysis," MacGraw-Hill, London, 1960.
[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.
[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.
[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.
[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.
[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.
[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.
[8]	I. C. Gohberg, P. Lancaster and L. Rodman, "Matrix Polynomials," Academic Press, New York, 1982.
[9]	M. F. Neuts, "Matrix-Geometric Solutions in Stochastic Models," The John Hopkins University Press, 1981.
[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.
[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.
[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.
[13]	R. A. Horn and C. R. Johnson, "Topics in Matrix Analysis," Cambridge University Press, 1999.
[14]	J. Y. Le Boudec, Steady-state probabilities of the PH/PH/1 queue, Queueing Systems, 3 (1988), 73-88.doi: 10.1007/BF01159088.
[15]	H. Luh, Matrix product-form solutions of stationary probabilities in tandem queues, Journal of the Operations Research, 42 (1999), 436-656.
[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.
[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.