کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
476909 1446083 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size
چکیده انگلیسی

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].


► We consider the two-dimensional cutting stock problem with stock of different sizes.
► A column generation based heuristic algorithm is proposed and computationally tested.
► The proposed algorithm outperforms the most effective algorithms from the literature.
► The two-dimensional knapsack problem with two-staged guillotine cuts is considered.
► A mixed integer linear programming model is proposed and computationally tested.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 218, Issue 1, 1 April 2012, Pages 251–260
نویسندگان
, , , , ,