A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting
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.
Year of publication: |
2010
|
---|---|
Authors: | Song, X. ; Chu, C.B. ; Lewis, R. ; Nie, Y.Y. ; Thompson, J. |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 202.2010, 2, p. 368-378
|
Publisher: |
Elsevier |
Subject: | Heuristic Dynamic programming 2D cutting |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Solving the response time variability problem by means of a genetic algorithm
Song, X., (2010)
-
An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem
Song, X., (2006)
-
Song, X., (2010)
- More ...