Article Contents
Article Contents

# Stochastic decomposition in discrete-time queues with generalized vacations and applications

• For several specific queueing models with a vacation policy, the stationary system occupancy at the beginning of a random slot is distributed as the sum of two independent random variables. One of these variables is the stationary number of customers in an equivalent queueing system with no vacations. For models in continuous time with Poissonian arrivals, this result is well-known, and referred to as stochastic decomposition, with proof provided by Fuhrmann and Cooper. For models in discrete time, this result received less attention, with no proof available to date. In this paper, we first establish a proof of the decomposition result in discrete time. When compared to the proof in continuous time, conditions for the proof in discrete time are somewhat more general. Second, we explore four different examples: non-preemptive priority systems, slot-bound priority systems, polling systems, and fiber delay line (FDL) buffer systems. The first two examples are known results from literature that are given here as an illustration. The third is a new example, and the last one (FDL buffer systems) shows new results. It is shown that in some cases the queueing analysis can be considerably simplified using this decomposition property.
Mathematics Subject Classification: Primary: 60K25, 68M20; Secondary: 90B22.

 Citation:

•  [1] S. C. Borst and O. J. Boxma, Polling models with and without switchover times, Operations Research, 45 (1997), 536-543.doi: 10.1287/opre.45.4.536. [2] O. J. Boxma and W. P. Groenendijk, Pseudo-conservation laws in cyclic-service systems, Journal of Applied Probability, 24 (1987), 949-964.doi: 10.2307/3214218. [3] H. Bruneel, Performance of discrete-time queueing systems, Computers Operations Research, 20 (1993), 303-320.doi: 10.1016/0305-0548(93)90006-5. [4] R. B. Cooper, "Introduction to Queueing Theory,'' North-Holland (Elsevier), New York, 1981. [5] S. De Clercq, B. Steyaert and H. Bruneel, Analysis of a multi-class discrete-time queueing system under the slot-bound priority rule, Proceedings of the 6th St. Petersburg Workshop on Simulation, (2009), 827-832. [6] S. W. Fuhrmann and R. B. Cooper, Stochastic decompositions in the M/G/1 queue with generalized vacations, Operations Research, 33 (1985), 1117-1129.doi: 10.1287/opre.33.5.1117. [7] S. Halfin, Batch delays versus customer delays, The Bell System Technical Journal, 62 (1983), 2011-2015. [8] L. Kleinrock, "Queueing Systems, Volume I: Theory,'' Wiley, New York, 1975. [9] K. Laevens and H. Bruneel, Analysis of a single-wavelength optical buffer, Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, (2003), 1-6. [10] L. Lakatos, Cyclic-waiting systems, Cybernetics and Systems Analysis, 46 (2010), 477-484.doi: 10.1007/s10559-010-9222-1. [11] Z. Liang and S. Xiao, Performance evaluation of single-wavelength fiber delay line buffer with finite waiting places, Journal of Lightwave Technology, 26 (2008), 520-527.doi: 10.1109/JLT.2007.915200. [12] J. Loris-Teghem, On a decomposition result for a class of vacation queueing systems, Journal of Applied Probability, 27 (1990), 227-231.doi: 10.2307/3214611. [13] W. Rogiest, J. Lambert, D. Fiems, B. Van Houdt, H. Bruneel and C. Blondia, A unified model for synchronous and asynchronous FDL buffers allowing closed-form solution, Performance Evaluation, 66 (2009), 343-355.doi: 10.1016/j.peva.2009.01.002. [14] W. Rogiest, K. Laevens, J. Walraevens and H. Bruneel, Analyzing a degenerate buffer with general inter-arrival and service times in discrete-time, Queueing Systems, 56 (2007), 203-212.doi: 10.1007/s11134-007-9032-y. [15] H. Takagi, "Queueing Analysis, Volume 3: Discrete-Time Systems,'' North-Holland (Elsevier), Amsterdam, 1991. [16] H. Takagi, "Analysis of Polling Systems,'' The MIT Press, Cambridge, Massachusetts, 1986. [17] J. Walraevens, B. Steyaert and H. Bruneel, Performance analysis of the system contents in a discrete-time non-preemptive priority queue with general service times, Belgian Journal of Operations Research (JORBEL), 40 (2001), 91-103.