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.