July  2017, 13(3): 1365-1381. doi: 10.3934/jimo.2016077

Queue length analysis of a Markov-modulated vacation queue with dependent arrival and service processes and exhaustive service policy

Budapest University of Technology and Economics, Department of Networked Systems and Services, MTA-BME Information systems research group, Magyar Tudósok Körútja 2,1117 Budapest, Hungary

* Corresponding author: Gábor Horváth

Received  September 2015 Revised  June 2016 Published  October 2016

Fund Project: The reviewing process of the paper was handled by Wuyi Yue and Yutaka Takahashi as Guest Editors.

The paper introduces a class of vacation queues where the arrival and service processes are modulated by the same Markov process, hence they can be dependent. The main result of the paper is the probability generating function for the number of jobs in the system. The analysis follows a matrix-analytic approach. A step of the analysis requires the evaluation of the busy period of a quasi birth death process with arbitrary initial level. This element can be useful in the analysis of other queueing models as well. We also discuss several special cases of the general model. We show that these special settings lead to simplification of the solution.

Citation: Gábor Horváth, Zsolt Saffer, Miklós Telek. Queue length analysis of a Markov-modulated vacation queue with dependent arrival and service processes and exhaustive service policy. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1365-1381. doi: 10.3934/jimo.2016077
References:
[1]

A.-S. Alfa, A discrete MAP/PH/1 queue with vacations and exhaustive time-limited service, Oper. Res. Lett., 18 (1995), 31-40.  doi: 10.1016/0167-6377(95)00015-C.  Google Scholar

[2]

A.-S. Alfa, Discrete time analysis of MAP/PH/1 vacation queue with gated time-limited service, Queueing Systems, 29 (1998), 35-54.  doi: 10.1023/A:1019123828374.  Google Scholar

[3]

Y. Baba, Analysis of a GI/M/1 queue with multiple working vacations, Operation Research Letters, 33 (2005), 201-209.  doi: 10.1016/j.orl.2004.05.006.  Google Scholar

[4]

S. Chang and T. Takine, Factorization and stochastic decomposition properties in bulk queues with generalized vacations, Queueing Systems, 50 (2005), 165-183.  doi: 10.1007/s11134-005-0510-9.  Google Scholar

[5]

B. T. Doshi, Queueing systems with vacations -a survey, Queueing Systems, 1 (1986), 29-66.  doi: 10.1007/BF01149327.  Google Scholar

[6]

N. S. C. Goswami, The discrete-time MAP/PH/1 queue with multiple working vacations, Applied Mathematical Modelling, 34 (2010), 931-946.  doi: 10.1016/j.apm.2009.07.021.  Google Scholar

[7]

G. HorváthB. Van Houdt and M. Telek, Commuting matrices in the queue length and sojourn time analysis of MAP/MAP/1 queues, Stochastic Models, 30 (2014), 554-575.  doi: 10.1080/15326349.2014.930669.  Google Scholar

[8]

J.-C. KeC.-H. Wu and Z. G. Zhang, Recent developments in vacation queueing models: A short survey, International Journal of Operations Research, 7 (2010), 3-8.   Google Scholar

[9]

G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling ASA-SIAM Series on Statistics and Applied Probability, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; American Statistical Association, Alexandria, VA, 1999. doi: 10.1137/1.9780898719734.  Google Scholar

[10]

J. H. LiN. S. Tian and W. Liu, Discrete-time GI/Geom/1 queue with multiple working vacations, Queueing Systems, 56 (2007), 53-63.  doi: 10.1007/s11134-007-9030-0.  Google Scholar

[11]

M. F. Neuts, A versatile Markovian point process, Journal of Applied Probability, 16 (1979), 764-779.  doi: 10.1017/S0021900200033465.  Google Scholar

[12]

Z. Saffer and M. Telek, Analysis of BMAP/G/1 vacation model of non-M/G/1-type, in EPEW, vol. 5261 of LNCS, Springer, Mallorca, Spain, 2008,212–226. doi: 10.1007/978-3-540-87412-6_16.  Google Scholar

[13]

Z. Saffer and M. Telek, Closed form results for BMAP/G/1 vacation model with binomial type disciplines, Publ. Math. Debrecen, 76 (2010), 359-378.   Google Scholar

