\input zb-basic
\input zb-ioport
\iteman{io-port 06066843}
\itemau{Furini, Fabio; Malaguti, Enrico; Dur\'an, Rosa Medina; Persiani, Alfredo; Toth, Paolo}
\itemti{A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size.}
\itemso{Eur. J. Oper. Res. 218, No. 1, 251-260 (2012).}
\itemab
Summary: 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 {\it G. F. Cintra} et al. [Eur. J. Oper. Res. 191, No. 1, 61--85 (2008; Zbl 1146.90499)].
\itemrv{~}
\itemcc{}
\itemut{cutting; packing; combinatorial optimization; column generation}
\itemli{doi:10.1016/j.ejor.2011.10.018}
\end