We tackle the unconstrained guillotine two-dimensional cutting prob- lem (U2DCP) by a new improved version of the knapsack func- tion based dynamic programming procedure of Gilmore and Gomory (1966). We correct an error found by Herz (1972) and two other errors we found in their procedure. We also integrate it with an original piece pre-processing phase, coordinate reduction by using raster points, and tailored refinements aimed at reducing the memory requirements and the computation time. The proposed procedure solves at the optimum a set of seven very large instances never solved before.

An exact dynamic programming procedure for very large-scale unconstrained two-dimensional guillotine cutting problem

SFORZA, ANTONIO;STERLE, CLAUDIO
2013

Abstract

We tackle the unconstrained guillotine two-dimensional cutting prob- lem (U2DCP) by a new improved version of the knapsack func- tion based dynamic programming procedure of Gilmore and Gomory (1966). We correct an error found by Herz (1972) and two other errors we found in their procedure. We also integrate it with an original piece pre-processing phase, coordinate reduction by using raster points, and tailored refinements aimed at reducing the memory requirements and the computation time. The proposed procedure solves at the optimum a set of seven very large instances never solved before.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/596413
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact