Premium
Efficient Ordering Heuristics in Binary Decision Diagram–based Fault Tree Analysis
Author(s) -
Mo Yuchang,
Zhong Farong,
Liu Huawen,
Yang Quansheng,
Cui Gang
Publication year - 2013
Publication title -
quality and reliability engineering international
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.913
H-Index - 62
eISSN - 1099-1638
pISSN - 0748-8017
DOI - 10.1002/qre.1382
Subject(s) - benchmark (surveying) , heuristics , binary decision diagram , heuristic , computer science , weighting , fault tree analysis , binary number , selection (genetic algorithm) , process (computing) , diagram , fault (geology) , data mining , algorithm , artificial intelligence , mathematics , reliability engineering , engineering , arithmetic , medicine , geodesy , database , seismology , geology , radiology , geography , operating system
In binary decision diagram–based fault tree analysis, the size of binary decision diagram encoding fault trees heavily depends on the chosen ordering. Heuristics are often used to obtain good orderings. The most important heuristics are depth‐first leftmost (DFLM) and its variants weighting DFLM (WDFLM) and repeated‐event‐priority DFLM (RDFLM). Although having been used widely, their performance is still only vaguely understood, and not much formal work has been done. This article firstly identifies some basic requirements for a reliable benchmark and gives a benchmark generation method. Then, using the generated benchmark, the performance of DFLM and its variants is studied. Both the experimental results and some interesting findings for our research questions are proposed. This article also presents a new weighting DFLM (NWDFLM) heuristic and the underlying basic ideas and gives both the experimental results and conclusions on the performance comparison. As a final synthesis of all previous results, a practical suggestion of the order of heuristic selection to process a large fault tree is NWDFLM < WDFLM < RDFLM. Copyright © 2012 John Wiley & Sons, Ltd.