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

Previous Article
M/M/c multiple synchronous vacation model with gated discipline
JIMO Home
This Issue
Next Article
G/M/1 type structure of a risk model with general claim sizes in a Markovian environment

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

Abstract
Related Papers

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 and 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.
[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.

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

[1]	Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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]	Raina Raj, Vidyottama Jain. Optimization of traffic control in $ MMAP\mathit{[2]}/PH\mathit{[2]}/S$ priority queueing model with $ PH $ retrial times and the preemptive repeat policy. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022044
[11]	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 and Continuous Dynamical Systems - S, 2020, 13 (8) : 2121-2134. doi: 10.3934/dcdss.2020181
[12]	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 and Continuous Dynamical Systems - B, 2009, 11 (3) : 785-803. doi: 10.3934/dcdsb.2009.11.785
[13]	Susanna Terracini, Juncheng Wei. DCDS-A Special Volume Qualitative properties of solutions of nonlinear elliptic equations and systems. Preface. Discrete and Continuous Dynamical Systems, 2014, 34 (6) : i-ii. doi: 10.3934/dcds.2014.34.6i
[14]	Anna Kostianko, Sergey Zelik. Inertial manifolds for 1D reaction-diffusion-advection systems. Part Ⅰ: Dirichlet and Neumann boundary conditions. Communications on Pure and Applied Analysis, 2017, 16 (6) : 2357-2376. doi: 10.3934/cpaa.2017116
[15]	Anna Kostianko, Sergey Zelik. Inertial manifolds for 1D reaction-diffusion-advection systems. Part Ⅱ: periodic boundary conditions. Communications on Pure and Applied Analysis, 2018, 17 (1) : 285-317. doi: 10.3934/cpaa.2018017
[16]	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 and Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
[17]	Fumioki Asakura, Andrea Corli. The path decomposition technique for systems of hyperbolic conservation laws. Discrete and Continuous Dynamical Systems - S, 2016, 9 (1) : 15-32. doi: 10.3934/dcdss.2016.9.15
[18]	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
[19]	Huseyin Coskun. Nonlinear decomposition principle and fundamental matrix solutions for dynamic compartmental systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6553-6605. doi: 10.3934/dcdsb.2019155
[20]	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

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Sofian De Clercq Wouter Rogiest Bart Steyaert Herwig Bruneel
on Google Scholar
Sofian De Clercq Wouter Rogiest Bart Steyaert Herwig Bruneel

[Back to Top]