TY - JOUR

T1 - Ordinal optimization of G/G/1/K polling systems with k-limited service discipline

AU - Horng, S. C.

AU - Lin, S. Y.

PY - 2009/2

Y1 - 2009/2

N2 - 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-6% in the solution space with probability 0.99.

AB - 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-6% in the solution space with probability 0.99.

KW - K-Limited service disciplines

KW - Ordinal optimization

KW - Performance analysis

KW - Polling systems

KW - Stochastic simulation optimization

UR - http://www.scopus.com/inward/record.url?scp=59349087517&partnerID=8YFLogxK

U2 - 10.1007/s10957-008-9444-9

DO - 10.1007/s10957-008-9444-9

M3 - 文章

AN - SCOPUS:59349087517

SN - 0022-3239

VL - 140

SP - 213

EP - 231

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

IS - 2

ER -