臺灣博碩士論文加值系統

單元製造為群組技術最主要的應用，需要一個有效的零件分群法則，來進行初步製造單元設計。集群分析法為常用方法之一，搭配特殊設計的相似係數，能集群相似度高的零件成為零件家族。集群分析法可分為階層分群與非階層分群兩種，但階層分群法容易有鏈結效應，而非階層分群事先需給定零件家族數目。故在本研究中提出一個以人工螞蟻分群模式為基之零件分群演算法，來解決上述問題。本演算法利用螞蟻分群特性：群體性與隨機性，使零件分群過程有再指派的機制，降低例外資料對分群結果之影響。另外，本演算法利用螞蟻的自我組織能力，自然地形成數群相似度甚高的零件家族，並利用嵌入合併法則的螞蟻去達到規劃者理想群數。本演算法已經被開發成APCS(Ant-based Part Clustering System)系統，並利用分群績效指標，對十五個文獻案例進行測試，都得到相當好的單元形成結果。最後與七種傳統集群分析法進行比較，顯現出本演算法在零件分群方面確實有較佳表現。

Cellular Manufacturing is one of the major applications of group technology. It requires an effective part clustering approach to execute preliminary manufacturing cell design. One of famous approaches is the cluster analysis method, which uses similarity coefficients and clustering methods to group similarity parts into part families. Clustering methods are divided into two categories: hierarchical and nonhierarchical methods. Hierarchical methods often suffer from chaining effects, while nonhierarchical methods need a predetermined cluster number. The research proposes a part clustering algorithm that is based on an artificial ant clustering model. The algorithm utilizes the characteristics of ants, congregation and randomness, to prevent grouping results from being fixed during clustering processes and to reduce the effects of noisy data. Besides, the algorithm has the ability of self-organization to form high homogeneous part families naturally. The algorithm has been developed to an ant-based part clustering software system (APCS). Fifteen literature problems were selected to test the proposed algorithm with respect to group efficancy. We found that the algorithm is able to obtain better machine cell configurations. A comparative study was also conducted to compare the algorithm with seven conventional clustering methods, and the results showed that the algorithm appears to outperform most of conventional methods.

摘要 I
Abstract II
致謝 III
Table of Contents IV
List of Figures VI
List of Tables VII
Chapter1 Introduction 1
1.1 The Background and Motivation of Research 1
1.2 The Objective of Research 2
1.3 The Flow Chart of Research 5
1.4 The Scope and Limitation of Research 8
1.5 The Framework of thesis 9
Chapter2 Literature Review 10
2.1 Group Technology 10
2.2 Cell Formation Methods 11
2.3 Cluster Analysis Method 15
2.3.1 Similarity Coefficient 15
2.3.2 Hierarchical Clustering Method 17
2.3.3 Non-Hierarchical Clustering Method 19
2.3.4 Two-Phase Cluster Analysis 20
Chapter3 Ant Clustering Model 22
3.1 Swarm Intelligence 22
3.2 The Introduction of Ant Clustering Model 22
3.3 The Application of Ant Clustering Model 25
Chapter4 Ant Clustering Algorithm 28
4.1 An Ant-based Part Clustering Algorithm 28
4.1.1 Initializing Phase 29
4.1.2 Producing Part Families 29
4.1.3 Refining Part Families 34
4.1.4 Combining Part Families 35
4.2 The Flow of Algorithm 37
4.3 Ant-based Part Clustering System(APCS) 38
4.3.1 Part Family Formation 39
4.3.2 Machine Assignment 39
4.3.3 Performance Evaluation 39
Chapter5 Case Verification and Comparison 42
5.1 Case Verification 42
5.1.1 Part Family Formation 42
5.1.2 Machine Assignment 47
5.1.3 Performance Evaluation 47
5.2 Comparative Study 48
5.2.1 Performance Consistency Measurement 50
5.2.2 Best Known Solution Comparative 52
5.2.3 Comparison with Cluster Analysis Method 53
5.3 Brief Summary 57
Chapter6 Conclusion and Future Work 58
6.1 Conclusion 58
6.2 Future Work 59
Bibliography 61

1.Askin, G. R., Cresswell, H. S., Goldberg, B. J. and Vakharia, J. A., 1991, A Hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing. International Journal of Production Research, 29, 1081-1100.

2.Bonabeau, E., Dorigo, M., and Theraulaz, G., 1999, Swarm intelligence：from natural to artificial systems. New York：Oxford University Press.

3.Burbidge, L. J., 1975, The introduction of group technology. New York：John Wiley and Sons.

4.Carrie, A. S., 1973, Numerical taxonomy applied to group technology and plant layout. International Journal of Production Research, 11, 399-416.

5.Chan, H. M. and Milner, D. A., 1982, Direct clustering algorithm for group formation in cellular manufacture. Journal of Manufacturing Systems, 1, 65-75.

6.Chandrasekharan, M. P., and Rajagopalan, R., 1986, An ideal seed non-hierarchical clustering algorithm for cellular manufacturing. International Journal of Production Research, 24, 451-464.

7.Chandrasekharan, M. P. and Rajagopalan, R., 1987, ZODIAC: an algorithm for concurrent formation of part families and machines cells. International Journal of Production Research, 25, 835-850.

8.Choobineh, F., 1988, A framework for the design of cellular manufacturing systems. International Journal of Production Research, 26, 1161-1172.

9.Deneubourg, J. L., Goss, S. and Franks, N., Sendova-Franks, A., Detrain, C., and Chretien, L., 1991, The dynamics of collective sorting robot-like ants and ant-like robots. In Proc. Of the 1st Conf. on Sim. of Adaptive Behavior, 356-363.

