µ BRKGA: um algoritmo genético paralelo de chaves aleatórias tendenciosas aplicado ao problema de posicionamento de figuras irregulares [Digital]
Tese
Português
681.3:004.021
Fortaleza, 2017.
O problema de posicionamento de figuras irregulares, também conhecido como Nesting Problem, tem sido estudado por várias décadas e constitui uma classe especial dos problemas de corte e empacotamento, cujo conjunto de itens com formatos arbitrários devem ser posicionados em uma superfície de encaixe...
Ver mais
O problema de posicionamento de figuras irregulares, também conhecido como Nesting Problem, tem sido estudado por várias décadas e constitui uma classe especial dos problemas de corte e empacotamento, cujo conjunto de itens com formatos arbitrários devem ser posicionados em uma superfície de encaixe com comprimento variável. Nesta tese, apresenta-se uma descrição das suas particularidades, destacando os desafios e algumas indústrias com aplicações relacionadas, por exemplo, a indústria naval, a de confecções e de couro. Isto é explanado por meio de uma revisão da literatura. Consideram-se, ainda, representações geométricas e métodos de resolução com estratégias distintas, objetivando o reconhecimento de oportunidades viáveis que possam ser abordadas de forma a encontrar soluções eficazes. Ademais, propõe-se uma abordagem (µ-BRKGA) composta por um algoritmo genético paralelo de chaves aleatórias tendenciosas para encontrar soluções compactas em tempos viáveis. Com o intuito de avaliar as soluções, aplica-se um método de posicionamento fundamentado na região livre de colisão formando leiautes de encaixes satisfatórios. Todo o processo é divido em três etapas: pré-processamento, execução do algoritmo e escolha da melhor solução. Como forma de verificação da eficiência do µ-BRKGA, submeteu-se a abordagem sobre testes computacionais nas instâncias de referência, comumente utilizadas na literatura, e os resultados obtidos foram analisados e comparados a outras pesquisas de notório impacto para a resolução do problema de posicionamento de figuras irregulares.
Palavras-chave: problema de posicionamento de figuras irregulares, algoritmos genéticos, chaves aleatórias, região livre de colisão, polígono de obstrução.
Ver menos
Palavras-chave: problema de posicionamento de figuras irregulares, algoritmos genéticos, chaves aleatórias, região livre de colisão, polígono de obstrução.
Ver menos
The Irregular Strip Packing Problem, also known as Nesting Problem, has been studied for several decades and constitutes a special class of cutting and packing problems, whose set of arbitrary shape items must be positioned on a container with variable length. In this thesis, presents a description...
Ver mais
The Irregular Strip Packing Problem, also known as Nesting Problem, has been studied for several decades and constitutes a special class of cutting and packing problems, whose set of arbitrary shape items must be positioned on a container with variable length. In this thesis, presents a description of its particularities, highlighting the challenges and some industries with related applications, for example, the shipbuilding, clothing and leather. This is explained by literature review. We also consider geometric representations and methods of resolution with distinct strategies, aiming at the recognition of viable opportunities that can be approached in order to find effective solutions. In addition, we propose an approach (µ-BRKGA) composed by a parallel biased random-key genetic algorithm to find compact solutions in viable times. In order to evaluate the solutions, a positioning method based on the collision-free region is applied, forming satisfactory layouts. The entire process is divided into three stages: pre-processing, execution of the algorithm and choosing the best solution. With the purpose of evaluate the proposed (µ-BRKGA) algorithm, computational tests using benchmark problems, commonly used in the literature, were applied and the results obtained were analyzed and compared to other research of notable impact to solve the irregular strip packing problem.
Keywords: irregular strip packing problem, genetic algorithms, random keys, collision-free region, no-fit polygon. Ver menos
Keywords: irregular strip packing problem, genetic algorithms, random keys, collision-free region, no-fit polygon. Ver menos
Disponibilidade forma física: Existe obra impressa de código : 102191
Amaro Júnior, Bonfim
Autor
Pinheiro, Plácido Rogério
Orientador
Pinheiro, Plácido Rogério
Banca examinadora
Thomaz, Antônio Clécio Fontelles
Banca examinadora
Toledo, Franklina Maria Bragion de
Banca examinadora
Campos, Gustavo Augusto Lima de
Banca examinadora
Nepomuceno, Napoleão Vieira
Banca examinadora