La. a 8, meres' SUPERPOSITION OF MARKOV RENEWAL PROCESSES AND THEIR APPLICATIONS C. Teresa Lam Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109-2117 Technical Report No. 90-21 August 1990, Revised January 1991, Revised May 1992 Submitted to Advances in Applied Probability

Superposition of Markov Renewal Processes and Their Applications C. Teresa Lam* Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, MI 48109 Abstract In this paper, we study the superposition of finitely many Markov renewal processes with countable state spaces. We define the S-Markov renewal equations associated with the superposed process. The solutions of the S-Markov renewal equations are derived and the asymptotic behaviors of these solutions are studied. These results are applied to calculate various characteristics of queueing systems with superposition semi-Markovian arrivals, queueing networks with bulk service, system availability, and continuous superposition remaining and current life processes. S-MARKOV RENEWAL EQUATION; SUPERPOSITION MARKOV RENEWAL THEOREM; SUPERPOSITION OF MARKOV RENEWAL PROCESSES; QUEUES WITH SUPERPOSITION SEMI-MARKOVIAN ARRIVALS; QUEUEING NETWORKS WITH BULK SERVICE; STATE DEPENDENT SERVICE RATES; SYSTEM AVAILABILITY; CONTINUOUS SUPERPOSITION REMAINING AND CURRENT LIFE PROCESSES AMS 1991 SUBJECT CLASSIFICATION: PRIMARY 60K15 SECONDARY 60K10; 60K20 *Research Supported in part by a fellowship from Horace H. Rackham School of Graduate Studies, The University of Michigan. 1

1 Introduction The problem of superposing two or more stochastic processes has been dealt with in a number of ways in previous research. One of these was originated by Palm (1943-1944) in his work of telephone traffic. He conjectured that under appropriate conditions, the superposition of a large number of uniformly sparse processes can be approximated by a Poisson process. This provides a theoretical basis for the use of a Poisson arrival process in many queueing models. Since then, the conjecture and related results have been discussed and proved by many authors. Some authors also considered the problem of finding necessary and sufficient conditions such that the superposition of finitely many processes is a renewal process or a Poisson process. The paper by Cinlar (1972) is an excellent review of these areas. Other works in the superposition of two or more streams concentrate on obtaining the distributions of the intervals between events or the distributions of counts in events in the superposed processes. The papers by Cox and Smith (1954), Lawrance (1973), Kshirsagar and Becker (1981) are devoted to these tasks. Their results were applied to the study of neuron firing and predator-prey models. Recently, Lam and Lehoczky (1991) considered the problem of the superposition of finitely many renewal processes, and studied the asymptotic behavior of the superposed process when the time t is large. In particular, they generalized the concepts of renewal functions, renewal equations and the key renewal theorem to the superposition of renewal processes. They applied their superposition key renewal theorem to the study of (ZP=1 GIi)/M/1/1 queueing systems. In this paper, we consider the superposition of finitely many Markov renewal processes defined on countable state spaces, and again, we study the asymptotic behavior of the resulting superposed process. In particular, we define the S-Markov renewal equation, and show that under appropriate conditions, the solution of this equation exists and is unique. Furthermore, by letting t -- oo, we derive the superposition Markov renewal theorem. The S-Markov renewal equations and superposition Markov renewal theorem are generalization of the S-renewal equations and the key superposition renewal theorem in Lam and Lehoczky (1991) to the superposition of Markov renewal processes. Also, it is a generalization of the Markov renewal equations and Markov renewal theorem introduced in Cinlar (1969a). 2

The superposition of two independent Markov renewal processes with countable state spaces was studied before by Cherry (1972), Cherry and Disney (1983). In these papers, they showed that the superposed process is again a Markov renewal process defined on a more general state space. The structures and properties of this general state space Markov renewal process were studied in detail. The same argument can be extended to show that the superposition of more than two (finitely many) independent Markov renewal processes with countable state spaces is also a Markov renewal process defined on a general state space. Hence, the superposed process is a special case of the semi-Markov processes on arbitrary state spaces defined in Cinlar (1969b). The S-Markov renewal equation defined in this paper is a special case of the fundamental equation defined in Cinlar (1969b) for an arbitrary state space semi-Markov process. The solutions of the fundamental equations and their asymptotic behaviors were studied in Cinlar (1969b) and Kesten (1974). In this paper, we show that the same results hold for the S-Markov equations under less restrictive assumptions and apply these results to study queueing and reliability problems. It is also worth pointing out here that the superposition of finitely many independent Markov renewal processes can also be modeled by a generalized semi-Markov process. More details will be given in Section 3 Example 2. Generalized semi-Markov processes have been widely studied in the literature, see for example, Schassberger (1976, 1977, 1978a, 1978b, 1978c), Burman (1981), Barbour (1982) and references there. The existence of stationary distributions of these processes as well as a certain insensitivity property of those distributions were studied in these papers. These results have been applied to study insensitivity properties of certain queueing or reliability problems. Just like the superposition of finitely many independent Markov renewal processes, generalized semi-Markov processes are also special cases of semi-Markov processes on arbitrary state spaces introduced by Cinlar (1969b). As shown in Cinlar (1969a, 1975b), Markov renewal equations and the related limit theorems have been applied to the study of steady state behavior of queueing systems, probability that a system is working at. time t when t is large, and distribution of the delay to a pedestrian in traffic theory. Cherry and Disney (1983) applied their results to describe the joint departure process of two independent M/G/1 queues and a classic problem in machine repair and maintenance. In 3

this paper, we show that the extension of the Markov renewal theorem or the key superposition renewal theorem to the superposition of finitely many independent Markov renewal processes enables us to analyze more complex queueing systems or reliability problems. In particular, the main theorem in this paper allows us to study the characteristics of a single server queue with superposition semi-Markovian arrivals and no waiting room, and the system availability of a device with different types of components connected both in series and in parallel. The paper is organized as follows: In Section 2, we present definitions and results of Markov renewal theory from the literature which are useful to us in later sections. The S-Markov renewal equations are defined in Section 3. The solution of the S-Markov renewal equation is also presented in the same section. In Section 4, we study the asymptotic behavior of the solution of the S-Markov renewal equation and apply it to various examples. This leads to the generalization of the Markov renewal theorem and the superposition key renewal theorem to the superposition Markov renewal theorem. Theorems stated in Sections 3 and 4 are proved in Section 5. 2 Preliminaries In this section, the definitions of Markov renewal processes and delayed Markov renewal processes are given. Some notations are also defined which will be referred to in later sections. For each n E JAV = {0, 1,2,...}, let Xn be a random variable taking values in a countable set E, and Tn be a random variable taking value in 2R+ = [0, oo) such that 0 = To < T1 < T2 <.... In this paper, we view To, T1, T2,... as the successive times of occurrence of some events and we think of Xn as the type of the event that has occurred at time T,. Definition 2.1 The stochastic process (x,X,T) = {x,X,,T; n E IN} is said to be a Markov renewal process with state space E and initial state x E E provided that Xo = x and for all n E IN, y E E, and t E JR+, P(Xn+l = y,Tn+1 - Tn < t I Xo,...,Xn;To,... * Tn) P(Xn+l= y,Tn+l - Tn t Xn). (2.1) 4

