An Ordering Heuristic for Reliability Evaluation of Multistate Networks

Evaluating the reliability of a multistate network (MSN) is an NP-hard problem, and the evaluation methods are usually based on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-minimal cuts (<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-MCs). However, the efficiency of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-MC-based reliability calculations is heavily influenced by the input order of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-MCs. In this paper, we propose a heuristic algorithm to optimize the input order and improve the efficiency of the Recursive Sum of Disjoint Products (RSDP) method used for reliability evaluation. The algorithm determines the arrangement order of each <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-MC by finding the minimum state of each component across all <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-MCs, forming these minimum states into a minimum vector, comparing each component of the individual <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-MCs with the corresponding component of the minimum vector, and then counting the number of components in each <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex>-MC that are larger than those in the minimum vector. Our experimental results demonstrate that the proposed heuristic significantly improves the efficiency of reliability evaluation, with greater improvements observed as network complexity increases.