Solving the non-preemptive two queue polling model with generally distributed service and switch-over durations and Poisson arrivals as a Semi-Markov Decision Process
This work addresses a complex Discrete Event Dynamic System (DEDS) modeling problem for polling systems, which has practical applications but is incremental in improving existing methods.
The paper tackled modeling a polling system with switch-over durations by proposing a Semi-Markov Decision Process (SMDP) formulation to enhance modeling power, and found that while the SMDP policy offered advantages, it involved trade-offs like truncation errors and computational costs compared to a more efficient Continuous-time Markov Decision Process (CTMDP) model.
The polling system with switch-over durations is a useful model with several practical applications. It is classified as a Discrete Event Dynamic System (DEDS) for which no one agreed upon modelling approach exists. Furthermore, DEDS are quite complex. To date, the most sophisticated approach to modelling the polling system of interest has been a Continuous-time Markov Decision Process (CTMDP). This paper presents a Semi-Markov Decision Process (SMDP) formulation of the polling system as to introduce additional modelling power. Such power comes at the expense of truncation errors and expensive numerical integrals which naturally leads to the question of whether the SMDP policy provides a worthwhile advantage. To further add to this scenario, it is shown how sparsity can be exploited in the CTMDP to develop a computationally efficient model. The discounted performance of the SMDP and CTMDP policies are evaluated using a Semi-Markov Process simulator. The two policies are accompanied by a heuristic policy specifically developed for this polling system a well as an exhaustive service policy. Parametric and non-parametric hypothesis tests are used to test whether differences in performance are statistically significant.