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

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

[2]

Veena Goswami, Gopinath Panda. Optimal customer behavior in observable and unobservable discrete-time queues. Journal of Industrial & Management Optimization, 2021, 17 (1) : 299-316. doi: 10.3934/jimo.2019112

[3]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[4]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[5]

Lingju Kong, Roger Nichols. On principal eigenvalues of biharmonic systems. Communications on Pure & Applied Analysis, 2021, 20 (1) : 1-15. doi: 10.3934/cpaa.2020254

[6]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[7]

Ilyasse Lamrani, Imad El Harraki, Ali Boutoulout, Fatima-Zahrae El Alaoui. Feedback stabilization of bilinear coupled hyperbolic systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020434

[8]

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, 2020  doi: 10.3934/dcdss.2020451

[9]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461

[10]

Simon Hochgerner. Symmetry actuated closed-loop Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 641-669. doi: 10.3934/jgm.2020030

[11]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029

[12]

Lingwei Ma, Zhenqiu Zhang. Monotonicity for fractional Laplacian systems in unbounded Lipschitz domains. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 537-552. doi: 10.3934/dcds.2020268

[13]

Peter H. van der Kamp, D. I. McLaren, G. R. W. Quispel. Homogeneous darboux polynomials and generalising integrable ODE systems. Journal of Computational Dynamics, 2021, 8 (1) : 1-8. doi: 10.3934/jcd.2021001

[14]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[15]

João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138

[16]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[17]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024

[18]

Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257

[19]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[20]

Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121

2019 Impact Factor: 1.366

Metrics

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

[Back to Top]