臺灣博碩士論文加值系統

一維儲料切割問題(one-dimensional cutting stock problem, 1D-CSP)存在於相當多加工及製造業之產品製程中，為降低其製造成本，尋求一個較低餘料(trim loss)之切割規劃(cutting plan)就成為主要目標之一；本文以一維儲料切割問題為研究方向，嘗試尋求一個低餘料之切割規劃。
本文提出三種方法用來求解單一長度儲料(stock) 一維儲料切割問題。最小儲料餘料法(Minimum Stock Trim Loss, MSTL)為本文所提方法的基礎，其演算流程與MBS (Minimum-bin-slack, Gupta and Ho, 1999)相似，但構件的選取方式不同。可調式儲料餘料法(Varying Stock Trim Loss, VSTL)及多重路徑最小儲料餘料法(Multiple Path Minimum Stock Trim Loss, MPMSTL)則為MSTL的改良，用以改善演算的結果。MSTL是以每次處理單根儲料為基準，運用訂定的排入及替換構件(order)選擇機制，在單根儲料中找出使其餘料長度最小的較佳構件排列方式，將所得的構件排入儲料中，剩餘構件依此方法作遞迴演算，陸續將構件排入儲料中，直到所有構件皆排入儲料為止。
VSTL是改良自MSTL，藉由改變餘料接受值，以改善演算結果。而MPMSTL亦是改良自MSTL。為了能夠藉由獲得更多的切割樣式來改善所求結果之品質，在MPMSTL中，一個樹狀結構限制清單被設計並與MSTL合作產生切割樣式。
最後將引用文獻中的數個範例，以比較本文所提三種方法和相關文獻的演算結果，並比較本文所提的三種方法找到較佳解的演算時間及演算次數。

One-dimensional cutting stock problem (1D-CSP) exists in the manufacturing processes of many products in the processing and manufacturing industries. For reducing the cost, to find a cutting process that will waste minimum materials is one of major objective during the production. It is also the aim of 1D-CSP. A 1D-CSP of constant stock length that focuses on minimizing the total trim loss will be studied in this thesis.
In this thesis, three algorithms were developed to solve 1D-CSP of constant stock length. Where, the Minimum Stock Trim Loss (MSTL) is the base algorithm of this paper that is similar to MBS algorithm (that had applied to solve one-dimensional bin-packing problem) but differs in the selection of cutting pattern. The Varying Stock Trim Loss (VSTL) and the Multiple Path Minimum Stock Trim Loss (MPMSTL) are the revised versions that are modified from the MSTL for improving the obtained results. Based on the principle of performing one cutting pattern at each time, several pre-defined mechanisms for the assignment of orders and the replacement of orders are adopted by the MSTL for finding a better cutting pattern with minimum trim loss. Once a cutting pattern is found, then those orders appear in the pattern is removed from. And the left orders are processed with the same procedures until no more order is need to be assigned into a stock.
The VSTL was modified from the MSTL. By changing the threshold value of the trim loss, the results from the VSTL are better than the ones from the MSTL.
The MPMSTL was also developed from the bases of the MSTL. For improving the solution quality by diversifying the obtained cutting patterns, in this method, a forbidden-tree list was developed to cooperate with MSTL to generate cutting pattern.
In order to demonstrate the performances of the proposed three methods, several computation instances obtained from literature were adopted. The comparisons between the obtained results from the proposed methods and the ones from literature were made in different ways. In addition, the relative parameters for each algorithm during the execution are also discussed in this thesis.

目錄
摘要 Ⅰ
Abstract Ⅲ
目錄 Ⅴ
圖目錄 Ⅶ
表目錄 Ⅷ
第一章 緖論 1
1.1 研究動機與目的 1
1.2 研究方法 2
1.3 論文架構 4
第二章 問題描述與文獻回顧 5
2.1 問題描述與定義 5
2.2 文獻回顧 6
第三章 研究方法 9
3.1 演算模式建構 9
3.2 MSTL與MBS的異同比較 19
3.3 MSTL演算法的延伸 22
第四章 研究結果 32
4.1 演算環境及參數 32
4.2 範例演算 32
第五章 結論與建議 47
參考文獻 50
附錄一 演算範例數據 52
附錄二 演算結果 54

