臺灣博碩士論文加值系統

本研究旨在探討一維裁切庫存問題，傳統裁切庫存問題為節省原料成本，因此考慮浪費最小化；也有的談到因樣式改變而造成更多的成本，因此考慮樣式種類最小化。而本研究所探討的產業其浪費部分可回收，且回收成本低，故本研究主要在考慮如何找出適當的樣式組合，並安排其裁切順序，以使得裁切作業外之總整備時間最小化。

在訂單種類不多的情況下，利用整數規劃與窮舉法便可簡單找出使裁切作業外之總整備時間最小化的組合，但在訂單種類多的情況下，窮舉法便不再適用。因此本研究利用進化演算法中的進化規劃來有效率的找出答案，而此法相較於現有實務上所運用之方法，能找出更佳的答案。

The purpose of this study is to discuss one-dimensional cutting stock problem (CSP). Traditional CSP researches considered minimizing trim loss for saving cost of raw materials. Furthermore, other CSP researches considered minimizing different patterns because of changing pattern may cause setup cost. In this study, we discuss certain industries which have two characteristics—waste can be recycled and the recycled cost is fairly low. For the reason, the purpose of this study is to find an appropriate combination of patterns and arrange its sequence to minimize total setup time.

It is easy to minimize total setup time by using integer programming (IP) and enumeration method if the categories of orders are not many. If they are, the method is useful no more. Hence this study proposes EP (Evolutionary Programming) of EA (Evolutionary Algorithms) to find out a solution efficiently, and compared with the real world’s solution, the result of the proposed method in this study is better.

摘要 Ⅰ
Abstract Ⅱ
目錄 Ⅲ
圖目錄 Ⅴ
表目錄 Ⅵ
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 1
1.3研究方法與架構 2
第二章 文獻探討 4
2.1 裁切庫存問題之起源 4
2.2 各種裁切庫存問題 7
2.3 進化運算與進化演算法（Evolutionary Computation& Evolutionary
Algorithms，EC& EA） 10
2.4 進化規劃（Evolutionary Programming，EP） 13
第三章 問題、模型定義 15
3.1 問題描述 15
3.2 假設 17
3.3 基本模型 17
第四章 研究方法 20
4.1 問題規模較小時之解決模式 20
4.1.1數字範例 21
4.1.2 範例分析 29
4.2 問題規模較大時之解決模式 30
4.2.1數字範例 32
4.2.2 範例分析 33
第五章 結論與建議 37
參考文獻 39
附錄一 42
附錄二 46

1.楊進德，「配電系統規劃的可靠度成本模型設計與價值分析之研究」，中山大學，博士論文，民國90年。
2.陳英欽，「以遺傳演算法求解一般整數策略下之經濟批量排程問題」，東海大學，碩士論文，民國91年。
3.許尚評，「一維裁切庫存問題之研究-薄膜產業之分裁順序安排作業探討」，長庚大學，碩士論文，民國93年。
4.翁振恭，「使用基因演算法於拓撲最佳化之研究」，大葉大學，碩士論文，民國93年。
5.張瀚文，「鋼筋裁切順序最佳化模式」，成功大學，碩士論文，民國93年。
6.沈宇晟，「鋼筋裁切問題之啟發式解法」，成功大學，碩士論文，民國94年。
7.Antonio, J., Chauvet, F., 1999, The cutting stock problem with mixed objectives: Two heuristics based on dynamic programming, European Journal of Operational Research 114, 395-402.
8.Back, T., Rudolph, G., Schwefel, H. P., 1993, Evolutionary programming and evolution strategies: similarities and differences, University of Dortmund, Department of Computer Science.
9.Dyckhoff, H., 1990, A Typology of Cutting and Packing Problems, European Journal of Operational Research 44, 145-159.
10.Foerster, H., Wascher, G., 1999, Pattern reduction in one-dimensional cutting stock problems, The 15th Triennial Conference of the International Federation of Operational Research Societies.
11.Fogel, David B., 1994, An Introduction to Simulated Evolutionary Optimization, IEEE Transactions on Neural Networks 5, 3-14.
12.Fogel, David B., 2000, What is evolutionary computation?, IEEE Spectrum, 26-32.
13.Gilmore, P. C., Gomory, R. E., 1961, A Linear Approach to the Cutting-Stock Problem, Operations Research 9, 849-859.
14.Gilmore, P. C., Gomory, R. E., 1963, A Linear Programming Approach to The Cutting Stock Problem—part II, Operations Research 11, 863-888.
15.Haessler, R. W., 1975, Controlling cutting pattern changes in one-dimensional trim problems, Operations Research 23, 483-493.
16.Harjunkoski, I., Westerlund, T., Porn, R., and Skrifvars, H., 1998, Different transformations for solving non-convex trim-loss problems by MINLP, European Journal of Operational Research 105,594-603.
17.Holthaus, O., 2003, On the best number of different standard lengths to stock for one-dimensional assortment problems, International Journal of Production Economics 83, 233-246.
18.Johnston, Tobert E., Sadinlija, E., 2004, A new model for complete solutions to one-dimensional cutting stock problems, European Journal of Operational Research 153, 176-183.
19.Liang, K. H., Yao, X., Newton, C., Hoffman, D., 2002, A new evolutionary approach to cutting stock problems with and without contiguity, Computers & Operations Research 29, 1631-1659.
20.Ragsdale, Cliff T., Zobel, C. W., 2004, The ordered cutting stock problem, Decision Science 35, 83-100.
21.Spears, William M., De Jong, K. A., Baeck, T., Fogel, David B., Garis, Hugo de., 1993, An overview of evolutionary computation, European Conference on Machine Learning.
22.Suliman, Saad M.A., 2001, Pattern generating procedure for the cutting stock problem, International Journal of Production Economics 74, 293-301.
23.Umetani, S., Yagiura, M., Ibaraki, T., 2003, One-dimensional cutting stock problem to minimize the number of different patterns, European Journal of Operational Research 146, 388-402.
24.Vanderbeck, F., 1999, Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem, Mathematiques Appliquees Bordeaux (MAB), Universite Bordeaux 1.
25.Wagner, Bret J., 1999, European Journal of Operational Research 117, 368-381.