General Dynamic Programming Algorithms Applied To Polling Systems

We formulate the problem of scheduling a single server in a multi-class queueing system as a Markov decision process under the discounted cost and the average cost criteria. We develop a new implementation of the modified policy iteration (MPI) dynamic programming algorithm to efficiently solve problems with large state spaces and small action spaces. This implementation has an enhanced policy evaluation (PE) step and an adaptive termination test. To numerically evaluate various solution approaches, we implemented value iteration and forms of modified policy iteration, and we further developed and implemented aggregation-disaggregation based (replacement process decomposition and group-scaling) algorithms appropriate to controlled queueing system models. Tests provide evidence that MPI outperforms the other algorithms for both the discounted cost and the average cost optimal polling problems. In light of the complexity of implementation for the aggregationdisaggregation based algorithm..