MATRIX PRODUCT-FORM SOLUTIONS FOR MARKOV-CHAINS WITH A TREE STRUCTURE

We have two aims in this paper. First, we generalize the well-known th eory of matrix-geometric methods of Neuts to more complicated Markov c hains. Second, we use the theory to solve a last-come-first-served que ue with a generalized preemptive resume (LCFS-GPR) discipline. The str ucture of the Markov chain considered in this paper is one in which on e of the variables can take values in a countable set, which is arrang ed in the form of a tree. The other variable takes values from a finit e set. Each node of the tree can branch out into d other nodes. The st eady-state solution of this Markov chain has a matrix product-form, wh ich can be expressed as a function of d matrices R(1),...,R(d). We the n use this theory to solve a multiclass LCFS-GPR queue, in which the s ervice times have PH-distributions and arrivals are according to the M arkov modulated Poisson process. In this discipline, when a customer's service is preempted in phase j (due to a new arrival), the resumptio n of service at a later time could take place in a phase which depends on j. We also obtain a closed form solution for the stationary distri bution of an LCFS-GPR queue when the arrivals are Poisson. This result generalizes the known result on a LCFS preemptive resume queue, which can be obtained from Kelly's symmetric queue.