Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482274 | European Journal of Operational Research | 2010 | 11 Pages |
Abstract
In this paper, a dynamic programming-based recursive method is proposed for solving an unconstrained 2D rectangular cutting problem. The algorithm is an incomplete method, in which some intricate cutting patterns may not be obtained. The worst case performance of the algorithm is evaluated and some theoretical analyses for the algorithm are performed. Compared to traditional dynamic programming, this algorithm gives a high percentage of optimal solutions (94.84%, 86.67% and 77.83% for small, medium and large sized unweighted instances, 99.67%, 99.50% and 97.00% for small, medium and large sized weighted instances) but features a far lower computational complexity. Computational results are also presented for some known benchmarks.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
X. Song, C.B. Chu, R. Lewis, Y.Y. Nie, J. Thompson,