• Previous Article
    An integrated approach based on Fuzzy Inference System for scheduling and process planning through multiple objectives
  • JIMO Home
  • This Issue
  • Next Article
    Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs
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, 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.

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

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

[4]

N. AkarN. Oguz and K. Sohraby, A Novel Computational Method for Solving Finite QBD Processes, Stochastic Models, 16 (2000), 273-311. doi: 10.1080/15326340008807588.

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

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

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

[8]

R. Bartel and G. Stewart, Solution of the equation AX+XB = C, Communications of the ACM, 15 (1972), 820-826.

[9]

V. ChandrasekaranV. IndhiraM. Saravanarajan and P. Rajadurai, A survey on working vacation queueing models, International Journal of Pure and Applied Mathematics, 106 (2016), 33-41.

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

[11]

B. Doshi, Queueing systems with vacations–A survey, Mathematica Applicanda, 1 (1986), 29-66. doi: 10.1007/BF01149327.

[12]

H. GailS. 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.

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

[14]

D. GaverP. 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.

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

[16]

A. Graham, Kronecker Products and Matrix Calculus: With Applications, John-Wiley, New York, 1981.

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

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

[19]

J. LiN. 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.

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

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

[22]

J. LiN. TianZ. 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.

[23]

J. LiW. Liu and N. Tian, Steady-state analysis of a discrete-time batch arrival queue withworking vacations, Performance Evaluation, 67 (2010), 897-912.

[24]

T. LiZ. 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.

[25]

C. LuoW. LiK. 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.

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

[27] M. Neuts, Matrix-geometric Soloution in Stochastic Model, Johns Hopkins University Press, Baltimore, MD, 1981.
[28]

M. Neuts, tructured Stochastic Matrices of M/G/1 Type and Their Applications, Marcel Dekker, New York, 1989.

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

[30]

C. SreenivasanS. 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.

[31]

N. Tian and Z. Zhang, Vacation Queueing Models-Theory and Application, Springer-Verlag, New York, 2006.

[32]

N. TianZ. 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.

[33]

N. TianJ. Li and Z. Zhang, Matrix-analytic method and working vacation queues-survey, International Journal of Information and Management Sciences, 20 (2009), 603-633.

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

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

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

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

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

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

[40]

Q. Ye, The analysis of $M^X$/M/1 queue with two-stage vacations policy, Communications in Statistics-Theory and Methods, 2018.

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.

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

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

[4]

N. AkarN. Oguz and K. Sohraby, A Novel Computational Method for Solving Finite QBD Processes, Stochastic Models, 16 (2000), 273-311. doi: 10.1080/15326340008807588.

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

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

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

[8]

R. Bartel and G. Stewart, Solution of the equation AX+XB = C, Communications of the ACM, 15 (1972), 820-826.

[9]

V. ChandrasekaranV. IndhiraM. Saravanarajan and P. Rajadurai, A survey on working vacation queueing models, International Journal of Pure and Applied Mathematics, 106 (2016), 33-41.

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

[11]

B. Doshi, Queueing systems with vacations–A survey, Mathematica Applicanda, 1 (1986), 29-66. doi: 10.1007/BF01149327.

[12]

H. GailS. 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.

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

[14]

D. GaverP. 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.

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

[16]

A. Graham, Kronecker Products and Matrix Calculus: With Applications, John-Wiley, New York, 1981.

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

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

[19]

J. LiN. 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.

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

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

[22]

J. LiN. TianZ. 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.

[23]

J. LiW. Liu and N. Tian, Steady-state analysis of a discrete-time batch arrival queue withworking vacations, Performance Evaluation, 67 (2010), 897-912.

[24]

T. LiZ. 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.

[25]

C. LuoW. LiK. 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.

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

[27] M. Neuts, Matrix-geometric Soloution in Stochastic Model, Johns Hopkins University Press, Baltimore, MD, 1981.
[28]

M. Neuts, tructured Stochastic Matrices of M/G/1 Type and Their Applications, Marcel Dekker, New York, 1989.

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

[30]

C. SreenivasanS. 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.

[31]

N. Tian and Z. Zhang, Vacation Queueing Models-Theory and Application, Springer-Verlag, New York, 2006.

[32]

N. TianZ. 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.

[33]

N. TianJ. Li and Z. Zhang, Matrix-analytic method and working vacation queues-survey, International Journal of Information and Management Sciences, 20 (2009), 603-633.

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

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

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

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

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

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

[40]

Q. Ye, The analysis of $M^X$/M/1 queue with two-stage vacations policy, Communications in Statistics-Theory and Methods, 2018.

