進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-1402201700355300
論文名稱(中文) 利用數學規劃與萬用啟發式演算法最佳化角度限制產品之刀模設計
論文名稱(英文) Using Mathematical Programming and Meta-heuristic Methods to Optimize the Design of Die-cuts for Angle Constrained Product
校院名稱 成功大學
系所名稱(中) 工程管理碩士在職專班
系所名稱(英) Institute of Engineering Management (on the job class)
學年度 105
學期 1
出版年 106
研究生(中文) 陳偉欽
研究生(英文) Wei-Chin Chen
電子信箱 sizemore.c.w.c@gmail.com
學號 N07021033
學位類別 碩士
語文別 中文
論文頁數 52頁
口試委員 口試委員-李汪洋
指導教授-李家岩
口試委員-張秀雲
口試委員-舒宇宸
中文關鍵字 刀模裁切  角度限制產品  混合整數規劃  粒子群演算法 
英文關鍵字 die-cutting  angle constrained product  mixed integer programming  particle swarrm optimization 
學科別分類
中文摘要 刀模裁切是一種常見於製造業卷料加工的製程,可連續產出預定外型之產品。然而具角度限制之光學膜產品,由於刀模內的圖形須以特定角度排列,據我們所知,目前尚無可求解最佳化刀模設計的方法。
本研究以數學規劃和萬用啟發式演算法分別建構混合整數規劃模型和粒子群演算法模型,求解具6片矩形及具12片矩形之刀模,並與人工排列之結果比較,作為模型驗證。發現混合整數規劃模型於二個刀模均可產生較佳之結果,分別可提升3.41和1.2的利用率;而粒子群演算法模型於具6片矩形之刀模可產生近似於人工排列的結果,惟在有限時間內無法求得具12片矩形之刀模之較佳解。
驗證結果證明本研究所建構之模型應用於刀模設計之可行性,未來可將其導入實務使用,輔助人工排列刀模。可望藉由減少浪費或降低成本,進而提升產業競爭力。
英文摘要 Die-cutting is a common process of reel processing in the manufacturing industry, and it can continuously generate products with pre-determined shapes. Currently, to the best of our knowledge, there are no methods to optimize the design of die-cuts for angle constrained optical film products; in particular, the units in the die-cuts must be arranged in a specific angle.
In this study, a mixed integer programming (MIP) and a particle swarm optimization (PSO) algorithm are proposed by using mathematical programming technique and meta-heuristic algorithm respectively. In order to verify the models, an empirical study of Taiwan’s display manufacturers is conducted to solve the die-cuts with 6 rectangles and 12 rectangles, and compare with the results of the existing artificial arrangements. It is found that the mixed integer programming model can produce better results in the two die-cuts examples, which can increase the utilization rate of 3.41% and 1.2%, respectively; and the particle swarm algorithm model can produce a result which is similar to the result of the artificial arrangement in the die-cut with 6 rectangles. But there is no better solution to the die-cut with 12 rectangles in a limited time spent.
The results show that the models constructed in this study are feasible to design die-cuts, and can be used for practical implement in the near future. It is expected to reduce waste and save costs, and thus enhance the industrial core competence.
論文目次 目錄
摘要 I
Extended Abstract II
誌謝 V
目錄 VI
圖目錄 VIII
表目錄 X
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與限制 2
1.4 研究流程 3
1.5 論文架構 4
第二章 文獻探討 5
2.1 切割問題 5
2.2 數學規劃 8
2.3 萬用啟發式演算法 11
2.4 小結 14
第三章 模型建構 15
3.1 定義刀模設計問題 15
3.2 混合整數規劃 18
3.3 粒子群演算法 23
第四章 實例驗證 28
4.1 產品介紹 28
4.2 模型求解 30
4.3 綜合比較 44
第五章 結論與未來研究方向 46
5.1 結論 46
5.2 未來研究方向 47
參考文獻 48
參考文獻 英文文獻
[1] Allaoua, B., Laoufi, A., Gasbaoui, B. & Abderrahmani, A. (2009), “Neuro-fuzzy DC motor speed control using particle swarm optimization,” Leonardo Electronic Journal of Practices and Technologies, 15 pp.1–18.
[2] Beasley, J., E. (1985), “Algorithms for Unconstrained Two-Dimensional Guillotine Cutting,” The Journal of the Operational Research Society, 36 (4) pp.297-306.
[3] Birattari, M., Paquete, L., Stützle, T. & Varrentrapp, K. (2001) Classification of Metaheuristics and Design of Experiments for the Analysis of Components, Technical Report AIDA-01-05, FG Intellektik, FB Informatik, Technische Universität Darmstadt, Darmstadt, Germany.
[4] Bratton, D. & Kennedy, J. (2007), “Defining a Standard for Particle Swarm Optimization,” IEEE Swarm Intelligence Symposium, pp.120-127.
[5] Clerc, M. & Kennedy, J. (2002), “The particle swarm—Explosion, stability, and
convergence in a multi-dimensional complex space,” IEEE Transactions on Evolutionary Computation, 6 (1) pp. 58–73.
[6] Dyckhoff, H. (1990), “A typology of cutting and packing problems,” European Journal Operational Research, 44 (2) pp.145-159.
[7] Floudas, C., A., Pardalos, P., M., Adjiman, C., S., Esposito, W., R., Gümüs, Z., H., Harding, S., T., Klepeis, J., L., Meyer, J., L. & Schweiger, C., A. (1999), Handbook of Test Problems in Local and Global Optimization, Dordrecht: Kluwer Academic Publishers.
[8] Gilmore, P., C. & Gomory, R., E. (1961), “A Linear Programming Approach to the Cutting-Stock Problem,” Operations Research, 9 (6) pp.849-859.
[9] Gilmore, P., C. & Gomory, R., E. (1963), “A Linear Programming Approach to the Cutting-Stock Problem-Part II,” Operations Research, 11 (6) pp.863-888.
[10] Gilmore, P., C. & Gomory, R., E. (1965), “Multistage Cutting Stock Problems of Two and More Dimensions,” Operations Research, 13 (1) pp.94-120.
[11] Goulimis, C. (1990), “Optimal solution for the cutting stock problem,” European Journal of Operational Research, 44 (2) pp.197-208.
[12] Harjunkoshi, I., Westerlund, T., Pörn, R. & Skrifvars, H. (1998), “Different transformations for solving non-convex trim-loss problems by MINLP,” European Journal of Operational Research, 105 (3) pp.594-603.
[13] Hinxman, A., I. (1980), “The trim-loss and assortment problems: A survey,” European Journal of Operational Research, 5 (1) pp.8-18.
[14] Hopper, E. & Turton, B., C., H. (2001), “An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem,” European Journal of Operational Research, 128 (1) pp.34-57.
[15] Karelahti, J. (2002) Solving the cutting stock problem in the steel industry, Unpublished Master Thesis, Department of Engineering Physics and Mathematics, Helsinki university of technology.
[16] Kennedy, J. & Eberhart, R., C. (1995), “Particle swarm optimization”, Proceedings of the IEEE International Conference on Neural Networks, 4 pp.1942-1948.
[17] Kennedy, J., Eberhart, R., C. & Shi, Y. (2001), Swarm Intelligence,
San Francisco, CA: Morgan Kaufmann Publishers.
[18] Li, H.L., Chang, C.T. & Tsai, J.F. (2002), “Approximately global optimization for assortment problems using piecewise linearization techniques,” European Journal of Operational Research, 140 (3) pp.584-589.
[19] Li, H.L., Huang, Y.H. & Fang, S.C. (2012), “A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment Problems,” Informs Journal on Computing, 25 (4) pp.643-653.
[20] Liu, D.S., Tan, K.C., Huang, S.Y., Goh, C.K. & Ho, W.K. (2008), “On solving multiobjective bin packing problems using evolutionary particle swarm optimization,” European Journal of Operational Research, 190 (2) pp.357-382.
[21] Lodi, A., Martello, S. & Vigo, D. (1999), “Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problem,” INFORMS Journal on Computing, 11 (4) pp.345-357.
[22] Lu, H.C., Ko, Y.C. & Yao, H.H. (2014), “A note on “Reducing the number of binary variables in cutting stock problems”, Optimization Letters, 8 (2) pp.569-579.
[23] Suliman, S., M., A. (2006), “A sequential heuristic procedure for the two-dimensional cutting-stock problem,” International Journal of Production Economics, 99 (1-2) pp.177-185.
[24] Vaessens, R., J., M., Aarts, E., H., L. & Lenstra, J., K. (1998), “A local search template,” Computer Science and Operations Research, 25 (11) pp.969-979.
[25] Vielma, J., P. (2015), “Mixed integer linear programming formulation techniques,” Society for Industrial and Applied Mathematics, 57 (1) pp.3-57.
[26] Wäscher, G., Haußner, H. & Schumann, H. (2007), “An improved typology of cutting and packing problems,” European Journal of Operational Research, 183 (3) pp.1109-1130.
[27] Yang, C.H. (2009) An Algorithm for Unconstrained Two-dimensional Guillotine Cutting Stock Problem with Defects, Unpublished Master Thesis, Department of Business Administration, National Chung Cheng University.
中文文獻
[28] 王祥安(2011),「利用線性規劃法求解LCD光學膜切割問題」,國立成功大學工業與資訊管理學系專班碩士論文。
[29] 方柏棟(2013),「整數規劃與資料挖掘於最佳裁切方式之應用」,東海大學工業工程與經營資訊學系碩士論文。
[30] 李東峻(2012),「造紙業原料切割問題之最佳化系統」,實踐大學資訊科技與管理學系碩士班碩士論文。
[31] 吳東儒(2012),「偏光板裁切計畫之編排研究」,國立成功大學工程科學系專班碩士論文。
[32] 徐劭逸(2010),「二維不規則排版問題之船廠案例探討研究」,國立臺灣海洋大學系統工程暨造船學系碩士論文。
[33] 張瑞玫(2006),「線性多目標規劃應用於配置及裝箱問題」,國立暨南國際大學資訊管理學系碩士論文。
[34] 劉育青(2010),「利用數學規劃及啟發式演算法求解角度限制產品的裁切問題」,國立成功大學工業與資訊管理學系專班碩士論文。
網頁文獻
[35] ROSE Analytics, “Simplex Method”, http://roseanalytics.com/linear-programming/ Accessed by January 7, 2017.
[36] William Cook (2004), “Branch-and-Cut Tree”, http://www.math.uwaterloo.ca/tsp/sweden/compute/compute.htm Accessed by January 7, 2017.
[37] Jiayue He et al. (2010), “Design for Optimizability: Traffic Management of a Future Internet”, https://www.researchgate.net/figure/226717592_fig4_Fig-5-Convex-and-nonconvex-functions-A-function-g-is-a-convex-function-if-domain-of-g Accessed by January 7, 2017.
[38] Eric Rowell, “Big-O Complexity Chart”, http://bigocheatsheet.com/ Accessed by January 7, 2017.
[39] IMS (Intelligent Manufacturing Systems) lecture slide (2013), “Exploitation vs. Exploration”.
[40] http://www.leandro-coelho.com/linearization-product-variables/ Accessed by September 19, 2016.
[41] Jonathan Becker (2013), “PSO example with two non-equal minima”, http://wirelesstechthoughts.blogspot.tw/2013/06/an-introduction-to-particle-swarm.html Accessed by January 7, 2017.
[42] https://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiLypm686XRAhUBvZQKHZ74BskQFggaMAA&url=http%3A%2F%2Fwww.fico.com%2Fen%2Fnode%2F8140%3Ffile%3D5125&usg=AFQjCNGIL6T4f3WaKyw46y1it_xVBgCBww&sig2=BK_rnd9ObGt7sjGMG2qUzA Accessed by September 19, 2016.
[43] http://m.jiemian.com/article/575922_yidian.html Accessed by January 3, 2017.
[44] https://zh.wikipedia.org/wiki/%E6%B6%B2%E6%99%B6%E6%98%BE%E7%A4%BA%E5%99%A8 Accessed by January 3, 2017.
[45] 2016 顯示器產業年鑑 - ITIS智網 Accessed by January 3, 2017.
[46] http://www.cmmt.com.tw/product.asp Accessed by January 3, 2017.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2021-09-01起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2021-09-01起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw