Skip to content

A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting

Research output: Contribution to journalArticlepeer-review

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
Original languageEnglish
Pages (from-to)368-378
Number of pages11
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 2010

Related information

Relations Get citation (various referencing formats)

ID: 84523