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

A Variable Neighborhood Descent Heuristic to the Redundancy Allocation Problems of Series-Parallel System

吳佳娟(Chia-Chuan Wu)

指導教授 ： 梁韵嘉

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

摘要

串並聯系統經常使用在對可靠度或安全性要求較高的系統及產品中，為提高串並聯系統之可靠度，增加子系統內的複置元件是常見的方法之一，然而複置元件的增加亦使系統成本及重量隨之增加，在能同時滿足系統成本及重量限制條件下，尋找使系統可靠度為最大化之複置配置狀態，此問題稱之為複置配置問題（Redundancy Allocation Problem，RAP），其本質屬於NP-hard，求解相當不容易。
本研究首次使用變動鄰域尋優法（Variable Neighborhood Descent；VND）求解該類問題，此演算法藉由系統化區域搜尋的方式，尋找在成本及重量限制下可靠度最大之複置元件配置狀態，並嘗試加入模擬退火法可接受較差解的機制，發展出一個混合啟發式演算法名為VND_SA，並利用測試例題進行求解，驗證其演算績效。
經由相關參數設計尋找最佳化參數組合，並比較測試例題求得的結果，變動鄰域尋優法所得的結果雖然略差於文獻最佳解但平均誤差不超過0.3％；而加入模擬退火法後雖能接受較差的解且擴大區域搜尋範圍，但卻未能有效幫助最佳解的搜尋。除上述結果外，在研究中更發現使用變動鄰域尋優法求解問題不需要複雜的參數設計，且在串並聯系統複置配置問題的求解時間上較其他演算法更有效率，可充分顯見變動鄰域搜尋法簡單、快速之優點。

關鍵字

複置配置 ； 串並聯系統 ； 變動鄰域尋優法

並列摘要

Series-parallel system has been frequently used to maintain the reliability and security of a product or system. In order to increase the system reliability, the inclusion of the redundant component is a common approach. Unfortunately, such inclusion will often lead to increasing weight and cost of a system. Thus, when the system cost and weight constraints are given, how to effectively select the optimal combination of components and redundancy level for each type of components so that the system reliability becomes the maximum has been considered an NP-hard redundant allocation problem (RAP).
The paper applies the algorithm of Variable Neighborhood Descent (VND) to solve RAP in the series-parallel system. That is, using the systematic neighborhood local search method to obtain the optimal redundancy allocation under both cost and weight constraints. This research also develops a hybrid algorithm called VND_SA in which an acceptance mechanism borrowed from simulated annealing is employed. A set of benchmark problem is tested to verify the effectiveness and efficiency of both algorithms.
Our result indicate that percentage deviation from best-known solutions is the lower than 0.3% using VND algorithm. In addition, VND_SA can not help improve solution quality as expected though it did expand the search area. Our research concludes that VND is a simple and fast algorithm to obtain the near-optimal solutions for RAP and does not need complex parameters design.

並列關鍵字

Redundancy allocation ； Series-Parallel System ； Variable neighborhood descent

參考文獻

56.黃宇辰，「應用混合式螞蟻演算法於可靠度串並聯系統元件配置問題之研究」，碩士論文，元智大學，民國九十二年。

36.Kuo, W., V. R. Prasad, F. A. Tillman and C. L. Hwang, Optimal Reliability Design: Fundamentals and Application, Cambridge University Press, U. K., 2001.

47.Pérez, J. A. M., J. M. Moreno-Vega and I. R. Martín, “Variable neighborhood tabu search and its application to the median cycle problem,” European Journal of Operational Research, vol. 151, no. 2, 2003, 365-378.

1.Aggarwal, K. K., J. S. Gupta and K. B. Misra, “A new heuristic criterion for solving a redundancy optimization problem,” IEEE Transactions on Reliability, vol. R-24, 1975, 86-87.

4.Bräysy, O., “A reactive variable neighborhood search for the vehicle routing problem with time window,” INFORMS Journal on Computing, vol. 15, no. 4, 2003.