Made available in DSpace on 2019-03-30T00:02:28Z (GMT). No. of bitstreams: 0
Previous issue date: 2017-08-08 / 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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.unifor.br:tede/102074 |
| Date | 08 August 2017 |
| Creators | Amaro Junior, Bonfim |
| Contributors | Pinheiro, Plácido Rogério, Pinheiro, Plácido Rogério, Thomaz, Antônio Clécio Fontelles, Toledo, Franklina Maria Bragion de, Campos, Gustavo Augusto Lima de, Nepomuceno, Napoleao Vieira |
| Publisher | Universidade de Fortaleza, Doutorado Em Informática Aplicada, UNIFOR, Brasil, Centro de Ciências Tecnológicas |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UNIFOR, instname:Universidade de Fortaleza, instacron:UNIFOR |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 1028774923510350190, 500, 500, -7645770940771915222 |
Page generated in 0.0023 seconds