Furthermore, given any x,y E E, t E 1R+, P(Xn+ = y,Tn+ - Tn < t Xn = x) = Q(x, y, t) (2.2) independent of n E IN. The family of probabilities Q = {Q(x, y,t);ax,y E E,t E iR+} is called a semi-Markov kernel. Let F(x,t) = EyE EQ(,y t) and m(x) = fo0 (1 - F(x,t))dt. Thus, F(x, t) is the probability distribution of the sojourn time of the process in state x E E and the expected sojourn time during each visit to x is given by m(x). Note that we are allowing m(x) = +oo for some x E E. Define the age (current life) of the process at time t to be the time since the last event occurred in the process. For each x E E, define u(x) = sup{t E 1R+: F(x,t) < 1}. If F(x,t) < 1 for all t E R+, then define u(x) = oo. Definition 2.2 The stochastic process (x,a,X,T) = {x,a,Xn,,T; n E IN} is said to be a delayed Markov renewal process with state space E, initial state x E E and initial age 0 < a < u(x) if Xo = x, Equation (2.1) holds for all n E N, Equation (2.2) holds for all n E {1, 2,...}, and P(X1 = y, T - To < t I Xo = x) = Qa(x,y,t) where Qa(x,,t) Q(x, y, t + a) - Q(x, y, a) 1 - F(x, a) and F(x,a) < 1 for all 0 < a < u(x), x E E. Define Qa(x,y,t) = 0 if a < 0 or a > u(x). Note that Qa(x,y,t) is the probability that knowing the current state is x and the age of the process is a, the next transition state is to state y and the remaining sojourn time in the current state is less than or equal to t. Let Fa(x,) = yEE Qa(x, y, t). Denote the delayed Markov renewal process with initial age a and initial state x by N(x, a). If a = 0, a delayed Markov renewal process becomes a Markov renewal process. The Markov renewal process defined here is the same as the time homogeneous Markov renewal process given in Cinlar (1975a). Consider the class of bounded functions Q: these are functions f: E x E x iR+ -- iR+ such that for all x, y E E, the function t i f(x, y, t) is nondecreasing and continuous from the right. 5

For t E R+, let f,g E G and define the convolution of f and g, denoted by f *g, by f*g(x,y,t) = Z f (x,) z, ds) gy, t - s). tE It] For all t E R+, let if y = x Q~(x,y, t) = I(x,y) =- - 0 otherwise and for n > 0, define recursively Qn+l(x, y,t) = Q * Qn(x, y,t). Note that Qn(x, y, t) E q and Ql(x,y, t) = Q(x,y,,t). To avoid certain difficulties, for the remainder of the paper, we assume that n(x, y, O) = 0 for all x, y E E and n E IV. This means that instantaneous transitions are impossible. With probability one, a non-zero time is spent between transitions. Now, put H = - =1Qn, R = E=o Qn, Ha = Q * R and Ra = I + Ha. The functions t - H(x, y, t) are called Markov renewal functions and the collection H = {H(x, y, ); x, y E} of these functions is called a Markov renewal kernel of the Markov renewal process with initial state x. H(x, y, t)l is the expected number of visits of this process to state y in the time interval (0, t]. Define H(x, t) = EYEE H(x, y, t). It is the expected number of transitions in the process during (O,t]. Similarly, define the functions t H Ha(x,y,t) to be the delayed Markov renewal functions and the collection Ha = {Ha(x, y, *);, xy E} of these functions to be the delayed Markov renewal kernel of the delayed Markov renewal process with initial state x and initial age a. Ha(x, y, t) is the expected number of visits of this delayed Markov renewal process to state y in the time interval (O,t]. Also, Ha(x,t) = yEE Ha(x,y,t). It is the expected number of transitions in the delayed process during (0, t]. Let P(x,y) = Q(x,y,,oo) and P be the matrix {P(x,y);x,y E E}. Consider the Markov chain X induced by P. Throughout the remainder of this paper, we shall assume that all the Markov renewal processes are irreducible recurrent aperiodic. Let A be a strictly positive invariant measure for a Markov renewal process X, i.e., for all y E E, A(x)P(x, y) = A(y). xEE'Unlike the Markov renewal functions defined in Cinlar (1975a), we exclude the event that takes place at the origin. 6

From Cinlar (1975a), the mean recurrence time of state x in N(x, a) is given by Am/A(x) where Am = YEyE A(y)m(y). It is understood that the mean recurrence time is +oo00 if m(x) = +oo or Am = +oo. Define a new kernel Q by A(y)Q(y,x,t) = A(x)Q(x,y,t). From Cinlar (1969a, 1975a), Q is again a semi-Markovian kernel. Furthermore, if H are the Markov renewal functions corresponding to Q, then A(y)H(y, x, t) = A(x)H(x, y, t) (2.3) and H(x,x,t) = H(x,x,t). Let G(x,y,t) be the distribution of the first passage time of the Markov renewal process with semi-Markov kernel Q to move from state x to state y. Then H(x, y, t) = G(x, y) * R(y, y)(t) = G(x, y, ds)R(y, y,t - s). [,t] * here represents the usual convolution. Let Ga(x, y, t) be the distribution of the first passage time of the delayed Markov renewal process with semi-Markov kernel Q, initial age a and initial state x to enter state y. Similarly, if G(y, x, t) is the distribution of the first passage time of the Markov renewal process with semi-Markov kernel Q to move from state y to state x, then H(y, x, t) = G(y, x) * R(x, x)(t). (2.4) In this paper, all the Markov renewal processes are assumed to be conservative, this means that P(supnENTn < oo) = 0. Let {X(t);t E JR+} be the semi-Markov process associated with the Markov renewal process (x,X,T). Define N(t) to be the number of transitions in the process during the time interval (0,t]. Write V+(t) = TN(t)+l - t and V-(t) = t - TN(t) Call {X(t),V+(t);t E R+} and {X(t),V-(t);t E 1R+} the continuous remaining and current life processes associated with the Markov renewal process. From Cinlar (1969a), provided that the Markov chain X is irreducible recurrent aperiodic, then lim P[X(t) = y,V+(t) > v X(O) x] = lim P[X(t) = y,V-(t) > v I X(O) = x] t —oo t-0oo =*A(y) |v, [1 - F(y, u)] du. (2.5) Am (v,oo) Other properties of Markov renewal processes or semi-Markov processes can be found in Pyke (1961a, 1961b, 1964, 1966) and Smith (1955). 7

