刀模裁切是一種常見於製造業卷料加工的製程，可連續產出預定外型之產品。然而具角度限制之光學膜產品，由於刀模內的圖形須以特定角度排列，據我們所知，目前尚無可求解最佳化刀模設計的方法。
本研究以數學規劃和萬用啟發式演算法分別建構混合整數規劃模型和粒子群演算法模型，求解具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.

英文文獻
[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.