Scheduling results applicable to decision-theoretic troubleshooting

• New NPNP-hardness results for troubleshooting problems are given.
• Polynomial-time solvable special cases of the NPNP-hard problems are discussed.
• A close connection between troubleshooting and scheduling problems is described.
• Basic troubleshooting with call-service action is shown to be solvable in O(nlog⁡n)O(nlog⁡n) time.

In decision-theoretic troubleshooting, we are given a Bayesian network model of a malfunctioning device and our task is to find a repair strategy with minimal expected cost. The troubleshooting problem has received considerable attention over the past two decades. We show that several troubleshooting scenarios proposed in the literature are equivalent to well-studied machine scheduling problems. This immediately yields new complexity-theoretic and algorithmic results for troubleshooting. We also apply scheduling results to multi-agent troubleshooting. Further, we examine the so-called call service action which is often used in troubleshooting but has no natural counterpart in machine scheduling. We show that adding the call service action to basic troubleshooting models does not make the problem intractable.