Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape

AM Del Valle, TA De Queiroz, FK Miyazawa… - Expert Systems with …, 2012 - Elsevier
Expert Systems with Applications, 2012Elsevier
In this paper, the two-dimensional cutting/packing problem with items that correspond to
simple polygons that may contain holes are studied in which we propose algorithms based
on no-fit polygon computation. We present a GRASP based heuristic for the 0/1 version of
the knapsack problem, and another heuristic for the unconstrained version of the knapsack
problem. This last heuristic is divided in two steps: first it packs items in rectangles and then
use the rectangles as items to be packed into the bin. We also solve the cutting stock …
In this paper, the two-dimensional cutting/packing problem with items that correspond to simple polygons that may contain holes are studied in which we propose algorithms based on no-fit polygon computation. We present a GRASP based heuristic for the 0/1 version of the knapsack problem, and another heuristic for the unconstrained version of the knapsack problem. This last heuristic is divided in two steps: first it packs items in rectangles and then use the rectangles as items to be packed into the bin. We also solve the cutting stock problem with items of irregular shape, by combining this last heuristic with a column generation algorithm. The algorithms proposed found optimal solutions for several of the tested instances within a reasonable runtime. For some instances, the algorithms obtained solutions with occupancy rates above 90% with relatively fast execution time.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果