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.
F. Furini, E. Malaguti, R. Medina Durán, A. Persiani, P. Toth (2012). A Column Generation Heuristic for the Two-Dimensional Cutting Stock Problem with Multiple Stock Size. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 218, 251-260 [10.1016/j.ejor.2011.10.018].
A Column Generation Heuristic for the Two-Dimensional Cutting Stock Problem with Multiple Stock Size
FURINI, FABIO;MALAGUTI, ENRICO;TOTH, PAOLO
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
