Resolução do problema de corte bidimensional com itens irregulares idênticos usando algoritmos genéticos e processamento de imagens digitais

Abstract

The cutting problem involves cutting larger objects into smaller items with the aim of minimizing waste. The objects can be raw materials, such as rolls of paper, glass sheets, metal plates, steel, aluminum or wood. The items represent the shape to be cut and may be described as concave or convex irregular geometries. The cut of raw material is an industrial process which has attracted the attention of many researchers, since it can generate large waste, increasing the production cost. Nevertheless, the set of possible solutions to this problem has a large number of combinations and, therefore, its computational complexity is considered NP-Hard. In this work, we proposed an approach based on Genetic Algorithm (GA) and Digital Image Processing (DIP) to deal with the problem of to cut rectangular plates (objects) in equal parts (items) with irregular shapes, categorized in the literature as 2D-I-IIPP. The aim is to maximize the number of items to be cut into the available area of the object in order to reduce waste and thus adding economic gains to the cutting process. In this approach the object and the items are represented as digital images. The GA is responsible for generating possible solutions (sets of translations and orientations of items). The evaluation of each solution generated by GA is performed by a RPID algorithm, which basically detects overlaps between the items placed on the object and calculates the quality of solution. To develop the proposed approach it was used the programming language C/C++ in addition to GAlib and Proeikon libraries. Based on computational experiments conducted the results indicate that the proposed approach is a good alternative to solve the problem investigated.