
-
Previous Article
Delay characteristics in place-reservation queues with class-dependent service times
- JIMO Home
- This Issue
-
Next Article
Performance evaluation and optimization of cognitive radio networks with adjustable access control for multiple secondary users
Multiserver retrial queue with setup time and its application to data centers
1. | Division of Policy and Planning Sciences, Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan |
2. | Division of Electronics and Informatics, Gunma University, 1-5-1 Tenjin-cho, Kiryu, Gunma 376-8515, Japan |
This paper considers a multiserver retrial queue with setup time which is motivated from application in data centers with the ON-OFF policy, where an idle server is immediately turned off. The ON-OFF policy is designed to save energy consumption of idle servers because an idle server still consumes about 60% of its peak consumption processing jobs. Upon arrival, a job is allocated to one of available off-servers and that server is started up. Otherwise, if all the servers are not available upon arrival, the job is blocked and retries in a random time. A server needs some setup time during which the server cannot process a job but consumes energy. We formulate this model using a three-dimensional continuous-time Markov chain obtaining the stability condition via Foster-Lyapunov criteria. Interestingly, the stability condition is different from that of the corresponding non-retrial queue. Furthermore, exploiting the special structure of the Markov chain together with a heuristic technique, we develop an efficient algorithm for computing the stationary distribution. Numerical results reveal that under the ON-OFF policy, allowing retrials is more power-saving than buffering jobs. Furthermore, we obtain a new insight that if the setup time is relatively long, setting an appropriate retrial time could reduce both power consumption and the mean response time of jobs.
References:
[1] |
J. R. Artalejo and T. Phung-Duc,
Markovian retrial queues with two way communication, Journal of Industrial and Management Optimization, 8 (2012), 781-806.
doi: 10.3934/jimo.2012.8.781. |
[2] |
L. A. Barroso and U. Hölzle,
The case for energy-proportional computing, Computer, 40 (2007), 33-37.
doi: 10.1109/MC.2007.443. |
[3] |
L. Bright and P. G. Taylor,
Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes, Stochastic Models, 11 (1995), 497-525.
doi: 10.1080/15326349508807357. |
[4] |
J. Chang and J. Wang,
Unreliable M/M/1/1 retrial queues with set-up time, Quality Technology & Quantitative Management, (2017), 1-13.
doi: 10.1080/16843703.2017.1320459. |
[5] |
J. E. Diamond and A. S. Alfa,
The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998), 1151-1177.
doi: 10.1080/15326349808807518. |
[6] |
J. E. Diamond and A. S. Alfa,
Matrix analytic methods for a multiserver retrial queue with buffer, Top, 7 (1999), 249-266.
doi: 10.1007/BF02564725. |
[7] |
G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997. Google Scholar |
[8] |
A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138. Google Scholar |
[9] |
A. Gandhi, S. Doroudi and M. Harchol-Balter,
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. |
[10] |
Q.-M. He, H. Li and Y. Q. Zhao,
Ergodicity of the BMAP/PH/s/s + K retrial queue with PH-retrial times, Queueing Systems, 35 (2000), 323-347.
doi: 10.1023/A:1019110631467. |
[11] |
G. Latouche and V. Ramaswami,
A logarithmic reduction algorithm for quasi-birth-death process, Journal of Applied Probability, 30 (1993), 650-674.
doi: 10.1017/S0021900200044387. |
[12] |
G. Latouche and V. Ramaswami,
Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999. |
[13] |
E. Morozov,
A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007), 157-168.
doi: 10.1007/s11134-007-9024-y. |
[14] |
E. Morozov and T. Phung-Duc,
Stability analysis of a multiclass retrial system with classical retrial policy, Performance Evaluation, 112 (2017), 15-26.
doi: 10.1016/j.peva.2017.03.003. |
[15] |
M. F. Neuts,
Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994. |
[16] |
T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi,
A simple algorithm for the rate matrices of level-dependent QBD processes, Proceedings of the 5th International Conference on Queueing Theory and Network Applications, (2010), 46-52.
doi: 10.1145/1837856.1837864. |
[17] |
T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi,
A matrix continued fraction approach to multiserver retrial queues, Annals of Operations Research, 202 (2013), 161-183.
doi: 10.1007/s10479-011-0840-4. |
[18] |
T. Phung-Duc,
Server farms with batch arrival and staggered setup, Proceedings of the Fifth symposium on Information and Communication Technology (SoICT 2014), (2014), 240-247.
doi: 10.1145/2676585.2676613. |
[19] |
T. Phung-Duc and K. Kawanishi, An efficient method for performance analysis of blended call centers with redial,
Asia-Pacific Journal of Operational Research, 31 (2014), 1440008 (33 pages). |
[20] |
T. Phung-Duc, M/M/1/1 retrial queues with setup time, Proceedings of the 10th International Conference on Queueing Theory and Network Applications, (2015), 93-104. Google Scholar |
[21] |
T. Phung-Duc and K. Kawanishi, Impacts of retrials on power-saving policy in data centers in Proceedings of the 11th International Conference on Queueing Theory and Network Applications, ACM, (2016), Article No. 22.
doi: 10.1145/3016032.3016047. |
[22] |
T. Phung-Duc,
Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017), 309-324.
doi: 10.1007/s11235-016-0177-z. |
[23] |
T. Phung-Duc,
Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017), 1329-1345.
|
[24] |
Y. W. Shin,
Stability of $MAP/PH/c/K$ queue with customer retrials and server vacations, Bulletin of the Korean Mathematical Society, 53 (2016), 985-1004.
doi: 10.4134/BKMS.b150337. |
[25] |
R. L. Tweedie,
Sufficient conditions for regularity, recurrence and ergodicity and Markov processes, Mathematical Proceedings of the Cambridge Philosophical Society, 78 (1975), 125-136.
doi: 10.1017/S0305004100051562. |
show all references
References:
[1] |
J. R. Artalejo and T. Phung-Duc,
Markovian retrial queues with two way communication, Journal of Industrial and Management Optimization, 8 (2012), 781-806.
doi: 10.3934/jimo.2012.8.781. |
[2] |
L. A. Barroso and U. Hölzle,
The case for energy-proportional computing, Computer, 40 (2007), 33-37.
doi: 10.1109/MC.2007.443. |
[3] |
L. Bright and P. G. Taylor,
Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes, Stochastic Models, 11 (1995), 497-525.
doi: 10.1080/15326349508807357. |
[4] |
J. Chang and J. Wang,
Unreliable M/M/1/1 retrial queues with set-up time, Quality Technology & Quantitative Management, (2017), 1-13.
doi: 10.1080/16843703.2017.1320459. |
[5] |
J. E. Diamond and A. S. Alfa,
The MAP/PH/1 retrial queue, Stochastic Models, 14 (1998), 1151-1177.
doi: 10.1080/15326349808807518. |
[6] |
J. E. Diamond and A. S. Alfa,
Matrix analytic methods for a multiserver retrial queue with buffer, Top, 7 (1999), 249-266.
doi: 10.1007/BF02564725. |
[7] |
G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, London, 1997. Google Scholar |
[8] |
A. Gandhi, M. Harchol-Balter and I. Adan, Server farms with setup costs, Performance Evaluation, 67 (2010), 1123-1138. Google Scholar |
[9] |
A. Gandhi, S. Doroudi and M. Harchol-Balter,
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. |
[10] |
Q.-M. He, H. Li and Y. Q. Zhao,
Ergodicity of the BMAP/PH/s/s + K retrial queue with PH-retrial times, Queueing Systems, 35 (2000), 323-347.
doi: 10.1023/A:1019110631467. |
[11] |
G. Latouche and V. Ramaswami,
A logarithmic reduction algorithm for quasi-birth-death process, Journal of Applied Probability, 30 (1993), 650-674.
doi: 10.1017/S0021900200044387. |
[12] |
G. Latouche and V. Ramaswami,
Matrix Analytic Methods in Stochastic Modelling, ASA-SIAM Series on Statistics and Applied Probability, SIAM, Philadelphia PA, 1999. |
[13] |
E. Morozov,
A multiserver retrial queue: Regenerative stability analysis, Queueing Systems, 56 (2007), 157-168.
doi: 10.1007/s11134-007-9024-y. |
[14] |
E. Morozov and T. Phung-Duc,
Stability analysis of a multiclass retrial system with classical retrial policy, Performance Evaluation, 112 (2017), 15-26.
doi: 10.1016/j.peva.2017.03.003. |
[15] |
M. F. Neuts,
Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Dover Publications, Inc., New York, 1994. |
[16] |
T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi,
A simple algorithm for the rate matrices of level-dependent QBD processes, Proceedings of the 5th International Conference on Queueing Theory and Network Applications, (2010), 46-52.
doi: 10.1145/1837856.1837864. |
[17] |
T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi,
A matrix continued fraction approach to multiserver retrial queues, Annals of Operations Research, 202 (2013), 161-183.
doi: 10.1007/s10479-011-0840-4. |
[18] |
T. Phung-Duc,
Server farms with batch arrival and staggered setup, Proceedings of the Fifth symposium on Information and Communication Technology (SoICT 2014), (2014), 240-247.
doi: 10.1145/2676585.2676613. |
[19] |
T. Phung-Duc and K. Kawanishi, An efficient method for performance analysis of blended call centers with redial,
Asia-Pacific Journal of Operational Research, 31 (2014), 1440008 (33 pages). |
[20] |
T. Phung-Duc, M/M/1/1 retrial queues with setup time, Proceedings of the 10th International Conference on Queueing Theory and Network Applications, (2015), 93-104. Google Scholar |
[21] |
T. Phung-Duc and K. Kawanishi, Impacts of retrials on power-saving policy in data centers in Proceedings of the 11th International Conference on Queueing Theory and Network Applications, ACM, (2016), Article No. 22.
doi: 10.1145/3016032.3016047. |
[22] |
T. Phung-Duc,
Exact solutions for M/M/c/Setup queues, Telecommunication Systems, 64 (2017), 309-324.
doi: 10.1007/s11235-016-0177-z. |
[23] |
T. Phung-Duc,
Single server retrial queues with setup time, Journal of Industrial and Management Optimization, 13 (2017), 1329-1345.
|
[24] |
Y. W. Shin,
Stability of $MAP/PH/c/K$ queue with customer retrials and server vacations, Bulletin of the Korean Mathematical Society, 53 (2016), 985-1004.
doi: 10.4134/BKMS.b150337. |
[25] |
R. L. Tweedie,
Sufficient conditions for regularity, recurrence and ergodicity and Markov processes, Mathematical Proceedings of the Cambridge Philosophical Society, 78 (1975), 125-136.
doi: 10.1017/S0305004100051562. |




| | | |
| 1203 | 150 | 59 |
| | | |
| | | |
| 1203 | 150 | 59 |
| | | |
| | | |
| 1203 | 149 | 58 |
| | | |
| | | |
| 1203 | 149 | 58 |
| | | |
| ||||
| | | | |
0.1 | 39 | | 39 | |
0.2 | 66 | | 66 | |
0.3 | 92 | | 92 | |
0.4 | 118 | | 118 | |
0.5 | 144 | | 144 | |
0.6 | 170 | | 170 | |
0.7 | 197 | | 196 | |
0.8 | 228 | | 227 | |
0.9 | 349 | | 321 | |
| ||||
| | | | |
0.1 | 39 | | 39 | |
0.2 | 66 | | 66 | |
0.3 | 92 | | 92 | |
0.4 | 118 | | 118 | |
0.5 | 144 | | 144 | |
0.6 | 170 | | 170 | |
0.7 | 197 | | 196 | |
0.8 | 228 | | 227 | |
0.9 | 349 | | 321 | |
[1] |
Takeshi Saito, Kazuyuki Yagasaki. Chebyshev spectral methods for computing center manifolds. Journal of Computational Dynamics, 2021 doi: 10.3934/jcd.2021008 |
[2] |
Lei Lei, Wenli Ren, Cuiling Fan. The differential spectrum of a class of power functions over finite fields. Advances in Mathematics of Communications, 2021, 15 (3) : 525-537. doi: 10.3934/amc.2020080 |
[3] |
Yohei Yamazaki. Center stable manifolds around line solitary waves of the Zakharov–Kuznetsov equation with critical speed. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3579-3614. doi: 10.3934/dcds.2021008 |
[4] |
Yusra Bibi Ruhomally, Muhammad Zaid Dauhoo, Laurent Dumas. A graph cellular automaton with relation-based neighbourhood describing the impact of peer influence on the consumption of marijuana among college-aged youths. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021011 |
[5] |
Qiang Lin, Yang Xiao, Jingju Zheng. Selecting the supply chain financing mode under price-sensitive demand: Confirmed warehouse financing vs. trade credit. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2031-2049. doi: 10.3934/jimo.2020057 |
[6] |
Paul E. Anderson, Timothy P. Chartier, Amy N. Langville, Kathryn E. Pedings-Behling. The rankability of weighted data from pairwise comparisons. Foundations of Data Science, 2021, 3 (1) : 1-26. doi: 10.3934/fods.2021002 |
[7] |
Zhang Chen, Xiliang Li, Bixiang Wang. Invariant measures of stochastic delay lattice systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3235-3269. doi: 10.3934/dcdsb.2020226 |
[8] |
Imene Aicha Djebour, Takéo Takahashi, Julie Valein. Feedback stabilization of parabolic systems with input delay. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021027 |
[9] |
Mirelson M. Freitas, Anderson J. A. Ramos, Manoel J. Dos Santos, Jamille L.L. Almeida. Dynamics of piezoelectric beams with magnetic effects and delay term. Evolution Equations & Control Theory, 2021 doi: 10.3934/eect.2021015 |
[10] |
Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389 |
[11] |
Cheng-Kai Hu, Fung-Bao Liu, Hong-Ming Chen, Cheng-Feng Hu. Network data envelopment analysis with fuzzy non-discretionary factors. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1795-1807. doi: 10.3934/jimo.2020046 |
[12] |
Woocheol Choi, Youngwoo Koh. On the splitting method for the nonlinear Schrödinger equation with initial data in $ H^1 $. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3837-3867. doi: 10.3934/dcds.2021019 |
[13] |
Xianbang Chen, Yang Liu, Bin Li. Adjustable robust optimization in enabling optimal day-ahead economic dispatch of CCHP-MG considering uncertainties of wind-solar power and electric vehicle. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1639-1661. doi: 10.3934/jimo.2020038 |
[14] |
Mikhail Gilman, Semyon Tsynkov. Statistical characterization of scattering delay in synthetic aperture radar imaging. Inverse Problems & Imaging, 2020, 14 (3) : 511-533. doi: 10.3934/ipi.2020024 |
[15] |
Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 |
[16] |
Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931 |
[17] |
Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 307-320. doi: 10.3934/naco.2020027 |
[18] |
Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206 |
[19] |
Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022 |
[20] |
Wenjing Liu, Rong Yang, Xin-Guang Yang. Dynamics of a 3D Brinkman-Forchheimer equation with infinite delay. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021052 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]