This research was supported by the National Science Foundation under Grant CDR 8803017 to the Engineering Research Center for Intelligent Manufacturing Systems and by a research grant from the AT&T Foundation.


G/M/1 and M/G/1-type Markov processes provide natural models for widely differing stochastic phenomena. Efficient recursive solutions for the equilibrium and transient analysis of these processes are therefore of considerable interest. In this direction, a new class of recursive solutions are proposed for the analysis of M/G/l and G/M/l type processes. In this report, the notion of when a process is LEDI-complete, which means it has complete Level Entrance Direction Information, is introduced for G/M/1-type Markov processes. This notion leads to a new class of recursive solutions, called finite-memory recursive solutions, for the equilibrium probabilities of a class of G/M/ 1-type Markov processes. A finite-memory recursive solution of order k has the form πn+k = π W1 +π n+1W2 + ••• +πn+k-1 Wk7 where πn is the vector of limiting probabilities of the states on level n of the process and Wi, 1 < i < k, are square matrices. It is also shown that the concept of LEDI- completeness leads to a finite- memory recursive solution for the transient behavior of this class of G/M/-1- type processes. Such a recursive solution has the form πn+k(s) = ^n(s)W1(s) +π n+i(s)W2(s) + • • • + πn+k-i(s)Wk(s). where π(s) is the Laplace transform of πn(t), the vector of state occupancy probabilities at time t for the states on level n of the process. The relationship between these finite-memory recursive solutions and matrix geometric solutions is also explored. The results are extended to the case where the transition rates are level dependent. It is also briefly explained how a finite memory recursion for the equilibrium and transient probabilities of M/G/l type Markov processes can be obtained.

Date of this Version