Redundancy allocation problem heuristic based on multiple-objective optimization concepts

David W. Coit, Abdullah Konak

Research output: Contribution to conferencePaperpeer-review


A new heuristic has been developed to maximize system reliability through redundancy allocation. In this problem, the objective is to maximize system reliability of a series-parallel system by selecting component types (from among discrete choices) and redundancy levels, given system-level design constraints. This is a difficult nonlinear problem with integer decision variables. The new heuristic is developed based on an alternative problem formulation, which is to consider the problem as a multiple-objective optimization problem, with the objectives of simultaneously maximizing the reliability of each individual subsystem. This is logical because a high system reliability can be achieved by maximizing the reliability of each individual subsystem. It is also an attractive formulation because the problem can be further transformed to more readily obtain solutions. This new heuristic has several distinct advantages compared to existing heuristics and to other mathematical programming approaches to the problem. It has been tested on 33 example problems with generally excellent results. The redundancy allocation problem has previously been solved using dynamic programming, integer programming, genetic algorithms, tabu search and other heuristics. Previous mathematical programming approaches to the problem artificially constrained component selections, within a particular subsystem, to be of the same type, i.e., no component mixing. This limitation was necessary so the problem could be transformed into a form such that mathematical programming algorithms could be applied. This is an unrealistic constraint to designers for many types of systems, including electricity transmission and generation systems, where different component types are used to provide redundancy. The advantage of heuristics, including that described here, are that this design restriction is not required and component mixing can be explicitly considered. The multiple-objectives are nonlinear but they can be individually transformed into multiple linear objectives. Then, the multiple objectives are combined into an equivalent single objective problem using objective function weights. Failure time of the system is equal to the minimum failure time of each subsystem so it is logical to weight each subsystem equally when combining the multiple objectives into a single objective function. This forms a surrogate problem that is entirely linear and can be readily solved using integer programming methods. However, without removing undesirable parts of the solution-space, solutions to the surrogate problem can be poor considering the original problem objective, i.e., maximize system reliability. Fortunately, the undesirable portions of the solution space can be systematically and repetitively identified and removed. A sequence of problems can then be solved by introducing cutting-planes that limit the minimum subsystem reliability. The new heuristic is demonstrated and tested on 33 sample problems. These problems are extensions of the original problem proposed by Fyffe, Hines & Lee. The objective is to maximize system reliability with system level constraints for cost and weight. For each subsystem, there are three or four functionally equivalent component that can be selected. There are no limitations on component mixing in this formulation. The results are compared to the max-min heuristic and to genetic algorithm and tabu search solutions to the same 33 test problems. This heuristic is demonstrated to be efficient and it readily results in solutions approaching the best found for all sample problems.

Original languageEnglish (US)
Number of pages1
StatePublished - 2004
EventIIE Annual Conference and Exhibition 2004 - Houston, TX, United States
Duration: May 15 2004May 19 2004


OtherIIE Annual Conference and Exhibition 2004
Country/TerritoryUnited States
CityHouston, TX

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Redundancy allocation problem heuristic based on multiple-objective optimization concepts'. Together they form a unique fingerprint.

Cite this