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

Publisher Website
Google Scholar
Abstract
In this paper we show that the sample path comparison used in Doshi [l] 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, we use the same approach to show a similar decomposition result for the steady state virtual waiting time. The special case of semi-Markov arrival process and i.i.d. service times is analysed further and stronger results are obtained for that case: we show that there is a unique invariant waiting time (virtual waiting time) distribution which is the limiting distribution for any initial conditions. We also show 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 in [1] were motivated by a recent paper of Lucantoni, Meier-Hellstern and Neuts [8] in which MAP/G/l 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/l 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.