Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Song, Xiang ORCID: https://orcid.org/0000-0003-0235-3734, Chu, C. B., Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X, Nie, Y. Y. and Thompson, Jonathan Mark 2010. A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting. European Journal of Operational Research 202 (2) , pp. 368-378. 10.1016/j.ejor.2009.05.047

Full text not available from this repository.

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.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords: Heuristic; Dynamic programming; 2D cutting
Publisher: Elsevier
ISSN: 0377-2217
Last Modified: 18 Oct 2022 12:45
URI: https://orca.cardiff.ac.uk/id/eprint/11080

Citation Data

Cited 8 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item