When to test? Troubleshooting with postponed system test

Troubleshooting is about computing a cost-efficient way to repair a faulty device. In this paper we investigate the most simple action-based troubleshooting scenario with a single extension: the overall system test is not required to be performed after each action, but it may be postponed until several actions have been performed. As shown by Kadane and Simon, the simple troubleshooting scenario is easily solvable in polynomial time. However, we conjecture that the new troubleshooting scenario is NP-hard and therefore describe an Θ(n3) time heuristic. The new heuristic guarantees optimality for a class of models, and for other classes of models we benchmark it against the optimal solution and other simpler greedy heuristics. The benchmark is performed on artificial models as well as a real-world troubleshooting model, and it suggests that the heuristics are close to optimal.

► Troubleshooting is about computing a cost-efficient way to repair a faulty device.
► To determine when the device has been repaired, the device may be inspected at a certain cost.
► We address the problem of finding a strategy describing when the device itself should be inspected to minimize the overall average repair cost.
► Experiments on artificial and real models suggest that the described heuristics perform well.