臺灣博碩士論文加值系統

　　原料裁切問題（Cutting Stock Problem, CSP）探討如何由已知尺寸的原料中，以最佳的方式裁切出符合需求尺寸的物件。對土木與建築工程而言，一維原料裁切問題可應用在鋼材裁切上。土木與建築工程所使用的需求鋼筋，通常都是用鋼鐵廠生產的亂尺料原料鋼筋，再交由鋼筋裁切廠進行裁切。好的裁切計畫可以減少廢料量並減少原料鋼筋之使用量。為減少非進度內使用之鋼筋存放，各種類需求鋼筋依要求供應順序裁切亦為重要課題。為此本研究探討一維鋼材原料裁切順序模式之構建。最佳化目標為滿足需求鋼筋數量與裁切順序之要求下使用最少的原料鋼筋根數產生鋼筋裁切順序計畫。

　　本研究與多數原料裁切問題研究以pattern方式規劃模式不同，本模式將每一根需求鋼筋獨立考慮，並在此概念下發展整個鋼筋裁切順序模式。模式並定義一組雙元整數變數以表示各類鋼筋之第一根與最後一根裁切之位置，並以限制式控制各類鋼筋切出之相對順序。本研究所建立之模式為一個二元整數規劃模式，可利用分枝定限法或其他廣用方法進行求解。

　　論文中呈現數個測試例，對應模式中各個裁切順序限制，驗證整個鋼筋裁切順序模式之正確性。各測試例規模之範圍包括鋼筋種類4到7種；需求鋼筋根數20到33根；原料鋼筋10到15根。決策變數個數範圍自319到570個。

　Cutting stock problems (CSP) deal with the optimal cutting of raw materials in order to satisfy the given demands of different order lengths. To civil and construction engineering, an application of one-dimensional cutting stock problem (1D-CSP) is the cutting of structural steel bars. Usually steel demands for civil and construction enginnering are cut from stock pieces in a cutting mill. A good cutting plan can reduce scrap and thus cut back the demand for stocks. To reduce temporary steel bar storage, it is important that steel bars are cut in an appropriate sequence. In this research we present a model for the one-dimensional steel cutting sequencing problem. The optimization objective is to minimize the consumption of stock pieces subject to demands and a given cutting sequence.

　In contrast to commonly used pattern-based models, our model considers each demand piece independently. The model uses a set of binary integer variables to represent when the first and last bars of each type are cut, and uses a set of constraints to control the relative cutting order between types. The resulting model is a binary integer program that can be solved by any standard algorithm such as branch and bound.

　In this thesis we present several computational examples to verify the correctness of the model. The scale of these examples range from 4 order types to 7 order types, a total of 20 to 33 demanded bars, and 10 to 15 stock pieces. The number of variables in these examples range from 319 to 570.

摘要　I
Abstract　II
目錄　III
表目錄　V
圖目錄　VI
誌謝　VIII
第一章 緒論　1
1.1研究動機與目的　1
1.2研究範圍與方法　2
1.3論文架構　3
第二章 問題描述與定義　4
2.1鋼筋生產與施工　4
2.1.1鋼筋生產流程　4
2.1.2鋼筋施工流程　8
2.1.3鋼筋工程分工方式　10
2.2工程成本　11
2.3鋼筋裁切施作　13
2.3.1裁切時的損耗　13
2.3.2裁切作業　14
2.4鋼筋裁切順序問題　15
2.4.1問題背景描述　15
2.4.2問題定義與基本假設　17
第三章 文獻回顧　19
3.1裁切問題相關文獻　19
3.2裁切順序問題相關文獻　27
第四章 數學模式　30
4.2模式構建　33
4.3模式求解方法與決策變數特性　42
4.3.1模式之決策變數及限制式數量　42
4.3.2模式求解方法　43
第五章 模式測試與分析　45
5.1測試例1　46
5.2測試例2　49
5.3測試例3　53
5.4測試例4　58
5.5測試例5　61
5.6測試例6　64
第六章 結論與後續研究　69
6.1結論　69
6.2後續研究　70
參考文獻　71
簡 歷　74

