American Institute of Mathematical Sciences

• Previous Article
Does the existence of "talented outliers" help improve team performance? Modeling heterogeneous personalities in teamwork
• JIMO Home
• This Issue
• Next Article
Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times
September  2020, 16(5): 2459-2477. doi: 10.3934/jimo.2019063

Algorithmic computation of MAP/PH/1 queue with finite system capacity and two-stage vacations

 School of Mathematics and Statistics, Nanjing University of Information Science and Technology, Nanjing, Jiangsu 210044, China

* Corresponding author: Qingqing Ye

Received  November 2018 Revised  February 2019 Published  May 2019

Fund Project: The first author is supported by Natural Science Foundation of Jiangsu Province (grant Nos. BK20180783, 18KJB110021), and The Startup Foundation for Introducing Talent of Nanjing University of Information Science and Technology(grant No. 2017r082)

In this article, we study a discrete-time MAP/PH/1 queue with finite system capacity and two-stage vacations. The two-stage vacations policy which comprises single working vacation and multiple vacations is featured by that once the system is empty during the regular busy period, the system first takes the working vacation during which the server can still provide the service but at a lower service rate. After this working vacation, if the system is empty, the server will take a vacation during which the server stops its service completely, otherwise, the server resumes to the normal service rate. For this queue, using the matrix-geometric combination solution method, we obtain the stationary probability vectors when the traffic intensity is not equal to one. In addition, we discuss the spectrum properties of the key matrices and give their decomposition results that can be used to reduce the computation loads. Further, waiting time is derived by constructing an absorbing Markov chain. Various performance measures are obtained. At last, some numerical examples are presented to show the impacts of system parameters on performance measures.

