差分演化演算法應用於單元形成問題

A Differential Evolution Approach for Machine Cell Formation

吳建寬(Jian-Kuan Wu)

指導教授 ： 林金城 ； 高有成

大同大學/電機資訊學院/資訊工程學系所/碩士(2008年)

摘要

本研究使用了一種基於差分演化演算法（differential evolution）的方式解決單元形成問題。單元形成是對零件與機器進行分群，使得加工過程類似的零件群組，可以集中在相關的機器群組中生產，以減少生產過程中的搬運浪費。為解決此問題，我們採用雙分群方式(bi-clustering)，亦即同時對機器與零件作資料分群的方法。因為差分演化演算法容易實作且不用設定太多參數，本研究利用差分演化演算法同時去尋找機器與零件的群中心，並將機器單元與零件家族自動配對。我們從過去文獻中選取了許多的測試問題，並將其測試結果展現，顯示出本研究所提方法可以有效地解決單元形成問題。

關鍵字

單元形成 ； 資料分群 ； 差分演化演算法 ； 群組技術

並列摘要

This paper presents a new approach based on differential evolution algorithms to solve cell formation problems. The proposed approach handles the problem in a way of data bi-clustering and can form machine cells and part families concurrently. Differential evolution is simple to implement and has fewer parameters needed to set. The proposed approach applies differential evolution to find machine cluster centers and part cluster centers at the same time. Thus the approach can form machine cells and their corresponding part families automatically. A number of test problems had been selected from literature and the experimental results reveal that the proposed approach is able to solve cell formation problems effectively.

並列關鍵字

differential evolution ； data clustering ； machine cell formation ； group technology

參考文獻

[1] Friedman, H. P. and Rubin, J. “On some invariant criteria for grouping data,” J. Amer. Statist. Ass. , Vol. 62, No. 320, pp.1159-1178, 1967.

[2] Selim, H.M., Askin, R.G.. and Vakharia, A.J. “Cell formation in group technology : Review, evaluation and directions for future research,” Computers and Industrial Engineering, Vol. 34, No.1, pp.3-20, 1998.

[4] Kumar, C.S. and Chandrasekharan, M.P. “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.

[5] McCormick, W.T., Schweitzer P.J. and White, T.W. “Problem decomposition and data reorganization by a clustering technique.” Operations Research, Vol. 20, pp. 993–1009, 1972.

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