3 S-Markov Renewal Equations In this section, the definition of the S-Markov renewal equation for the superposition of Markov renewal processes is given. The S-Markov renewal equation is a generalization of the S-renewal equation for the superposition of renewal processes introduced in Lam and Lehoczky (1991) to the superposition of Markov renewal processes. It will be shown that under some regularity conditions on the component Markov renewal processes, the solution of the S-Markov renewal equation exists and is unique. Suppose that there are p > 2 independent delayed Markov renewal processes in operations simultaneously. From now on, S = {1,2,...,p} and the subscript i refers to the ith component process. Let Ei be the state space of the ith process, put E = El x... x Ep. Suppose that, at time 0, the processes have ages al,...,ap and in states x1,...,p. Let x = (1i,.., Xp) and a = (al,...,ap). Let Tn be the time of the nth event in the superposition process, and let Yn = (Yn,... Ynp) and An = (An1,..., Anp) be the vectors indicating the states and ages of the component processes at time Tn. Put Zn = (Y,,An) and let a = miniESai. Denote the superposition process by N(x, a) and let N(x, a, t) = max{n E V: Tn < t}. The same argument extended to p > 2 in Cherry and Disney (1983) can be used to show that the stochastic process ((x, ),a, Z, T) is a delayed Markov renewal process with state space l = E x JR., initial state (x, &) = (x1,..., xp, a, - a,..., ap - a) and initial age a. The semi-Markov kernel Q of this Markov renewal process can be computed from the Qi. Let F be the class of functions f: Ex IRp'+l -- R+ such that (x, a) - f(x, a, t) is bounded for each t, and (a, t) f(x,a, t) is Borel measurable in a and right continuous in t. Note that, then, t f(x, a, t) is bounded over bounded intervals. Define the convolution of f E F and Q, denoted Q * f, by Q * f(x,a, t) (3.1) YE Ji+ Q-((x, ), (y, db), du)f(y, b, t - u) Y EE,, t] j i E yi E, (xi, yi, du) {J[1 - F (xu)] f(ri(x,y ),si(a,u), t-u) where Si = S \ {i}, for any i E S, ri: E x Ei -+ E is a function such that ri(x,y) = 8

(X1,... -, X Y,Z+1,..,xp) and s: lRp+ - JRP+ is a function such that si(a,u) = (al + u,..., ai- + u, 0, ai+1 + u,..., ap + u). Note that Q * f E OF. A function f E F is said to satisfy an S-Markov renewal equation if for all x E E, a E /R+ and t E /R+, f(x, a, t) = g(x, a, t) + Q * f(x, a, t) (3.2) for some function g E F. Equation (3.2) reduces to the S-renewal equation considered in Lam and Lehoczky (1991) if for all i E S, Ei consists of a single point (I Ei 1= 1). When p = 1, the S-Markov renewal equation becomes the Markov renewal equation given in Cinlar (1969a, 1975a, 1975b). If p = 1 and I El 1= 1, the S-Markov renewal equation reduces to the ordinary renewal equation. Examples: 1. It is not difficult to verify that f(x,a,t) = E[N(x,a,t)] = EiES Hi"(xit) satisfies the S-Markov renewal equation with g(x, a, t) = 1 - IEs[1 - FIi(xi, t)]. 2. Let X(t) = (Xl(t),...,Xp(t)),V+(t) = (VI+(t),...,V+(t)) and V(t) = (V1-(t),...,V (t)) where Xi(t), Vi+(t) and Vi-(t) are defined in Section 2. Call (X(t), V+(t)) and (X(t), V-(t)) the continuous superposition remaining and current life processes respectively. The process X is a generalized semi-Markov process. (X,V+) and (X,V-) are both supplemented generalized semi-Markov processes as discussed in Schassberger (1977, 1978b) and Burman (1981). Let W+(t) = TN(x,a,t)+l - t and z = (Z,...,Zp) E E. Now fz,w(x,a,t) = P[X(t) = z,W+(t) > w | (X(O),V-(O)) = (x,a)] satisfies the S-Markov renewal equation with gz,w(x, a, t) = I(x, z) RiES[1 - Fai (xi, t + w)] where I(x, z) = 1 when z = x and zero otherwise. 3. Queues with superposition semi-Markovian arrivals: Consider a single server queueing system with no waiting room. The arrival process is the superposition of p independent point processes. For the ith arrival process, suppose there are Ni types of customers. Ni here may be finite or infinite. Let Xi,, be the type of the nth arriving customer in the ith stream, n E IV and Xi, = i = = {1,2,...,Ni}. Let the instants of arrivals be -aiTi,,Ti,2,.... Suppose (ai,xi,Xi,Ti) = {aixi,Xi,,Ti,;n E IN} can 9

be modeled by a delayed Markov renewal process. We assume that the service times are independent and identically distributed whose common distribution function is 1 - egrt, t E JIR+. There is no waiting room in this system. This means that a customer arrives and finds the server busy leaves the system and never returns. Assume that at time t = 0, the server is busy. Let f(x,a, t) be the probability that the server is busy at time t and X be an exponentially distributed random variable with parameter P. Conditional on the time T1 of the first arrival in the superposed process, and using the memorylessness property of the exponential distribution, we have 1 T1 > t and X > t f(x,a,t)= 0 T > t and X t (3.3) f(ri(x, yi),si(a, u), t - u) T1 = u < t and I1 = (i, yi) where Ij = (i, yi) indicates that the jth arrival to the system comes from the ith component process and is of type yi. f(x, a, t) satisfies the S-Markov renewal equation with g(x,a,t) = P(T1 > t,X > t) = e-'t I[i - Fa(i,t)]. (3.4) iES The queueing system (PZ=1 GIi)/M/1/1 studied in Lam and Lehoczky (1991) is a special case of our problem where Ni = 1 for all i E S. Queues with a single semi-Markovian arrival stream were studied by Cinlar (1967). It is well known that the output of a M/G/1 queue with either finite or infinite waiting room is a semi-Markov process whose states are queue sizes. Suppose that there are p independent M/G/1 queues, the merged output of these p M/G/1 queues becomes the input of a single server queue with no waiting room. Call this the second stage queue. The queueing characteristics of the second stage queue with superposition semi-Markovian arrival streams can be studied by the methods in this paper. There are other instances where the output processes of M/G/1 queues can be characterized by semi-Markov processes. For example, the number of customers served during a service time, instead of being one, is a random variable depending on the number of customers in the system just at the start of that service. The queue lengths after departure together with the times between departures form a semi-Markov process. For details on semi-Markov analysis of a bulk queue, see Neuts (1965, 1966). Similarly, we can allow the 10

