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 | Size | Format | |
---|---|---|---|---|
JonathanLS_DISSERT.pdf | 6 MB | Adobe PDF | ![]() View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.