臺灣博碩士論文加值系統

本研究使用了一種基於差分演化演算法（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.

Abstract iv
致謝 v
目錄 vi
圖目錄 viii
表目錄 ix
CHAPTER 1 緒論 10
1.1 研究背景與動機 10
1.2 研究範圍 11
1.3 論文架構 12
CHAPTER 2 文獻探討 13
2.1 矩陣式模型 13
2.2 績效指標 15
2.2 集群分析法 15
2.3 基因演算法 16
2.4 粒子群演算法 17
2.5 差分演化演算法 18
CHAPTER 3 差分演化單元形成演算法 20
3.1 符號表示 20
3.2 差分演化單元形成演算法 21
3.3 績效指標GE值 24
CHAPTER 4 差分演化單元形成系統 26
4.1 系統流程 26
4.2 案例說明 28
CHAPTER 5 實例驗證與比較研究 31
5.1 穩定性實驗 31
5.2 文獻比較 34
5.3 演算法綜合比較 35
5.4 複雜度實驗 43
5.5 參數值實驗 43
5.6 區域搜索 45
5.7 結論 47
CHAPTER 6 結論與未來展望 49
6.1 結論 49
6.2 未來展望 50
參考文獻 51
附錄 54
1.重置矩陣 case 16 54
2.重置矩陣 case 17 55

[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.
[3]Busygin S., Prokopyev O. and Pardalos P.M. “Biclustering in data mining,” Computer & Operations Research 35, Vol. 35, pp. 2964-2987, 2008.
[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.
[7]Chan, H. M. and Milner, D. A. “Direct clustering algorithm for group formation in cellular manufacture.” Journal of Manufacturing Systems, Vol. 1, pp. 64-76, 1982.
[8]Han, J. and Kamber, M., “Data Mining: Concepts and Techniques.” Morgan Kaufmann Publishers, 2001.
[9]Goldberg, D.E. “Genetic Algorithm in Search.” Optimization and Machine Learning, Addision-Wesley, New York, 1989.
[10]Davis, L. “Handbook of Genetic Algorithm.” Van Nostrand Reinhold, New York, 1991.
[11]Tseng, L.Y. “Genetic algorithm for clustering, feature selection and Classification.” IEEE International Conference on Neural Networks, Vol. 3, pp.1612-1616, 1997.
[12]Maulik, U. and Bandyopadhyay, S, “Genetic algorithm-based clustering technique.” Pattern Recognition Vol. 33, pp.1455-1465, 2000.
[13]Kennedy, J. and Eberhart, R.C. “Particle Swarm Optimization,” Proceedings of the IEEE International Joint Conference on Neural Networks, Vol. 4, pp. 1942-1948, 1995.
[14]Eberhart, R.C. and Shi, Y. “Particle swarm optimization: developments, applications and resources” Proceedings of the IEEE Congress on Evolutionary Computation, pp. 81-86, 2001.
[15]van der Merwe, D.W. and Engelbrecht, A.P. “Data clustering using particle swarm optimization.” Proceedings of IEEE Congress on Evolutionary Computation 2003, pp. 215-220, 2003.
[16]Storn, R. and Price, K. ”Differential Evolution – A simple and Efficient AdaDtive Scheme for Global Optimization over Continuous Spaces,” Technical Report, TR-95.012, ICSI, 1995.
[17]Storn R. and Price, K. “Differential evolution — A simple and efficient heuristic for global optimization over continuous spaces,” Journal of Global Optimization, Vol. 11, No. 4, pp. 341–359, 1997.
[18]Paterlini, S. and Krink, T. “High performance clustering with differential evolution,” Proceedings of the IEEE Congress on Evolutionary Computation, Vol. 2, pp. 2004-2011, 2004.
[19]Chandrasekharan, M.P. and Rajagopalan, R. “An ideal seed non-hierarchical clustering algorithm for cellular manufacturing,” International Journal of Production Research, Vol. 24, pp. 451-464, 1986.
[20]Chandrasekharan, M.P. and Rajagopalan, R. “ZODIAC—an algorithm for concurrent formation of part-families and machine-cell,” International Journal of Production Research, Vol. 25, p.p. 835–850, 1987.
[21]Chandrasekharan, M.P. and Rajagopalan, R. “GROUPABILITY: Analysis the properties of binary data matrices for group technology,” International of Journal of Production Research, Vol. 27, pp. 1035-1052, 1989.
[22]Zolfaghari, S. and Liang, M. “A new genetic algorithm for the machine/part grouping problem involving processing times and lot sizes,” Computers and Industrial Engineering, Vol. 45, pp. 713-731, 2003.
[23]Paterlini, S. and Krink, T. “Using differential evolution to improve the accuracy of bank rating systems,” Computational Statistics & Data Analysis, Vol. 52, pp. 68-87, 2007.