1.中國鋼鐵企業網頁http://www.csc.com.tw/index.asp。
2.豐興鋼鐵股份有限公司網頁http://www.fenghsin.com.tw/profile.htm。
3.楊秉蒼，「營建鋼筋裁切規劃系統實作與應用」，詹氏書局，2002年。
4.楊世清，「營建管理技術手冊」，地景出版社，1998年。
5.林蔚菁，「系統模擬於鋼筋供應鏈管理之研究」，朝陽科技大學營建工程研究所碩士論文，2003年。
6.沈宇晟，「鋼筋裁切問題之啟發式解法」，國立成功大學土木工程學研究所碩士論文，2005年。
7.Dyckhoff, H., “A Typology of Cutting and Packing Problems,” European Journal of Operational Research, Vol. 44, pp. 145–159 (1990).
8.Gilmore, P.C., and Gomory, R.E., “A Linear Programming Approach to the Cutting Stock Problem,” Operations Research, Vol. 9, pp. 849–859(1961).
9.Gilmore, P.C., and Gomory, R.E., “A Linear Programming Approach to the Cutting Stock Problem – Part II,” Operations Research, Vol. 11, pp. 863–888(1963).
10.Dyson, R. G. and Gregory, A.S., “The Cutting Stock Problem in the flat glass industry,” Operations Research Quarterly 25, pp.41-54(1974).
11.Madsen, O.B.G., “An application of travelling-salesman routines to solve pattern-allocation problem in the glass industry,” Journal of the Operational Research Society 39, pp.249-256(1988).
12.Yuen, B.J., and Richardson, K.V., “Establishing the Optimality of Sequencing Heuristics for Cutting Stock Problems,” European Journal of Operational Research, Vol. 84, No. 3, pp. 590-598(1995).
13.Yanasse, H.H., “On A Pattern Sequencing Problem to Minimize The Maximum Number of Open Stacks,” European Journal of Operational Research, Vol. 100,pp. 454-463(1997).
14.Becceneri, J.C., Yanasse, H.H., Soma, N.Y., “A Method for Solving The Minimization of The Maximum Number of Open Stacks Problem within A Cutting Process,” European Journal of Operational Research, Vol. 31,pp. 2315-2332(2004).
15.Foerster, H., and Wascher, G., “Simulated annealing for order spread minimization in sequencing cutting partterns,” European Journal of Operational Research, Vol. 110,pp. 272-281(1998).
16.Faggioli, E., and Bentivoglio, C.A., ” Heuristic and Exact Methods for the Cutting Sequencing Problem,” European Journal of Operational Research, Vol. 110, No. 3, pp. 564-575(1998).
17.Vasko, F.J., Newhart, D.D., Stott, J., and Kenneth L., “A Hierarchical Approach for One-Dimensional Cutting Stock Problems in the Steel Industry that Maximizes Yield and Minimizes Overgrading,” European Journal of Operational Research, Vol. 114, No. 1, pp. 72-82(1999).
18.Wong, W.K., Chan, C.K., and Ip, W.H., “Optimization of spreading and cutting sequencing model in garment manufacturing,” Computers In Industry, Vol. 43, pp. 1-10(2000).
19.Armbruster, M., “A Solution Procedure for a Pattern Sequencing Problem as Part of a One-Dimensional Cutting Stock Problem in the Steel Industry,” European Journal of Operational Research, Vol. 141, No. 2, pp. 328-340(2002).
20.McMullen, P.P., M., Clark, M., Albritton D., Bell, J., “A Correlation and Heuristic Approach for Obtaining Production Sequences Requiring a Minimum Tool Replacements,” Computers and Operations Research, Vol. 30, pp. 443-462 (2003).
21.Johnston, R.E., Sadinlija, E., “A new model for complete solutions to one-dimensional cutting stock problems,” European Journal of Operational Research, Vol. 153, pp. 176-183 (2004).
22.S. Baum and Jr. L. E. Trotter. “Integer rounding for polymatroid and branching problems,” SIAM Journal on Algebraic Discrete Methods, Vol. 2, pp.416-425(1981).
23.Nash,Stephen G., Sofer, Ariela, Linear and Nonlinear Programming, pp.200-204, McGraw-Hill(1996).