Citation: Qingqing Ye. Algorithmic computation of MAP/PH/1 queue with finite system capacity and two-stage vacations. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2459-2477. doi: 10.3934/jimo.2019063
References:
 [1] A. Alfa, A discrete MAP/PH/1 queue with vacations and exhaustive time-limited service, Operations Research Letters, 18 (1995), 31-40.  doi: 10.1016/0167-6377(95)00015-C.  Google Scholar [2] A. Alfa, Discrete time analysis of MAP/PH/1 vacation queue with gated time service, Queueing Systems, 29 (1998), 35-54.  doi: 10.1023/A:1019123828374.  Google Scholar [3] A. Alfa, Some decomposition results for a class of vacation queue, Operations Research Letters, 42 (2014), 140-144.  doi: 10.1016/j.orl.2014.01.005.  Google Scholar [4] N. Akar, N. Oguz and K. Sohraby, A Novel Computational Method for Solving Finite QBD Processes, Stochastic Models, 16 (2000), 273-311.  doi: 10.1080/15326340008807588.  Google Scholar [5] Y. Baba, Analysis of a GI/M/1 queue with multiple working vacations, Operations Research Letters, 33 (2005), 201-209.  doi: 10.1016/j.orl.2004.05.006.  Google Scholar [6] Y. Baba, The M/PH/1 queue with working vacations and vacation interruption, journal of Systems Science and Systems Engineering, 19 (2010), 496-503.  doi: 10.1007/s11518-010-5149-3.  Google Scholar [7] A. Banik, Stationary analysis of a BMAP/R/1 queue with R-type multiple working vacations, Communications in Statistics-Simulation and Computation, 46 (2015), 1035-1061.  doi: 10.1080/03610918.2014.990096.  Google Scholar [8] R. Bartel and G. Stewart, Solution of the equation AX+XB = C, Communications of the ACM, 15 (1972), 820-826.   Google Scholar [9] V. Chandrasekaran, V. Indhira, M. Saravanarajan and P. Rajadurai, A survey on working vacation queueing models, International Journal of Pure and Applied Mathematics, 106 (2016), 33-41.   Google Scholar [10] S. Chakravarthy and S. Ozkar, MAP/PH/1 queueing model with working vacation and crowdsourcing, Mathematica Applicanda, 44 (2016), 263-294.  doi: 10.14708/ma.v44i2.1244.  Google Scholar [11] B. Doshi, Queueing systems with vacations–A survey, Mathematica Applicanda, 1 (1986), 29-66.  doi: 10.1007/BF01149327.  Google Scholar [12] H. Gail, S. Hantler and B. Taylor, Solutions of the basic matrix equation for M/G/1 and G/M/1 type Markov chain, Stochastic Models, 10 (1994), 1-43.  doi: 10.1080/15326349408807287.  Google Scholar [13] S. Gao, J. Wang and W. Li, An M/G/1 retrial queue with general retrial times, working vacations and vacation interruption, Asia-Pacific Journal of Operational Research, 31 (2014), 1440006. doi: 10.1142/S0217595914400065.  Google Scholar [14] D. Gaver, P. Jacobs and G. Latouche, Finite birth-and-death models in randomly changing environments, Advances in applied probability, 16 (1984), 715-731.  doi: 10.2307/1427338.  Google Scholar [15] C. Goswami and N. Selvaraju, 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 [16] A. Graham, Kronecker Products and Matrix Calculus: With Applications, John-Wiley, New York, 1981. Google Scholar [17] J. Kim, D. Choi and K. Chae, Analysis of Queue-length Distribution of the M/G/1 Queue with Working Vacation, Hawaii International Conference on Statistics and Related Fields, 2003. Google Scholar [18] D. Latouche and V. Ramaswamig, Introduction to matrix method in stochastic modelling, PA: Society for Industrial and Applied Mathematics, Philadelphia, 1999. doi: 10.1137/1.9780898719734.  Google Scholar [19] J. Li, N. 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 [20] J. Li and N. Tian, The discrete-time GI/Geom/1 queue with working vacations and vacation interruption, Applied Mathematics and Computation, 185 (2007), 1-10.  doi: 10.1016/j.amc.2006.07.008.  Google Scholar [21] J. Li and N. Tian, Performance analysis of a G/M/1 Queue with single working vacation, Applied Mathematics and Computation, 217 (2011), 4960-4971.  doi: 10.1016/j.amc.2010.11.045.  Google Scholar [22] J. Li, N. Tian, Z. Zhang and H. Luh, Analysis of the M/G/1 Queue with exponentially working vacations–a matrix analytic approach, Queueing Systems, 61 (2009), 139-166.  doi: 10.1007/s11134-008-9103-8.  Google Scholar [23] J. Li, W. Liu and N. Tian, Steady-state analysis of a discrete-time batch arrival queue withworking vacations, Performance Evaluation, 67 (2010), 897-912.   Google Scholar [24] T. Li, Z. Liu and Z. Wang, M/M/1 retrial queue with collisions and working vacation interruption under N-policy, RAIRO-Operations Research, 46 (2012), 355-371.  doi: 10.1051/ro/2012022.  Google Scholar [25] C. Luo, W. Li, K. Yu and C. Ding, The matrix-form solution for $Geo^X$ /G/1/N working vacation queue and its application to state-dependent cost control, Computers and Operations Research, 67 (2016), 63-74.  doi: 10.1016/j.cor.2015.07.015.  Google Scholar [26] V. Naumov, Matrix-mulrtiplicative approach to quasi-birth-death process analysis, in Matrix-Analytic Methods in Stochastic Models, Marcel Dekker, New York, 1996, 87–106. Google Scholar [27] M. Neuts, Matrix-geometric Soloution in Stochastic Model, Johns Hopkins University Press, Baltimore, MD, 1981.   Google Scholar [28] M. Neuts, tructured Stochastic Matrices of M/G/1 Type and Their Applications, Marcel Dekker, New York, 1989. Google Scholar [29] L. Servi and S. Finn, M/M/1 queues with working vacation (M/M/1/WV), Performance Evaluation, 50 (2002), 41-52.  doi: 10.1016/S0166-5316(02)00057-3.  Google Scholar [30] C. Sreenivasan, S. Chakravarthy and A. Krishnamoorthy, MAP / PH /1 queue with working vacations, vacation interruptions and N policy, Applied Mathematical Modelling, 37 (2013), 3879-3893.  doi: 10.1016/j.apm.2012.07.054.  Google Scholar [31] N. Tian and Z. Zhang, Vacation Queueing Models-Theory and Application, Springer-Verlag, New York, 2006. Google Scholar [32] N. Tian, Z. Ma and M. Liu, The discrete time Geom/Geom/1 queue with multiple working vacations, Applied Mathematical Modelling, 32 (2008), 2941-2953.  doi: 10.1016/j.apm.2007.10.005.  Google Scholar [33] N. Tian, J. Li and Z. Zhang, Matrix-analytic method and working vacation queues-survey, International Journal of Information and Management Sciences, 20 (2009), 603-633.   Google Scholar [34] A. Vadivu and R. Arumuganathan, Analysis of MAP/G/1/N queue with two phases of service under single (multiple) vacation(s), International Journal of Operational Research, 25 (2016), 47-76.  doi: 10.1504/IJOR.2016.073251.  Google Scholar [35] 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 [36] D. Yang and D. Wu, Cost-minimization analysis of a working vacation queue with N-policy and server breakdowns, Computers and Industrial Engineering, 82 (2015), 151-158.   Google Scholar [37] Q. Ye and L. Liu, The analysis of M/M/1 queue with two vacation policies (M/M/1/SWV+MV), International Journal of Computer Mathematics, 94 (2017), 115-134.  doi: 10.1080/00207160.2015.1091450.  Google Scholar [38] Q. Ye and L Liu, Performance Analysis of the GI/M/1 Queue with Single Working Vacation and Vacations, Methodology and Computing in Applied Probability, 19 (2017), 685-714.  doi: 10.1007/s11009-016-9496-5.  Google Scholar [39] Q. Ye and L Liu, The analysis of discrete time Geom/Geom/1 queue with single working vacation and multiple vacations (Geom/Geom/1/SWV+MV), RAIRO-Operations Research, 52 (2018), 95-117.  doi: 10.1051/ro/2017079.  Google Scholar [40] Q. Ye, The analysis of $M^X$/M/1 queue with two-stage vacations policy, Communications in Statistics-Theory and Methods, 2018. Google Scholar

