Reliability-redundancy allocation problem in multi-state flow network: Minimal cut-based approximation scheme

Reliability-redundancy allocation problem (RRAP), a challenging reliability optimization problem, aims to optimize the redundancy level and the component reliability simultaneously for each stage (i.e. subsystem) of the system. The RRAP was mainly studied under binary-state setting on different redundancy strategies, methodologies, and multi-objective formulations. However, the methods are all meta-heuristic algorithms, and no studies focused on RRAP in multi-state flow network (MFN) systems. In this paper, we study the RRAP in MFN considering the minimization of cost or the maximization of reliability under resource constraints. The MFN RRAP is a mixed-integer non-linear programming problem, which is NP-hard. We propose a minimal cut-based approximation scheme to transform it into an integer programming problem. The feasibility guarantee is analyzed to ensure that this approximation scheme can generate a feasible solution with a high probability. The posterior check is conducted to reduce the conservative theoretical sample size empirically. The numerical experiments on MFNs illustrate the tradeoff performance between the accuracy of solutions and the computational complexity, and the outperformance of our proposed method compared to a meta-heuristic algorithm.

Automated summary

This paper studies the reliability-redundancy allocation problem in multi-state flow networks, considering the minimization of cost or the maximization of reliability under resource constraints. An approximation scheme based on minimal cut is proposed to transform the problem, and feasibility guarantee and posterior check are conducted to ensure the quality of the solution. Numerical experiments show the tradeoff between accuracy and computational complexity, and the outperformance of the proposed method compared to a meta-heuristic algorithm.