More Web Proxy on the site http://driver.im/

article

Ordinal Optimization of G/G/1/K Polling Systems with k-Limited Service Discipline

Authors:

S. -Y. LinAuthors Info & Claims

Journal of Optimization Theory and Applications, Volume 140, Issue 2

Pages 213 - 231

https://doi.org/10.1007/s10957-008-9444-9

Published: 01 February 2009 Publication History

Abstract

In this paper, we propose an ordinal optimization theory based algorithm to solve the optimization problem of G/G/1/K polling system with k -limited service discipline for a good enough solution using limited computation time. We assume that the arrival rates do not deteriorate visibly within a very short period. Our approach consists of two stages. In the first stage, we employ a typical genetic algorithm to select N =1024 roughly good solutions from the huge discrete solution space Ω using an offline trained artificial neural network as a surrogate model for fitness evaluation. The second stage consists of several substages to select estimated good enough solutions from the previous N , and the solution obtained in the last substage is the good enough solution that we seek. Using numerous tests, we demonstrate: (i) the computational efficiency of our algorithm in the aspect that we can apply our algorithm in real-time based on the arrival rate assumption; (ii) the superiority of the good enough solution, which achieves drastic objective value reduction in comparison with other existing service disciplines. We provide a performance analysis for our algorithm based on the derived models. The results show that the good enough solution that we obtained is among the best 3.31 10⁶% in the solution space with probability 0.99.

References

[1]

Takagi, H.: Analysis and application of polling model. In: Haring, G., Lindemann, C., Reiser, M. (eds.) Performance Evaluation: Origins and Directions. Lecture Notes in Computer Science, vol. 1769, pp. 423---442. Springer, Berlin (2000)

[2]

Hirayama, T., Hong, S.J., Krunz, M.: A new approach to analysis of polling systems. Queueing Syst. 48(1---2), 135---158 (2004)

[3]

Winands, E.M.M., Adan, I.J.B.F., van Houtum, G.J.: Mean value analysis for polling systems. Queueing Syst. 54(1), 35---44 (2006)

Digital Library

[4]

Eliazar, I.: Gated polling systems with levy inflow and inter-dependent switchover times: a dynamical-systems approach. Queueing Syst. 49(1), 49---72 (2005)

Digital Library

[5]

Leung, K.K.: Cyclic-service systems with nonpreemptive, time-limited service. IEEE Trans. Commun. 42(8), 2521---2524 (1994)

[6]

Vishnevskii, V.M., Semenova, O.V.: Mathematical methods to study the polling systems. Autom. Remote Control 67(2), 173---220 (2006)

[7]

Takagi, H.: Analysis of finite capacity polling systems. Adv. Appl. Probab. 23, 373---387 (1991)

[8]

Jung, W.Y., Un, C.K.: Analysis of a finite-buffer polling system with exhaustive service based on virtual buffering. IEEE Trans. Commun. 42(12), 3144---3149 (1994)

[9]

Borst, S.C., Boxma, O.J., Levy, H.: The use of service limits for efficient operation of multistation single-medium communication systems. IEEE/ACM Trans. Netw. 3(5), 602---612 (1995)

Digital Library

[10]

Lin, S.-Y., Horng, S.-C.: Ordinal optimization approach to stochastic simulation optimization problems and applications. In: Proc. 15th IASTED Int. Conf. Appl. Simul. Model. Rhodes, Greece, pp. 274---279 (2006)

[11]

Andradóttir, S.: Simulation optimization: integrated research and practice. INFORMS J. Comput. 14(3), 216---219 (2002)

[12]

Ólafsson, S., Kim, J.: Simulation optimization. In: Proc. 2002 Winter Simul. Conf. San Diego, CA, pp. 79---84 (2002)

[13]

Gosavi, A.: Simulation-Based Optimization: Parametric Optimization Techniques and Reinforcement Learning. Kluwer Academic, Boston (2003)

[14]

Spall, J.C.: Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. Hoboken, Wiley-Interscience, New Jersy (2003)

[15]

Haupt, R.L., Haupt, S.E.: Practical Genetic Algorithms, 2nd edn. Hoboken, Wiley, New Jersy (2004)

[16]

Suman, B., Kumar, P.: A survey of simulated annealing as a tool for single and multiobjective optimization. J. Oper. Res. Soc. 57(10), 1143---1160 (2006)

[17]

Hedar, A.R., Fukushima, M.: Tabu search directed by direct search methods for nonlinear global optimization. Eur. J. Oper. Res. 170(2), 329---349 (2006)

[18]

Winker, P., Gilli, M.: Applications of optimization heuristics to estimation and modelling problems. Comput. Stat. Data Anal. 47(2), 211---223 (2004)

[19]

Fu, M.C., Glover, F.W., April, J.: Simulation optimization: a review, new developments, and applications. In: Proc. 2005 Winter Simul. Conf., Orlando, FL, pp. 83---95 (2005)

[20]

