本研究主要探討二維平面的切割問題，此問題已被廣泛應用在面板業、玻璃業、布料業等產業，以有效使用原物料並提昇產品的競爭力。雖然過去有許多相關的文獻提出各種不同的方法來解決此問題，但所提出的方法求解品質不佳或求解速度慢。本研究運用確定性最佳化模式求解二維平面切割問題，可求得全域最佳解，本研究進一步將模式中的0-1變數減少，以加快求解時間，增加運算效率。本研究也探討不同規格原物料情況下的切割問題，運用數學模型求出最適生產規劃，進行多個原物料的切割，相較於過去只能進行單一原物料的切割，讓成本最小，原物料使用最精簡，可有效地協助企業創造利潤並提昇產品的競爭力，幾個案例也會提出來驗證所提出方法的正確性與實用性。

This study investigates the two-dimensional cutting stock problems. This issue has been widely addressed in the panel industry, glass industry, cloth industry and other industries, to effectively reduce the use of materials and enhance the competitiveness of the products. Although various approaches have been presented to solve this problem in many works, but they cannot guarantee to find a global solution or the solution process is too time-consuming. This study proposes a deterministic optimization model to solve the problem to find a global optimal solution. Moreover, this study reduces the binary variables of the original model to increase the computational efficiency. The proposed model also considers the cutting stock problem with different sizes of raw materials. Solving the formulated model, we can obtain the best production plan with lowest cost and optimize the utilization of the raw materials. The obtained results can help the company to create profits and enhance competitiveness of their products. Some cases are also presented to demonstrate the effectiveness and usefulness of the proposed method.

目　錄

摘　要 i
ABSTRACT ii
目　錄 vi
表目錄 viii
圖目錄 ix
第一章　緒論 1
1.1 研究背景與動機 1
1.2 研究目的 4
1.3 研究架構 5
第二章　文獻探討 6
2.1原物料切割問題 6
2.1.1平面原物料切割問題 7
2.2最佳化演算法 9
2.2.1確定性方法 9
2.2.2 啟發式演算法 10
2.2.3整數規劃 12
第三章　研究方法 14
3.1 模型概念 14
3.2 不同原物料大小之二維切割模型 15
3.3改良之特殊序列集合第一型 19
3.3.1特殊序列集合第一型之限制式 19
3.3.2 特殊序列集合第一型之限制式簡化 21
3.4啟發式演算法 23
3.4.1 模型概念 23
3.4.2模型定義 23
3.4.3模型內容 23
第四章　範例應用 26
4.1 鋼板切割範例 26
4.1.1啟發式演算法應用 26
4.1.2最佳化數學模型應用 34
4.1.3 結果比較 37
4.2面板切割範例 38
4.2.1最佳化數學模型應用 39
4.2.2結果比較 43
第五章　結論與建議 44
5.1結論 44
5.2未來建議 45
參考文獻 46