[14]

Z. Saffer and W. Yue, M/M/c multiple synchronous vacation model with gated discipline, Journal of Industrial and Management Optimization (JIMO), 8 (2012), 939-968.  doi: 10.3934/jimo.2012.8.939.  Google Scholar

[15]

W. -H. Steeb, Matrix Calculus and Kronecker Product with Applications and C++ Programs World Scientific, 1997. doi: 10.1142/3572.  Google Scholar

[16]

H. Takagi, Queueing Analysis -A Foundation of Performance Evaluation, Vacation and Prority Systems, vol. 1 North-Holland, New York, 1991.  Google Scholar

[17]

N. Tian and Z. G. Zhang, Vacation Queueing Models: Theory and Applications vol. 93, Springer Science & Business Media, 2006.  Google Scholar

[18]

D. Wu and H. Takagi, M/G/1 queue with multiple working vacations, Performance Evaluation, 63 (2006), 654-681.  doi: 10.1016/j.peva.2005.05.005.  Google Scholar

show all references

References:
[1]

A.-S. Alfa, A discrete MAP/PH/1 queue with vacations and exhaustive time-limited service, Oper. Res. Lett., 18 (1995), 31-40.  doi: 10.1016/0167-6377(95)00015-C.  Google Scholar

[2]

A.-S. Alfa, Discrete time analysis of MAP/PH/1 vacation queue with gated time-limited service, Queueing Systems, 29 (1998), 35-54.  doi: 10.1023/A:1019123828374.  Google Scholar

[3]

Y. Baba, Analysis of a GI/M/1 queue with multiple working vacations, Operation Research Letters, 33 (2005), 201-209.  doi: 10.1016/j.orl.2004.05.006.  Google Scholar

[4]

S. Chang and T. Takine, Factorization and stochastic decomposition properties in bulk queues with generalized vacations, Queueing Systems, 50 (2005), 165-183.  doi: 10.1007/s11134-005-0510-9.  Google Scholar

[5]

B. T. Doshi, Queueing systems with vacations -a survey, Queueing Systems, 1 (1986), 29-66.  doi: 10.1007/BF01149327.  Google Scholar

[6]

N. S. C. Goswami, The discrete-time MAP/PH/1 queue with multiple working vacations, Applied Mathematical Modelling, 34 (2010), 931-946.  doi: 10.1016/j.apm.2009.07.021.  Google Scholar

[7]

G. HorváthB. Van Houdt and M. Telek, Commuting matrices in the queue length and sojourn time analysis of MAP/MAP/1 queues, Stochastic Models, 30 (2014), 554-575.  doi: 10.1080/15326349.2014.930669.  Google Scholar

[8]

J.-C. KeC.-H. Wu and Z. G. Zhang, Recent developments in vacation queueing models: A short survey, International Journal of Operations Research, 7 (2010), 3-8.   Google Scholar

[9]

G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling ASA-SIAM Series on Statistics and Applied Probability, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; American Statistical Association, Alexandria, VA, 1999. doi: 10.1137/1.9780898719734.  Google Scholar

[10]

J. H. LiN. S. Tian and W. Liu, Discrete-time GI/Geom/1 queue with multiple working vacations, Queueing Systems, 56 (2007), 53-63.  doi: 10.1007/s11134-007-9030-0.  Google Scholar

[11]

M. F. Neuts, A versatile Markovian point process, Journal of Applied Probability, 16 (1979), 764-779.  doi: 10.1017/S0021900200033465.  Google Scholar

[12]

Z. Saffer and M. Telek, Analysis of BMAP/G/1 vacation model of non-M/G/1-type, in EPEW, vol. 5261 of LNCS, Springer, Mallorca, Spain, 2008,212–226. doi: 10.1007/978-3-540-87412-6_16.  Google Scholar

[13]

Z. Saffer and M. Telek, Closed form results for BMAP/G/1 vacation model with binomial type disciplines, Publ. Math. Debrecen, 76 (2010), 359-378.   Google Scholar

[14]

