Sequential testing of n-out-of-n systems: Precedence theorems and exact methods

Salim Rostami, Stefan Creemers, Wenchao Wei and Roel Leus
Additional contact information
Salim Rostami: IESEG - School of Management (LEM)
Stefan Creemers: LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique
Roel Leus: KU Leuven - Catholic University of Leuven = Katholieke Universiteit Leuven

Post-Print from HAL

Abstract: The goal of sequential testing is to discover the state of a system by testing its components one by one. We consider n-out-of-n systems, which function only if all n components work. The testing continues until the system state (up or down) is identified. The tests have known execution costs and failure probabilities, and are subject to precedence constraints. The objective is to find a sequence of tests that minimizes the total expected cost of the diagnosis. We show how to strengthen the precedence graph without losing all optimal solutions. We examine different formulations for the problem, and propose a dynamic-programming (DP) and a branch-and-price algorithm. Our computational results show that our DP noticeably outperforms the state of the art. Using a novel memory management technique, it significantly increases the size of the instances that can be solved to optimality within given limits on runtime and memory.

Keywords: Scheduling; System testing; Precedence theorems; Dynamic programming; Branch-and-price (search for similar items in EconPapers)
Date: 2019-05-01
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Published in European Journal of Operational Research, 2019, 274 (3), pp.876-885. ⟨10.1016/j.ejor.2018.10.036⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-02114147

DOI: 10.1016/j.ejor.2018.10.036

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().