考慮裁切大小及成本不同之平面切割問題

2D Cutting Stock Problems with Various Sizes and Costs

孫櫻芳(Ying-Fang Sun)

指導教授 ： 蔡榮發

國立臺北科技大學/管理學院/經營管理系碩士班/碩士(2014年)

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

摘要

本研究主要探討二維平面的切割問題，並針對特定切割產業依照訂單需求的數量及產品尺寸進行切割。此實際問題可應用在造紙業、玻璃業、布料等等。如何在一批已限定尺寸的原料做出最有效率的應用，將會影響到業者的生產成本及市場競爭力。因此本研究利用最佳化演算法解決平面切割問題，例如有一組不同尺寸的矩形或圓形，如何做出最佳的切割計畫才能使原物料減少裁切損失。此研究同時探討啟發式演算法及確定性方法，根據演算法分析所得到的結果為全域最佳解，求得的結果使面積使用率達到最高、生產成本降低。並提出範例來說明所提出的方法之實用性與有效性。

關鍵字

二維平面切割 ； 裁切損失 ； 最佳化

並列摘要

This study mainly discusses two-dimensional cutting stock problems considering orders with different quantities and different sizes or shapes. The application areas of the problem includes paper industry, glass industry, clothing industry, and other material cutting or design industries. How to enhance the utilization of the raw materials and increase the competitiveness of the products therefore becomes an important issue. This study uses an optimization method to solve the problems such that a set of different size rectangles or circles can be cut from the raw material with least trim loss. We combine deterministic method with heuristic method to improve the computational efficiency and the solution quality. According to the obtained analytic results, we can achieve the highest area utilization of raw materials and lower production costs. Moreover, numerical examples are used to illustrate the practicability and the validity of the proposed model.

並列關鍵字

two-dimensional cutting stock problems ； trim loss ； optimization

參考文獻

[1] Gilmore, P. C. and Gomory, R. E., “A linear programming approach to the cutting stock problem,” Operational Research, 1961, Volume: 9, pp.848-859.

[3] Holthaus, O., “Decomposition approaches for solving the integer one dimensional cutting stock problem with different types of standard lengths,” European Journal of Operational Research, 2002, Volume: 141, pp.295-312.

[4] Umetani, S.,Yagiura, M. and Ibaraki, T., “One-dimensional cutting stock problem to minimize the number of different patterns,” European Journal of Operational Research, 2003, Volume: 146, pp.388-402.

[5] Schilling, G. and Georgiadis, M. C., “An algorithm for the determination of optimal cutting patterns,” Computer & Operations Research, 2002, Volume: 29, pp.1041-1058.

[6] Gradisar, M. and Trkman, P., “A combined approach to the solution to the general one-dimensional cutting stock problem,” Computers & Operations Research, 2005, Volume: 32, pp.1793-1807.