Return to search

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

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2016-07-01T14:58:21Z
No. of bitstreams: 1
Marisa Carla Voigt Gava.pdf: 1946904 bytes, checksum: 369bf987709311eddcb1f66a7c5fad55 (MD5) / Made available in DSpace on 2016-07-01T14:58:21Z (GMT). No. of bitstreams: 1
Marisa Carla Voigt Gava.pdf: 1946904 bytes, checksum: 369bf987709311eddcb1f66a7c5fad55 (MD5)
Previous issue date: 2016-02-29 / 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. / O problema de corte consiste em cortar objetos maiores em itens menores com o objetivo de minimizar as sobras. Os objetos podem ser matérias-primas, tais como bobinas de papel, folhas de vidro, placas de metal, aço, alumínio ou madeira. Os itens representam o formato que deverá ser cortado e podem ser descritos como de geometrias irregulares côncavas ou convexas. O corte de matéria-prima é um processo industrial que tem atraído a atenção de muitos pesquisadores, visto que pode gerar grandes desperdícios, elevando o custo da produção. Não obstante, o conjunto de possíveis soluções para esse tipo de problema possui um grande número de combinações e, por esse motivo, sua complexidade computacional é considerada NP-Hard. Neste trabalho é proposta uma abordagem baseada em Algoritmo Genético (AG) e Processamento de Imagens Digitais para lidar com o problema de cortar placas retangulares (objetos) em peças idênticas (itens) com formas irregulares, categorizado na literatura como 2D-I-IIPP. O objetivo é maximizar o número de itens a serem cortados na área disponível do objeto, visando diminuir os desperdícios e, consequentemente, agregando ganhos econômicos ao processo de corte. Nesta abordagem tanto os objetos como os itens são representados como imagens digitais. O AG é responsável por gerar as possíveis soluções (conjuntos de translações e orientações dos itens). A avaliação de cada solução gerada pelo AG é realizada por um algoritmo de Processamento de Imagens Digitais que basicamente detecta as sobreposições entre os itens posicionados sobre o objeto e calcula a qualidade da solução. Para desenvolver a abordagem proposta foi utilizada a linguagem de programação C/C++, além das bibliotecas GAlib e Proeikon. Os resultados obtidos nos experimentos computacionais realizados indicam que a abordagem proposta é uma boa alternativa para solução do problema investigado.

Identiferoai:union.ndltd.org:IBICT/oai:localhost:tede/1483
Date29 February 2016
CreatorsGava, Marisa Carla Voigt
ContributorsAraújo, Sidnei Alves de, Araújo, Sidnei Alves de, Campos, Fernando Celso de, Librantz, Andre Felipe Henriques, Junqueira, Leonardo
PublisherUniversidade Nove de Julho, Programa de Mestrado em Engenharia de Produção, UNINOVE, Brasil, Engenharia
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguagePortuguese
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações da Uninove, instname:Universidade Nove de Julho, instacron:UNINOVE
Rightsinfo:eu-repo/semantics/openAccess
Relation2551182063231974631, 600

Page generated in 0.0028 seconds