System Time Distribution of Dynamic Traveling Repairman Problem Under the PART-n-TSP Policy

We propose the PART-n-TSP policy for the Dynamic Traveling Repairman Problem [1]. We compute a good approximation for the distribution of the system time, defined as the elapsed time between the arrival and the completion of each task. PART-n-TSP stabilizes the system for every load in [0; 1). PART-n-TSP has lower system time variance than PARTTSP [14] and Nearest Neighbor [1] when the load is neither too small or too large. We show that PART-n-TSP is also optimal for system time expectation under light and heavy loads.