現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:結合多元相似係數和超圖形切割法在群組技
術之應用 [以論文名稱查詢館藏系統]
論文英文名稱:Group Technology by Integrating Similarity
coefficient and Hypergraph Partitioning [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:工業工程與管理研究所
中文姓名:侯孟毅
英文姓名:Meng-Yi Hou
研究生學號:93378013
學位類別:碩士
語文別:中文
口試日期:2006-12-06
論文頁數:107
指導教授中文名:吳建文
指導教授英文名:Chien-Wen Wu
口試委員中文名:王河星;杜壯
口試委員英文名:Chuang Tu
中文關鍵詞:群組技術製造單元形成相似係數超圖形切割
英文關鍵詞:Group technologyManufacturing cell formationSimilarity coefficientHypergraph partitioning
論文中文摘要:群組技術一直以來都被認定為是解決生產製造系統問題的一項重要技術,而它主要目的就是將一個生產製造系統依照其相似的產品或是機台,分成多個子系統以便於管理。
在這篇文章中,我們提出一種強化相似係數的多元相似係數並且結合超圖形切割的新方法(Integrating Similarity coefficient and Hypergraph Partitioning -SCHP),來解決生產製造系統問題;多元相似係數的目的是反應多個項目之間的各種狀態發生的次數來計算關係強度,它能夠幫忙提升分群的績效;超圖形切割法原本是為了解決超大型積體電路設計而被提出,超圖形切割法能盡量保持切割後項目集合之間的關聯性和未切割前是一致的。步驟為先分階層找出機台之間的多元相似係數,然後再以超圖形切割法來進行分群,進而比較分群結果。
另外,我們也從相關的文獻中,挑選數個不同大小和結構的例子,以群組效力為績效指標,來評估我們所提出方法的分群績效,並同時和其它的方法做一個比較,從實驗的結果可以看出,我們所提出的方法在單元形成問題上,可以產生很好的分群效果。
論文英文摘要:Group Technology (GT) is an important method for solving problems in manufacturing system. The objective of group technology is to decompose a manufacturing system into a set of subsystems based on similarity of products and resources which are easier to manage. Recently, group technology has been successfully applied to many management areas, especially in cellular manufacturing systems.
I In this paper, we present a new approach (SCHP) that combines multi-item similarity coefficient with hypergraph partitioning for the group technology problem. We first use multi-item similarity coefficient to identify the similarity among multiple machines. We then use hypergraph partitioning to partition machines into groups while preserving the associations among machines.
We tested our approach by twenty test sets collected from the literature. The experimental results showed that the proposed approach can find quality solutions for cell formation problems.
論文目次:摘要....................................... I
ABSTRACT.................................. II
誌謝...................................... IV
目錄....................................... V
表目錄................................... VII
圖目錄.....................................IX
第一章 緒論.................................1
1.1 研究背景與動機..........................1
1.2 研究目的................................2
1.3 研究流程................................3
第二章 文獻回顧.............................5
2.1 相似係數................................5
2.2 群聚分析...............................10
2.1.1 矩陣式群聚法.........................11
2.1.2 階層式群聚演算法.....................13
2.1.3 非階層式群聚法.......................15
2.1.4 數學規劃法...........................17
2.1.5 圖形法...............................20
2.3 超圖形分割.............................22
2.3.1 收縮階段.............................24
2.3.2 分割階段.............................25
2.3.3 還原、修正階段.......................25
2.4 人工智慧...............................26
2.4.1 類神經網路...........................26
2.4.2 基因演算法...........................28
2.4.3 模擬退火法...........................34
2.5 資料挖掘...............................37
2.5.1 Apriori .............................38
2.5.2 高頻項目集...........................40
2.5.3 關聯法則.............................41
第三章 研究方法............................44
3.1 問題定義...............................44
3.1.1 對角線矩陣...........................44
3.1.2 衡量效力.............................45
3.1.3 相似係數.............................46
3.1.4 多元相似係數.........................48
3.2 軟體下載...............................49
3.3 方法步驟...............................53
3.4 範例說明...............................56
第四章 效能分析............................61
4.1 相似係數演算式.........................62
4.2 參數實驗案例...........................69
4.3 績效衡量比較...........................94
第五章 結論................................97
文獻.......................................98
論文參考文獻:[1] Alexei Elinson, Dana S. Nau, Feature-based similarity assessment of solid models, ACM Special Interest Group on Computer Graphics and Interactive Techniques, 1997, pp. 297 – 310.
[2] Agrawal, R., Srikant, R., Fast Algorithm for Mining Association Rules, Proceedings of 20th VLDB Conference, 1994, pp.487-499.
[3] Askin, R G. Gresswell, S.H., Goldberg, J. B. and Vakharia, A. J., A Hamiltonian path approach to reordering the part-machine matrix for cellular manufacturing, International Journal of Production Research, 1991, Vol. 29 No.10, pp.1081-1100.
[4] Baroni-Urbani,C., and Buser,M.W., Similarity of binary data, Systematic Zoology, 1976, Vol. 25, pp.251- 259.
[5] B. Adenso-Diaz, S. Lozano, I. Eguia ,Part-machine grouping using weighted similarity coefficients, Computers & Industrial Engineering, 2005, Vol. 48, pp. 553-570.
[6] Ballakur, A. and Steudel, H. J., A with-in cell utilization based heuristic for designingcellular manufacturing systems, International Journal of Production Research, 1987, Vol. 25, pp. 639-655.
[7] Bishop, Y. M. M., Fienberg, S. E., and Holland, P. W., Discrete Multivariate Analysis: Theory and Practice (Cambridge, MA: MIT Press), 1975.
[8] Boctor, F., A linear formulation of the machine-part cell formation problem. International Journal of Production Research, 1991, Vol. 29(2), pp343-356.
[9] Burbidge, J. H., Production flow analysis for planning group technology.Journal of Operations Management, 1991, Vol. 10(1), pp.5-27.
[10] Chandrasekharan , M. P., Rajagopalan, R., GROUPABILITY: an analysis of the properties of binary data matrices for group technology. International Journal of Production Research, 1989, Vol. 27, pp.1035-1052.
[11] Chandrasekharan , M. P., Rajagopalan, R., An ideal seed non-hierarchical clustering algorithm for cellular manufacturing. International Journal of Production Research, 1986, Vol.24, pp.451-464.
[12] Chandrasekharan , M. P., Rajagopalan, R., MODROC: an extension of rank order clustering for group technology. International Journal of Production Research, 1986, Vol. 24, pp.1221-1233.
[13] Chandrasekharan, M. P., and Rajagopalan, R., ZODIAC—an algorithm for concurrent formation of part families and machine-cells, International Journal of Production Research, 1987, Vol. 25, pp.835–850.
[14] Chan, H. M. and Miller, D A., 1982, Direct clustering algorithm for group formation in cellular manufacturing, Journal of Manufacturing Systems, 1982, vol. 1, no.10, pp.65-74.
[15] Chan, F. T. S., K. L. Mak, L. H. S. Luong and X. G. Ming, Machine-component grouping using genetic algorithms, Robotics and Computer-Integrated Manufacturing, 1998, Vol.14, pp.339-346.
[16] Chen, W. -H., and Srivastava, B., Simulated annealing procedures for forming machine cells in group technology. European Journal of Operational Research, 1994, Vol. 75(1), pp.100-111.
[17] Chen, M.-S., H an, J., and Yu, P. S., Data Mining: an overview from a database perspective. IEEE Transactions on Knowledge and Data Engineering, 1996, Vol.8, pp.866–883.
[18] Chen, M.C., Configuration of Cellular Manufacturing Systems Using Association Rules Induction, International Journal of Production Research, 2003, Vol. 41, no. 2, pp.381-395.
[19] Dimopoulos, C., and Mort, A., A hierarchical clustering methodology based on genetic programming for the solution of simple cell-formation problems, International Journal of Production Research, 2001, Vol. 39, pp.1-19.
[20] Evelyn C.Brown and Robert T. Sumichrast, CF-GGA: a grouping genetic algorithm for the cell formation problem, INT. J. PROD. RES., 2001,Vol.39, no.16, pp.3651-3669.
[21] Fantahun M. Defersha, Mingyuan Chen. A comprehensive mathematical model for the design of cellular manufacturing systems. Int. J. Production Economics 103 ,2006, pp.767–783.
[22] Fiduccia, C. M., Mattheyses, R. M., A linear time heuristic for improving network partitions. In Proc. 19th IEEE Design Automation Conference, 1982, pp.175-181.
[23] Forgy, E., Cluster analysis of multivariate data: Efficiency vs. interpretability of classifications. Biometrics,1965, vol.21, pp.768-780.
[24] Gomory, R. E., and Hu, T. C., Multi-terminal network flows. SIAM Journal on Applied Mathematics, 1661, Vol. 9(4), pp.551-570.
[25] Gupta, T., and Seifoddini, H, Production data based similarity coefficent for Machine-component grouping decisions in the design of a cellular manufacturing system, International Journal of Production Research, 1990, Vol.28(7), pp.1247-1269.
[26] Heragu, S. S., Group Technology and Cellular Manufacturing. IEEE Transactions on Systems, Man, and Cybernetics, 1994, Vol.24, pp.203-215.
[27] Han, E-H. G. Karypis, V. Kumar, and B. Mobasher. Clustering Based On Association Rule Hypergraphs. Workshop on Research Issues on Data Mining and Knowledge Discovery, 1997.
[28] Han, E.H., Karypis, G., Kumar, V., et al. Hypergraph based clustering in high-dimensional data sets: a summary of results, Data Engineering Bulletin, 1998, Vol.21, pp.15-22.
[29] Holley, J.W., and Guilford, J.P., A note on the G index of agreement, Educational and Psychological Measurement, 1964, 24, pp.749-753.
[30] Hwang, H. and J. U. Sun, A genetic-algorithm-based heuristic for the GT cell formation problem, Computers ind. Engng., 1996, Vol.30(4), pp.941-955.
[31] Irani, S. A., Cohen, P. H., and Cavalier, T. M., Design of cellular manufacturing systems. Transactions of the ASME, 1992, pp.352-361.
[32] Islam K.M.S.; Sarker B. R., A similarity coefficient measure and machine-parts grouping in cellular manufacturing systems , Journal of Production Research, 15 February 2000, Vol. 38, no.3, pp.699-720.
[33] Jaccard P. Nouvelles recherches sur la distribution florale, Bull Soc Vaud Sci Nat 1908, 44, pp.223-70.
[34] Jacobs, F. R and Muth, J.F., 1988, Large scale clustering for group technology part family and tooling analysis, ORSA/TIMS Joint National Meeting, Denver, Oct. 1988, pp.23-26.
[35] Joines, J. A., Manufacturing cell design using genetic algorithms, MSc Thesis. Raleigh, NC: North Carolina State University, 1993.
[36] Jose´ Fernando Gonc¸alves, Mauricio G.C. Resendeb, An evolutionary algorithm for manufacturing cell formation. Computers & Industrial Engineering, 2004, 47, pp.247–273.
[37] J. Wang, A linear assignment clustering algorithm based on the least similar cluster representatives, IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 1999, vol.29, no.1, pp.100-104.
[38] Kandiller, L., 1998, A cell formation algorithm: Hypergraph approximation – Cut tree. European Journal of Operational Research, 1998,109, pp.686-702.
[39] Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S., Multilevel hypergraph partitioning: application in vlsi domain. Technical report, Department of Computer Science, University of Minnesota.1997
[40] Karypis, G., Kumar, V., hMETIS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science, University of Minnesota, 1998, Available on the WWW at URL http://www.cs.umn.edu/~metis.
[41] Karypis, G., Kumar, V., Multilevel k-way hypergraph partitioning. Technical report, Department of Computer Science, University of Minnesota. 1998,
[42] Karypis, G., Kumar, V., A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing. 1998,
[43] Karypis, G., Multilevel hypergraph partitioning. Technical report, Department of Computer Science, University of Minnesota.2002.
[44] Kernighan, B. W., Lin, S., An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970, pp.291-307.
[45] King, J. R., Machine-component grouping in production flow analysis: an approach using a rank order clustering algorithm. International Journal of Production Research, 1980, 18, pp.213-232.
[46] King, J. R., Nakornchai, V., Machine-component group formation in group technology: review and extension. International Journal of Production Research,1982, 20, pp.117-133.
[47] Kirkpatrick, S., and Gelatt, C.D., Optimization by simulated annealing, 1983, Sci., 22, pp.671-680.
[48] Kumar, K. R., Kusiak, A., and Vannelli, A., Grouping of parts and components in flexible manufacturing systems. European Journal of Operational Research, 1986,24(3), pp.387-397.
[49] Kumar, C. S., Chandrasekharan, M. P., Grouping efficacy: a quantitative criterion for goodness of block diagonal forms of binary matrices in group technology. International Journal of Production Research, 1990,28, pp.233-243.
[50] Kusiak, A., The Generalized Group Technology Concept, International Journal of Production Research, 1987, 25(4), pp.561-569.
[51] Kusiak, A. and Chow, W.S., Decomposition of Manufacturing Systems, IEEE Journal of Robotics and Automation, 1988, vol. 4, no. 5, pp.457-471
[52] L. Kaufman and P. J. Rousseeuw, Finding Groups in data, An Itroduction to cluster analysis, JohnWiley & Sons,Brussels, Belgium. 1990,
[53] Luong, L. H. S., A cellular similarity coefficient algorithm for the design of manufacturing cells. International Journal of Production Research,1993, 31(8), pp.1757-1766.
[54] Mak, K.L., Wong, Y.S., and Wang, X.X., An adaptive genetic algorithm for manufacturing cell formation, International Journal of Advanced Manufacturing Technology, 2000, 16, pp.491-497.
[55] Malave, C. O., & Ramachandran, S., A neural network-based design of cellular manufacturing system. Journal of Intelligent Manufacturing,1991, 2, pp.305–314.
[56] Mcauley, J., Machine Grouping for Efficient Production, The Production Engineer, 1972,51, pp.53-57.
[57] McCormick, W. T., Schweitzer, P. J., & White, T. W, Problem decomposition data reorganization by a clustering technique. Operation Research, 1972, 20(5), pp.993–1009.
[58] Menouar Boulif, Karim Atif. A new branch-&-bound-enhanced genetic algorithm for the manufacturing cell formation problem. Computers & Operations Research ,2006,33, pp. 2219-2245.
[59] Metropolis, N., Rosenbluth, A.W., and Teller, A.H., Equation of state calculations by fast computing machines,” Journal of Chemical Physics, 1953, 21, pp.1087-1092.
[60] Miltenburg, J., Zhang, W., 1991, A comparative evaluation of nine well-known algorithms for solving the cell formation problem in group technology. Journal of Operations Management, 10, 44-72.
[61] Mitrofanov, S. P., The Scientific Principles of Group Technology. Boston Spa, Yorkshire, UK: National Lending Library Translation, 1966.
[62] Onwubolu, G.C. and M. Mutingi, A genetic algorithm approach to cellular manufacturing systems. Computers and industrial engineering, 2001, 39, pp.125-144.
[63] P. G. Brisbane and A. D. Rovira. A comparison of methods for classifying rhizosphere bacteria. J. Gen. Microbiol.1961, 26, pp.379- 392.
[64] Rajagopalan, R., and Batra, J. L., Design of cellular production systems: a graph-theoretic approach. International Journal of Production Research, 1975,13(6), pp.567-579.
[65] Romesburg, H.C., Cluster Analysis for Researchers (Belmont, CA: Lifetime Learning Publications, Wadsworth, Inc) ,1984.
[66] R. R. Sokal and C. D. Michener, A quantitative approach to a problem in classification. Evolution,1957, 11, pp.130-162.
[67] R. R. Sokal and C. D. Michener. A statistical method for evaluating systematic relationships. Univ. Kansas Sci. Bull. 1958, 38, pp.1409-1438.
[68] Seifoddini, H., and Wolfe, P. M., Selection of a threshold value based on material handling cost in machine–component grouping. IIE Transactions, 1987,19(3), pp.266-270.
[69] Seifoddini, H., Single linkage versus average linkage clustering in machine cells formation applications. Computers and Industrial Engineering, 1989, 16, pp.419-426.
[70] Shunk DL. Group technology provides organized approach to realizing benefits of CIMS. Industrial Engineering 1985, 17, pp.74–81.
[71] Srinivasan, G., Narendran, T. T., and Mahadevan, B., An assignment model forthe part-families problem in group technology. International Journal of Production Research, 1990,28(1), pp.145-152.
[72] Srinivasan, G.., Narendran, T. T., GRAFICS-a nonhierarchical clustering algorithm for group technology. International Journal of Production Research, 1991, 29, pp.463-478.
[73] Srinivasan, G., A clustering algorithm for machine cell formation in group technology using minimum spanning trees. International Journal of Production Research, 1994, 32(9), pp.2149-2158.
[74] U. Hamann. Merkmal sbestand und Verwandts chaftsbezie chungen der Farinosae. Ein Beitrag zum System der Monokttyledonen. Willddenowia 2, 1961, pp.639-768.
[75] Venugopal, V., & Narendran, T. T., A genetic algorithm approach to the machine-component grouping problem with multiple objectives. Computers in Industrial Engineering, 1992, 22(4), pp.469–480.
[76] Venugopal, V., & Narendran, T. T., Cell formation in manufacturing systems through simulated annealing: an experimental evaluation. International Journal of Production Research, 1992, 63(3), pp.409–422.
[77] Vohra, T., Chen, D. -S., Chang, J. C., and Chen, H. -C., A network approach to cell formation in cellular manufacturing. International Journal of Production Research, 1990, 28(11), pp.2075-2084.
[78] Wang, J. and Roze, c., Formation of Machine Cells and Families: A Modified P-median Model and Comparative Study, Internation Journal of Production Research, 1997, 35(5), pp.1259-1286.
[79] Wei, J. C., and Kern, G. M., Commonality analysis: a linear cell clusting algorithm for group technology. International Journal of Production Research, 1989, 27(12), pp.2053-2062.
[80] Won, Y., New p-median approach to cell formation with alternative process plans, International Journal of Production Research, 2000, 38, pp. 229-240.
[81] Yasuda, K., and Yin, Y., A dissimilarity measure for solving the cell formation problem in cellular manufacturing. Computer &Industrial Engineering, 2001, 39, pp.1-17.
[82] Yong Yin, Kazuhiko Yasuda, Similarity coefficient methods applied to the cell formation problem: A taxonomy and review. International Journal of Production economics, 2006, 101(2), pp.329-352.
[83] Y. M. M. Bishop, S. E. Fienberg and P. W. Holland. Discrete Multivariate Analysis: Theory and Practice. MIT Press Cambridge, MA, 1975.
[84] Zahir Albadawi, Hamdi A. Bashir, Mingyuan Chen, A mathematical approach for the formation of manufacturing cells. Computers & Industrial Engineering , 2005, 48, pp.3–21
[85] 吳建文,邱順福 2005, Group technology by frequent itemset mining and hypergraph partitioning. 國立台北科技大學工業工程與管理研究所碩士論文
論文全文使用權限:不同意授權