A parallel algorithm for reliability assessment of multi-state flow networks based on simultaneous finding of all multi-state minimal paths and performing state space decomposition

This article presents a new efficient method for reliability evaluation of two-terminal Multi-state Flow Networks (MFNs). Indirect State Space Decomposition (SSD) methods are usually more efficient than direct SSD methods. However, indirect SSD methods require searching for all d-MPs/d-MCs. The presented method requires only an MFN, a system demand requirement d, and the probability distributions of states of components as an input. The presented algorithm uses a partition technique to decompose a state space into smaller and distinct subspaces. The algorithm tries to determine a d-flow with a lower bound for each subspace. If a flow exists and it is a d-MP, the algorithm computes the probability that a capacity vector belongs to this subspace and is bounded below by the d-MP and decomposes this subspace into smaller subspaces. For all subspaces without d-MP, the presented algorithm uses parallel computations and the SSD method to compute the probability that a capacity vector belongs to this subspace and is bounded below by a d-MP. The numerical experiments show that the efficiency of the presented method improves in comparison with other indirect SSD methods if the number of available logical processes and the number of d-MPs increase.