Figure 1.  Schematic representation
Figure 2.  E(L) versus N
Figure 3.  Pempty versus N
Figure 4.  Pfull versus N
Figure 5.  PW versus N
Figure 6.  PV versus N
Figure 7.  PB versus N
Figure 8.  Ploss versus N
Figure 9.  lg (Ploss) versus N
Figure 10.  E(L) versus N
Figure 11.  Pempty versus N
Figure 12.  Pfull versus N
Figure 13.  PW versus N
Figure 14.  PV versus N
Figure 15.  PB versus N
Figure 16.  Ploss versus N
Figure 17.  lg(Ploss) versus N
Figure 18.  ρ < 1
Figure 19.  ρ > 1
[1]

Shan Gao, Jinting Wang. On a discrete-time GI$^X$/Geo/1/N-G queue with randomized working vacations and at most $J$ vacations. Journal of Industrial & Management Optimization, 2015, 11 (3) : 779-806. doi: 10.3934/jimo.2015.11.779

[2]

Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discrete-time finite buffer queue. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1121-1133. doi: 10.3934/jimo.2016.12.1121

[3]

Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435

[4]

Bin Li, Jie Sun, Honglei Xu, Min Zhang. A class of two-stage distributionally robust games. Journal of Industrial & Management Optimization, 2019, 15 (1) : 387-400. doi: 10.3934/jimo.2018048

[5]

Dequan Yue, Jun Yu, Wuyi Yue. A Markovian queue with two heterogeneous servers and multiple vacations. Journal of Industrial & Management Optimization, 2009, 5 (3) : 453-465. doi: 10.3934/jimo.2009.5.453

[6]

Dequan Yue, Wuyi Yue, Gang Xu. Analysis of customers' impatience in an M/M/1 queue with working vacations. Journal of Industrial & Management Optimization, 2012, 8 (4) : 895-908. doi: 10.3934/jimo.2012.8.895

[7]

Sheng Zhu, Jinting Wang. Strategic behavior and optimal strategies in an M/G/1 queue with Bernoulli vacations. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1297-1322. doi: 10.3934/jimo.2018008

[8]

Jingzhi Li, Hongyu Liu, Qi Wang. Fast imaging of electromagnetic scatterers by a two-stage multilevel sampling method. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 547-561. doi: 10.3934/dcdss.2015.8.547

[9]

Zhiping Chen, Youpan Han. Continuity and stability of two-stage stochastic programs with quadratic continuous recourse. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 197-209. doi: 10.3934/naco.2015.5.197

[10]

Urszula Foryś, Beata Zduniak. Two-stage model of carcinogenic mutations with the influence of delays. Discrete & Continuous Dynamical Systems - B, 2014, 19 (8) : 2501-2519. doi: 10.3934/dcdsb.2014.19.2501

[11]

Hideaki Takagi. Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026

[12]

Yutaka Sakuma, Atsushi Inoie, Ken’ichi Kawanishi, Masakiyo Miyazawa. Tail asymptotics for waiting time distribution of an M/M/s queue with general impatient time. Journal of Industrial & Management Optimization, 2011, 7 (3) : 593-606. doi: 10.3934/jimo.2011.7.593

[13]

Shaojun Lan, Yinghui Tang. Performance analysis of a discrete-time $ Geo/G/1$ retrial queue with non-preemptive priority, working vacations and vacation interruption. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1421-1446. doi: 10.3934/jimo.2018102

[14]

Shaojun Lan, Yinghui Tang, Miaomiao Yu. System capacity optimization design and optimal threshold $N^{*}$ for a $GEO/G/1$ discrete-time queue with single server vacation and under the control of Min($N, V$)-policy. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1435-1464. doi: 10.3934/jimo.2016.12.1435

[15]

Dequan Yue, Wuyi Yue, Guoxi Zhao. Analysis of an M/M/1 queue with vacations and impatience timers which depend on the server's states. Journal of Industrial & Management Optimization, 2016, 12 (2) : 653-666. doi: 10.3934/jimo.2016.12.653

[16]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

[17]

Chien Hsun Tseng. Applications of a nonlinear optimization solver and two-stage comprehensive Denoising techniques for optimum underwater wideband sonar echolocation system. Journal of Industrial & Management Optimization, 2013, 9 (1) : 205-225. doi: 10.3934/jimo.2013.9.205

[18]

Dan Liu, Shigui Ruan, Deming Zhu. Stable periodic oscillations in a two-stage cancer model of tumor and immune system interactions. Mathematical Biosciences & Engineering, 2012, 9 (2) : 347-368. doi: 10.3934/mbe.2012.9.347

[19]

Biswajit Sarkar, Bijoy Kumar Shaw, Taebok Kim, Mitali Sarkar, Dongmin Shin. An integrated inventory model with variable transportation cost, two-stage inspection, and defective items. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1975-1990. doi: 10.3934/jimo.2017027

[20]

Rüdiger Schultz. Two-stage stochastic programs: Integer variables, dominance relations and PDE constraints. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 713-738. doi: 10.3934/naco.2012.2.713

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (7)
  • HTML views (54)
  • Cited by (0)

Other articles
by authors

[Back to Top]