Test sequencing for sequential system diagnosis with precedence constraints and imperfect tests

We study sequential system testing with the objective of minimizing the total expected testing costs. The goal is to discover the state of a system that consists of a set of independent components. The state of the system depends on the states of the individual components and is classified as working if at least a pre-specified number of components are working, otherwise it is said to be down. During the diagnostic testing procedure, components are tested one by one, in a pre-specified order. The resulting test sequencing problem is NP-hard with general precedence constraints even when the tests are perfect, in which case a component test always reports the correct state of the component. In this work, we will also consider the additional complication that tests can be imperfect, meaning that a test can report a component to be working when it is actually down, and vice versa. We develop a tabu search algorithm together with a simulation-based evaluation technique that incorporates importance sampling to find high-quality solutions within limited runtimes.