A heuristic approach to variables ordering in binary decision diagram
Jim-Eng Ng · Iowa State University Digital Repository (Iowa State University) · 2000
Fault Tree is a well-known way of expressing failure combinations of a system. The Fault Tree analysis process, however, is computationally expensive and time consuming as the size of a Fault Tree increases. Binary Decision Diagram (BDD) is a Directed Acyclic Graph (DAG) encoding of a Fault Tree. This has been shown to be the most effective way of evaluating a Fault Tree. The encoding method employs an If-Then-Else (ite) methodology to represent the functionality of a system based on its events. The only drawback of BDD is that the size of the diagram is highly dependent on the ordering of the events that are used in the process of analysis. This paper inspects the relationship of the factors that affect the events ordering and present an ordering heuristic that will yield a reasonable size of BDD for all different formation of Fault Trees. Random trees are generated to experiment using simulation with a given number of events and gates. The BDD analysis results show that it reduces the overall sizes of a BDD for a given fault tree.