An Investigation of Paper Cutting Problem by Dynamic Programming and Heuristic Approaches

以動態規劃及啓發演算法為基礎解求解紙張裁切問題

張百棧(Pei-Chann Chang) ； 謝日章(Jih-Chang Hsieh)

《工業工程學刊》 22卷6期 (2005/11) Pp. 463-472

https://doi.org/10.29977/JCIIE.200511.0003

摘要

本研究主要使用動態規劃法探討紙張裁切問題，此外，也提出兩個啓發法降低裁切的損失。此問題為NP-Hard問題並且屬於組合性問題，若採用最佳化解法之動態規劃演算法，將無法有效求解，因此將此之轉化為包裝問題，並發展兩個啓發式解法提供實務上應用。第一個方法為將原本的問題轉換為對偶形式，而裁切的特徵是依據C(下標 i)/A(下標 i)降冪的順序；第二個方法為藉由顧客的需求將紙張大小可能的組合產生可行解。為了比較動態規劃演算法與兩個啓發式方法之績效，本研究經由廣泛性的模擬測試求得。最後，實驗的結果指出本研究所提出的兩個啓發式方法能有效解決紙張裁切問題，可作為實務上應用之參考。

關鍵字

紙張裁切問題 ； 裁切損失 ； 動態規劃 ； 啓發式方發

並列摘要

The major focus of this research is to formulate the paper cutting problem using dynamic programming. Two heuristic approaches are also developed for practical applications in minimizing the trim losses. Paper cutting problems are NP-hard and have the combinatorial explosion characteristic. It is not efficient to generate cutting patterns by dynamic programming. Thus, the problem is transformed into a Knapsack problem and two heuristic approaches are developed to provide alternatives for practical use in manufacturing company. The first heuristic is to transform the original problem into the dual form, then cutting patterns are generated according to the descending order of C(subscript i)/A(subscript i). The second heuristic is to organize the possible combinations of the size of the paper ordered by the customer to form a feasible cutting pattern. The dynamic programming model and heuristic approaches are evaluated through extensive simulation studies. The computational result indicates that the proposed heuristic approaches are quite satisfactory. The result may be of interest to other practical manufacturing companies.

並列關鍵字

Paper cutting ； Trim loss ； Dynamic programming ； Heuristic approaches

參考文獻

Agrawal, P. K.(1993).Determining stock-sheet-size to minimize trim loss.European Journal of Operational Research.64,423-431.

Agrawal, P. K.(1993).Minimizing trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guillotine cuts.European Journal of Operational Research.64,410-422.

Blazewicz, J.,M. Drozdowski,B. Soniewicki,R. Walkowiak(1989).Two dimensional cutting problem: basic complexity results and algorithms for irregular shapes.Fundamental Control Engineering.14

Christofides, N.,C. Whitlock(1977).An algorithm for two-dimensional cutting problems.Operational Research.25,30-40.

Cung, V. M. Hifi,B. L. Cun(2000).Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm.International Transaction in Operation Research.7,185-210.