EconPapers    
Economics at your fingertips  
 

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).

 
Page updated 2025-01-08
Handle: RePEc:eee:proeco:v:145:y:2013:i:2:p:451-462