Minimum-cost diagnostic strategies for k-out-of-n systems with imperfect tests

A k-out-of-n system configuration requires that, for the overall system to be functional, at least k out of the total of n components be working. We consider the problem of sequentially testing the components of a k-out-of-n system in order to learn the state of the system, when the tests are costly and when the individual component tests are imperfect, which means that a test can identify a component as working when in reality it is down, and vice versa. Each component is tested at most once. The stopping criterion for the inspection is the attainment of a lower bound on the confidence level regarding the system state. We define different classes of inspection policies and we examine global optimality of each of the classes. We show that a globally optimal policy can be found in polynomial time when the predictive error probabilities are the same for all the components.