The Use of Eigenvalues for Finding Equilibrium Probabilities of Certain Markovian Two-Dimensional Queueing Problems

Abstract

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 X1 and the phase X2, X1 ≤ 0, 0 ≤ X2 ≤ N. Except for some boundary levels, the rates of the events are independent of the level, and no event can change X1, X2, or X1 + X2 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 signicantly 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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 20 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.