Please use this identifier to cite or link to this item: http://repositorio.ufersa.edu.br/handle/prefix/846
Type: Dissertação
Title: Contribuições em otimização combinatória para o problema de corte bidimensional guilhotinado não-estagiado
Authors: Silva, Jonathan Lopes da
First Advisor: Aloise, Dario José
First member of the board: Lima Júnior, Francisco Chagas de
Second member of the board: Liberalino, Carlos Heitor Pereira
Third member of the board: Nascimento, Hugo Alexandre Dantas do
Resume: Os problemas de corte de materiais são recorrentes no cotidiano da indústria, sendo encontrados nas mais diferentes formas.Oproblema de corte bidimensional guilhotinado é uma dessas formas. Ele surge pelas restrições da ferramenta de corte, tipicamente a guilhotina. Este trabalho apresenta três abordagens para solucionar o problema em questão: uma abordagem matemática, uma abordagem exata computacional e uma abordagem heurística. A abordagem matemática consiste em um modelo de programação linear baseado em listas de itens e montagem do arranjo de corte partindo dos itens, unindo-os dois a dois, tentando maximizar o número de uniões sem ultrapassar as dimensões da placa. A abordagem exata computacional tratá-se de um algoritmo Branch-and-Bound modificado para permitir que estados mais promissores possam ser analisados antes, comportando-se como um algoritmo de busca em profundidade com uma pequena etapa em largura, na qual ordena os filhos na árvore de decisão pelo desperdício gerado. Por fim, a abordagem heurística é composta das metaheurísticas GRASP, Busca Tabu, Algoritmo Genético, BRKGA e Religação de Caminhos combinados com uma heurística de montagem baseada nos algoritmos propostos por Nascimento, Longo e Aloise (1999). Essas metaheurísticas foram combinadas em um time assíncrono para alcançar melhores resultados que os já encontrados na literatura. Além de melhorar os resultados conhecidos, a pesquisa também tinha como objetivo apresentar um modelo viável, em número de variáveis, e resultados ótimos para instâncias comumente utilizadas para o problema supracitado e novas opções de obtê-los em instâncias que venham a surgir no futuro. Testes mostraram a competividade dos algoritmos propostos frente aos melhores resultados encontrados, reduzindo inclusive o número total de placas, bem como a capacidade dos métodos exatos propostos de encontrar as soluções ótimas para as instâncias testadas. Cerca de de 25% dos resultados ótimos foram encontrados, passando esse número para 75%, quando considerados os resultados dos algoritmos metaheurísticos que atingiram o limite inferior das instâncias
Keywords: Corte bidimensional guilhotinado
Programação linear
Branch and bound
Metaheurística
Time assíncrono (A-Team)
Two-dimensional guillotined cutting
Linear programming
Branch and bound
Metaheuristics
Asynchronous team (A-Team)
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA
Language: por
Country: Brasil
Publisher: Universidade Federal Rural do Semi-Árido
Institution Initials: UFERSA
Program Name: Programa de Pós-graduação em Ciência da Computação
Citation: SILVA, Jonathan Lopes da. Contribuições em otimização combinatória para o problema de corte bidimensional guilhotinado não-estagiado. 2017. 128 f. Dissertação (Mestrado em Ciência da Computação), Universidade Federal Rural do Semi-Árido, Mossoró, 2017.
Access Type: Acesso Aberto
URI: http://repositorio.ufersa.edu.br/handle/prefix/846
Issue Date: 23-Aug-2017
License Term: CC-BY-SA
Appears in Collections:Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
JonathanLS_DISSERT.pdf6 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.