We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3]. © 2011 Elsevier B.V. All rights reserved.

A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size / Furini, F.; Malaguti, E.; Medina Duran, R.; Persiani, A.; Toth, P.. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 218:1(2012), pp. 251-260. [10.1016/j.ejor.2011.10.018]

A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size

Furini F.;
2012

Abstract

We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3]. © 2011 Elsevier B.V. All rights reserved.
File allegati a questo prodotto
File Dimensione Formato  
VE_2012_11573-1571746.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 568.3 kB
Formato Adobe PDF
568.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11573/1571746
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 36
  • ???jsp.display-item.citation.isi??? 29
social impact