臺灣博碩士論文加值系統

二維矩形原料切割問題是屬於一種困難度極高的組合最佳化問題，它是將預先備好的矩形原料切割出滿足需求規格的矩形物件，使所產生的殘廢料最少。由於此類問題的結構複雜，並會隨著問題的規模增加，使解題時間呈現指數遞增之情形。在實務應用上，原料利用率一直是切割產業營運的重要指標之一，故如何在滿足需求物件的需求數量要求下，使用最少量的原料物件總數產生切割計畫，已成為切割產業相當重視的課題。本研究建構一個適用於二維矩形原料裁切樣式最佳化的整數非線性規劃模式，搭配分支界限法，求得在滿足所有需求物件的狀態下，使用最少的原料物件。經由LINGO 11.0演算結果顯示，本研究建構的整數非線性規劃模式可以快速的執行完演算過程，利用最少的原料物件數量切割出完整的需求物件數量，且能夠準確的找尋出需求物件的中心置放於原料物件的位置座標，以方便裁切加工。

The two-dimensional cutting stock problem consists of cutting a rectangular plate into specified smaller rectangular pieces, so that the objective function is optimized. This problem is also classified as NP-hard. In practical, raw material utilization has always been an important factor for the cutting industry, therefore, efficient use of the minimum quantity of raw plate in cutting while meet the requirements of the smaller pieces has become more important. In this research, we have developed an integer nonlinear programming formulation for optimizing the layout of the smaller pieces on the raw plate while the required quantity for the raw plate is minimized. Test problems have been optimally solved by a branch and bound method in LINGO solver. The results show that our formulation outperformed others in getting the optimal solution, also can provide the exact coordinates for the smaller pieces on the raw plates in order to cut the plates with ease.

明志科技大學碩士學位論文指導教授推薦書..........i
明志科技大學碩士學位論文口試委員會審定書........ii
明志科技大學學位論文授權書....................iii
誌 謝......................................iv
摘 要.......................................v
ABSTRACT...................................vi
目 錄.....................................vii
表目錄......................................ix
圖目錄.......................................x
第一章 緒論.................................1
1.1 研究背景與動機........................1
1.2 研究目的.............................1
1.3 切割問題簡介..........................2
1.4 分支界限法簡介........................4
1.5 研究流程與架構........................7
第二章 文獻探討.............................9
2.1 二維矩形切割問題......................9
2.2 二維切割問題之確定性求解方法...........11
2.2.1 整數規劃法...........................12
2.2.2 動態規劃法...........................14
2.2.3 非線性模式線性化求解..................15
2.3 二維切割問題之啟發式演算法.............15
第三章 數學規劃模式.........................18
3.1 問題描述.............................18
3.2 參數及變數定義........................20
3.3 求解基本概念.........................23
3.4 模式建構.............................28
第四章 範例及分析...........................34
4.1 測試範例一...........................34
4.2 測試範例二...........................36
4.3 測試範例三...........................39
4.4 測試範例四...........................42
第五章 結論與建議...........................46
5.1 結論................................46
5.2 建議................................46
參考文獻.....................................48
附錄........................................52
附錄A：LINGO程式碼 *.lg4.....................52

中文部份
張美忠 (1992) 。「貨物運輸棧板裝載問題啟發式解法之應用」。交通大學 土木工程研究所 碩士論文。
楊國隆、熊高生 (2009) 。作業研究入門導引－使用LINGO。台北市：文魁資訊股份有限公司。
廖慶榮 (1994) 。作業研究。台北市：三民書局股份有限公司。