10.De Witte, J., 1980, The use of similarity coefficients in production flow analysis. International Journal of Production Research, 18, 503-514.

11.Dorigo, M., Gambardella, M. L., 2002, Guest editorial special section on ant colony optimization. IEEE Transactions on Evolutionary Computation, 6, 317-319.

12.Groover P. M., 2001, Automation, Production Systems, and Computer-Integrated Manufacturing, Prentice Hall International Editions, Second Edition.

13.Gupta, T. and Seifoddini, H., 1990, Production data based similarity coefficient for machine-component grouping decisions in the design of a cellular manufacturing system. International Journal of Production Research, 28, 1247-1269.

14.Handl, J. and Meyer, B., 2002, Improved ant-based clustering and sorting in a document retrieval interface. Proceedings of the Seventh international Conference on Parallel Problem Solving from Nature (PPSN VII). LNCS , 2439.

15.Islam, K. Md. S. and Sarker, B. R., 2000, A similarity coefficient measure and machine-parts grouping in cellular manufacturing systems. International Journal of Production Research, 38, 699-720.

16.Johnson, R. A., and Wichern, D. W., 1998, Applied Multivariate Statistical Analysis, Prentice Hall, New Jersey.

17.King, 1980, Machine component grouping in production flow analysis: an approach using rank order clustering. International Journal of Production Research, 18, 213.

18.King, J. R. and Nakornchai. V., 1982, Machine component group formation in Group Technology--review and extension. International Journal of Production
Research, 20, 117-133

19.Kuntz, P., Layzell, P., and Snyers, D., 1997, A Colony of Ant-like Agents for Partitioning in VLSI Technology. Proceedings of Fourth European Conference
On Artificial Life, MIT Press, 417-424.

20.Lai, W. K., Hoe, K. M., Tai, S. Y. Tracy, and Seah, C. Y. Melissa, 2001, Classifying English web pages with smart ant-like agents. World Automation Congress, Proceedings of the 5th Biannual, 13, 9-13.

21.Lumer, E. and Faieta, B., 1994, Diversity and adaptation in populations of clustering ants. Proceeding of the Third International Conference on Simulation of Adaptive Behavior：From Animals to Animats, MIT Press/ Bradford Books, Cambridge, MA, l3, 501-508.

22.McAuley, J., 1972, Machine grouping for efficient production. The Production Engineer, 51, 53-57.

23.Mosier, C., 1989, An experiment investigating the application of clustering procedures to the gt machine cell formation problem. International Journal of Production Research, 27, 1811-1935.

24.Monmarche, N., Slimane, M. and Venturini, G., 1999, AntClass: discovery of clusters in numeric data by a hybridization of an ant colony with the Kmeans algorithm. Internal Repport No.213, E3i, 1-21.

25.Prabhakaran, G., Janakiraman, T. N. and Sachithanandam, M., 2002, Manufacturing Data-Based combined dissimilarity coefficient for machine cell formation. The International Journal of Advanced Manufacturing Technology, 19, 889-897.

26.Punj G. and Stewart D., 1983, Cluster analysis in marketing research：review and suggestions for application. Journal of Marketing Research, 145.
27.Rajagopalan, R. and Batra, J., 1975, Design of cellular production systems—a graph theoretic approach. International Journal of Production Research, 13, 53-68.

28.Selim, H. M., Askin, R. G. and Vakharia, A. J., 1998, Cell formation in group technology：Review Evaluation and directions for future research. Computers industrial Engineering, 34, 3-20.

29.Seifoddini, H., 1989, A note on the similarity coefficient method and the problem of improper machine assignment in group technology applications. International Journal of Production Research, 27, 1161-1165.

30.Seifoddini, H. and Wolfe, P. M., 1986, Application of similarity coefficient method in group technology. AIIE Transactions, 271-277.

31.Shafer, S. M., and Meredith, J. R., 1990, A comparison of selected manufacturing cell formation techniques. International Journal of Production Research, 28, 661-673.

32.Shafer, S. M. and Rogers, D. F., 1993 (a), Similarity and distance measures for cellular manufacturing. PartI. A survey. International Journal of Production Research, 31, 1133-1142.

33.Shafer, S. M. and Rogers, D. F., 1993 (b), Similarity and distance measures for cellular manufacturing. PartII. A extension and comparison. International Journal of Production Research, 31, 1315-1326.

34.Stanfel, E. L., 1985, Machine clustering for economic production. Engineering costs and production economics, 9, 73-81.

35.Waghoderkar, P. H. and Sahu, S., 1984, Machine-component cell formation in group technology：MACE. International Journal of Production Research, 22, 937-948.

36.Wemmerlöv. U. and Hyer. N. L., 1986, Procedures for the part family machine group identification problem in cellular manufacturing. Journal of Operations Research, 6, 125-147.

37.Wu, B., Zhongzhi S., 2001, A clustering algorithm based on swarm intelligence, International Conferences on Info-tech & Info-net, Bejing, ICII, 3, 58-66.

38.Wu, B., Zheng Y. L., Liu, S. and Shi, Z., 2002, CSIM: A Document Clustering Algorithm Based On Swarm Intelligence, IEEE Evolutionary Computation. Proceedings of the 2002 Congress on, 1, 12-17.

39.Wu, H. L., Venugopal, R., and Barash, A., 1986, Design of a cellular manufacturing system：A syntactic pattern recognition approach, Jounal of Manufacturing Systems, 5, 81-88.

40.詹世煌，民90，以集群法偵測迴歸分析之影響值，國立成奶j學統計學系碩士論文。

41.黃俊英，民89，多變量分析(第七版)，中國經濟企業研究所。