On the efficiency of functional decomposition in fault tree analysis

Abstract

The exact analysis of complex fault trees is a very difficult task. Many methods have been defined to reduce computation time and working memory usage. This problem was recently studied by the authors who proposed an approach based on functional decomposition. A complex fault tree is recursively decomposed into a set of mutually exclusive simpler fault trees until their dimensions are compatible with the available working memory size. Then, the results of the analysis of all generated simpler trees are composed to obtain the results for the original un-decomposed fault tree. Large fault trees, which were impossible to analyse owing to insufficient working memory for the construction of the binary decision diagrams, were successfully analysed by means of the functional decomposition method. Since a fault tree is decomposed with respect to a small subset S of the vector x of basic events, the efficiency of the decomposition process is highly dependent on this subset. Hence the problem is how to select the events of S in order to minimise the fault tree analysis time. This article describes and compares four different algorithms to construct S with the aim of identifying the one for which the decomposition procedure requires the least computational time. Owing to the heuristic nature of this problem, all algorithms have been tested on a number of fault trees of different complexity in order to draw useful indications on the relatively ‘best’ one(s). According to the efficiency measures adopted for comparison purposes, the results showed that the best way to proceed is to set S as a minimal path set of the fault tree to be decomposed.