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

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