A Computational Complexity Analysis of an Algorithm for Reliability Optimization

Least-cost allocation of redundancy within subsystems of a series-parallel system to meet a requirement for system reliability may be modelled as a nonlinear integer program in which the number of variables is equal to the number of subsystems. The data are the system requirement, the reliabilities of the identical components within each subsystem and the costs of these components. The model has a linear cost function as its objective and a single non-linear constraint that enforces the requirement for system reliability. The continuous counterpart of the discrete problem can be solved by solving a polynomial equation. The main result of this paper is a bound on the effort required to obtain from the solution of the continuous relaxation the optimal numbers of redundant components for the subsystems.