平面原料切割問題之最佳化演算法

An Optimization Algorithm for Two Dimensional Cutting Stock Problems

謝秉倫(Ping-Lun Hsieh)

指導教授 ： 蔡榮發

國立臺北科技大學/管理學院/商業自動化與管理研究所/碩士(2006年)

https://doi.org/10.6841/NTUT.2006.00398

摘要

切割產業由於缺乏實現混合生產的有效方法，因此生產方式仍舊以現有批次生產的製造方式來切割各式產品，每一批次只切割一種產品尺寸。本研究為因應切割產業的需求提出最佳化演算法來解決平面原料切割問題。演算法所得到的解為全域最佳解，不同於啟發式演算法所得到的區域最佳解或可行解。
產業範例顯示，平面原料切割演算法可以依照訂單需求數量找出最佳生產方式，亦可解決產品之間的多重解問題，確實可以幫助產業實現混合生產並獲得原料成本降低之競爭優勢。另外，演算法加入了原料基板多樣化與設置成本的考量後，更加強了演算法的完整性也更符合產業實際需求。

關鍵字

最佳化 ； 原料切割問題

並列摘要

Due to lack of efficient approaches of mixed production, the present production approach of the cutting industries is batch production that each glass substrate is cut into plates of one size only. This study proposes an optimization algorithm for two-dimensional cutting stock problems of the cutting industries. The solution of the proposed algorithm is a global optimum which is different from a local optimum or a feasible solution that is found by the heuristic algorithms.
Numerical examples are shown that the proposed algorithm not only finds out the optimal cutting way according to the order quantities but also presents a method of finding alternative solutions. Additionally, the proposed algorithm takes various stock sizes and setup cost into consideration to enhance the completeness to fit industrial needs.

並列關鍵字

Optimization ； Cutting Stock Problem

參考文獻

[1] Holthaus, O., Decomposition approaches for solving the integer one dimensional cutting stock problem with different types of standard lengths. Eur J Oper Res, 2002, 141, 295-312.

[2] Umetani, S., Yagiura, M. and Ibaraki, T., One-dimensional cutting stock problem to minimize the number of different patterns. Eur J Oper Res, 2003, 146, 388-402.

[3] Gradisar, M. and Trkman, P., A combined approach to the solution to the general one-dimensional cutting stock problem. Computers Oper Res, 2005, 32, 1793-1807.

[4] Saad, M.A. Suliman, Pattern generating procedure for the cutting stock problem. Int. J. Production Economics, 2001, 74, 293-301.

[5] Hifi, M., An improvement of Viswanathan and Bagchi’s exact algorithm for constrained tow-dimensional cutting stock. Computers Ops Res, 1997, 24, 727-736.