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

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 Omega 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.31x10(-6)% in the solution space with probability 0.99.