The use of eigenvalues for finding equilibrium probabilities of certain Markovian two-dimensional queueing problems

A number of papers have appeared recently using eigenvalues for solving steady-state queueing problems. In this paper, we analyze Markovian systems with two state variables, the level X-1 and the phase X-2, X-1 greater than or equal to 0, 0 less than or equal to X-2 less than or equal to N. Except for some boundary levels, the rates of the events are independent of the level, and no event can change X-1, X-2, or X-1 + X-2 by more than 1. In this case, the eigenvectors are essentially Sturm sequences, which implies that all eigenvalues are real. The properties of the Sturm sequences allow us to design an extension of the binary search to find all eigenvalues. As it turns out, once the interval containing an eigenvalue is narrowed down sufficiently, it is preferable to use Newton's method. A computational-complexity study indicates that the resulting algorithm should be significantly faster than matrix-iterative methods. Two numerical examples are discussed involving servers with breakdowns, and in both cases, our method yields highly accurate results. Tentative reasons why this is to be expected are provided.