圖目錄
圖2.1-1 定製構件切割規劃示意圖 5
圖3.1-1 MSTL演算流程 10
圖3.1-2 構件排入儲料示意圖 11
圖3.1-3 單一儲料之較佳構件排列流程圖 14
圖3.3-1 樹狀結構限制清單示意圖 24
圖3.3-2 MPMSTL演算結果樹狀圖 24
圖3.3-3 MPMSTL流程圖 27
圖3.3-4 MPMSTL演算結果 31
圖4.2-1 MPMSTL分支路徑示意圖 34
圖4.2-2 Case No.9 儲料使用量比較圖 41
圖4.2-3 Case No.8 儲料使用量比較圖 42
圖4.2-4 Case No.6 儲料使用量比較圖 42
圖4.2-5 Case No.8 分支數與儲料使用量結果圖 45
圖4.2-6 Case No.8 樹高(層)與儲料使用量結果圖 45
圖4.2-7 Case No.8 根節點數與儲料使用量結果圖 46
圖4.2-8 演算搜尋範圍示意圖 46

表目錄
表3.1-1 MSTL引用範例 16
表3.1-2 MSTL演算結果列表 18
表3.2-1 MSTL與MBS比較範例 20
表3.2-2 MBS演算結果 21
表3.2-3 MSTL演算結果 21
表3.3-1 MPMSTL引用範例資料表 30
表3.3-2 MPMSTL演算結果統計表 30
表4.2-1本文演算法和其它演算法結果比較表 34
表4.2-2 VSTL及MPMSTL結果比較表 37
表4.2-3 餘料接受值及構件排列比較表 39
表A-1 演算範例數據表 50

1.Applegate, D.L., Buriol, L., Dillard, B., Johnson, D.S., and Shor, P.W. (2003), “The cutting-stock approach to bin-packing: Theory and experiments,” In Proceedings of the 5th Workshop on Algorithm Engineering and Experimentation. SIAM, Philadelphia, PA, pp.1-15.

2.Dyckhoff, H. (1990), “A typology of cutting and packing problems,” European Journal of Operational Research, Vol.44, pp.145-159.

3.Eilon, S., Christonfides, N. (1971), “The loading problem,” Management Science, Vol.17, No.5, pp.259-268.

4.Gilmore, P.C., Gomory, R.E. (1961), “A linear programming approach to the cutting stock problem,” Operations Research, Vol.9, pp.849-859.

5.Gilmore, P.C., Gomory, R.E. (1963), “A linear programming approach to the cutting stock problem: Part II, “Operations Research, Vol.11, pp.863-888.

6.Gradišar, M., Jesenko, J., Resinovič, G. (1997), “Optimization of roll cutting in clothing industry”, Computer and Operations Research, Vol.24, pp.945-953.

7.Gradišar, M., Resinovič, G., Kljajić, M. (1999), “A hybrid approach for optimization of one-dimensional cutting”, European Journal of Operational Research, Vol.119, pp.719-728.

8.Haessler, R.W., and Sweeney, P.E. (1991), “Cutting stock problems and solution procedures,” European Journal of Operational Research, Vol.54, No.5, pp.141-150.

9.Haessler, R.W. (1971), “A heuristic programming solution to a nonlinear cutting stock problem,” Management Science, Vol.17, No.12, pp.B793-802.

10.Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., and Graham, R.L. (1974), “Worst-case performance bounds for simple one-dimensional packing algorithm” SIAM Journal of Computing, Vol.3, No.4, pp.299-326.

11.Gupta, J.N.D., Ho, J.C (1999), “A new heuristic algorithm for the one-dimensional bin-packing problem,” In Production Planning & Control Vol.10, No.6, pp598-603.

12.Stadtler, H. (1990), “A one-dimensional cutting stock problem in the aluminium industry and its solution,” European Journal of Operational Research, Vol.44, pp.209-223.

13.Weng, W.C., Yang C.T., Hung, C.F. (2003), “The optimization of section steel arrangement for ship construction associated with cutting rule by genetic algorithm”, The 17th Asian-Pacific Technical Exchange and Advisory Meeting on Marine Structure, pp.237-246, National Cheng Kung University, Tainan, Taiwan.

14.Yang, C.T., Sung, T.S., Weng, W.C. (2006), “An improved tabu search approach for one-dimensional cutting stock problem,” Advances in Engineering Software.(In Press)

15.Yang, C.T., Wu, W.S., Sung, T.C.(2006a),”A research for one-dimensional cutting stock problem with practical rules,” The 18th National Conference on Naval Architecture and Marine Engineering, Keelung. Taiwan, March 18-19(in Chinese)

16.Yang, C.T., Sung, T.C., Hung, Y.H., and Lee, Y.F. (2004), “Numerical experiments with BFD and tabu search for one-dimensional cutting stock problem,” The Proceedings of CIIE Conference, Taiwan, December 18.(in Chinese)