Generalizations of the stochastic decomposition results for single server queues with vacations

This paper shows that the sample path comparison used by Doshi to prove the stochastic decomposition of the steady state waiting time for GI/G/1 queue with exhaustive service and multiple vacations can also be used to prove that this decomposition result is valid for more general (stationary) arrival and service processes. In addition, it uses the same approach to show a similar decomposition result for the steady state virtual waiting time. The special case of semi-Markov arrival processes and i.i.d. service times is analysed further and stronger results are obtained for that case: the paper shows that there is a unique invariant waiting time (virtual waiting time) distribution which is the limiting distribution for any initial conditions. It also shows that conditional distributions of the steady state waiting time and virtual waiting time (given the supplementary variables describing the state of the arrival process) have the stochastic decomposition property. Finally, the steady state queue length and the queue length seen by a departing customer exhibit a matrix integral form of decomposition. This work and a revisit to the methods used by Doshi were motivated by a recent paper of Lucantoni, Meier-Hellstern and Neuts in which MAP/G/1 queues with exhaustive service and multiple vacations are analysed in considerable detail (MAPs form a subset of the class of semi-Markov processes). Besides obtaining many computable formulae, their analysis revealed the stochastic decomposition results for MAP/G/1 queues with vacations. The sample path approach used in this paper shows that the decomposition is the result of a more fundamental structural relationship between the sample paths of queues with and without vacations and so is valid under much weaker assumptions on the arrival and service processes.