Minimizing the Average Cost of Testing Coherent Systems: Complexity and Approximate Algorithms

The paper deals with the problem of finding optimal testing policy to minimize the average cost of determining the state of a s-coherent system. Computational complexity of this problem is analysed and strong evidence presented that an exact, polynomial-time, algorithm is very unlikely to exist. Instead, three approximate algorithms having polynomial running times are suggested and evaluated. Two of them guarantee reasonably good solutions and might be practical.