[PDF] An ordering heuristic for building Binary Decision Diagrams for fault

View - Download An ordering heuristic for building Binary Decision Diagrams for fault

Previous PDF

Next PDF

Iff (I'^J Vpl ik.FR9800301

Productio

n d'energi e (hydraulique thermiqu e e t nucleaire UN E

HEURISTIQU

E

D'ORDONNANCEMEN

T DE S

VARIABLE

S POU R L A

CONSTRUCTIO

N D'U N

DIAGRAMM

E D E

DECISIO

N

BINAIR

E (BDD A PARTI R D'U N ARBR E D E

DEFAILLANCE

S AN

ORDERING

HEURISTIC

FOR

BUILDING

BINARY

DECISION

DIAGRAMS

FOR

FAULT-TREES

97N
1 0013 9

DIRECTION DES ETUDES ET

RECHERCHE

S

SERVIC

E

REACTEUR

S

NUCIEAIRE

S E T

ECHANGEUR

S

DEPARTEMEN

T ETUDE S D E

SClRET

E E T D E

FIABILIT

E Aou t 199
7

BOUISSOUM

UN E

HEURISTIQU

E

D'ORDONNANCEMEN

T DE

SVARIABLES POUR LA CONSTRUCTION D'UNDIAGRAMME DE DECISION BINAIRE (BDD) APARTIR D'UN ARBRE DE DEFAILLANCES

AN

ORDERING

HEURISTIC

FOR

BUILDINGBINARY DECISION DIAGRAMS FORFAULT-TREES

Pages 1

197NB00139

Diffusion

J.-M

Lecoeuvr

e

EDF-DE

R

Servic

e IPN

Departemen

t PROVA L1, avenue du General-de-Gaulle92141 Clamart Cedex©EDF1997 ISS N

1161-061

1

SYNTHESE :

Le s diagramme s d e décisio n binair e (BDD ont récemmen t fai t un e apparitio

nremarquée dans le domaine de la sûreté de fonctionnement. Ce type de représentationdes fonctions booléennes rend possible l'évaluation d'arbres de défaillancescomplexes, aussi bien qualitativement (recherche des coupes minimales) quequantitativement (calcul exact de la probabilité des événements sommets).

Tout e fonctio n booléenn e e t e n particulie r tou t arbr e de s défaillances cohéren

tou non, peut être représenté par un BDD. Le BDD est une représentation canoniquedès qu'on a choisi un ordonnancement des variables (à savoir, dans le cas d'un arbre dedéfaillance, les événements de base).Les outils reposant sur l'emploi de BDD tels que METAPRIME (1) ouARALIA (2) peuvent, dans certains cas, donner des résultats plus précis que les outilsconventionnels, avec une rapidité d'exécution 1 000 fois supérieure.

ED F a explor c e typ e d e technologie e t a test

METAPRIME

ARALI A e

td'autres outils basés sur les BDD (3) dans le cadre de coopérations avec la société Bullet l'université de Bordeaux. Ces tests ont démontré que la taille du BDD, qu'il estnécessaire de construire en totalité avant une quelconque utilisation, est extrêmementsensible à l'ordonnancement retenu pour les variables. Pour un arbre de défaillancedonné, cette taille peut varier de plusieurs ordres de grandeur, ce qui peut conduire àdes besoins excessifs en mémoire et en temps machine. Le problème de trouver unordonnancement optimal étant impossible à résoudre dans les applications réelles, denombreuses heuristiques ont été proposées en vue d'en trouver un qui soit acceptable,de façon économique (en termes de besoins en calcul).

L'obje

t d e cett e not e es t d e présente r u n prétraitemen t d e l'arbr e d e défaillance

s(que nous appellerons "optimisation") donnant l'assurance de ce que les résultatsdonnés par différentes heuristiques sur l'arbre de défaillances "optimisé" ne seront pasexcessivement sensibles à la façon dont l'arbre est "écrit" (le même arbre peut êtreécrit de nombreuses façons différentes, par simple changement de l'ordre des fils dechaque porte). Cette propriété repose sur une preuve théorique. Contrairement àcertaines heuristiques bien connues et que nous rappelons dans cette note, la méthodeque nous proposons ne repose pas seulement sur l'intuition et les expériencespratiques.

Cett e méthod e convien t particulièremen t bie n au x arbre s d e défaillance

sconstruits automatiquement à partir de la représentation physique d'un système, par unalgorithme remontant vers l'amont des flux du système. Ce type d'algorithme estemployé par la plupart des programmes automatisant la construction des arbres dedéfaillances, par exemple CAT, STARS, FIABEX, FIGARO (4), (5), (6), (7).

L'utilisatio

n d e notr e méthod e a permi s d e construir e e n quelque s seconde s l

eBDD d'un grand nombre d'arbres pour lesquels la version initiale ne pouvait pas êtretraitée sur une station de travail dotée de 128 Mo de RAM. Ce résultat a en outre étéobtenu à un coût très raisonnable : les optimisations les plus difficiles prennent moinsd'une minute sur une station de travail de type SUN SPARC 10.

97NB0013

9 (HT-52/97/031/A

EXECUTIVE SUMMARY:

Binar y

Decisio

n

Diagram

s (BDD hav e recentl y mad e a noticeabl e entr y i n th

eRAMS field. This kind of representation for boolean functions makes possible theassessment of complex fault-trees, both qualitatively (minimal cutsets search) andquantitatively (exact calculation of top event probability).

An y boolea n function andfi n particula r an y fault-tree whethe r coheren t o r not

,can be represented by a BDD. The BDD is a canonical representation of the function,as soon as one has chosen a variable (i.e., in the fault-tree case, basic event) ordering.

Tool s base d o n th e us e o f BDDs lik e

METAPRIM

E [1] o r ARALI A [2] ca nin some cases give more accurate results than conventional tools, while running1 000 times faster. ED F ha s investigate d thi s kin d o f technology an d teste d

METAPRIME

,ARALIA, and other tools based on BDDs [3], in the framework of cooperations withthe BULL company and with the Bordeaux University. These tests have demonstratedthat the size of the BDD, that has to be built thorougly before any king of assessmentcan begin, is dramatically sensitive to the ordering chosen for the variables. For a givenfault-tree, this size may vary by several orders of magnitude. This can lead to excessiveneeds, both in terms of memory and CPU time.

Th equotesdbs_dbs22.pdfusesText_28

[PDF] consommation d'énergie hydraulique dans le monde

[PDF] quelle est la place de l'hydraulique dans la production mondiale d'électricité

[PDF] nombre de barrage hydraulique en france

[PDF] barrage hydroélectrique en france liste

[PDF] td barrage de couesnon

[PDF] sujet bac si mont saint michel

[PDF] bac si barrage

[PDF] le cas du mont saint michel management

[PDF] centre nautique de bayonne

[PDF] classement des barrages en algerie

[PDF] nombre de barrage en algerie 2016

[PDF] rapport de jury capes lettres modernes 2017

[PDF] rapport jury capes interne lettres modernes 2014

[PDF] rapport de jury capes interne lettres modernes 2015

[PDF] rapports de jury capes lettres modernes