service times of the M/G/1 queues to be dependent on the queue size. Again, we have a Markov renewal process whose states are queue sizes after departure. Suppose there are p independent M/G/1 queues with bulk service or state dependent service times, and the merged output from these queues becomes the input of a single server queue with exponential service times and no waiting room. Call this queue the second stage queue. In the case of the bulk service queues, assume that customers in the same batch are also served at the same time by the server in the second stage queue and the service times are independent of batch size. Equations (3.3) and (3.4) above can be used to study the blocking probability at time t of the second stage queue. 4. System availability: Consider a device with p components connected in parallel. The device is not working when all the components are under repair. The ith component consists of a finite number of subcomponents connected in series. There are Ni < oo different types of subcomponents for component i, i E S. If any one subcomponent fails, the whole component fails. Let Xi,n be the type of the subcomponent causing the nth failure in the ith component and -ai, Ti, Ti,2,... be the times of successive failures. The times Ti,n+l - Ti,n n > 1, between two failures are the sum of the repair time of the subcomponent which failed at Ti,, and a failure free interval following the repair. Furthermore, Ti,1 + ai is also the sum of the repair time of the subcomponent which failed at time -ai and a failure free interval following the repair. Assume Xi,o = E Ei = {1, 2,..., Ni}, i E S. We suppose that subcomponent of type yi in the ith component has exponential lifetimes with parameter 4(i, yi), and suppose its repair time has distribution (i, yi,.). Under these assumptions, the failure process of the device can be modeled by the superposition of p delayed Markov renewal processes. Let Z(t) = (i, zi) if the last failure before time t comes from the ith component and is of subcomponent type zi. Define W(t) to be equal to 1 or 0 according as the device is working or under repair at time t. Let fi,z,(x,a,t) = P[Z(t) = (i,zi),W(t) = 0 | (X(O),V-(O)) = (x,a)] where X(O) and V-(O) are defined in Example 2 above. Conditional on the time of the first failure of the subcomponent of the device, fi zi(x, a, t) satisfies the S-Markov renewal equation with gi,z (x,a,t) = I(xi,zi)I(ai = a) nI 1-( Fxjaj) (3.5) j~$ 1 - Fj(xj, aj) 11

where Fj(xj,t) = E Q(xj, t) y3 Ej Qj(xj,yj,t) = J/ k(J, yj)e-(J)up(j, x t - u) du, 0(j) = EyjEEj (j,Yj), I(ai = a) = 1 if aE < aj for all j E S and 0 otherwise. Similarly, I(xi,zi) = 1 when zi = xi and 0 otherwise. As discussed in Section 1, the S-Markov renewal equation is also a special case of the fundamental equation introduced in Cinlar (1969b) for semi-Markov processes on arbitrary spaces. The results derived in Cinlar (1969b) assumed that the functions f and g are bounded. In this paper, we are working with the class of functions F. In Cinlar (1969b), he derived the solutions of the fundamental equations and their asymptotic properties by assuming that the interevent time of the semi-Markov process is independent of the terminating state. Since given any semiMarkov process, we can always define another semi-Markov process such that the interevent time of this new semi-Markov process is independent of the terminating state, the results in Cinlar (1969b) is very general mathematically. In this paper, we present the solutions of the S-Markov renewal equations and their limiting results for the superposition of general Markov renewal processes. Our results can therefore be applied directly to study the queueing and reliability problems above without first defining a new semi-Markov process who interevent time is independent of the terminating state. Note that Equation (3.1) above can be rewritten as Q * f(x,a, t) = x,a[f(Zi, t -Ti)]. Hence, the S-Markov renewal equation can also be written as f(x,a,t) = g(xa,t) + ~x,a[f(Z,t- Ti)]. Theorem 3.1 Suppose that t i- supxiEi Hi(xi,t) is bounded on bounded intervals. Then, for each g E F there is a unique f E T that is the solution of the S-Markov renewal equation (3.2). That f is f(x, a, t) = g(x, a, t) + Ug(x, a, t) (3.6) 12

where the second term, Ug(x,a, t), is given by YEEiES t] L{H L Ha' ((xi\L,yi,dvi) X k l ax- dFk (yk, Vi Vk)] yeE iES LCS_ kES]\L [ X I 1 - Fj(xj, aj + vi)I(xj, yj) g(y, b, t - vi) j 1 - Fj(xj, aj) where I(x, y) is 1 or 0 as x = y or x $ y, and b = (bl,...,bp) is given by ak + vi if kE L bk= vi-Vk ifkESi\L ~ (3.7) 0 if k = i The proof of the theorem will be given in Section 5. Here, we offer some explanatory comments. The function t |- supxiEE, Hi(xi,t) is bounded on finite interval ensures that regardless of initial state, the expected number of transitions in the delayed Markov renewal process is finite on bounded interval. Note that this condition is stronger that the regularity assumption defined in Cherry (1972), Cherry and Disney (1983), Pyke (1961), Pyke and Schaufele (1964). The expression for Ug(x,a,t) may be explained as follows: There is a last event around the time vi, that event belongs to the ith component process and is of type Yi. The set L is the collection of component processes j that have no events during [O,t]. The processes k outside L U {i} have at least one event during [0, vi], its last event around the time vk < vi and is of type Yk. Examples: 1. When g(x, a, t) = 1 if t E JR+ and 0 otherwise, it is easily checked that the solution of the S-Markov renewal equation is given by f(x,a, t) = 1 + EiEs Hi'(xi, t). 2. For each i E S, let gi: Ei x JR+ -- R+ be a function such that for every xi E Ei, the function t - g(xi,t) is bounded over finite intervals, and for every fixed t E JR+, the function x; i g(xi,t) is bounded. When f(x,a,t) = IEs{g(xi, a + t)/[l - Fi(xi, ai)]} an argument similar to the proof of Corollary (2.3) in Lam and Lehoczky (1991) applies to show that the solution of the S-Markov renewal equation is also of product form. The 13

solution is Axg, a t)xi, ai + t) + Hai (,,yi,ds)gi(yi t s f(x,a, t) = I.I - Fi(xi,ai + i i, )it - ) Now, letting t - oo and using the Markov renewal theorem, provided that for all i S, gi is directly integrable with respect to Ai as defined in Cinlar (1975a), we have lim f(x a, t)- iE A(y) gi(yi,u)du. ~00 i'ES [Ay EEE AimMi + We know from above that fz,w(x,a,t) = P[X(t) = z,W+(t) > w | (X(O),V-(O)) = (x,a)] satisfies the S-Markov renewal equation with gz,u,(x, a, t) = I(x, z) nES[l1 - Fi(xi, t + w)]. gz,w(x,a, t) therefore has the required product form. Hence, lim P[X(t) = z,W+(t) > w | (X(O),V-(O)) = (x,a)] t —oo = n Aimi wo [l -Fi u)] d (3.8) which is the product of the individual limiting continuous remaining or current life distributions of the component processes. A Similar argument in Cinlar (1969a) page 163 can be used to show that limiting distribution of the continuous superposition current life process is also given by Equation (3.8). 3. Similarly, we can write down the solutions of the S-Markov renewal equations when g(x, a, t) are given by Expressions (3.4) and (3.5) in the queueing and system availability examples above. These solutions look rather complicated. However, in the next section, it will be shown that as t -* oo, the limit of the solution f(x, a, t) exists and the resulting expression is very simple. 4 Superposition Markov Renewal Theorem and Applications In this section, it will be shown that under some regularity conditions on g(x,a, t), in the limit as t -- oo, the limit of f(x,a,t) exists and is independent of both the initial ages and states of the individual delayed Markov renewal processes. This result is a generalization of the key 14

