The methods for exactly solving redundancy allocation optimization for multi-state series–parallel systems

Redundancy allocation problems (RAPs) is a classical family of reliability optimization problems. RAP for multi-state systems (MSSs) is among the most difficult RAPs. Multi-state series–parallel system (MSSPS) is among the most commonly-applied structure of MSSs. To the knowledge of the authors, in literature there is no exact approach to solve MSSPS RAP. In this work, we propose an efficient exact solution method based on dynamic programming to solve it. In literature, there are two formulations of RAP, namely maximizing the system reliability and minimizing of the system cost under the resource constraints. In this work, we investigate the conversion between the two formulations such that the two different RAP formulations can be exactly solved via our proposed method. Experiments are conducted on the well-known benchmarks. The results are compared with the published ones achieved by meta-heuristics. Our methods confirm that majority of the published solutions are in fact global-optimal. In addition, our methods find three new global-optimal solutions. The experiments also illustrate that on systems with more subsystems and fewer component types, our proposed method significantly outperforms the heuristic method in MSSPS RAP with exact optimal solutions and less running time.