Matrix Product-Form Solution for an LCFS-PR Single-Server Queue with Multiple Arrival Streams Governed by a Markov Chain

This paper considers a stationary single-server queue with multiple arrival streams governed by a Markov chain, where customers are served on an LCFS preemptive-resume basis. Service times of customers from each arrival stream are generally distributed and service time distributions for different arrival streams may be different. Under these assumptions, it is shown that the stationary joint distribution of queue strings representing from which arrival stream each customer in the system arrived and remaining service times of respective customers in the system has a matrix product-form solution, where matrices constituting the solution are given in terms of the infinitesimal generator of a certain Markov chain. Compared with the previous works, the result in this paper is more general in the sense that general service time distributions are allowed, and it has the advantage of computational efficiency. Note also that the result is a natural extension of the classical result for the LCFS-PR M/G/1 queue. Further, utilizing the matrix product-form solution, we derive a new expression of the vector Laplace–Stieltjes transform of the stationary distribution of unfinished work in the work-conserving single-server queue with multiple arrival streams governed by a Markov chain, which is given by the sum of matrix-geometric series.     

Sample-path analysis of processes with imbedded point processes

The purpose of this paper is to review, unify, and extend previous work on sample-path analysis of queues. Our main interest is in the asymptotic behavior of a discrete-state, continuous-time process with an imbedded point process. We present a sample-path analogue of the renewal-reward theorem, which we callY=X. We then applyY=X to derive several relations involving the transition rates and the asymptotic (long-run) state frequencies at an arbitrary point in time and at the points of the imbedded point process. Included are sample-path versions of the rate-conservation principle, the global-balance conditions, and the insensitivity of the asymptotic frequency distribution to the distribution of processing time in a LCFS-PR service facility. We also provide a natural sample-path characterization of the PASTA property.The research of this author was partially supported by the U.S. Army Research Office, Contract DAAG29-82-K-0151 at N.C. State University, and by the National Science Foundation, Grant No. ECS-8719825, at the University of North Carolina, Chapel Hill.The research of this author was partially supported by the U.S. Army Research Office, Contract DAAG29-82-K-0151 at N.C. State University.