show all references

References:
 [1] A. Alfa, A discrete MAP/PH/1 queue with vacations and exhaustive time-limited service, Operations Research Letters, 18 (1995), 31-40.  doi: 10.1016/0167-6377(95)00015-C.  Google Scholar [2] A. Alfa, Discrete time analysis of MAP/PH/1 vacation queue with gated time service, Queueing Systems, 29 (1998), 35-54.  doi: 10.1023/A:1019123828374.  Google Scholar [3] A. Alfa, Some decomposition results for a class of vacation queue, Operations Research Letters, 42 (2014), 140-144.  doi: 10.1016/j.orl.2014.01.005.  Google Scholar [4] N. Akar, N. Oguz and K. Sohraby, A Novel Computational Method for Solving Finite QBD Processes, Stochastic Models, 16 (2000), 273-311.  doi: 10.1080/15326340008807588.  Google Scholar [5] Y. Baba, Analysis of a GI/M/1 queue with multiple working vacations, Operations Research Letters, 33 (2005), 201-209.  doi: 10.1016/j.orl.2004.05.006.  Google Scholar [6] Y. Baba, The M/PH/1 queue with working vacations and vacation interruption, journal of Systems Science and Systems Engineering, 19 (2010), 496-503.  doi: 10.1007/s11518-010-5149-3.  Google Scholar [7] A. Banik, Stationary analysis of a BMAP/R/1 queue with R-type multiple working vacations, Communications in Statistics-Simulation and Computation, 46 (2015), 1035-1061.  doi: 10.1080/03610918.2014.990096.  Google Scholar [8] R. Bartel and G. Stewart, Solution of the equation AX+XB = C, Communications of the ACM, 15 (1972), 820-826.   Google Scholar [9] V. Chandrasekaran, V. Indhira, M. Saravanarajan and P. Rajadurai, A survey on working vacation queueing models, International Journal of Pure and Applied Mathematics, 106 (2016), 33-41.   Google Scholar [10] S. Chakravarthy and S. Ozkar, MAP/PH/1 queueing model with working vacation and crowdsourcing, Mathematica Applicanda, 44 (2016), 263-294.  doi: 10.14708/ma.v44i2.1244.  Google Scholar [11] B. Doshi, Queueing systems with vacations–A survey, Mathematica Applicanda, 1 (1986), 29-66.  doi: 10.1007/BF01149327.  Google Scholar [12] H. Gail, S. Hantler and B. Taylor, Solutions of the basic matrix equation for M/G/1 and G/M/1 type Markov chain, Stochastic Models, 10 (1994), 1-43.  doi: 10.1080/15326349408807287.  Google Scholar [13] S. Gao, J. Wang and W. Li, An M/G/1 retrial queue with general retrial times, working vacations and vacation interruption, Asia-Pacific Journal of Operational Research, 31 (2014), 1440006. doi: 10.1142/S0217595914400065.  Google Scholar [14] D. Gaver, P. Jacobs and G. Latouche, Finite birth-and-death models in randomly changing environments, Advances in applied probability, 16 (1984), 715-731.  doi: 10.2307/1427338.  Google Scholar [15] C. Goswami and N. Selvaraju, 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 [16] A. Graham, Kronecker Products and Matrix Calculus: With Applications, John-Wiley, New York, 1981. Google Scholar [17] J. Kim, D. Choi and K. Chae, Analysis of Queue-length Distribution of the M/G/1 Queue with Working Vacation, Hawaii International Conference on Statistics and Related Fields, 2003. Google Scholar [18] D. Latouche and V. Ramaswamig, Introduction to matrix method in stochastic modelling, PA: Society for Industrial and Applied Mathematics, Philadelphia, 1999. doi: 10.1137/1.9780898719734.  Google Scholar [19] J. Li, N. 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 [20] J. Li and N. Tian, The discrete-time GI/Geom/1 queue with working vacations and vacation interruption, Applied Mathematics and Computation, 185 (2007), 1-10.  doi: 10.1016/j.amc.2006.07.008.  Google Scholar [21] J. Li and N. Tian, Performance analysis of a G/M/1 Queue with single working vacation, Applied Mathematics and Computation, 217 (2011), 4960-4971.  doi: 10.1016/j.amc.2010.11.045.  Google Scholar [22] J. Li, N. Tian, Z. Zhang and H. Luh, Analysis of the M/G/1 Queue with exponentially working vacations–a matrix analytic approach, Queueing Systems, 61 (2009), 139-166.  doi: 10.1007/s11134-008-9103-8.  Google Scholar [23] J. Li, W. Liu and N. Tian, Steady-state analysis of a discrete-time batch arrival queue withworking vacations, Performance Evaluation, 67 (2010), 897-912.   Google Scholar [24] T. Li, Z. Liu and Z. Wang, M/M/1 retrial queue with collisions and working vacation interruption under N-policy, RAIRO-Operations Research, 46 (2012), 355-371.  doi: 10.1051/ro/2012022.  Google Scholar [25] C. Luo, W. Li, K. Yu and C. Ding, The matrix-form solution for $Geo^X$ /G/1/N working vacation queue and its application to state-dependent cost control, Computers and Operations Research, 67 (2016), 63-74.  doi: 10.1016/j.cor.2015.07.015.  Google Scholar [26] V. Naumov, Matrix-mulrtiplicative approach to quasi-birth-death process analysis, in Matrix-Analytic Methods in Stochastic Models, Marcel Dekker, New York, 1996, 87–106. Google Scholar [27] M. Neuts, Matrix-geometric Soloution in Stochastic Model, Johns Hopkins University Press, Baltimore, MD, 1981.   Google Scholar [28] M. Neuts, tructured Stochastic Matrices of M/G/1 Type and Their Applications, Marcel Dekker, New York, 1989. Google Scholar [29] L. Servi and S. Finn, M/M/1 queues with working vacation (M/M/1/WV), Performance Evaluation, 50 (2002), 41-52.  doi: 10.1016/S0166-5316(02)00057-3.  Google Scholar [30] C. Sreenivasan, S. Chakravarthy and A. Krishnamoorthy, MAP / PH /1 queue with working vacations, vacation interruptions and N policy, Applied Mathematical Modelling, 37 (2013), 3879-3893.  doi: 10.1016/j.apm.2012.07.054.  Google Scholar [31] N. Tian and Z. Zhang, Vacation Queueing Models-Theory and Application, Springer-Verlag, New York, 2006. Google Scholar [32] N. Tian, Z. Ma and M. Liu, The discrete time Geom/Geom/1 queue with multiple working vacations, Applied Mathematical Modelling, 32 (2008), 2941-2953.  doi: 10.1016/j.apm.2007.10.005.  Google Scholar [33] N. Tian, J. Li and Z. Zhang, Matrix-analytic method and working vacation queues-survey, International Journal of Information and Management Sciences, 20 (2009), 603-633.   Google Scholar [34] A. Vadivu and R. Arumuganathan, Analysis of MAP/G/1/N queue with two phases of service under single (multiple) vacation(s), International Journal of Operational Research, 25 (2016), 47-76.  doi: 10.1504/IJOR.2016.073251.  Google Scholar [35] 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 [36] D. Yang and D. Wu, Cost-minimization analysis of a working vacation queue with N-policy and server breakdowns, Computers and Industrial Engineering, 82 (2015), 151-158.   Google Scholar [37] Q. Ye and L. Liu, The analysis of M/M/1 queue with two vacation policies (M/M/1/SWV+MV), International Journal of Computer Mathematics, 94 (2017), 115-134.  doi: 10.1080/00207160.2015.1091450.  Google Scholar [38] Q. Ye and L Liu, Performance Analysis of the GI/M/1 Queue with Single Working Vacation and Vacations, Methodology and Computing in Applied Probability, 19 (2017), 685-714.  doi: 10.1007/s11009-016-9496-5.  Google Scholar [39] Q. Ye and L Liu, The analysis of discrete time Geom/Geom/1 queue with single working vacation and multiple vacations (Geom/Geom/1/SWV+MV), RAIRO-Operations Research, 52 (2018), 95-117.  doi: 10.1051/ro/2017079.  Google Scholar [40] Q. Ye, The analysis of $M^X$/M/1 queue with two-stage vacations policy, Communications in Statistics-Theory and Methods, 2018. Google Scholar
