TY - JOUR
T1 - A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting
AU - Song, Xiang
AU - Chu, C.
AU - Lewis, R.
AU - Nie, Y.
AU - Thompson, J.
PY - 2010
Y1 - 2010
N2 - 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: Heuristic; Dynamic programming; 2D cutting
AB - 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: Heuristic; Dynamic programming; 2D cutting
U2 - 10.1016/j.ejor.2009.05.047
DO - 10.1016/j.ejor.2009.05.047
M3 - Article
SN - 0377-2217
VL - 202
SP - 368
EP - 378
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -