American Institute of Mathematical Sciences

July  2017, (3): 1329-1345. doi: 10.3934/jimo.2016075

Single server retrial queues with setup time

 Division of Policy and Planning Sciences, Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan

Received  September 2015 Revised  May 2016 Published  October 2016

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

This paper considers single server retrial queues with setup time where the server is aware of the existence of retrying customers. In the basic model, the server is switched off immediately when the system becomes empty in order to save energy consumption. Arriving customers that see the server occupied join the orbit and repeat their attempt after some random time. The new feature of our models is that an arriving customer that sees the server off waits at the server and the server is turned on. The server needs some setup time to be active so as to serve the waiting customer. If the server completes a service and the orbit is not empty, it stays idle waiting for either a new or retrial customer. Under the assumption that the service time and the setup time are arbitrarily distributed, we obtain explicit expressions for the generating functions of the joint queue length. We also obtain recursive formulas for computing the moments of the queue length. We then consider an extended model where the server has a closedown time before being turned off for which an explicit solution is also obtained.

Citation: Tuan Phung-Duc. Single server retrial queues with setup time. Journal of Industrial & Management Optimization, 2017, (3) : 1329-1345. doi: 10.3934/jimo.2016075
References:
 [1] J. R. Artalejo, Analysis of an M/G/1 queue with constant repeated attempts and server vacations, Computers and Operations Research, 24 (1997), 493-504.  doi: 10.1016/S0305-0548(96)00076-7.  Google Scholar [2] L. A. Barroso and U. Holzle, The case for energy-proportional computing, Computer, 40 (2007), 33-37.  doi: 10.1109/MC.2007.443.  Google Scholar [3] W. Bischof, Analysis of M/G/1-queues with setup times and vacations under six different service disciplines, Queueing Systems, 39 (2001), 265-301.  doi: 10.1023/A:1013992708103.  Google Scholar [4] S. Derkic and J. E. Stafford, Symbolic computation of moments in priority queues, INFORMS Journal on Computing, 14 (2002), 261-277.  doi: 10.1287/ijoc.14.3.261.115.  Google Scholar [5] S. Drekic, J. E. Stafford and G. E. Willmot, Symbolic calculation of the moments of the time of ruin, Insurance: Mathematics and Economics, 34 (2004), 109-120.  doi: 10.1016/j.insmatheco.2003.11.004.  Google Scholar [6] T. V. Do, M/M/1 retrial queue with working vacations, Acta Informatica, 47 (2010), 67-75.  doi: 10.1007/s00236-009-0110-y.  Google Scholar [7] G. I. Falin and J. G. C. Templeton, Retrial Queues Chapman and Hall, London, 1997. Google Scholar [8] A. Gandhi, M. Harchol-Balter and M. A. Kozuch, Are sleep states effective in data centers?, Proceedings of IEEE 2012 International Green Computing Conference (IGCC), (2012), 1-10.  doi: 10.1109/IGCC.2012.6322260.  Google Scholar [9] A. Gandhi, S. Doroudi, M. Harchol-Balter and A. Scheller-Wolf, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Proceedings of the ACM SIGMETRICS, (2013), 153-166.   Google Scholar [10] A. Gandhi, S. Doroudi, M. Harchol-Balter and A. Scheller-Wolf, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Queueing Systems, 77 (2014), 177-209.  doi: 10.1007/s11134-014-9409-7.  Google Scholar [11] S. Kapodistria, T. Phung-Duc and J. Resing, Linear birth/immigration-death process with binomial catastrophes, Probability in the Engineering and Informational Sciences, 30 (2016), 79-111.  doi: 10.1017/S0269964815000297.  Google Scholar [12] V. J. Maccio and D. G. Down, On optimal policies for energy-aware servers, Performance Evaluation, 90 (2013), 36-52.  doi: 10.1109/MASCOTS.2013.11.  Google Scholar [13] I. Mitrani, Managing performance and power consumption in a server farm, Annals of Operations Research, 202 (2013), 121-134.  doi: 10.1007/s10479-011-0932-1.  Google Scholar [14] T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, M/M/3/3 and M/M/4/4 retrial queues, Journal of Industrial and Management Optimization, 5 (2009), 431-451.  doi: 10.3934/jimo.2009.5.431.  Google Scholar [15] T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, State-dependent M/M/c/c+ r retrial queues with Bernoulli abandonment, Journal of Industrial and Management Optimization, 6 (2010), 517-540.  doi: 10.3934/jimo.2010.6.517.  Google Scholar [16] T. Phung-Duc, An explicit solution for a tandem queue with retrials and losses, Operational Research, 12 (2012), 189-207.  doi: 10.1007/s12351-011-0113-7.  Google Scholar [17] T. Phung-Duc, Impatient customers in power-saving data centers, Lecture Notes in Computer Science, 8499 (2014), 185-199.  doi: 10.1007/978-3-319-08219-6_13.  Google Scholar [18] T. Phung-Duc, Server farms with batch arrival and staggered setup, Proceedings of the Fifth Symposium on Information and Communication Technology, (2014), 240-247.  doi: 10.1145/2676585.2676613.  Google Scholar [19] T. Phung-Duc, Exact solutions for M/M/$c$/Setup queues Telecommunication Systems 2016. doi: 10.1007/s11235-016-0177-z.  Google Scholar [20] T. Phung-Duc, Multiserver queues with finite capacity and setup time, Lecture Notes in Computer Science, 9081 (2015), 173-187.  doi: 10.1007/978-3-319-18579-8_13.  Google Scholar [21] T. Phung-Duc, M/M/1/1 retrial queues with setup time, Advances in Intelligent Systems and Computing, 383 (2015), 93-104.  doi: 10.1007/978-3-319-22267-7_9.  Google Scholar [22] C. Schwartz, R. Pries and P. Tran-Gia, A queuing analysis of an energy-saving mechanism in data centers, Proceedings of IEEE 2012 International Conference on Information Networking (ICOIN), (2012), 70-75.  doi: 10.1109/ICOIN.2012.6164352.  Google Scholar [23] H. Takagi, Priority queues with setup times, Operations Research, 38 (1990), 667-677.  doi: 10.1287/opre.38.4.667.  Google Scholar [24] H. Takagi and K. Sakamaki, Symbolic moment calculation for the sojourn time in M/G/1 queues with Bernoulli feedback, Journal of the Operations Research Society of Japan, 42 (1999), 78-87.  doi: 10.1016/S0453-4514(99)80006-4.  Google Scholar [25] H. Takagi and K. Sakamaki, Moments for M/G/1 queues, Mathematica Journal, 6 (1996), 75-80.   Google Scholar [26] H. Takagi and S. Kudoh, Symbolic higher-order moments of the waiting time in an M/G/1 queue with random order of service, Stochastic Models, (1997), 167-179.  doi: 10.1080/15326349708807419.  Google Scholar

show all references

References:
 [1] J. R. Artalejo, Analysis of an M/G/1 queue with constant repeated attempts and server vacations, Computers and Operations Research, 24 (1997), 493-504.  doi: 10.1016/S0305-0548(96)00076-7.  Google Scholar [2] L. A. Barroso and U. Holzle, The case for energy-proportional computing, Computer, 40 (2007), 33-37.  doi: 10.1109/MC.2007.443.  Google Scholar [3] W. Bischof, Analysis of M/G/1-queues with setup times and vacations under six different service disciplines, Queueing Systems, 39 (2001), 265-301.  doi: 10.1023/A:1013992708103.  Google Scholar [4] S. Derkic and J. E. Stafford, Symbolic computation of moments in priority queues, INFORMS Journal on Computing, 14 (2002), 261-277.  doi: 10.1287/ijoc.14.3.261.115.  Google Scholar [5] S. Drekic, J. E. Stafford and G. E. Willmot, Symbolic calculation of the moments of the time of ruin, Insurance: Mathematics and Economics, 34 (2004), 109-120.  doi: 10.1016/j.insmatheco.2003.11.004.  Google Scholar [6] T. V. Do, M/M/1 retrial queue with working vacations, Acta Informatica, 47 (2010), 67-75.  doi: 10.1007/s00236-009-0110-y.  Google Scholar [7] G. I. Falin and J. G. C. Templeton, Retrial Queues Chapman and Hall, London, 1997. Google Scholar [8] A. Gandhi, M. Harchol-Balter and M. A. Kozuch, Are sleep states effective in data centers?, Proceedings of IEEE 2012 International Green Computing Conference (IGCC), (2012), 1-10.  doi: 10.1109/IGCC.2012.6322260.  Google Scholar [9] A. Gandhi, S. Doroudi, M. Harchol-Balter and A. Scheller-Wolf, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Proceedings of the ACM SIGMETRICS, (2013), 153-166.   Google Scholar [10] A. Gandhi, S. Doroudi, M. Harchol-Balter and A. Scheller-Wolf, Exact analysis of the M/M/k/setup class of Markov chains via recursive renewal reward, Queueing Systems, 77 (2014), 177-209.  doi: 10.1007/s11134-014-9409-7.  Google Scholar [11] S. Kapodistria, T. Phung-Duc and J. Resing, Linear birth/immigration-death process with binomial catastrophes, Probability in the Engineering and Informational Sciences, 30 (2016), 79-111.  doi: 10.1017/S0269964815000297.  Google Scholar [12] V. J. Maccio and D. G. Down, On optimal policies for energy-aware servers, Performance Evaluation, 90 (2013), 36-52.  doi: 10.1109/MASCOTS.2013.11.  Google Scholar [13] I. Mitrani, Managing performance and power consumption in a server farm, Annals of Operations Research, 202 (2013), 121-134.  doi: 10.1007/s10479-011-0932-1.  Google Scholar [14] T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, M/M/3/3 and M/M/4/4 retrial queues, Journal of Industrial and Management Optimization, 5 (2009), 431-451.  doi: 10.3934/jimo.2009.5.431.  Google Scholar [15] T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, State-dependent M/M/c/c+ r retrial queues with Bernoulli abandonment, Journal of Industrial and Management Optimization, 6 (2010), 517-540.  doi: 10.3934/jimo.2010.6.517.  Google Scholar [16] T. Phung-Duc, An explicit solution for a tandem queue with retrials and losses, Operational Research, 12 (2012), 189-207.  doi: 10.1007/s12351-011-0113-7.  Google Scholar [17] T. Phung-Duc, Impatient customers in power-saving data centers, Lecture Notes in Computer Science, 8499 (2014), 185-199.  doi: 10.1007/978-3-319-08219-6_13.  Google Scholar [18] T. Phung-Duc, Server farms with batch arrival and staggered setup, Proceedings of the Fifth Symposium on Information and Communication Technology, (2014), 240-247.  doi: 10.1145/2676585.2676613.  Google Scholar [19] T. Phung-Duc, Exact solutions for M/M/$c$/Setup queues Telecommunication Systems 2016. doi: 10.1007/s11235-016-0177-z.  Google Scholar [20] T. Phung-Duc, Multiserver queues with finite capacity and setup time, Lecture Notes in Computer Science, 9081 (2015), 173-187.  doi: 10.1007/978-3-319-18579-8_13.  Google Scholar [21] T. Phung-Duc, M/M/1/1 retrial queues with setup time, Advances in Intelligent Systems and Computing, 383 (2015), 93-104.  doi: 10.1007/978-3-319-22267-7_9.  Google Scholar [22] C. Schwartz, R. Pries and P. Tran-Gia, A queuing analysis of an energy-saving mechanism in data centers, Proceedings of IEEE 2012 International Conference on Information Networking (ICOIN), (2012), 70-75.  doi: 10.1109/ICOIN.2012.6164352.  Google Scholar [23] H. Takagi, Priority queues with setup times, Operations Research, 38 (1990), 667-677.  doi: 10.1287/opre.38.4.667.  Google Scholar [24] H. Takagi and K. Sakamaki, Symbolic moment calculation for the sojourn time in M/G/1 queues with Bernoulli feedback, Journal of the Operations Research Society of Japan, 42 (1999), 78-87.  doi: 10.1016/S0453-4514(99)80006-4.  Google Scholar [25] H. Takagi and K. Sakamaki, Moments for M/G/1 queues, Mathematica Journal, 6 (1996), 75-80.   Google Scholar [26] H. Takagi and S. Kudoh, Symbolic higher-order moments of the waiting time in an M/G/1 queue with random order of service, Stochastic Models, (1997), 167-179.  doi: 10.1080/15326349708807419.  Google Scholar
Transitions among states
Transition among states
Probability of OFF state against $\alpha$ ($\rho = 0.7$)
Mean number of jobs in orbit against $\alpha$ ($\rho = 0.7$)
Probability of OFF state against $\alpha$ ($\rho = 0.1$)
Mean number of jobs in orbit against $\alpha$ ($\rho = 0.1$)
 [1] Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1 [2] Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907 [3] Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379 [4] Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617 [5] Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045 [6] Ravi Anand, Dibyendu Roy, Santanu Sarkar. Some results on lightweight stream ciphers Fountain v1 & Lizard. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020128 [7] Christophe Zhang. Internal rapid stabilization of a 1-D linear transport equation with a scalar feedback. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021006 [8] Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617 [9] Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $p$-ary $t$-weight linear codes to Ramanujan Cayley graphs with $t+1$ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133 [10] Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199 [11] Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075 [12] Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183 [13] Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493 [14] Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189 [15] Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258 [16] Linlin Li, Bedreddine Ainseba. Large-time behavior of matured population in an age-structured model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2561-2580. doi: 10.3934/dcdsb.2020195 [17] Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044 [18] Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069 [19] Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200 [20] Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015

2019 Impact Factor: 1.366