Stability of Dynamic Traveling Repairman Problem Under Polling-Sequencing Policies

We establish a necessary and sufficient condition for stability in the dynamic traveling repairman problem (DTRP) [3] under the class of polling-sequencing (P-S) policies satisfying unlimited-polling and economy of scale. The P-S class includes some of the policies proven to be optimal for the expectation of system time under light and heavy loads in the DTRP literature. The number of tasks inside each polling partition is shown to be a Markov chain. Policies such as first come first serve, traveling salesman policy, nearest neighbor and Daganzo's algorithm are shown to have economy of scale.