A GRASP meta-heuristic for two-dimensional irregular cutting stock problem

Reducing expensive raw material waste is an important goal in the industry. In this paper, two-dimensional irregular cutting stock problem—a nesting problem that differs from other in their irregular shape of the pieces—with demand is studied, in which the required pieces has to be produced from large rectangular sheet minimizing material waste. Structure of this problem made it intractable for practical applications such that exact algorithms are not able to solve it in a reasonable time. Greedy randomized adaptive search procedure (GRASP) meta-heuristic algorithm is adapted to tackle the problem by providing high-quality solution in an appropriate time. The algorithm does not depend on the shape (convexity and regularity) of pieces and is able to deliver an optimum solution for instances up to 30 pieces of 7 different types. In addition, computational results are provided for different test problems from the related literature.