現在位置首頁 > 博碩士論文 > 詳目
  • 同意授權
論文中文名稱:應用高頻項目集探勘求解彈性製造系統中的作業指派及空間分配問題 [以論文名稱查詢館藏系統]
論文英文名稱:Applying frequent itemset mining to solve operation assignment and capacity allocation problem in flexible manufacturing systems [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:工業工程與管理研究所
畢業學年度:97
出版年度:98
中文姓名:林載添
英文姓名:Tzai-Tian Lin
研究生學號:96378001
學位類別:碩士
語文別:中文
口試日期:2009-06-29
論文頁數:44
指導教授中文名:吳建文
口試委員中文名:陳凱瀛;黃祥熙
中文關鍵詞:彈性製造系統機器承載問題資料探勘
英文關鍵詞:Flexible manufacturingMachine loading problemFrequent itemset mining
論文中文摘要:我們討論彈性製造系統(FMS)中的作業及刀具指派問題,我們假設系統中的機器有著作業時間及刀具容納空間的限制,而每種作業都有其特定的權重。我們希望找出一個方法,該方法能適當的指派作業及刀具至系統中使得被指派作業能為系統帶來最高的權重。在文中我們說明了本問題為NP-hard問題。
本研究建構了一個以資料探勘為基礎的方法求解最高權重的作業指派及空間分配問題,為了比較本方法的求解績效,本研究運用過去文獻中提出的禁忌搜尋法來求解相同問題。最後實驗結果顯示本研究提出的方法可以效率的求得最佳解,而禁忌搜尋法只能求得近似最佳解,因而證明本方法較禁忌搜尋法優良。
論文英文摘要:We consider the problem of operation assignment and capacity allocation arising in a flexible manufacturing system. We assume that the operating time of Computer Numerically Controlled (CNC) machine and its capacity for tools are both limited. Besides, the weights of all operations are given. Our target is to find a good approach which can select proper operations and assign them together with their required tools to CNC machine so as to maximize the total weight of selected operations for FMSs. In this study, we show that the problem is NP-hard and develop a novel approach based on frequent itemset mining to solve the problem. For comparing the performance of our approach, we consider a heuristic and a tabu search algorithm presented by literature to solve the above problem. The results of our computational tests have revealed that our approach could produce optimal solutions very quickly. It shows our approach is better than the tabu search approach.
論文目次:摘 要 ii
Abstract iii
目錄 iv
表目錄 v
圖目錄 vi
第一章 緒論 1
1.1 研究背景及動機 1
第二章 文獻探討 4
2.1 作業指派及空間分配問題的相關研究 4
2.2 機器負載問題的相關研究 6
2.2.1 機器負載問題的目標函數 6
2.2.2 機器負載問題的限制式 9
2.2.3 機器負載問題的求解方法 10
2.3 禁忌搜尋法的介紹 11
2.3.1 禁忌搜尋法的主要結構 11
2.3.2 啟發法求初始解的演算步驟 13
2.3.3 禁忌搜尋法的演算步驟 14
2.4 高頻項目集探勘的介紹與相關研究 17
第三章 問題描述 21
3.1 問題的複雜度 21
3.2 數學模型建構 22
第四章 研究方法與執行步驟 26
4.1 高頻項目集問題 26
4.2 最高權重作業及刀具指派問題 27
4.3 本研究方法 27
第五章 實驗設計與實驗結果 32
第六章 結論與建議 35
參考文獻 36
論文參考文獻:[1] 朱敦堅,工廠FMS化,全華科技圖書股份有限公司,1988,第1頁.
[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness: Freeman San Francisco, 1979.
[3] J. Han and M. Kamber, Data mining: concepts and techniques: Morgan Kaufmann, 2006, pp. 265-269.
[4] S. S. Hwang and J. G. Shanthikumar, An FMS production planning system and evaluation of part selection approaches: Produced and distributed by Center for Research in Management, University of California, Berkeley Business School, 1987.
[5] A. Atmani and R. S. Lashkari, "A model of machine-tool selection and operation allocation in FMS," International Journal of Production Research, vol. 36, pp. 1339-1349, 1998.
[6] J. J. Bernardo and Z. Mohamed, "The measurement and use of operational flexibility in the loading of flexible manufacturing systems," European Journal of Operational Research, vol. 60, pp. 144-155, 1992.
[7] M. Berrada and K. E. Stecke, "A branch and bound approach for machine load balancing in flexible manufacturing systems," Management Science, pp. 1316-1335, 1986.
[8] S. Bilgin and M. Azizoglu, "Capacity and tool allocation problem in flexible manufacturing systems," Journal of the Operational Research Society, vol. 57, pp. 670-681, 2006.
[9] S. Bilgin and M. Azizoglu, "Operation assignment and capacity allocation problem in automated manufacturing systems," Computers & Industrial Engineering, vol. 56, pp. 662-676, 2009.
[10] K. M. Bretthauer and M. A. Venkataramanan, "Machine loading and alternate routing in a flexible manufacturing system," Computers and Industrial Engineering, vol. 18, pp. 341-350, 1990.
[11] Y. J. Chen and R. G. Askin, "A multiobjective evaluation of flexible manufacturing system loading heuristics," International Journal of Production Research, vol. 28, pp. 895-911, 1990.
[12] I. J. Chen and C. H. Chung, "Effects of loading and routeing decisions on performance of flexible manufacturing systems," International Journal of Production Research, vol. 29, pp. 2209-2225, 1991.
[13] H. C. Co, J. S. Biermann, and S. K. Chen, "A methodical approach to the flexible-manufacturing-system batching, loading and tool configuration problems," International Journal of Production Research, vol. 28, pp. 2171-2186, 1990.
[14] T. H. D'Alfonso and J. A. Ventura, "Assignment of tools to machines in a flexible manufacturing system," European Journal of Operational Research, vol. 81, pp. 115-133, 1995.
[15] L. De Vecchi, G. Parola, T. Tolio, and Q. Semeraro, "TWM1: a system for integrated tool and workpiece management in FMSs—loading and part selection," CIRP-Journal of Manufacturing Systems, vol. 22, pp. 325–330, 1993.
[16] F. Glover, "Tabu search--part II," INFORMS Journal on Computing, vol. 2, p. 4, 1990.
[17] R. Grassi, A. Grieco, Q. Semeraro, and T. Tolio, "September 1995, Loading algorithm for FMSs provided with a tool transport system," Atti del II Convergo AITEM, Padova, Italy, pp. 291–300.
[18] A. Grieco, Q. Semeraro, and T. Tolio, "A review of different approaches to the FMS loading problem," International Journal of Flexible Manufacturing Systems, vol. 13, pp. 361-384, 2001.
[19] M. H. Han, Y. K. Na, and G. L. Hogg, "Real-time tool control and job dispatching in flexible manufacturing systems," International Journal of Production Research, vol. 27, pp. 1257-1267, 1989.
[20] J. Han, J. Pei, Y. Yin, and R. Mao, "Mining frequent patterns without candidate generation: A frequent-pattern tree approach," Data Mining and Knowledge Discovery, vol. 8, pp. 53-87, 2004.
[21] M. S. Hillier and M. L. Brandeau, "Optimal component assignment and board grouping in printed circuit board manufacturing," Operations Research, pp. 675-689, 1998.
[22] V. N. Hsu and R. De Matta, "An efficient heuristic approach to recognize the infeasibility of a loading problem," International Journal of Flexible Manufacturing Systems, vol. 9, pp. 31-50, 1997.
[23] S. S. Hwan and A. W. Shogan, "Modelling and solving an FMS part selection problem," International Journal of Production Research, vol. 27, pp. 1349-1366, 1989.
[24] H. Katayama, "FMS tool change schemes and their characteristics," Computers and Industrial Engineering, vol. 27, pp. 75-80, 1994.
[25] Y. D. Kim and C. A. Yano, "Heuristic approaches for loading problems in flexible manufacturing systems," IIE transactions, vol. 25, pp. 26-39, 1993.
[26] N. Kirkavak and C. Dincer, "Analytical loading models in flexible manufacturing systems," European Journal of Operational Research, vol. 71, pp. 17–31, 1993.
[27] H. Kuhn, "A heuristic algorithm for the loading problem in flexible manufacturing systems," International Journal of Flexible Manufacturing Systems, vol. 7, pp. 229-254, 1995.
[28] P. Kumar, N. K. Tewari, and N. Singh, "Joint consideration of grouping and loading problems in a flexible manufacturing system," International Journal of Production Research, vol. 28, pp. 1345-1356, 1990.
[29] N. Kumar and K. Shanker, "A genetic algorithm for FMS part type selection and machine loading," International Journal of Production Research, vol. 38, pp. 3861-3887, 2000.
[30] A. Kumar, M. K. Tiwari, R. Shankar, and A. Baveja, "Solving machine-loading problem of a flexible manufacturing system with constraint-based genetic algorithm," European Journal of Operational Research, vol. 175, pp. 1043-1069, 2006.
[31] A. Kusiak, "Flexible manufacturing systems: a structural approach," International Journal of Production Research, vol. 23, pp. 1057-1073, 1985.
[32] R. S. Lashkari, S. P. Dutta, and A. M. Padhye, "A new formulation of operation allocation problem in flexible manufacturing systems: mathematical modelling and computational experience," International Journal of Production Research, vol. 25, pp. 1267-1283, 1987.
[33] S. M. Lee and H. J. Jung, "A multi-objective production planning model in a flexible manufacturing environment," International Journal of Production Research, vol. 27, pp. 1981-1992, 1989.
[34] M. Liang and S. Taboun, "Part selection and part assignment in flexible manufacturing systems with cellular layout," Computers & Industrial Engineering, vol. 23, pp. 63-67, 1992.
[35] M. Liang and S. P. Dutta, "An integrated approach to the part selection and machine loading problem in a class of flexible manufacturing systems," European Journal of Operational Research, vol. 67, pp. 387-404, 1993.
[36] M. Liang, "Integrating machining speed, part selection and machine loading decisions in flexible manufacturing systems," Computers and Industrial Engineering, vol. 26, pp. 599-608, 1994.
[37] B. K. Modi and K. Shanker, "Models and solution approaches for part movement minimization and load balancing in FMS with machine, tool and process plan flexibilities," International Journal of Production Research, vol. 33, pp. 1791-1816, 1995.
[38] A. A. Moreno and F. Y. Ding, "Heuristics for the FMS-loading and part-type-selection problems," International Journal of Flexible Manufacturing Systems, vol. 5, pp. 287-300, 1993.
[39] S. K. Mukhopadhyay, S. Midha, and V. M. Krishna, "A heuristic procedure for loading problems in flexible manufacturing systems," International Journal of Production Research, vol. 30, pp. 2213-2228, 1992.
[40] S. K. Mukhopadhyay, M. K. Singh, and R. Srivastava, "FMS machine loading: a simulated annealing approach," International Journal of Production Research, vol. 36, pp. 1529-1547, 1998.
[41] S. Ozpeynirci and M. Azizoglu, "Beam search algorithm for capacity allocation problem in flexible manufacturing systems," Computers & Industrial Engineering, 2008.
[42] S. Ozpeynirci and M. Azizoglu, "Capacity allocation problem in flexible manufacturing systems: branch and bound based approaches," International Journal of Production Research, vol. 99999, pp. 1-18, 2008.
[43] S. Ozpeynirci and M. Azizoglu, "Bounding approaches for operation assignment and capacity allocation problem in flexible manufacturing systems," Computers and Operations Research, vol. 36, pp. 2531-2540, 2009.
[44] A. Prakash, N. Khilwani, M. K. Tiwari, and Y. Cohen, "Modified immune algorithm for job selection and operation allocation problem in flexible manufacturing systems," Advances in Engineering Software, vol. 39, pp. 219-232, 2008.
[45] B. Ram, S. Sarin, and C. S. Chen, "A model and a solution approach for the machine loading and tool allocation problem in a flexible manufacturing system," International Journal of Production Research, vol. 28, pp. 637-645, 1990.
[46] H. K. Roh and Y. D. Kim, "Due-date based loading and scheduling methods for a flexible manufacturing system with an automatic tool transporter," International Journal of Production Research, vol. 35, pp. 2989-3004, 1997.
[47] S. C. Sarin and C. S. Chen, "The machine loading and tool allocation problem in a flexible manufacturing system," International Journal of Production Research, vol. 25, pp. 1081-1094, 1987.
[48] T. Sawik, "Modelling and scheduling of a Flexible Manufacturing System," European Journal of Operational Research, vol. 45, pp. 177-190, 1990.
[49] T. Sawik, "Mixed Integer Programming for Scheduling Flexible Flow Lines with Limited Intermediate Buffers," Mathematical and Computer Modelling, vol. 31, pp. 39-52, 2000.
[50] K. Shanker and Y. J. J. Tzen, "A loading and dispatching problem in a random flexible manufacturing system," International Journal of Production Research, vol. 23, pp. 579-595, 1985.
[51] K. Shanker and A. Srinivasulu, "Some solution methodologies for loading problems in a flexible manufacturing system," International Journal of Production Research, vol. 27, pp. 1019-1034, 1989.
[52] M. S. Sodhi, R. G. Asking, and S. Sen, "Multi-period tool and production assignment in flexible manufacturing systems," International Journal of Production Research, vol. 32, pp. 1281-1294, 1994.
[53] M. S. Sodhi, A. Agnetis, and R. G. Askin, "Tool addition strategies for flexible manufacturing systems," International Journal of Flexible Manufacturing Systems, vol. 6, pp. 287-310, 1994.
[54] C. Y. Song, H. Hwang, and Y. D. Kim, "Heuristic algorithm for the tool movement policy in flexible manufacturing systems," Journal of manufacturing systems, vol. 14, pp. 160-168, 1995.
[55] B. Srivastava and W. H. Chen, "Part type selection problem in flexible manufacturing systems: tabu search algorithms," Annals of Operations Research, vol. 41, pp. 279-297, 1993.
[56] K. E. Stecke and J. J. Solberg, "Loading and control policies for a flexible manufacturing system," International Journal of Production Research, vol. 19, pp. 481-490, 1981.
[57] K. E. Stecke, "Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems," Management Science, pp. 273-288, 1983.
[58] K. E. Stecke, "A hierarchical approach to solving machine grouping and loading problems of flexible manufacturing systems," European Journal of Operational Research, vol. 24, pp. 369-378, 1986.
[59] K. E. Stecke, "Planning and scheduling approaches to operate a particular FMS," European Journal of Operational Research, vol. 61, pp. 273-291, 1992.
[60] M. K. Tiwari, B. H. Rika, N. K. V. Rthi, P. Jaggi, and S. K. Mukhopadhyay, "A heuristic solution approach to the machine loading problem of an FMS and its Petri net model," International Journal of Production Research, vol. 35, pp. 2269-2284, 1997.
[61] M. K. Tiwari and N. K. Vidyarthi, "Solving machine loading problems in a flexible manufacturing system using a genetic algorithm based heuristic approach," International Journal of Production Research, vol. 38, pp. 3357-3384, 2000.
[62] M. K. Tiwari and V. Allada, "Solving the machine-loading problem in a flexible manufacturing system using a combinatorial auction-based approach," International Journal of Production Research, vol. 42, pp. 1879-1893, 2004.
[63] M. K. Tiwari, S. Kumar, and R. Shankar, "Solving Part-Type Selection and Operation Allocation Problems in an FMS: An Approach Using Constraints-Based Fast Simulated Annealing Algorithm," IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A SYSTEMS AND HUMANS, vol. 36, p. 1170, 2006.
[64] D. Werra and M. Widmer, "Loading problems with tool management in flexible manufacturing systems: A few integer programming models," International Journal of Flexible Manufacturing Systems, vol. 3, pp. 71-82, 1991.
[65] J. M. Wilson, "An alternative formulation of the operation-allocation problem in flexible manufacturing systems," International Journal of Production Research, vol. 27, pp. 1405-1412, 1989.
[66] C. Wu, "Applying frequent itemset mining to identify a small itemset that satisfies a large percentage of orders in a warehouse," Computers and Operations Research, vol. 33, pp. 3161-3170, 2006.
[67] R. Agrawal and R. Srikant, "Fast algorithms for mining association rules," 1994, pp. 487–499.
[68] S. H. Chung and G. L. Doong, "A procedure to solve part mix and tool assignment problems in FMS," 1989, p. 111.
[69] B. M. Colosimo, C. Conti, A. Grieco, and T. Tolio, "FMS loading in presence of tool sharing," pp. 137–144.
[70] M. Liang, "Part selection, machine loading, and machining speed selection in flexible manufacturing systems," 1993, pp. 259-262.
[71] A. A. Moreno and F. Y. Ding, "Goal oriented heuristics for the FMS loading (and part type selection) problems," 1989, p. 105.
[72] S. Rajagopalan, "Formulation and heuristic solutions for parts grouping and tool loading in flexible manufacturing systems," 1986.
[73] K. Shanker and S. Rajamarthandau, "Loading problem in FMS: part movement minimization," 1989, p. 99.
[74] K. E. Stecke, I. Kim, and A. Michigan, "A flexible approach to implementing the short-term FMS planning function " 1986, p. 283.
論文全文使用權限:同意授權於2012-08-06起公開