結合ACO與PSO演算法求解動態單元形成問題

Combination of ACO and PSO algorithms for solving dynamic cell formation problems

劉寶義(Bao-yi Liu)

指導教授 ： 楊承亮 ； 高有成

大同大學/經營設計學院/資訊經營學系所/碩士(2010年)

摘要

針對客戶端少量多樣的產品需求，單元製造系統是最具生產效率的方式之
一，而求解單元形成問題則是在設計單元製造系統中最重要的一個步驟。在單元
形成問題中，主要運用群組技術將相似的零件集合成零件家族，並形成相對應的
機器單元，目的為降低零件在機器間的搬運成本等。而過去文獻大多探討組數事
先已知且固定的單元形成問題，反而對於組數事先未知的情況甚少著墨。因此本
研究提出結合螞蟻最佳化演算法(ACO)與粒子群最佳化演算法(PSO)的一個混合
式演算方法，透過ACO 演算法先形成機器重置矩陣，再利用PSO 演算法切割該
重置矩陣形成機器單元，並逐一指派零件形成零件家族。本研究試圖在組數事先
未知的情況下求解動態單元形成問題。在經過與過去文獻實例驗證後，證明本研
究提出的演算方法具有優異的動態單元形成結果以及求解效率。

關鍵字

單元形成問題 ； 螞蟻演算法 ； 粒子演算法 ； 動態分群

並列摘要

Cellular manufacturing system (CMS) is one of the most effective approaches to deal with the requirements of manufacturing small amount and large-variety products. The most important step in the design of CMS is to solve the cell formation problems (CFP). The main idea of most CFP approaches is to cluster similar parts into part families and cluster machines into machine cells concurrently in order to reduce the transportation cost of parts among machine cells in the production stage. In the past decades, most of the CFP approaches need the number of clusters to be given beforehand, and very few papers focus on dynamic cell formation problems (DCFP). Therefore, this paper proposes a new algorithm based on the ant colony optimization (ACO) algorithm and particle swarm optimization (PSO) algorithm to solve the dynamic CFP. Performance evaluation of the proposed approach is conducted by testing five CFP cases selected from the literature. The results of testing show that the proposed approach can solve the dynamic CFP very well.

並列關鍵字

cell formation problems ； Ant Colony Optimization ； Particle Swarm Optimization ； Dynamic clustering

參考文獻

[1] Aljaber N., Baek W. and Chen C.L. , A tabu search approach to the cell formation problem , Computers and Industrial Engineering , Vol.32 , No.1 , pp.169-185 , 1997 .

[2] Andres C. and Lozano S. , A particle swarm optimization algorithm for partmachine grouping , Robotics and Computer-Integrated Manufacturing , Vol.22 , pp.468-474 , 2006 .

[3] Ateme-Nguema B.H. and Dao T.-M. , Optimization of cellular manufacturing systems design using the hybrid approach based on the ant colony and tabu search techniques , IEEE International Conference on Industrial Engineering and Engineering Management , pp.668-673 , 2007 .

[4] Chan H.M. and Milner D.A. , Direct clustering algorithm for group formation in cellular manufacture , Journal of Manufacturing Systems , Vol.1 , No.1 , pp.64-76 , 1982 .

[5] Chandrasekharan M.P. and Rajagopalan R. , An ideal seed non-hierarchical clustering algorithm for cellular manufacturing , International Journal of Production Research , Vol.24 , No.2 , pp.451-464 , 1986 .