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-209. 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-1710. doi: 10.1016/j.apm.2006.05.010.  Google Scholar

[3]

R. L. Burden and J. Douglas, "Numerical Analysis,'' 7th Edition, Brooks/Cole, USA, 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-87. Google Scholar

[5]

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

[6]

B. T. Doshi, Queueing systems with vacations-a survey, Queueing Systems Theory Appl., 1 (1986), 29-66. 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-1129. 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-828. Google Scholar

[9]

T. Lee, The M/G/1/N queue with vacation and exhaustive service discipline, Operations Research, 32 (1984), 774-784. 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-63. 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-2977. 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-600. 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, Johns Hopkins University Press, Baltimore, Md., 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-52. 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, North-Holland Publishing Co., Amsterdam, 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-344. 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, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975.  Google Scholar

[18]

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

show all references

References:
[1]

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

[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-1710. doi: 10.1016/j.apm.2006.05.010.  Google Scholar

[3]

R. L. Burden and J. Douglas, "Numerical Analysis,'' 7th Edition, Brooks/Cole, USA, 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-87. Google Scholar

[5]

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

[6]

B. T. Doshi, Queueing systems with vacations-a survey, Queueing Systems Theory Appl., 1 (1986), 29-66. 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-1129. 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-828. Google Scholar

[9]

T. Lee, The M/G/1/N queue with vacation and exhaustive service discipline, Operations Research, 32 (1984), 774-784. 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-63. 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-2977. 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-600. 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, Johns Hopkins University Press, Baltimore, Md., 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-52. 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, North-Holland Publishing Co., Amsterdam, 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-344. 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, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975.  Google Scholar

[18]

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

[1]

Cheng-Dar Liou. Optimization analysis of the machine repair problem with multiple vacations and working breakdowns. Journal of Industrial & Management Optimization, 2015, 11 (1) : 83-104. doi: 10.3934/jimo.2015.11.83
[2]

Cheng-Dar Liou. Note on "Cost analysis of the M/M/R machine repair problem with second optional repair: Newton-Quasi method". Journal of Industrial & Management Optimization, 2012, 8 (3) : 727-732. doi: 10.3934/jimo.2012.8.727
[3]

Kuo-Hsiung Wang, Chuen-Wen Liao, Tseng-Chang Yen. Cost analysis of the M/M/R machine repair problem with second optional repair: Newton-Quasi method. Journal of Industrial & Management Optimization, 2010, 6 (1) : 197-207. doi: 10.3934/jimo.2010.6.197
[4]

Zhanyou Ma, Pengcheng Wang, Wuyi Yue. Performance analysis and optimization of a pseudo-fault Geo/Geo/1 repairable queueing system with N-policy, setup time and multiple working vacations. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1467-1481. doi: 10.3934/jimo.2017002
[5]

Yuhong Dai, Nobuo Yamashita. Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 61-69. doi: 10.3934/naco.2011.1.61
[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]

Shummin Nakayama, Yasushi Narushima, Hiroshi Yabe. Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1773-1793. doi: 10.3934/jimo.2018122
[8]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[9]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[10]

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

Pikkala Vijaya Laxmi, Seleshi Demie. Performance analysis of renewal input $(a,c,b)$ policy queue with multiple working vacations and change over times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 839-857. doi: 10.3934/jimo.2014.10.839
[12]

Zhanyou Ma, Wenbo Wang, Linmin Hu. Performance evaluation and analysis of a discrete queue system with multiple working vacations and non-preemptive priority. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1135-1148. doi: 10.3934/jimo.2018196
[13]

Guodong Ma, Jinbao Jian. A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization. Journal of Industrial & Management Optimization, 2015, 11 (1) : 307-328. doi: 10.3934/jimo.2015.11.307
[14]

Caglar S. Aksezer. On the sensitivity of desirability functions for multiresponse optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 685-696. doi: 10.3934/jimo.2008.4.685
[15]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[16]

Basim A. Hassan. A new type of quasi-newton updating formulas based on the new quasi-newton equation. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 227-235. doi: 10.3934/naco.2019049
[17]

K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026
[18]

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

Lingling Lv, Zhe Zhang, Lei Zhang, Weishu Wang. An iterative algorithm for periodic sylvester matrix equations. Journal of Industrial & Management Optimization, 2018, 14 (1) : 413-425. doi: 10.3934/jimo.2017053
[20]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy