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.  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.  doi: 10.2307/3214218.  Google Scholar

[3]

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

[4]

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

[8]

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

[10]

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

[15]

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

[16]

H. Takagi, "Analysis of Polling Systems,'', The MIT Press, (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.   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.  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.  doi: 10.2307/3214218.  Google Scholar

[3]

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

[4]

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

[8]

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

[10]

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

[15]

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

[16]

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

[1]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109
[2]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[3]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[4]

Wenmin Gong, Guangcun Lu. On coupled Dirac systems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (8) : 4329-4346. doi: 10.3934/dcds.2017185
[5]

Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810
[6]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161
[7]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329
[8]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017
[9]

Graziano Crasta, Philippe G. LeFloch. Existence result for a class of nonconservative and nonstrictly hyperbolic systems. Communications on Pure & Applied Analysis, 2002, 1 (4) : 513-530. doi: 10.3934/cpaa.2002.1.513
[10]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451
[11]

F.J. Herranz, J. de Lucas, C. Sardón. Jacobi--Lie systems: Fundamentals and low-dimensional classification. Conference Publications, 2015, 2015 (special) : 605-614. doi: 10.3934/proc.2015.0605
[12]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[13]

Francisco Braun, Jaume Llibre, Ana Cristina Mereu. Isochronicity for trivial quintic and septic planar polynomial Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5245-5255. doi: 10.3934/dcds.2016029
[14]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087
[15]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189
[16]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 307-320. doi: 10.3934/naco.2020027
[17]

Marian Gidea, Rafael de la Llave, Tere M. Seara. A general mechanism of instability in Hamiltonian systems: Skipping along a normally hyperbolic invariant manifold. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6795-6813. doi: 10.3934/dcds.2020166
[18]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004
[19]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195
[20]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences