American Institute of Mathematical Sciences

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

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

Sofian De Clercq 1, , Wouter Rogiest 1, , Bart Steyaert 1, and  Herwig Bruneel 1,

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.
Keywords: decomposition, polling systems., priority queues, Queueing, FDL-buffers.
Mathematics Subject Classification: Primary: 60K25, 68M20; Secondary: 90B2.
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-543. doi: 10.1287/opre.45.4.536.  Google Scholar

[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.  Google Scholar

[3]

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

[4]

R. B. Cooper, "Introduction to Queueing Theory,'' North-Holland (Elsevier), New York, 1981.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[7]

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

[8]

L. Kleinrock, "Queueing Systems, Volume I: Theory,'' Wiley, New York, 1975. Google Scholar

[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. Google Scholar

[10]

L. Lakatos, Cyclic-waiting systems, Cybernetics and Systems Analysis, 46 (2010), 477-484. doi: 10.1007/s10559-010-9222-1.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[16]

H. Takagi, "Analysis of Polling Systems,'' The MIT Press, Cambridge, Massachusetts, 1986.  Google Scholar

[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.  Google Scholar

show all references

References:
[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.  Google Scholar

[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.  Google Scholar

[3]

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

[4]

R. B. Cooper, "Introduction to Queueing Theory,'' North-Holland (Elsevier), New York, 1981.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[7]

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

[8]

L. Kleinrock, "Queueing Systems, Volume I: Theory,'' Wiley, New York, 1975. Google Scholar

[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. Google Scholar

[10]

L. Lakatos, Cyclic-waiting systems, Cybernetics and Systems Analysis, 46 (2010), 477-484. doi: 10.1007/s10559-010-9222-1.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

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

[16]

H. Takagi, "Analysis of Polling Systems,'' The MIT Press, Cambridge, Massachusetts, 1986.  Google Scholar

[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.  Google Scholar

[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, 2020, 16 (3) : 1077-1098. 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]

Zsolt Saffer, Miklós Telek, Gábor Horváth. Analysis of Markov-modulated fluid polling systems with gated discipline. Journal of Industrial & Management Optimization, 2021, 17 (2) : 575-599. doi: 10.3934/jimo.2019124
[6]

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
[7]

Gang Chen, Zaiming Liu, Jingchuan Zhang. Analysis of strategic customer behavior in fuzzy queueing systems. Journal of Industrial & Management Optimization, 2020, 16 (1) : 371-386. doi: 10.3934/jimo.2018157
[8]

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
[9]

Matteo Petrera, Yuri B. Suris. Geometry of the Kahan discretizations of planar quadratic Hamiltonian systems. Ⅱ. Systems with a linear Poisson tensor. Journal of Computational Dynamics, 2019, 6 (2) : 401-408. doi: 10.3934/jcd.2019020
[10]

Jacques Demongeot, Dan Istrate, Hajer Khlaifi, Lucile Mégret, Carla Taramasco, René Thomas. From conservative to dissipative non-linear differential systems. An application to the cardio-respiratory regulation. Discrete & Continuous Dynamical Systems - S, 2020, 13 (8) : 2121-2134. doi: 10.3934/dcdss.2020181
[11]

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
[12]

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

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
[14]

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
[15]

Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
[16]

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
[17]

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
[18]

Huseyin Coskun. Nonlinear decomposition principle and fundamental matrix solutions for dynamic compartmental systems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (12) : 6553-6605. doi: 10.3934/dcdsb.2019155
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (70)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy