October  2012, 8(4): 925-938. doi: 10.3934/jimo.2012.8.925

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

1. 

SMACS Research Group, Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent

Received  September 2011 Revised  July 2012 Published  September 2012

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.
Citation: Sofian De Clercq, Wouter Rogiest, Bart Steyaert, Herwig Bruneel. Stochastic decomposition in discrete-time queues with generalized vacations and applications. Journal of Industrial & Management Optimization, 2012, 8 (4) : 925-938. doi: 10.3934/jimo.2012.8.925
References:
[1]

S. C. Borst and O. J. Boxma, Polling models with and without switchover times,, Operations Research, 45 (1997), 536. 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. doi: 10.2307/3214218.

[3]

H. Bruneel, Performance of discrete-time queueing systems,, Computers Operations Research, 20 (1993), 303. doi: 10.1016/0305-0548(93)90006-5.

[4]

R. B. Cooper, "Introduction to Queueing Theory,'', North-Holland (Elsevier), (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.

[6]

S. W. Fuhrmann and R. B. Cooper, Stochastic decompositions in the M/G/1 queue with generalized vacations,, Operations Research, 33 (1985), 1117. doi: 10.1287/opre.33.5.1117.

[7]

S. Halfin, Batch delays versus customer delays,, The Bell System Technical Journal, 62 (1983), 2011.

[8]

L. Kleinrock, "Queueing Systems, Volume I: Theory,'', Wiley, (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.

[10]

L. Lakatos, Cyclic-waiting systems,, Cybernetics and Systems Analysis, 46 (2010), 477. 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. 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. 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. 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. doi: 10.1007/s11134-007-9032-y.

[15]

H. Takagi, "Queueing Analysis, Volume 3: Discrete-Time Systems,'', North-Holland (Elsevier), (1991).

[16]

H. Takagi, "Analysis of Polling Systems,'', The MIT Press, (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.

show all references

References:
[1]

S. C. Borst and O. J. Boxma, Polling models with and without switchover times,, Operations Research, 45 (1997), 536. 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. doi: 10.2307/3214218.

[3]

H. Bruneel, Performance of discrete-time queueing systems,, Computers Operations Research, 20 (1993), 303. doi: 10.1016/0305-0548(93)90006-5.

[4]

R. B. Cooper, "Introduction to Queueing Theory,'', North-Holland (Elsevier), (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.

[6]

S. W. Fuhrmann and R. B. Cooper, Stochastic decompositions in the M/G/1 queue with generalized vacations,, Operations Research, 33 (1985), 1117. doi: 10.1287/opre.33.5.1117.

[7]

S. Halfin, Batch delays versus customer delays,, The Bell System Technical Journal, 62 (1983), 2011.

[8]

L. Kleinrock, "Queueing Systems, Volume I: Theory,'', Wiley, (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.

[10]

L. Lakatos, Cyclic-waiting systems,, Cybernetics and Systems Analysis, 46 (2010), 477. 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. 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. 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. 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. doi: 10.1007/s11134-007-9032-y.

[15]

H. Takagi, "Queueing Analysis, Volume 3: Discrete-Time Systems,'', North-Holland (Elsevier), (1991).

[16]

H. Takagi, "Analysis of Polling Systems,'', The MIT Press, (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.

[1]

Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial & Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767

[2]

Thomas Demoor, Dieter Fiems, Joris Walraevens, Herwig Bruneel. Partially shared buffers with full or mixed priority. Journal of Industrial & Management Optimization, 2011, 7 (3) : 735-751. doi: 10.3934/jimo.2011.7.735

[3]

Yoshiaki Kawase, Shoji Kasahara. Priority queueing analysis of transaction-confirmation time for Bitcoin. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2018193

[4]

Simone Göttlich, Patrick Schindler. Optimal inflow control of production systems with finite buffers. Discrete & Continuous Dynamical Systems - B, 2015, 20 (1) : 107-127. doi: 10.3934/dcdsb.2015.20.107

[5]

