A new cut-based algorithm for the multi-state flow network reliability problem

作者：Yeh Wei Chang^*; Bae Changseok; Huang Chia Ling

来源：Reliability Engineering & System Safety, 2015, 136: 1-7.

DOI：10.1016/j.ress.2014.11.010

• Reliability
• Multistate network
• d-MC
• MC

Many real-world systems can be modeled as multi-state network systems in which reliability can be derived in terms of the lower bound points of level d, called d-minimal cuts (d-MCs). This study proposes a new method to find and verify obtained d-MCs with simple and useful found properties for the multistate flow network reliability problem. The proposed algorithm runs in O(mop) time, which represents a significant improvement over the previous O(mp(2)sigma) time bound based on max-flow/min-cut, where p, sigma and m denote the number of MCs, d-MC candidates and edges, respectively. The proposed algorithm also conquers the weakness of some existing methods, which failed to remove duplicate d-MCs in special cases. A step-by-step example is given to demonstrate how the proposed algorithm locates and verifies all d-MC candidates. As evidence of the utility of the proposed approach, we present extensive computational results on 20 benchmark networks in another example. The computational results compare favorably with a previously developed algorithm in the literature.

• 出版日期2015-4
• 单位清华大学