superposition renewal theorem in Lam and Lehoczky (1991) and the Markov renewal theorem in Cinlar (1969a, 1975a, 1975b). Before the theorem is given, we need the following two definitions. Definition 4.1 Let h be a function defined on R1+. For every positive 6, n = (nl,...,np) and p, ni 1,2,..., i E S, let hn(6) = inf{h(b) (ni - 1)6 < bi < ni6; i E S}, hn(6) = sup{h(b) (ni - 1)6 < bi < ni6; i E S}, oo 00 h(6) = E E kn() and h(6) = P E E n(6). iES ni=l iES ni=l Then h is said to be directly Riemann integrable (notation: h E D(1P )) if both series h(6) and h(S) converge absolutely for every positive 6, and the difference h(6) - h(6) goes to 0 as 6 -- 0. If h e D(1ip+), then lim h(S) = lim h(6) = h(b) db. 68-4O 86 —0 J Definition 4.2 Let h be a function defined on E x IR+ and v be a positive measure on E. For every positive 6, n = (nl,..., n), p,ni = 1,2,..., i E S and y E E, let hn(6) = = v(y)inf{h(y,b) (ni - 1)56 bi < ni;; i E S}, yEE hn(6) = v(y) sup{h(y,b): (ni - 1)6 < bi < ni6; i E S}, yEE h(6) = 6 E E Ahn() and (6) = bP E E hn(). iES ni=l iES ni=l Then h is said to be directly Riemann integrable with respect to v (notation: g E D,( R+)) if both series h(6) and h(6) converge absolutely for every positive 6, and the difference h(6) - h(6) goes to 0 as 6 -, 0. For i E S and b E R., define Kig(y, b,t) = g(y, ib, t) n [1 - Fk(yk,bk)] kESi 15

