REDUNDANCY ALLOCATION OF SERIES-PARALLEL SYSTEMS USING A VARIABLE NEIGHBOURHOOD SEARCH ALGORITHM

摘要

This paper presents a meta-heuristic algorithm, variable neighbourhood search (VNS), to the redundancy allocation problem (RAP). The RAP, an NP-hard problem, has attracted much attention of prior work, generally in a restricted form where each subsystem must consist of identical components. The newer meta-heuristic methods overcome this limitation and offer a practical way to solve large instances of the relaxed RAP where different components can be used in parallel. Authors' previous work has shown the promise of variable neighbourhood descent (VND) method, the simplest version among VNS variations, on RAP. The variable neighbourhood search method itself has not been used in reliability design, yet it is a method that fits perfectly those combinatorial problems with potential neighbourhood structures, as in the case of the RAP. Therefore, authors further extend their work to develop a VNS algorithm for the RAP and test on a set of well-known benchmark problems from the literature. Results on 33 test instances ranging from less to severely constrained conditions show that the variable neighbourhood search method improves the performance of VND and provides competitive solution quality at very economically computational expense in comparison with the best-known heuristics including ant colony optimization, genetic algorithm, and tabu search.