American Institute of Mathematical Sciences

Advanced
January  2012, 8(1): 1-17. doi: 10.3934/jimo.2012.8.1

A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations

Chia-Huang Wu 1, , Kuo-Hsiung Wang 2, , Jau-Chuan Ke 3, and  Jyh-Bin Ke 4,

1. 

Department of Industrial Engineering and Management, National Chiao Tung University, Hsingchu 30050, Taiwan
2. 

Department of Business Administration, Asia University, Wufeng, Taichung 41354, Taiwan
3. 

Department of Applied Statistics, National Taichung Institute of Technology, Taichung 404, Taiwan
4. 

Department of Applied Mathematics, National Chung-Hsing University, Taichung 402, Taiwan

Received  December 2009 Revised  June 2011 Published  November 2011

This paper focuses on an M/M/$s$ queue with multiple working vacations such that the server works with different service rates rather than no service during the vacation period. We show that this is a generalization of an M/M/1 queue with working vacations in the literature. Service times during vacation period, or during service period and vacation times are all exponentially distributed. We obtain the useful formula for the rate matrix $\textbf{R}$ through matrix-geometric method. A cost function is formulated to determine the optimal number of servers subject to the stability conditions. We apply the direct search algorithm and Newton-Quasi algorithm to heuristically find an approximate solution to the constrained optimization problem. Numerical results are provided to illustrate the effectiveness of the computational algorithm.
Keywords: Newton-Quasi algorithm; optimization; rate matrix; sensitivity anal- ysis; working vacations..
Mathematics Subject Classification: Primary: 60K10, 60K25; Secondary: 90B22, 90B2.
Citation: Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1
References:
[1]

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

[2]

A. D. Banik, U. C. Gupta and S. S. Pathak, On the GI/M/1/N queue with multiple working vacations-analytic analysis and computation,, Applied Mathematical Modelling, 31 (2006), 1701.  doi: 10.1016/j.apm.2006.05.010.  Google Scholar

[3]

R. L. Burden and J. Douglas, "Numerical Analysis,'', 7th Edition, (2001).   Google Scholar

[4]

U. Chatterjee and S. P. Mukherjee, GI/M/1 queue with server vacations,, Journal of the Operational Research Society, 41 (1990), 83.   Google Scholar

[5]

E. K. P. Chong and S. H. Zak, "An Introduction to Optimization,'', 2nd Edition, (2001).   Google Scholar

[6]

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

[7]

S. W. Fuhrmann and R. B. Cooper, Stochastic decompositions in the M/G/1 queue with generalized vacations,, Operations Research, 33 (1985), 1117.  doi: 10.1287/opre.33.5.1117.  Google Scholar

[8]

F. Karaesmen and S. M. Gupta, The finite capacity GI/M/1 queue with server vacations,, Journal of the Operational Research Society, 47 (1996), 817.   Google Scholar

[9]

T. Lee, The M/G/1/N queue with vacation and exhaustive service discipline,, Operations Research, 32 (1984), 774.  doi: 10.1287/opre.32.4.774.  Google Scholar

[10]

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

[11]

C.-H. Lin and J.-C. Ke, Multi-server system with single working vacation,, Applied Mathematical Modelling, 33 (2009), 2967.  doi: 10.1016/j.apm.2008.10.006.  Google Scholar

[12]

W.-Y. Liu, X.-L. Xu and N.-S. Tian, Stochastic decomposition in the M/M/1 queue with working vacations,, Operations Research Letters, 35 (2007), 595.  doi: 10.1016/j.orl.2006.12.007.  Google Scholar

[13]

M. F. Neuts, "Matrix-Geometric Solutions in Stochastic Models. An Algorithmic Approach,'', Johns Hopkins Series in the Mathematical Sciences, 2 (1981).   Google Scholar

[14]

L. D. Servi and S. G. Finn, M/M/1 queues with working vacations (M/M/1/WV),, Performance Evaluation, 50 (2002), 41.  doi: 10.1016/S0166-5316(02)00057-3.  Google Scholar

[15]