Tekin, E., Sabuncuoglu, I.: Simulation optimization: a comprehensive review on theory and applications. IIE Trans. 36(11), 1067---1081 (2004)

[21]

Lau, T.W.E., Ho, Y.C.: Universal alignment probability and subset selection for ordinal optimization. J. Optim. Theory Appl. 93(3), 455---489 (1997)

Digital Library

[22]

Ho, Y.C.: An explanation of ordinal optimization: Soft computing for hard problems. Inf. Sci. 113(3---4), 169---192 (1999)

[23]

Ho, Y.C., Zhao, Q.C., Jia, Q.S.: Ordinal Optimization: Soft Optimization for Hard Problems. Springer, New York (2007)

[24]

Palit, A.K., Popović, D.: Computational Intelligence in Time Series Forecasting Theory and Engineering Applications. Springer, London (2005)

[25]

Hornik, K., Stinchcombe, M., White, H.: Multilayer fedforward networks are universal approximators. Neural Netw. 2(5), 359---366 (1989)

Digital Library

[26]

Fonseca, D.J., Navaresse, D.O., Moynihan, G.P.: Simulation metamodeling through artificial neural networks. Eng. Appl. Artif. Intell. 16(3), 177---183 (2003)

[27]

Alam, F.M., McNaught, K.R., Ringrose, T.J.: A comparison of experimental designs in the development of a neural network simulation metamodel. Simul. Oper. Res. 12(7---8), 559---578 (2004)

[28]

Moller, M.F.: A scaled conjugate gradient algorithm for fast supervised learning. Neural Netw. 6(4), 525---533 (1993)

Digital Library

[29]

Yen, C.H., Wong, D.S.H., Jang, S.S.: Solution of trim-loss problem by an integrated simulated annealing and ordinal optimization approach. J. Intell. Manuf. 15(5), 701---709 (2004)

[30]

Deng, M., Ho, Y.C.: Iterative ordinal optimization and its applications. In: Proc. 36th IEEE Conf. Decis. Contr., San Diego, CA, vol. 4, pp. 3562---3567 (1997)

[31]

Banks, J., Carson, J., Nelson, B.L., Nicol, D.: Discrete Event System Simulation, 4th edn. Prentice-Hall, Upper Saddle River (2005)

[32]

Lin, S.-Y., Horng, S.-C.: Optimization of G/G/1/K polling systems with k-limited service discipline. Technical Report ECE #01, Department of Electrical and Control Engineering, National Chiao Tung University, Hsinchu, Taiwan, March (2008)

[33]

Yazici, B., Yolacan, S.: A comparison of various tests of normality. J. Stat. Comput. Simul. 77(2), 175---183 (2007)

[34]

D'Agostino, R.B., Stephens, M.A.: Goodness-of-Fit Techniques. Dekker, New York (1986). Table 4.7, 123

[35]

Chen, C.H., Lin, J.W., Cesan, E.Y., Chick, S.E.: Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discret. Event Dyn. Syst. Theory Appl. 10(3), 251---270 (2000)

Cited By

Cao YCurrie COnggo BHiggins M(2021)Simulation optimization for a digital twin using a multi-fidelity frameworkProceedings of the Winter Simulation Conference10.5555/3522802.3523002(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3523002
Horng SLin S(2019)Evolutionary algorithm assisted by surrogate model in the framework of ordinal optimization and optimal computing budget allocationInformation Sciences: an International Journal10.1016/j.ins.2013.01.024233(214-229)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2013.01.024

Recommendations

Polling systems with a gated/exhaustive discipline
ValueTools '08: Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools

We consider a polling system where the server cyclically serves the queues according to the following discipline: the server does one round of visits to the queues applying the gated service discipline at each of the queues, followed by one round of ...
A batchSPP/G/1 queue with multiple vacations and exhaustive service discipline

This paper considers a batch-arrival single-server queueing system with multiple vacations and exhaustive service discipline. Customers arrive to the system in accordance with a batch switched Poisson process (batchSPP). Using the supplementary variable ...
M/G/1/N Queue with Vacation Time and Exhaustive Service Discipline

This paper studies an M/G/1 queueing system with a finite waiting room and with server vacation times consisting of periods of time that the server is away from the queue doing additional work. This model has been used in conjunction with a related ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Optimization Theory and Applications

Journal of Optimization Theory and Applications Volume 140, Issue 2

February 2009

159 pages

ISSN:0022-3239

Issue’s Table of Contents

Copyright © Copyright © 2009 Springer Science+Business Media, LLC.

Publisher

Plenum Press

United States

Publication History

Published: 01 February 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cao YCurrie COnggo BHiggins M(2021)Simulation optimization for a digital twin using a multi-fidelity frameworkProceedings of the Winter Simulation Conference10.5555/3522802.3523002(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3523002
Horng SLin S(2019)Evolutionary algorithm assisted by surrogate model in the framework of ordinal optimization and optimal computing budget allocationInformation Sciences: an International Journal10.1016/j.ins.2013.01.024233(214-229)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2013.01.024

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents