變動鄰域搜尋法於串並聯系統複置配置問題之研究

Redundancy Allocation of Series-Parallel Systems Using Variable Neighbourhood Search Algorithms

陳怡靜(Yi-Ching Chen)

元智大學/工程學院/工業工程與管理學系/碩士(2004年)

摘要

串並聯系統複置配置問題通常都發生在對產品可靠度或安全性有著極高要求時所採用，此時系統設計以系統可靠度最大化為目標，為提高系統之目標，增加子系統內的複置元件是常見的方法之一，複置元件增加可提高系統可靠度，但系統成本及重量也隨之增加；另一常見之系統設計則以系統成本最小化為目標，並同時受到系統可靠度及重量之限制，在能時滿足系統目標及系統限制條件下，尋找使系統目標最佳化之複置配置狀態，此問題稱為複置配置問題（Redundancy Allocation Problem，RAP），其本質屬於NP-hard，求解相當不容易。
本研究使用變動鄰域搜尋法（Variable Neighborhood Search；VNS）求解該類問題，此演算法藉由系統化區域搜尋的方式，尋找在滿足系統限制下系統目標最佳化之複置配置狀態，並利用五組測試例題分別針對系統可靠度最大化及系統成本最小化這兩類複置配置問題進行求解，驗證其演算績效。
變動鄰域搜尋法求解問題時，不需要複雜的參數設計，本研究經由簡易的參數設計找出個別表現最佳及平均表現最佳的參數組合，並與其他演算法在相同測試例題求得的結果進行比較，發現變動鄰域搜尋法所得的結果在五組測試例題中，有四組的表現VNS皆優於其他演算法，而另一組的表現雖然較其他文獻所採用之演算法結果稍差，但其中VNS也提出了11個新的問題已知最佳解；除此之外，在研究中也發現使用變動鄰域搜尋法在串並聯系統複置配置問題上，不僅求解品質優於其他的演算法，求解時間較其他演算法更有效率，可充分顯見變動鄰域搜尋法簡單、快速之優點。

關鍵字

複置配置 ； 串並聯系統 ； 變動鄰域搜尋法 ； Redundancy allocation

並列摘要

This study presents a meta-heuristic, variable neighbourhood search (VNS), to the redundancy allocation problem (RAP). The RAP, an NP-hard problem, either maximizing system reliability or minimizing system cost given system-level constraints on reliability, cost, weight, etc. RAP has attracted much attention of prior work, generally in a restricted form where each subsystem must consist of identical components. Recent meta-heuristic methods in the literature overcome this limitation and offer a practical way to solve large instances of the relaxed RAP where different components can be used in parallel.
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 these cases of the RAP. That is, VNS employs the systematic change of neighbourhood search to obtain the optimal redundancy allocation under both system-level constraints. This study applies VNS to solve RAP in the form of series-parallel systems. Five sets of well-known benchmark problems are tested to verify the effectiveness and efficiency of proposed algorithms. Results on these benchmarks show that the VNS algorithms provide competitive solution quality at very economically computational expense in comparison with the best-known heuristics in the literature. In addition, VNS also demonstrates its simpleness and fastness in obtaining optimal solutions for RAP.

並列關鍵字

Series-parallel system ； Variable neighborhood search