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 / M., Russo; Sforza, Antonio; Sterle, Claudio. - (2013), pp. 343-343. (Intervento presentato al convegno EURO | INFORMS. 26TH EUROPEAN CONFERENCE ON OPERATIONAL RESEARCH tenutosi a 04/07/2013 nel 01/07/2013).
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
