Efficient Solutions for a Class of Non-Markovian Models

Although the use of embedded Markov chains has been known for some time, the application of this technique has been very ad hoc and has not been established as a standard approach for a wide class of models. Recently however, there has been progress in the direction of identifying an interesting class of models which are not Markovian but which can yield to a well defined solution method based on the analysis of an embedded Markov chain. Example applications that yield to this approach include polling models with deterministic timeout periods and models with deterministic service time queues. In this paper we derive efficient methods for computing both the transition probabilities for the embedded chain and performance measures expressible as Markov reward functions. Calculating the transition probabilities for the embedded chain requires transient analysis, and our computational procedures are based on uniformization. Examples are given to demonstrate the effectiveness of the methods and the extended class of models that are solvable with these techniques.