Algoritmos heurísticos para o problema de nesting com rotações livres

Abstract

The problem of cutting and packing irregular pieces, or Nesting’s problem, aims to find the best position of pieces within a range, trying to minimize the height used (and, consequently, the space used by the pieces). This problem is of great relevance since the cutting and packing of pieces occur in the furniture, textiles, and footwear industries. The problem addressed is two-dimensional with convex and non-convex pieces, with free rotation. Our goal is to be able to answer the following research question: “Is there any way to improve the efficiency of solving the problem of two-dimensional Nesting with free rotations, using heuristics?". Five positioning rules, five sorting rules, and two rotation rules were initially implemented to answer this question, and twenty-five constructive heuristics were proposed, each using combinations of a positioning rule, a sorting rule, and both rotation rules. Computational experiments made with twelve instances of the literature indicated that, among these heuristics, those that use two positioning rules (called a and b) stood out. In particular, one of them obtained better results (although similar to the others). A heuristic called the Multiple Positioning Heuristic, and a Genetic Algorithm were also implemented, which use the combination of these two position rules that stood out. After comparing the proposed methods, it was possible to notice that the Multiple Positioning Heuristic obtained better results in eight of the twelve tested instances. After defining our best method, we compare it with the results found in the literature. Our approach’s results were promising, surpassing the best results in three of the eight instances in the literature.