英文部分
[1] Ahmet,C. D., Baris, B., “A Generalized Approach to the Solution of One-Dimensional Stock-Cutting Problem for Small Shipyards”, Journal of Marine Science and Technology,2011, Volume:19, pp.368-376.
[2] Anderson, D., An introduction to management science, 2011,pp.315-321.
[3] Andrea, L., Michele, M. , “Integer linear programming models for 2-staged two-dimensional knapsack problems”, Mathematical Programming,2003, Volume:94,pp.257-278.
[4] Beasley, J. E., “An algorithm for the two-dimensional assortment problem,” European Journal of Operational Research, 1985, Volume: 19, pp.253-261.
[5] Beasley, J. E., “A population heuristic for constrained two-dimensional non-guillotine cutting,” European Journal of Operational Research, 2004, Volume: 156, pp.601-627.
[6] Blazewicz, J., Drozdowski, M. , Soniewicki , B., and Walkowiak, R., “Two-Dimensional Cutting Problem: Basis Complexity Results and Algorithms for Irrrgular Shapes.”, Foundations of Control Engineering,1989, Volume:14, pp.137-160.
[7] Chang, P. C. and Hsieh, J. C., “An investigation of paper cutting problem by dynamic programming and heuristic approaches,” Journal of the Chinese Institute of Industrial Engineers, 2005, Volume: 22, pp.463-472.
[8] Chen, C.S., Sarin, S. and Balasubramanian, R., “A mixed-Integer programming model for a class of assortment problems,” European Journal of Operational Research, 1993, Volume:63, pp.362-367.
[9] Cui, Y., Zhao, X., Yang, Y. and Yu, P., “A heuristic for the one-dimensional cutting stock problem with pattern reduction,” Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2008, Volume: 222, pp.677-685.
[10] Dyckhoff, H. and Gal, H. K. A., “Trim loss and related problems,” Omega, 1985,Volume: 13, pp.59-72.
[11] Dyckhoff, H., “A typology of cutting and packing problems,” European Journal of Operational Research, 1990, Volume: 44, pp.145-159.
[12] Gradisar, M. and Trkman, P., “A combined approach to the solution to the general one-dimensional cutting stock problem,” Computers & Operations Research, 2005, Volume: 32, pp.1793-1807.
[13] G, Y.G. and Kang, M.K., “A fast algorithm for two-dimensional palletloading problems of large size”, European Journal of Operational Research, 2001, Volume:134, 193-202.
[14] Gilmore , P. C., Gomory , R. E. , “A linear Programming Approach to the Cutting-Stock Problem”, Operations Research, 1961,Volume:9,pp.849-859.
[15] Holthaus, O., “Decomposition approaches for solving the integer one dimensional cutting stock problem with different types of standard lengths,” European Journal of Operational Research, 2002, Volume: 141, pp.295-312.
[16] Ismail, H. S., and Hon, K. K. B. ,“The nesting of two-dimensional shapes using
genetic algorithms,” Proceedings of the Institution of Mechanical Engineers. Part
B: Journal of Engineering Manufacture, 1995 , Volume:209, pp.115-124.
[17] Leung, T. W., C. K. Chan and D. M. Troutt, “Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem.”,European Journal of Operational Research, 2003,Volume:145, pp.530-542.
[18] Li, H. L. and Chang, C. T., “An approximately global optimization method for assortment problems,” European Journal of Operational Research, 1998, Volume: 105, pp.604-612.
[19] Lu, H.C., Huang ,Y.H., Kuo-An Tseng “An integrated algorithm for cutting stock problems in the thin-film transistor liquid crystal display industry”, Computers & Industrial Engineering journal,2013, Volume:64, pp.1084-1092.
[20] Lu , H.C. , Ko, Y. C., Yao, H.H.“A note on “Reducing the number of binary variables in cutting stock problems”, Optimization Letters,2014, Volume 8, pp.569-579.
[21] Mauro, D. A., José, C.D.D., Manuel, I.,“The Bin Packing Problem with Precedence Constraints”, Operations Research,2012, Volume:60, pp.1491-1504.
[22] Miro, G., Peter, T., “A combined approach to the solution to the general one-dimensional cutting stock problem”,2005, Computers & operations research, Volume:32,pp.1793-1807.
[23] Rode, M., Rosenberg, O., “An analysis of heuristic trim-loss algorithms”, Engineering Costs and Production Economics, 1987,Volume:12, pp.71-78.
[24] Silva, E., Alvelos, F., J.M. Valerio de Carvalho, “An integer programming model for two- and three-stage two-dimensional cutting stock problems” European Journal of Operational Research 205 ,2010,pp. 699-708
[25] Suliman, S.M. A., “Pattern generating procedure for the cutting stock problem,” International Journal Production Economics, 2001, Volume: 74, pp.293-301.
[26] Tsai, J. F., Hsieh, P. L. and Huang, Y. H. , “An optimization algorithm for
cutting stock problems in the TFT-LCD industry,” Computers and Industrial
Engineering, 2009, Volume:57, pp.913-919
[27] Tülin, A., RIfat, G. Ö., “An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing”, European Journal of Operational Research, 2009, Volume:196, pp.737-743.
[28] Umetani, S.,Yagiura, M. and Ibaraki, T., “One-dimensional cutting stock problem to minimize the number of different patterns,” European Journal of Operational Research, 2003, Volume: 146, pp.388-402.
[29] Viswanathan, K. V. and Bagchi, A., “Best-first search methods for constrained
two-dimensional cutting stock problems,” Operations Research, 1993,Volume: 41, pp.768-776.
[30] Wang, P.Y., “Two algorithms for constrained two-dimensional cutting stock
problems,” Operations Research,1983,Volume:3l, pp.573-586.
[31] Wäscher,G., Haußner,H. and Schumann,H., “An improved typology of cutting and packing problems,” European Journal of Operational Research, 2007, Volume:183, pp.1109-1130.
[32] Wang, X.Q., Huang, L., Cui, Y.D.,“Using Layer Patterns in Solving the Two-Dimensional Cutting Stock Problem”, International Journal of Information and Management Sciences,2011, Volume:22(2) , pp.189-200.

中文部分
[1]方柏棟，2013，整數規劃與資料挖掘於最佳裁切方式之應用，東海大學工業工程與
經營資訊學系碩士論文，台中。
[2]楊靖航，2011，限制條件下的二維切割問題之確定性演算法，明志科技大學工業工程與管理研究所碩士論文，新北。
[3]李英碩，2007，客服中心人員排班問題之整數規劃，國立清華大學碩士論文，新竹。
[4]廖麗滿,顧維鈞，2013，結合二元整數規劃模式與二分搜尋法求解混合型裝配線平衡問題研究，創新與經營管理學刊，第1-13頁。
[5]林潔婷，2008，以多目標整數規劃進行污水下水道用戶接管工程作業排程之研究，國立高雄第一科技大學，高雄。