H. Takagi, "Queueing Analysis: A Foundation of Performance Evaluation," Vol. 1, Vacation and Priority Systems,, Part 1, (1991).   Google Scholar

[16]

N. Tian, D. Zhang and C. Cao, The GI/M/1 queue with exponential vacations,, Queueing Systems Theory Appl., 5 (1989), 331.  doi: 10.1007/BF01225323.  Google Scholar

[17]

J. A. White, J. W. Schmidt and G. K. Benett, "Analysis of Queueing System,'', Operations Research and Industrial Engineering, (1975).   Google Scholar

[18]

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

show all references

References:
[1]

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

[2]

A. D. Banik, U. C. Gupta and S. S. Pathak, On the GI/M/1/N queue with multiple working vacations-analytic analysis and computation,, Applied Mathematical Modelling, 31 (2006), 1701.  doi: 10.1016/j.apm.2006.05.010.  Google Scholar

[3]

R. L. Burden and J. Douglas, "Numerical Analysis,'', 7th Edition, (2001).   Google Scholar

[4]

U. Chatterjee and S. P. Mukherjee, GI/M/1 queue with server vacations,, Journal of the Operational Research Society, 41 (1990), 83.   Google Scholar

[5]

E. K. P. Chong and S. H. Zak, "An Introduction to Optimization,'', 2nd Edition, (2001).   Google Scholar

[6]

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

[7]

S. W. Fuhrmann and R. B. Cooper, Stochastic decompositions in the M/G/1 queue with generalized vacations,, Operations Research, 33 (1985), 1117.  doi: 10.1287/opre.33.5.1117.  Google Scholar

[8]

F. Karaesmen and S. M. Gupta, The finite capacity GI/M/1 queue with server vacations,, Journal of the Operational Research Society, 47 (1996), 817.   Google Scholar

[9]

T. Lee, The M/G/1/N queue with vacation and exhaustive service discipline,, Operations Research, 32 (1984), 774.  doi: 10.1287/opre.32.4.774.  Google Scholar

[10]

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

[11]

C.-H. Lin and J.-C. Ke, Multi-server system with single working vacation,, Applied Mathematical Modelling, 33 (2009), 2967.  doi: 10.1016/j.apm.2008.10.006.  Google Scholar

[12]

W.-Y. Liu, X.-L. Xu and N.-S. Tian, Stochastic decomposition in the M/M/1 queue with working vacations,, Operations Research Letters, 35 (2007), 595.  doi: 10.1016/j.orl.2006.12.007.  Google Scholar

[13]

M. F. Neuts, "Matrix-Geometric Solutions in Stochastic Models. An Algorithmic Approach,'', Johns Hopkins Series in the Mathematical Sciences, 2 (1981).   Google Scholar

[14]

L. D. Servi and S. G. Finn, M/M/1 queues with working vacations (M/M/1/WV),, Performance Evaluation, 50 (2002), 41.  doi: 10.1016/S0166-5316(02)00057-3.  Google Scholar

[15]

H. Takagi, "Queueing Analysis: A Foundation of Performance Evaluation," Vol. 1, Vacation and Priority Systems,, Part 1, (1991).   Google Scholar

[16]

N. Tian, D. Zhang and C. Cao, The GI/M/1 queue with exponential vacations,, Queueing Systems Theory Appl., 5 (1989), 331.  doi: 10.1007/BF01225323.  Google Scholar

[17]

J. A. White, J. W. Schmidt and G. K. Benett, "Analysis of Queueing System,'', Operations Research and Industrial Engineering, (1975).   Google Scholar

[18]

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

[1]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[2]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[3]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034
[4]

Gheorghe Craciun, Abhishek Deshpande, Hyejin Jenny Yeon. Quasi-toric differential inclusions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2343-2359. doi: 10.3934/dcdsb.2020181
[5]

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
[6]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[7]

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
[8]

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
[9]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[10]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[11]

Zhigang Pan, Chanh Kieu, Quan Wang. Hopf bifurcations and transitions of two-dimensional Quasi-Geostrophic flows. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021025
[12]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81
[13]

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
[14]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[15]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027
[16]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008
[17]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[18]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (41)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences