An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem
Mauro Russo,
Antonio Sforza and
Claudio Sterle
International Journal of Production Economics, 2013, vol. 145, issue 2, 451-462
Abstract:
In this paper we tackle the unconstrained non-staged guillotine two-dimensional cutting problem (U2DCP) with rectangular pieces and one rectangular stock sheet. This problem has been widely treated in literature by exact and heuristic solution methods which use the knapsack function introduced by Gilmore and Gomory (1966) and implement more effective variants of their dynamic programming procedure to compute the related recursive expression. We highlight three errors present in the original procedure by Gilmore and Gomory (1966). The first error was noted by Herz (1972) but no correction was provided. The other two errors have never been noted before. These errors affect the accuracy of the solution and cause the increase of the computational requirements. Corrections for these errors are presented and an improved computational procedure is proposed. The new procedure has been tested on a wide set of instances (PackLib2) and compared with the best exact and heuristic methods present in literature. The experimentation shows that the procedure significantly outperforms the best dynamic programming algorithm proposed for the U2DCP and it compares well with the best heuristic and the best exact algorithm for the problem.
Keywords: Cutting stock; Guillotine cutting; Knapsack function (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations: View citations in EconPapers (2)
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527313001953
Full text for ScienceDirect subscribers only
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:145:y:2013:i:2:p:451-462
DOI: 10.1016/j.ijpe.2013.04.031
Access Statistics for this article
International Journal of Production Economics is currently edited by Stefan Minner
More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu (repec@elsevier.com).