英文部分
Babu, A. R. and Babu, N. R. (1999) “Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms,” International Journal of Production Research, 37, pp.1625-1643.
Beasley, J. E. (1985) “Algorithms for unconstrained two-dimensional guillotine cutting,” Journal of the Operational Research Society, 36, pp.297–306.
Beasley, J. E. (1985) “An exact two-dimensional non-guillotine cutting tree search procedure,” Operations Research, 33, pp.49-64.
Beasley, J. E. (2004) “A population heuristic for constrained two-dimensional non-guillotine cutting,” European Journal of Operational Research, 156, pp.601-627.
Chen, C. S., Sarin, S. and Balasubramanian, R. (1993) “A mixed-integer programming model for a class of assortment problems,” European Journal of Operational Research, 63, pp.362-367.
Chen, C. S., Sarin, S. and Ram, B. (1991) “The pallet packing for non-uniform box sizes,” International Journal of Production Research, 29, pp.1963-1968.
Christofides, N. and Hadjiconstantinou, E. (1995) “An exact algorithm for general, orthogonal two-dimensional knapsack problems,” European Journal of Operational Research 83, pp.39–56.
Christofides, N. and Whitlock, C. (1977) “An algorithm for two dimensional cutting problems,” Operations Research, 25, pp.30-44.
Cintra, G., Minyazawa, F. K., Wakabayashi, Y. and Xavier, E.C. (2008) “Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation,” European Journal of Operational Research, 191, pp.61-85.
Cui, Y. D. (2007) “Simple block patterns for the two-dimensional cutting problem,” Mathematical and Computer Modeling, 45, pp.943-953.
Dyckhoff, H. (1990) “A typology of cutting and packing problems,” European Journal of Operational Research, 44, pp.145-159.
Gilmore, P. C. and Gomory, R. E. (1961) “A linear programming approach to the cutting stock problem,” Operations Research, 9, pp.848-859.
Gilmore, P. C. and Gomory, R. E. (1963) “A linear programming approach to the cutting stock problem, Part II,” Operations Research, 11, pp.863-888.
Gilmore, P. C. and Gomory, R. E. (1965) “Multistage cutting stock problems of two and more dimensions,” Operations Research, 13, pp.94-120.
Gilmore, P. C. and Gomory, R. E. (1966) “The theory and computation of knapsack functions,” Operations Research, 14, pp.1045-1074.
Ismail, H. S., and Hon, K. K. B. (1995) “The nesting of two-dimensional shapes using genetic algorithms,” Proceedings of the Institution of Mechanical Engineers. Part B: Journal of Engineering Manufacture, 209, pp.115-124.
Leung, T. W., Chan, C. K. and Troutt, D. M. (2003) “Applications of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem,” European Journal of Operational Research, 145, pp.530-542.
Leung, T. W., Yung, C. H. and Troutt, M. D. (2001) “Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem,” Computers and Industrial Engineering, 40, pp.201-214.
Li, H. L. and Chang, C. T. (1998) “An approximately global optimization method for assortment problems,” European Journal of Operational Research, 105, pp.604-612.
Li, H. L., and Tsai, J. F. (2001) “A fast algorithm for assortment optimization problems,” Computers and Operations Research, 28, pp.1245-1252.
Li, H. L., Chang, C. T. and Tsai J. F. (2002) “Approximately global optimization for assortment problems using piecewise linearization techniques,” European Journal of Operational Research, 140, pp.584-589.
Lodi A. and Monaci M. (2003) “Integer linear programming models for 2-staged two-dimensional knapsack problems,” Mathematical Programming Series B, 94, pp.257-278.
Tsai, J. F., Hsieh, P. L. and Huang, Y. H. (2009) “An optimization algorithm for cutting stock problems in the TFT-LCD industry,” Computers and Industrial Engineering, 57, pp.913-919
Viswanathan, K. V. and Bagchi, A. (1993) “Best-first search methods for constrained two-dimensional cutting stock problems,” Operations Research, 41, pp.768-776.
Wang, P.Y. (1983) “Two algorithms for constrained two-dimensional cutting stock problems,” Operations Research, 3l, pp.573-586.
Wu, T. H., Chen, J. F., Low, C. and Tang, P. T. (2003) “Nesting of two-dimensional parts in multiple plates using hybrid algorithm,” International Journal of Production Research, 41, pp.3883-3900.
Yanasse, H. H. (1997) “On a pattern sequencing problem to minimize the maximum number of open stacks,” European Journal of Operational Research, 100, pp.454-463.