應用螞蟻演算法求解製造單元重置矩陣切割問題

Applying Ant Colony Optimization to Rearranged Matrix Partitioning Problems for cellular manufacturing

鄭凱文(Kevin Cheng)

指導教授 ： 高有成

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

摘要

設計單元製造系統必須先解決單元形成問題（Cell Formation Problems，CFP），亦即設法找出適當的零件家族與機器單元，使得高度相似的零件盡量在同一個機器單元加工。這些分群方法被稱為群組技術（group technology，GT），其中矩陣式分群方法是常用到的方法。其先將包含機器與零件關係的初始矩陣，以特定方法轉換成重置矩陣(rearranged matrix)，再從重置矩陣中辨識出群組區塊，其內包含相關聯的零件家族與機器單元。但在相關文獻中，大都著重在重置矩陣的產生方法，反而對如何切割重置矩陣產生正確的單元區塊甚少著墨。因此本研究發展一套重置矩陣切割方法，來確認重置矩陣中的單元區塊。為有效求解大形問題，本研究利用螞蟻演算法(Ant Colony Optimization, ACO)發展出重置矩陣切割演算法，使其可以有效切割重置矩陣，進而正確辨識單元區塊，並且可以得到較佳的整體分群效益。在經過與二十五個文獻案例比較實驗，結果證明本研究提出的演算法可以得到相當不錯的單元形成結果。

關鍵字

旅行者問題 ； 矩陣切割 ； 單元製造 ； 群組技術 ； 螞蟻演算法

並列摘要

The manufacturing cell formation is a crucial issue in the design of a cellular manufacturing system. Many array-based methods have been proposed to solve cell formation problems. In the methods, the rows and columns of an initial machine-part matrix are reordered to form a structured matrix in which clusters of machines and parts are visible to be identified. An inherent problem is that the reordered matrices are often not well-structured and difficult to be partitioned into mutually separable clusters by visual inspection. Unfortunately previous researches seldom stress this problem. This paper proposes a matrix reordering and partitioning approach primarily based upon ant colony optimization (ACO). The proposed approach utilizes a colony of artificial ants to first find the best machine and part sequences in order to form a reordered matrix and then find the best partitioning points from the reordered matrix through laying pheromone trails on possible cutting points. The proposed approach has been developed as two software systems called the ANTSP and ACOMP algorithms, respectively. Performance evaluation of the approach was conducted by testing a set of cell formation problems selected from the literature. Testing results show that the proposed appraoch can effectively decompose intractable reordered matrix and provide satisfactory cell formation results.

並列關鍵字

cell formation problems ； Group technology ； Ant colony optimization ； TSP

參考文獻

[40] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Instroduction to Algorithms. McGraw-Hill Book Company, 1992.

[1] Ballakur, A., 1985, An investigation of part family machine group formation in designing a cellular manufacturing system. Unpublished PhD thesis, University of Wisconsin-Madison.

[2] Boctor, F. F., 1991, A linear formulation of the machine-part cell formation problem. International Journal of Production Research, 29, 343–356.

[3] Boe, W. J., & Cheng, C. H. (1991). A close neighbour algorithm for designing a cellular manufacturing system. International Journal of Production Research, 29, 2097-2116.

[4] C.S. Kumar and M.P. Chandrasekharan, “Grouping efficiency: a quantitative criterion for goodness of block diagonal forms of binary matrices in group technology” International Journal of Production Research, Vol. 28, pp.233-243, 1990.