P. Adda, J. L. Dimi, A. Iggidir, J. C. Kamgang, G. Sallet, J. J. Tewa. General models of host-parasite systems. Global analysis. Discrete & Continuous Dynamical Systems - B, 2007, 8 (1) : 1-17. doi: 10.3934/dcdsb.2007.8.1

[6]

Gang Chen, Zaiming Liu, Jingchuan Zhang. Analysis of strategic customer behavior in fuzzy queueing systems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2018157

[7]

A. Zeblah, Y. Massim, S. Hadjeri, A. Benaissa, H. Hamdaoui. Optimization for series-parallel continuous power systems with buffers under reliability constraints using ant colony. Journal of Industrial & Management Optimization, 2006, 2 (4) : 467-479. doi: 10.3934/jimo.2006.2.467

[8]

Denis de Carvalho Braga, Luis Fernando Mello, Carmen Rocşoreanu, Mihaela Sterpu. Lyapunov coefficients for non-symmetrically coupled identical dynamical systems. Application to coupled advertising models. Discrete & Continuous Dynamical Systems - B, 2009, 11 (3) : 785-803. doi: 10.3934/dcdsb.2009.11.785

[9]

Susanna Terracini, Juncheng Wei. DCDS-A Special Volume Qualitative properties of solutions of nonlinear elliptic equations and systems. Preface. Discrete & Continuous Dynamical Systems - A, 2014, 34 (6) : i-ii. doi: 10.3934/dcds.2014.34.6i

[10]

Anna Kostianko, Sergey Zelik. Inertial manifolds for 1D reaction-diffusion-advection systems. Part Ⅰ: Dirichlet and Neumann boundary conditions. Communications on Pure & Applied Analysis, 2017, 16 (6) : 2357-2376. doi: 10.3934/cpaa.2017116

[11]

Anna Kostianko, Sergey Zelik. Inertial manifolds for 1D reaction-diffusion-advection systems. Part Ⅱ: periodic boundary conditions. Communications on Pure & Applied Analysis, 2018, 17 (1) : 285-317. doi: 10.3934/cpaa.2018017

[12]

Fumioki Asakura, Andrea Corli. The path decomposition technique for systems of hyperbolic conservation laws. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 15-32. doi: 10.3934/dcdss.2016.9.15

[13]

Galina Kurina, Sahlar Meherrem. Decomposition of discrete linear-quadratic optimal control problems for switching systems. Conference Publications, 2015, 2015 (special) : 764-774. doi: 10.3934/proc.2015.0764

[14]

Alexandre Caboussat, Allison Leonard. Numerical solution and fast-slow decomposition of a population of weakly coupled systems. Conference Publications, 2009, 2009 (Special) : 123-132. doi: 10.3934/proc.2009.2009.123

[15]

Huseyin Coskun. Nonlinear decomposition principle and fundamental matrix solutions for dynamic compartmental systems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-53. doi: 10.3934/dcdsb.2019155

[16]

Jeongsim Kim, Bara Kim. Stability of a cyclic polling system with an adaptive mechanism. Journal of Industrial & Management Optimization, 2015, 11 (3) : 763-777. doi: 10.3934/jimo.2015.11.763

[17]

Yejuan Wang, Tomás Caraballo. Morse decomposition for gradient-like multi-valued autonomous and nonautonomous dynamical systems. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1-24. doi: 10.3934/dcdss.2020092

[18]

Bart Feyaerts, Stijn De Vuyst, Herwig Bruneel, Sabine Wittevrongel. Performance analysis of buffers with train arrivals and correlated output interruptions. Journal of Industrial & Management Optimization, 2015, 11 (3) : 829-848. doi: 10.3934/jimo.2015.11.829

[19]

Tuan Phung-Duc, Ken’ichi Kawanishi. Multiserver retrial queues with after-call work. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 639-656. doi: 10.3934/naco.2011.1.639

[20]

Tuan Phung-Duc. Single server retrial queues with setup time. Journal of Industrial & Management Optimization, 2017, (3) : 1329-1345. doi: 10.3934/jimo.2016075

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (0)

[Back to Top]