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

Rostami, Salim; Creemers, Stefan; Wei, Wenchao; Leus, Roel

Document type :

Article dans une revue scientifique

DOI :

10.1016/j.ejor.2018.10.036

Title :

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

Author(s) :

Rostami, Salim [Auteur]
Creemers, Stefan [Auteur]
Lille économie management - UMR 9221 [LEM]
Wei, Wenchao [Auteur]
Leus, Roel [Auteur]
Catholic University of Leuven - Katholieke Universiteit Leuven [KU Leuven]

Journal title :

European Journal of Operational Research

Pages :

876-885

Publisher :

Elsevier

Publication date :

2019-05-01

ISSN :

0377-2217

English keyword(s) :

Scheduling
System testing
Precedence theorems
Dynamic programming
Branch-and-price

HAL domain(s) :

Sciences de l'Homme et Société
Sciences de l'Homme et Société/Gestion et management

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Lille Économie Management (LEM) - UMR 9221

Source :

Harvested from HAL

Sequential testing of n-out-of-n systems: ... BibTeX CSV Excel RIS

Sequential testing of n-out-of-n systems: ...

BibTeX

CSV

Excel

RIS