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

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.

► We investigate 2D irregular shape knapsack and cutting stock problems.
► The 0–1 knapsack problem is solved by a GRASP heuristic.
► The unconstrained knapsack is solved in two steps: irregular items packed into rectangles; and, resultant rectangles packed into the bin.
► A column generation approach that uses the algorithm of the unconstrained knapsack is presented for the cutting stock problem.
► Optimal solutions and solutions with occupancy rates above 90% were obtained spending little CPU time.