Z. Saffer and W. Yue, M/M/c multiple synchronous vacation model with gated discipline, Journal of Industrial and Management Optimization (JIMO), 8 (2012), 939-968.  doi: 10.3934/jimo.2012.8.939.  Google Scholar

[15]

W. -H. Steeb, Matrix Calculus and Kronecker Product with Applications and C++ Programs World Scientific, 1997. doi: 10.1142/3572.  Google Scholar

[16]

H. Takagi, Queueing Analysis -A Foundation of Performance Evaluation, Vacation and Prority Systems, vol. 1 North-Holland, New York, 1991.  Google Scholar

[17]

N. Tian and Z. G. Zhang, Vacation Queueing Models: Theory and Applications vol. 93, Springer Science & Business Media, 2006.  Google Scholar

[18]

D. Wu and H. Takagi, M/G/1 queue with multiple working vacations, Performance Evaluation, 63 (2006), 654-681.  doi: 10.1016/j.peva.2005.05.005.  Google Scholar

Figure 1.  Subset relations of the considered special vacation queue models
Figure 2.  Cycles in the evolution of the queue
Figure 3.  The mean number of jobs in the system
Table 1.  Vector β as a function of the vacation distribution
Uniform Exponential Weibull
The general model (0.546, 0.109, 0.345) (0.543, 0.116, 0.341) (0.539, 0.142, 0.319)
The MAP/MAP/1
vacation queue
(0.214, 0.097, 0.091,
… 0.04, 0.382, 0.176)
(0.214, 0.097, 0.091,
… 0.04, 0.382, 0.176)
(0.214, 0.097, 0.091,
… 0.04, 0.382, 0.176)
QBD vac. queue(0.546, 0.109, 0.345) (0.543, 0.115, 0.342)(0.53, 0.14, 0.33)
The indep. QBD
vacation queue
(0.21, 0.101, 0.09,
… 0.041, 0.373, 0.185)
(0.207, 0.104, 0.089,
… 0.042, 0.367, 0.191)
(0.197, 0.113, 0.086,
… 0.046, 0.348, 0.21)
Uniform Exponential Weibull
The general model (0.546, 0.109, 0.345) (0.543, 0.116, 0.341) (0.539, 0.142, 0.319)
The MAP/MAP/1
vacation queue
(0.214, 0.097, 0.091,
… 0.04, 0.382, 0.176)
(0.214, 0.097, 0.091,
… 0.04, 0.382, 0.176)
(0.214, 0.097, 0.091,
… 0.04, 0.382, 0.176)
QBD vac. queue(0.546, 0.109, 0.345) (0.543, 0.115, 0.342)(0.53, 0.14, 0.33)
The indep. QBD
vacation queue
(0.21, 0.101, 0.09,
… 0.041, 0.373, 0.185)
(0.207, 0.104, 0.089,
… 0.042, 0.367, 0.191)
(0.197, 0.113, 0.086,
… 0.046, 0.348, 0.21)
[1]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094

[2]

Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565

[3]

Xiaohong Li, Mingxin Sun, Zhaohua Gong, Enmin Feng. Multistage optimal control for microbial fed-batch fermentation process. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021040

[4]

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

[5]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

[6]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[7]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

[8]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931

[9]

Jiaquan Liu, Xiangqing Liu, Zhi-Qiang Wang. Sign-changing solutions for a parameter-dependent quasilinear equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1779-1799. doi: 10.3934/dcdss.2020454

[10]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210

[11]

Lucas C. F. Ferreira, Jhean E. Pérez-López, Élder J. Villamizar-Roa. On the product in Besov-Lorentz-Morrey spaces and existence of solutions for the stationary Boussinesq equations. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2423-2439. doi: 10.3934/cpaa.2018115

[12]

Vo Anh Khoa, Thi Kim Thoa Thieu, Ekeoma Rowland Ijioma. On a pore-scale stationary diffusion equation: Scaling effects and correctors for the homogenization limit. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2451-2477. doi: 10.3934/dcdsb.2020190

[13]

Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024

[14]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[15]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446

[16]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269

[17]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065

[18]

Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175

[19]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521

[20]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (97)
  • HTML views (393)
  • Cited by (0)

Other articles
by authors

[Back to Top]