現在位置首頁 > 博碩士論文 > 詳目
  • 同意授權
論文中文名稱:應用啟發式演算法求解彈性製造系統的機器負載問題 [以論文名稱查詢館藏系統]
論文英文名稱:A Heuristic Balancing Approach for Machine Loading Problem in Flexible Manufacturing Systems [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:資訊與運籌管理研究所
畢業學年度:100
出版年度:101
中文姓名:彭鈞暘
英文姓名:Jyun-Yang Peng
研究生學號:99938009
學位類別:碩士
語文別:中文
口試日期:2012-06-21
論文頁數:37
指導教授中文名:吳建文
口試委員中文名:盧宗成;杜壯
中文關鍵詞:彈性製造系統作業指派CPLEX啟發式演算法
英文關鍵詞:Flexible Manufacturing SystemsOperation AssignmentCPLEXHeuristic
論文中文摘要:彈性製造系統 ( Flexible Manufacturing Systems ; FMSs ) 是一種結合多台電腦數位控制 ( Computer Numerically Controlled ; CNC ) 機器、機器人及無人搬運車等裝置的全自動控制生產系統。彈性製造系統的重要性在於具有零工生產的彈性及流程生產的效率,可有效的處理大量各種不同的加工作業以滿足顧客需求的變化。
本研究假設每個作業只能指派給一台機器,當作業被指派至機器時全部的工作都必須完成,機器裝有執行作業所需的所有工具,目標是指派作業與所需的工具到CNC機器並同時滿足彈性製造系統的生產限制,如機器的工具空間及生產時間等,達成最大的作業權重。並加入了平衡機器工作量的限制,如此一來不僅能最大化生產量並可以讓機器負載更為順暢。採用CPLEX數學規劃的方法求得最佳解並提出啟發式演算法在合理的時間求得近似最佳解。
論文英文摘要:Flexible manufacturing systems ( FMSs ) are defined as collections of computer numerically controlled ( CNC ) machines and automated material handling mechanisms.
We assume that each operation can be allocated to only one machine. We aim to assign operations to machines and allocate machine capacities in order to maximize the total weights of completed operations. We introduce a workload balancing constraint. Our model not only maximizes the throughput but also tries to smooth machine loading.
We use the CPLEX mathematical programming method to find out the optimal solution and propose a heuristic approach to obtain a near optimal solution in a reasonable time. Experiments have been performed and the results will be shown.
論文目次:摘要 I
ABSTRACT II
誌謝 III
目錄 IV
表目錄 V
圖目錄 VI
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究限制 3
1.4 研究流程 3
第二章 文獻探討 5
2.1 作業指派及空間分配問題的相關研究 5
2.1.1 工作量平衡 6
2.1.2 工具決策 8
2.1.3 搬運裝置 10
2.2 禁忌搜尋法 11
2.3 分支界限法與集束搜尋法 12
第三章 問題描述與研究方法 14
3.1 問題描述及數學模型 14
3.2 啟發式演算法 16
第四章 實驗設計與結果 27
4.1 實驗設計 27
4.2 實驗結果 27
第五章 結論 30
參考文獻 31
論文參考文獻:[1] S. Bilgin and M. Azizoglu, “Operation assignment and capacity allocation problem in automated manufacturing systems”, Computers & Industrial Engineering, vol. 56, pp. 662-676, 2009.
[2] S. Bilgin 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.
[3] L. J. Zeballos, “A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems”, Robotics and Computer-Integrated Manufacturing, vol 26, pp. 725-743, 2010.
[4] K. E. Stecke, “Formulation and solution at non linear integer production planning problem for flexible manufacturing system”, Management Science, vol. 29, pp. 273-288, 1983.
[5] S. S. Hwan and A. W. Shogan, “Modeling and solving an FMS part selection problem”, International Journal of Production Research, vol. 27, pp. 1349-1366, 1989.
[6] 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, vol. 36, pp. 1170-1184, 2006.
[7] 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.
[8] 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.
[9] L.B. Toktay and R. Uzsoy, “A capacity allocation problem with integer side constraints”, European Journal of Operational Research, vol. 109, pp. 170-182, 1998.
[10] E. Akcal, A. Ungor and R. Uzsoy, “Short-term capacity allocation problem with tool and setup constraints”, Naval Research Logistics, vol. 52, pp. 754-764, 2005.
[11] 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.
[12] B. Catay, S. S. Erenguc and A. J. Vakharta, “Capacity allocation with machine duplication in semiconductor manufacturing”, Naval Research Logistics, vol. 52, pp. 659-669, 2005.
[13] K. Shanker and Ya-Juei J. Tzen, “A loading and dispatching problem in a random flexible manufacturing system”, International Journal of Production Research, vol. 23, pp. 575-595, 1985.
[14] R. Swarnkar and M. K. Tiwari, “Modeling machine loading problem of FMSs and its solution methodology using a hybrid tabu search and simulated annealing-based heuristic approach”, Robotics and Computer-Integrated Manufacturing, vol. 20, pp. 199-209, 2003.
[15] J. A. Ventura, F. F. Chen and M. S. Leonard, “Loading tools to machines in flexible manufacturing systems”, Computers and Industrial Engineering, vol. 15, pp. 223-230, 1988.
[16] M. Berrada and K. E. Stecke, “A branch and bound approach for machine load balancing in flexible manufacturing systems”, Management Science, vol. 32, pp. 1316-1335, 1986.
[17] 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.
[18] Y. D. Kim, G. C. Lee, S. K. Lim and S. K. Choi, “Tool requirements planning in a flexible manufacturing system: minimizing tool costs subject to a makespan constraint”, International Journal of Production Research, vol. 41, pp. 3339-3357, 2003.
[19] 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.
[20] 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.
[21] S. Bilgin and M. Azizoglu, “Capacity allocation problem in flexible manufacturing systems: branch and bound based approaches”, International Journal of Production Research, vol. 47, pp. 5941-5958, 2009.
[22] S. Bilgin and M. Azizoglu, “Beam search algorithm for capacity allocation problem in flexible manufacturing systems”, Computers & Industrial Engineering, vol. 56, pp. 1464-1473, 2009.
[23] M. B. Teitz and P. Bart, “Heuristic methods for estimating the generalized vertex median of a weighted graph”, Operations Research, vol. 16, pp. 955-961, 1968.
[24] K. E. Rosing and C. S. ReVelle, “Heuristic concentration: two stage solution construction”, European Journal of Operational Research, vol. 97, pp. 75-86, 1997.
[25] K. E. Rosing, C. S. ReVelle and D. A. Schilling, “A gamma heuristic for the p-median problem”, European Journal of Operational Research, vol. 117, pp. 522-532, 1999.
[26] Y.-D. Kim, “A study on surrogate objectives for loading a certain type of flexible manufacturing systems”, International Journal of Production Research, vol. 31, pp. 381-392, 1993.
[27] N. Kumer and K. Shanker, “Comparing the effectiveness of workload balancing objectives in FMS loading”, International Journal of Production Research, vol. 39, pp. 843-871, 2001.
[28] N. Kirkavak and C. Dincer, “Analytical loading models in flexible manufacturing systems”, European Journal of Operational Research, vol. 71, pp. 17-31, 1993.
[29] M. S. Sodhi, A. Agnetis and R. G. Askin, “Tool addition strategies for flexible manufacturing systems”, International Journal of Flexible Manufacturing Systems, vo. 6, pp. 287-310.
[30] Y.-J. Chen and R. G. Askin, “A multi-objective evaluation of flexible manufacturing system loading heuristics.” International Journal of Production Research, vol. 28, pp. 895-911, 1990.
[31] 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.
[32] F. Guerrero, “Machine loading and part type selection in flexible manufacturing systems”, International Journal of Production Research, vol. 37, 1999.
[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, 1989.
[34] S. Y. Jang, J. Park and N. Park, “An integrated decision support system for FMS production planning and scheduling problems”, International Journal of Advanced Manufacturing Technology, vol. 11, 1996.
[35] K. Shanker and N. Kumar, “Solving FMS loading problem with genetic algorithm: a strategy for solution generation and recombination”, Proceedings of the 4th International Conference on Computer Integrated Manufacturing, pp. 472-483, 1997.
[36] 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.
[37] P. Kumer, 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.
[38] M. Liang and S. P. Dutta, “Combined part selection, load sharing and machine loading problem in hybrid manufacturing systems”, International Journal of Production Research, vol. 30, pp. 2335-2349, 1992.
[39] H. C. Co, “Streamlining material flow in flexible manufacturing systems: a lesson in simplicity”, International Journal of Production Research, vol. 30, pp. 1483-1499.
[40] J. C. Irastorza and R. H. Deaneb, “A loading and balancing methodology for job shop control”, A I I E Transactions, vol. 6, pp. 302-307, 1974.
[41] C. Arbib, M. Lucertini and F. Nicolo, “Workload balance and part-transfer minimization in flexible manufacturing systems”, International Journal of Flexible Manufacturing Systems, vol. 3, pp. 5-25, 1990.
[42] T. Sawik, “Modelling and scheduling of a FMS”, European Journal of Operational Research, vol. 45, pp. 85-95, 1990.
[43] J. M. Wilson, “Approaches to machine load balancing in flexible manufacturing systems”, Journal of Operational Research Society, vol. 43, pp. 415-423, 1992.
[44] N. Singh, Y. P. Aneja and S. P. Rana, “A bicriterion framework for operations assignment and routing flexibility analysis in cellular manufacturing systems”, European Journal of Operational Research, vol. 60, pp. 200-210, 1992.
[45] M. Liang and S. P. Dutta, “An integrated approach to the part selection and machine loading problem in a class of FMSs”, European Journal of Operational Research, vol. 67, pp. 387-404, 1993.
[46] 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.
[47] 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.
[48] P. Wu, “A case study in FMS production planning and dispatching”, International Journal of Flexible Manufacturing Systems, vol. 7, pp. 361-372, 1995.
[49] K. Bhaskar and G. Srinivasan, ”Static and dynamic operator allocation problems in cellular manufacturing systems”, International Journal of Production Research, vol. 35, pp. 3467-3482, 1997.
[50] V. 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.
[51] A. A. Moreno and Fong-Yuen Ding, “Heuristics for the FMS-loading and part-type-selection”, International Journal of Flexible Manufacturing Systems, vol. 5, pp. 287-300, 1993.
[52] 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.
[53] M. K. Tiwari, B. Haza Rika, N.K. Vidya 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.
[54] J.G. Shanthikumar and K. E. Stecke, “Reducing work-in-process inventory in certain classes of flexible manufacturing systems”, European Journal of Operational Research , vol. 26, pp. 266-271, 1986.
[55] D. D. Yao and S. C. Kim, “Reducing the congestion in a class of job shops”, Management Science, vol. 33, pp. 1165-1172, 1987.
[56] Y.-D. Kim and C.A. Yano, “Impact of throughput-based objectives and machine grouping decisions on the short-term performance of flexible manufacturing systems”, International Journal of Production Research, vol. 35, pp. 3303-3322, 1997.
[57] M. Liang and S. P. Dutt, “A mixed-integer programming approach to the machine loading and process planning problem in a process layout environment”, International Journal of Production Research, vol. 28, pp. 1471-1484, 1990.
[58] Zhi-Long Chen, “Simultaneous job scheduling and resource allocation on parallel machines”, Annals of Operations Research, vol. 129, pp. 135-153, 2004.
[59] K. E. Stecke, “Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems”, Management Science, vol. 29, pp. 273-288, 1993.
[60] L. C. Leung, S. K. Maheshwari and W. A. Miller, “Concurrent part assignment and tool allocation in FMS with material handling considerations”, International Journal of Production Research, vol. 31, pp. 117-138, 1993.
[61] W. L. Pearn, S. H. Chung and M. H. Yang, “A case study on the wafer probing scheduling problem”, Production Planning & Control: The Management of Operations, vol. 13, pp. 66-75, 2002.
[62] Yeong-Dae Kim and C. Arai Yano, “A new branch and bound algorithm for loading problem in flexible manufacturing systems”, International Journal of Flexible Manufacturing Systems, vol. 6, pp. 361-381, 1994.
[63] S. Rajakumar, V. P. Arunachalam and V. Selladurai, “Workflow balancing strategies in parallel machine scheduling”, The International Journal of Advanced Manufacturing Technology, vol. 23, pp. 366-374, 2004.
[64] 林載添,應用高繁項目集探勘求解彈性製造系統中的作業指派及空間分配問題,碩士論文,國立臺北科技大學工業工程與管理研究所,台北,2009。
論文全文使用權限:同意授權於2017-08-01起公開