where Iib = (bi,..-, bi_ bi+l,... bp), and let Pi(db) = db1... dbi-ldb+l... dbpo(dbi). Note that 60 is the Dirac delta function. For any nonempty L C S and y E E, let AL(y) = HeL Ai(yi), and in particular put A(y) = As(y) = HiES Ai(yi). Theorem 4.3 (Superposition Markov Renewal Theorem) Let g E F and let f be the solution of the S-Markov renewal equation (3.2). Suppose that t - supZiEEi Hi(xi, t) is bounded on finite intervals, Kig considered as a mapping from E x JRP+ into JIR+ (mapping (y, b,..., bi,, bi,...., bp, t) into Kig(y, b, t)) is directly Riemann integrable with respect to AL for every nonempty L C S with i E L, and for each fixed y E E, Kig(y, *) considered as a mapping from R+P -^ 1R+ (mapping (bl,..., bi_1, bi+1,..., b,, t)) is directly Riemann integrable. Then, lim f(x,a,t) = du. (4.1) lim f (X7 a, t)=js jm [C i ~ A(y) du pi (db)Kig(y, b, u). (4.1) t +00 VES / Ajmj iY EEES + + Proof: The proof will be given in Section 5. Note that in Equation (4.1), J 1ii(db)Kig(y, b, u) = f db... d-dbil... dbpKig(y, ib, t). If the imbedded Markov chains, Xi, are all irreducible recurrent aperiodic nonnull, then there exist invariant measures Ai for Xi, i E S such that EziEE Ai(zi) = 1. In this case, Result (4.1) can be rewritten as li f(x,a, t)= ( j { ~[((Y, A), u)]du} t-oo' Ajmj where 1. From Lam (1990), 1 /E[,Es(1 /A7m;)] is the mean interevent time of the stationary superposed process and Aimi is the mean interevent time of the ith stationary Markov renewal process. 2. (Y,A) is a random row vector such that (Y,A) = (Yl,..., Yi-l, i, Yi+1.-. Yp,Ai,...,Ai-lx,0,Ai+l,...,Ap) 16

with probability (1/Aimi)/[EjEs(1/Ajm)]. P(Yi = ys) = Ai(y2), yi E Ei. {(Yi,Ai)}iEs are independent pairs of random variables such that for all yi E Ei and w E JR+, P(Yi = Y, Ai > w) -= A(y) ( [1 - Fi(yi, u)] du. (4.2) A imi (w,oo) Note that (4.2) is just limiting continuous remaining or current life distribution given in Equation (2.5). As mentioned earlier on that the stochastic process ((x,a),a,Z,T) is a delayed Markov renewal process with state space Q = E x R'+, it is not difficult to show that Zn is a Markov chain (discrete time superposition current life process) with state space Q. Furthermore, from Lam (1990), Z, has a unique stationary distribution which is the same as the distribution of (Y, A). Hence, the superposition Markov renewal theorem study here is closely related to the renewal theorem given by Kesten (1974) for a Markov chain with separable metric state space. However, the conditions of the theorem given in Kesten (1974) are restrictive, very unintuitive and hard to check in practice. See also Jacod (1971, 1974) for other results related to those of Cinlar (1969b) and Kesten (1974). Examples: 1. Queues with superposition semi-Markovian arrivals: In this example, f(x,a,t) is the probability that the server is busy at time t and it satisfies the S-Markov renewal equation with g(x,a, t) given by Expression (3.4). By the superposition Markov renewal theorem, lim f(x, a, t) (4.3) t- o0 - Z (yE ) f V[1 F(yv)]j) [1- Fj(yj,u)] du dv. iESyEE Ai(Yi) { e lS-Fi(y )] { I,5 Ai} Suppose the ith semi-Markov arrival stream is the output of a M/G/1 queue with infinite waiting room. Assume that the arrival rate of this M/G/1 queue is ai and the mean service time is,i. Provided that aOii is strictly less than one for all i E S, the stationary distribution Ai exists for each Markov chain Xi. The stationary distribution Ai is derived in Cinlar (1975a) and its generating function is given in Prabhu (1965) and Cherry (1983). Furthermore, from Cherry (1983), Aimi = l/a;,. The function Fi(yi,t) = EzEE, Qi(yi,zit) and the matrix Qi(t) = {Qi(yz, t);yi,Zi E E E} are also given in Cinlar (1975a). 17

Similarly, the stationary distribution and the semi-Markov kernel of the queue length at departure points of a M/G/1 queue with finite waiting room, bulk service or state dependent service times are given in Cinlar (1975a), Neuts (1966) and Harris (1967a, 1967b) respectively. Substituting those expressions into Equation (4.3), we obtain the limiting blocking probability at time t of the second stage queue. The blocking probability that an arbitrary customer arrives to a stationary second stage queue and finds the server busy is derived in Lam (1990). 2. System availability: From Cinlar (1975a), Example (10.6.23), for i E S, the stationary distribution is given by Ai(Yi) = q(i,yi)/c(i), yi E Ei. If the mean repair time of type yi subcomponent of the ith component is Vi(i,,yi), then mi(yi) =?(i, yi) + [1/~(i)]. Let q(i)+(i) = EyiEi b(i, yi)(i, yi) and q(i, yi) = q(i, yi)/[l + q(i)+(i)]. Now, by the superposition Markov renewal theorem, lim P[Z(t) = (i,zi),W(t) = 0 (X(O),V-(0)) = (x,a)] t-0oo - kzi zi)J [-(i zi, v)]{J7J {Yn Z40)j [1 - p(j, yjuu)]du} dv. J+m {3^[EESi yE, () } ) 5 Proof of Theorems Proof of Theorem 3.1: The proof is a direct extension of the proof of Theorem (2.2) in Lam and Lehoczky (1991) for the superposition of p independent renewal processes. We first verify that f specified by Equation (3.6) fulfills the requisite boundedness properties. First note that by assumption, supX.EE, Hi(xi, t) is bounded over finite intervals, this implies for every finite t E IR+, a = (al,...,ap) E RP+, there exists a finite constant Ct such that P P sup I[1 + Hi'(xi, t)] < sup I[2 + Hi(xi,t)] < Ct. xEE i= xEEi= Also, g E F means that for every finite t E BP+, there exists a finite constant,t such that I g(x,a,t) I< rt for all x E-E and a E 1+. Hence, for each t E lR+, we have 18

I f(x,a,t) I K< at {1 + E E E A H' (xi yi dvi) L L | Hk ( yk,dVk)1 I(x )] } yEE iES LCSi [,t] kESi\L,v [i(L = t 1+ EE H,'(x, yi, dvi) n k (Xk Yk, i) I(xjyyj) yEE iES LCSi,t] kSi\LL J -= t 1{ H' (xi, dvi) Hk (Xk, Vi)] iES LCSi LkESi \L = nt [ + HIaI'(x, t)] < Kt Ct < 00. iES Hence, f E:F. Before we show that Expression (3.6) solves the S-Markov renewal equation, let us define the following. For each m > 1, consider the process N(Ym, Am), this is the superposition of p independent delayed Markov renewal processes with initial state Ym and initial age Am. Let Tm,n represents the time of the nth event that occurs in the process N(Ym, Am). Also, let Ym,n and Am,n be respectively the state and the age of the superposition process N(Ym, Am) at time Tm,n. Let Zm,n = (Ym,n,Am,,). For n > m, conditional on Tm and Zm = (Ym,Am), we have Tn = Tm + Tm,n-m, Yn = Ym,n-m, and An = Am,n-mm. In words, knowing Tm, Ym and Am, then the times of n events in the process N(x,a) are equal to Tm plus the times of n - m events in the process N(Ym, Am). Also, the state and the age of the superposition process at the time of n events, Tn, is the same as those of N(Ym Am) at the times of n - m events. It follows that for all n > m > 1, Ex,a[f(Znt-Tn)] = ~xa{~ymAm[f(Znt-Tn) I Tm Zm]} = Ex,a{Ym,A,[f(Zm,nmt - Tm - Tm,n-m) I Tm,Zm]} (5.1) We can now solve the S-renewal equation by successive approximations, and we use equality (5.1) to simplify each step in the approximation to obtain f(x,a,t) = g(x,a,t) + x,a[f(Z, t- T1)] = g(x,a,t) + x,a[g(Zl,t - T1)] + Ex,a{y1,Al[f(Z1, t - T1 - Tl,) I T1,Zl]} = g(x,a,t)+ Ex,a[g(Zi,t - T) + ~x,a[f(Z2,t - T2) 19

n-1...= g(x,a,t) + E x,a[g(Zt, t - Ti)] + Cx,a[f(Z,t - Tn)] (5.2) 1=1 Next we want to show that for each fixed t, lim I Ex,a[f(Znt - T,)] 1= 0. (5.3) n —* oo To show Result (5.3), it is sufficient to show that the number of Tn belonging to [O,t] is almost surely finite. Now, for the latter, it is sufficient to show that the expected number of renewals or events in the superposed process in [0, t] is finite. Ex,a[N(x, a, t)] = Hi(xi, t) < E Hi(xi, t) < oo iES iES by assumption. Result (5.3) therefore follows. Letting n -E oo in Equation (5.2), the solution of the S-Markov renewal equation becomes 00 f(x,a,t) = g(x,a,t) + Ex,a[g(Zl,t - T)]. 1=1 Next observe that I=1 = E E E E | (Qi?')m'(xi,Yidvi) 1 F(a I(vj, EEEZ E E Zi(] dL ) 1- Fj(xzjaj +i) j) I=1 yEE iES LESl mELI [Ot] L x J (k )m (k,yk, dvk)[1 - Fk(yk,vi- vk)]g(y,b,t- vi) (5.4) kESi\L ) E E E E Qi)m'(xi, Yi, dv1- Fan = Z Z Z Z<?.;=|5\ |m~~l70t] Ya6 1 -________a _ yEE iES LESi I=IS\LI mEL 1 - F(,a + i),yj) x JJa(Ql.)M(xk, yk, dvA;k)[1 - Fk(yk,v i - vA)]g(y,b, t - v ) kESi\L J,]] where LI = {m = (ml,..., mp) E VNP: jEs mj = 1, mj = 0 if j 6 L and mj > 0 if j E S \ L} and Sil = {L C Si:1 S \ L j< min{l,p}}. Expression (5.4) above can be explained as follows: There is a last event (the Ithe event in the superposed process) around the time vi, that event belongs to the ith component process and it is of type yi. There is a total of mi events occurred 20

in process i during [0,t]. The set L is the collection of component processes j that have no events during [0,t]. The processes k outside L U {i} have mk > 0 event during [0, vi], its last event around the time vk < vi and is of type Yk. Finally, observe E E(Qt)' (xij, yiX dvi ) n(Qak )mk (xk, yk,dvk) I=IS\Ll mELI LkESi\L = H' (xi, yi,dvi) [ n Hk(xk,Yk,dvk). This completes the proof of the theorem. O For the proof of superposition Markov renewal theorem, we require the following notations and lemmas. For the remainder of this section, let us assume that all the conditions in Theorem (4.3) hold. Lemma 5.1 For all i E S, x, y E E, a E IR, and nonempty subsets L of Si, lim R'(xi, yi,dvi) J Rk(xk,yk,dvk) I(xj,yj) Kg(y,b,t - vi) = 0 t —0oo,t] k L, vi (5.5) where b is defined in Equation (3.7) in Section 3. Proof: By symmetry, it is sufficient to prove Lemma (5.1) for i = p. Let h: E x 1R P -- Rp be a function such that h(y,a)= [j I(x yj) Kpg(y, al,..., ap,0,ap) (5.6) where L is a nonempty subset of S,. Given any 6 > 0 and fixed y E E, let hn(6) be as defined in Definition (4.1) for the function h(y,.). For j E S and nj E WV, define the indicator function I6,j(t) such that Inj(t) = 1 if t E [(nj - 1)6,nj6). Let L(t,nj,6) = [t - njS,t - (nj - 1)6), L(t,aj, np,6) = [(t/6)+(aj/6)- np, (t/6) + (aj/6) - np + 2] and L(m) be the set {n E NP: ni > m for some i E S}, m E IV. For every j E S, x,y E E and a E IRP, we have 1> G (xj, yj, t) = H(x, yj, t)- Hj (xj,yj)* Gj(yj, yj)(t) 21

> [H^j(x, yj, t)- Hja(xj,yj, t-6)][1-Gj(yj,yj, )] = [R j yjt) (xj, yj, t - )] [1 - Gj (yj, yj, )] and choosing 6 such that Gj(yj,yj,6) < 1, we have wj(yj, b) = sup[R' (xj, yj, t) - Rj (xj, yj,t - 6)] < ~~. (5.7) t Since any interval can be partitioned into finite number of intervals of smaller length, (5.7) holds for any 6 > 0. Hence, for any fixed y E E and 6 > 0, w(y, ) = max j(yj,6) < oo. jES Observe that o Rp(xpypdvp) n ro R'k(Xk7ykdvk)] [II(xzjyj) Kpg(y,b,t - vp) E E Rp(Xypdvp) fI J Rk(XkYkdVk)[ I(aj + vp) a=l na=l (tnp,6) kESp\L L('nk,6) iL < w(y, 6)IS\L I n [k\~~ EL(ta[,~]p,6)1 hn(6) np=l ESc\L nk=l k njpL(tajnp) 7ip=l LkESp\L nk=l- jELnjL(t,aj,np,8)j <.' [b)ifL nI E ]n E hn(6) + w(y, 6)IS\LI E hM(). np=l kESp\L nk=l' jEL njEL(t,aj,np,6) nEL(m) (5.8) Taking limits as t -+ oo, the first term in Equation (5.8) vanishes. Now, letting m - oo, h(y,.) 6'D(R+) for each fixed y E E implies that the second term in (5.8) also converges to 0. Lemma 5.2 For all i E S, x, y E E and a E 1R+, tliO R (xi, yi, dvi) [ Rk (xk, k,dvk)] i(ybt - v) t-^o J[00,t] L J v,] = (H A(y)J du JiP i(db)Kig(y,b,u) (5.9) where b is defined in Equation (3.7) in Section 3 with L = 0 (the empty set). 22

Proof: By symmetry, it is sufficient to prove the Lemma for i = p. Using the notations defined in the proof of Lemma (5.1) above, we have Rp (xp yp dvp) [ Rk(Xk, Ykdvk)1 Kp(y, b,t - vp) < E R,(xp,,yp,dv,)[ ( E Rk(Xk, k,dVk)) hn(6) + w(y, )P ) h n(). np=l L(tnS) kE nk L(vnk nEL(m) By ordinary renewal theory, lim / Rk(, k, dvk) = Ak( Vp —~ L(vp,nk,6) Akmk Since t - np < vp < t - (np - 1)6, hence vp - oo as t -- oo and Riemann integrable, l / RP(pypdvp) 11 R ( Yk RdVk)] Ig(yb tV ) li inf l RP(tnp,6) ep SPp [knS L(vp,nk,6) ( 5 nlim 5 ( [ R,(p P(Zp,yp,dv) [ ln l(- r Rxk y' (x)k,(ykdvk) jE^S a=-1 n<= - - Also, lim inf/ Rap (XP ypdvp) RaXY ydVk) Kpg(y, b,t - v) 1 \ P o" =^,]Rax, yp, dvep) Rixpy, dyv, d vVkoYb A(5-) a=-1 n=l t0 JL(t,np,6) (vp,nk,S) = (n rjmj1PA(Y) E Zn()- (5-11) j~ EjmJ a=lna=l 23

The proof is completed by using (5.10), (5.11) and the definition of Riemann integrability. O Both Lemmas (5.1) and (5.2) still hold when we replace Rl(x1,,Yi,t),..., R pP(xp, ypIt) in (5.5) and (5.9) by H1j (xi, y1, t),..., HpP(, ypt) respectively. In the case when the state space E is finite, since Kig(y, ) (E D(R+.) when considered as a mapping from 2RP+ into IR+ for each y E E and i E S, it follows immediately that limf(xat) (a-IS ) =YEE duKIR+ b t-+ 0 s j\jE Ajmj y feE iES In the case of infinitely but countable many states, however, we can no longer pass the limit inside the summation without some justification. Since the delayed Markov renewal functions and the Markov renewal functions have the same limiting behavior, it is sufficient to prove the theorem for a = 0. 0 here represents a row vector of p zeros. Lemma 5.3 Let h be a nonnegative function defined on JR+. For any t E 1R+, k E S and Xk, Yk E k, we have Hk(yk, xk) * h(t) < Rk(k, Xk) * h(t). Proof: Using Equation (2.4) and since Gk(yk, Xk,t) is a distribution function, Hk(yk, k) * h(t) = [Gk(Yk, Xk) * Rk(xk, k)] * h(t) < Rk(xk, Xk) * h(t) as desired. 1 Lemma 5.4 For all i E S, x E E, and nonempty subsets L of Si, lim E H(xi,yi,dvi) Hk(xk, yk, dvk) J I(xj, yi) Kig(y,b,t - vi) = 0 YEE,tL,v EL where b is defined in Equation (3.7) in Section 3. Proof: Again, it is sufficient to consider the case when i = p. Let h be as defined in Equation (5.6) and b = (b1,..., bp) be as defined in Equation (3.7). Let b' = (b1,...,bp-1,t - vp). 24

Using Equation (2.3) and applying Lemma (5.3) repeatedly, we have S\L(X) [ Hp(xp yp, dvp) E,] Hk(xk,yk,dVk) h(y,b') yeE LkESp\L yeE= Jt] P y [kp (p\, p) dvp) nAk(Yk)Hk(yk Xk, dvk) h(y b') < Y Ayp) Hp(yp,x,dvp) [ \k(Yk) Rk(xk,7kdVk) h(y,b') < f xp(xp,xp,dv) Fp 17 Rk(xkXkdvk) [ AIS\L(y)h(y, b')] J[Ot] [kESp\L J LYEE Since CKpg considered as a mapping from E x 1R+ into R+ is directly Riemann integrable with respect to AL for every nonempty L C S, the same argument used in the proof of Proposition (10.4.15(a)) in Cinlar (1975a) applies to show that EyEE AIS\L(y)h(yb') is directly Riemann integrable. The proof is now completed using Lemma (5.1). E Lemma 5.5 For every i E S and x E E, lim E~ Hi(xiyi, dvi) ][ Hk(Xk,yk,dvk) Kig(y,b,t-vi) t YEE 9t] I;i l (en n E ) (y ) I u (db)Kig(y b u) where b is defined in Equations (3. 7) in Section 3 with L = 0. Proof: It is sufficient to consider the case when i = p. Using Equation (2.3) and applying Lemma (5.3) repeatedly, we have A(x) [ Hp(x, y ) [I [ v Hk(xkYk,dVk)] Kpg(y,b,t - p) < I[ Rp(xp,xpdvp) [I jI[ Rk(xk',xk dvk)] A(y)Ipg(y,b,t - vp). (5.12),[o~t],vp] k yEE The same argument used in Lemma (5.4) can be used to show that EyEE A(y)Kpg(y, b, t - vp) is directly Riemann integrable. This, together with Equation (5.12), Lemma (5.2) and the 25

monotone convergence theorem imply that tlimy~ t Hp(xp, ypdvp) [k' I P / o Hk(xkykdvk) Kpg(y,b,t - vp) -00YEE'3t].cESP V, n j ) A(Y) du pp(db)Kpg(y,b, t - vp) (5.13) On the other hand, since Kpg(y, *) considered as a mapping from iWP. into JR+ is directly Riemann integrable and from the remark after Lemma (5.2), we have for any a E JR, lim / H (xp, yp, dvp) J [ Hk (xk, Yk, dvk) Kpg(y,b,t- vp) y —EEJ [ot]. kES,v] >y lim HA[Ox] yp, dvp) Hk pzk, ykbt-vp) yEE. k]Sp.VP] = (n - ) ) A(y) du j /p(db)Kp(y,b,t -vp) (5.14) The proof is now completed by (5.13) and (5.14). O Combining Lemmas (5.4) and (5.5), the superposition Markov renewal theorem now follows. Acknowledgement I would like to thank the referee whose valuable comments helped improve the presentation of results in this paper. References [1] Barbour, A. D. (1982) Generalized semi-Markov schemes and open queueing networks. J. Appl. Prob., vol 19, 469-474. [2] Burman, D. Y. (1981) Insensitivity in queueing systems. Adv. Appl. Prob., 13, 846-859. 26

[3] Cherry, W. P. (1972) The superposition of two independent Markov renewal processes. Ph. D. Dissertation, Department of Industrial and Operations Engineering, University of Michigan. [4] Cherry, W. P. and Disney, R. L. (1983) The superposition of two independent Markov renewal processes. Zastos Mat., XVII, 567-602. [5] Cinlar, E. (1967) Queues with semi-Markovian arrivals. J. Appl. Prob., 4, 365-379. [6] Cinlar, E. (1969a) Markov renewal theory. Adv. Appl. Prob., 1, 123-187. [7] Cinlar, E. (1969b) On semi-Markov processes on arbitrary spaces. Proc. Camb. Phil. Soc., 66, 381-392. [8] Cinlar, E. (1972) Superposition of point processes. In Stochastic Point Processes, ed. P. A. W. Lewis. Wiley-Interscience, New York, 546-606. [9] Cinlar, E. (1975a) Introduction to stochastic processes. Prentice-Hall. [10] Cinlar, E. (1975b) Markov renewal theory: a survey. Management Science, vol 21, no. 7, 727-752. [11] Cox, D. R. and Smith, W. L. (1954) On the superposition of renewal processes. Biometrika, 41, 91-99. [12] Harris, C. M. (1967a) Queues with state-dependent stochastic service rates. Oper. Res., 15, 117-130. [13] Harris, C. M. (1967b) Queues with stochastic service rates. Naval Res. Logist. Quart., 14, 219-230. [14] Jacod, J. (1971) Theoreme de renouvellement et classification pour les chaines semiMarkoviennes. Ann. Inst. H. Poincare, Sect. B, 7, 83-129. [15] Jacod, J. (1974) Corrections et complements a Particle: Theoreme de renouvellement et classification pour les chaines semi-Markoviennes. Ann. Inst. H. Poincare, Sect. B, 10, 201-209. 27

[16] Kesten, H. (1974) Renewal theory for functionals of a Markov chain with general state space. Ann. Prob., 2, 355-386. [17] Kshirsagar A. M. and Becker M. (1981) Superposition of Markov renewal processes. South African Statist. J., 15, 13-30. [18] Lam, C. Y. T. and Lehoczky, J. P. (1991) Superposition of renewal processes. Advances in Applied Probability, 23, 64-85. [19] Lam, C. Y. T. (1990) Stationary distributions for the superposition of Markov renewal processes. Technical Report 90-23, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor. [20] Lawrance, A. J. (1973) Dependency of intervals between events in superposition process. J. R. Statist. Soc. B 35, 306-315. [21] Neuts, M. F. (1965) The busy period of queue with batch service. Oper. Res., 13, 815-819. [22] Neuts, M. F. (1966) Semi-Markov analysis of a bulk queue. Bull. Soc. Math. Belg., 18, 28-42. [23] Palm, C. (1943-1944) Variation in intensity in telephone conversations. Ericsson Technics, 1-89. [24] Prabhu, N. U. (1965) Queues and inventories. J. Wiley, New York. [25] Pyke, R. (1961a) Markov renewal processes: definitions and preliminary properties. Ann. Math. Statist., 32, 1231-1242. [26] Pyke, R. (1961b) Markov renewal processes with finitely many states. Ann. Math. Statist., 32, 1243-1259. [27] Pyke, R. and Schaufele, R. (1964) Limit theorems for Markov renewal processes. Ann. Math. Statist., 35, 1746-1764. [28] Pyke, R. and Schaufele, R. (1966) The existence and uniqueness of stationary measures for Markov renewal processes. Ann. Math. Statist., 37, 1439-1462. 28

UNIVERSITY OF MICHIGAN 3 9015 04732 7757 [29] Schassberger, R. (1976) On the equilibrium distribution of a class of finite-state generalized semi-Markov process. Math. Operat. Res., 1, 395-406. [30] Schassberger, R. (1977) Insensitivity of steady-state distributions of generalized semiMarkov process - Part I. Ann. Prob., 5, 87-99. [31] Schassberger, R. (1978a) Insensitivity of steady-state distributions of generalized semiMarkov processes - Part II. Ann. Prob., 6, 85-93. [32] Schassberger, R. (1978b) Insensitivity of steady-state distributions of generalized semiMarkov process with speeds. Adv. Appl. Prob., 10, 836-851. [33] Schassberger, R. (1978c) Insensitivity of stationary probabilities in networks of queues. Adv. Appl. Prob., 10, 906-912. [34] Smith, W. L. (1955) Regenerative stochastic processes. Proc. Roy. Soc. Ser. A., 232, 6-31. 29