A new ordering heuristic based on ZBDDs' cutoff strategies

Two approaches have been proposed by A. Rauzy to handle the large-scale fault trees or event trees. The first one consists in using ZBDDs (Zero-suppressed Binary Decision Diagrams) to implement classical MCS (Minimal Cut Sets) algorithm. The second consists in designing heuristics and strategies to reduce the complexity of the BDDs (Binary Decision Diagrams) construction. It has been shown that the complexity of ZBDDs is less sensitive to the conventional heuristics and strategies compared with the complexity of BDDs, because these heuristics are based on BDDs. In term of the fact that cutoffs couldn't be applied on the intermediate BDDs, the failure probability of the basic events is not considered in the ordering procedure, therefore the heuristics applicable to ZBDDs need to be designed. This paper is motivated to combine the MCS/ZBDD and designing heuristics for ZBDDs together. A new ordering heuristic, which takes the failure probability into account and utilizes that the cutoffs can be applied on each intermediate ZBDD, is proposed. This heuristic accelerates the analysis progress by bringing forward the cutoffs and reducing the complexity of the intermediate ZBDDs. RiskA, a Zero-suppressed Binary Decision Diagram package extended to safety and reliability analysis, has adopted this new heuristic. RiskA's cutoff strategies, which have some relations with the ordering scheme, are also introduced. The correctness and efficiency of the new heuristic are verified by some practical models' analyses.