Schematic representation
E(L) versus N
Pempty versus N
Pfull versus N
PW versus N
PV versus N
PB versus N
Ploss versus N
lg (Ploss) versus N
E(L) versus N
Pempty versus N
Pfull versus N
PW versus N
PV versus N
PB versus N
Ploss versus N
lg(Ploss) versus N
ρ < 1
ρ > 1
 [1] Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016 [2] Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348 [3] Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, , () : -. doi: 10.3934/era.2020117 [4] Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013 [5] 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 [6] Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012 [7] Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264 [8] Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020049 [9] Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032 [10] Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079 [11] Anton A. Kutsenko. Isomorphism between one-Dimensional and multidimensional finite difference operators. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020270 [12] Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120 [13] Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $q$-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440 [14] Hai-Feng Huo, Shi-Ke Hu, Hong Xiang. Traveling wave solution for a diffusion SEIR epidemic model with self-protection and treatment. Electronic Research Archive, , () : -. doi: 10.3934/era.2020118 [15] Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018 [16] Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351 [17] Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073 [18] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [19] Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046 [20] Serena Dipierro, Benedetta Pellacci, Enrico Valdinoci, Gianmaria Verzini. Time-fractional equations with reaction terms: Fundamental solutions and asymptotics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 257-275. doi: 10.3934/dcds.2020137

2019 Impact Factor: 1.366