Submitted by Lara Oliveira (lara@ufersa.edu.br) on 2018-03-15T21:26:01Z
No. of bitstreams: 1
JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2018-06-18T16:59:44Z (GMT) No. of bitstreams: 1
JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2018-06-18T16:59:51Z (GMT) No. of bitstreams: 1
JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5) / Made available in DSpace on 2018-06-18T16:59:58Z (GMT). No. of bitstreams: 1
JonathanLS_DISSERT.pdf: 6143092 bytes, checksum: 68ad13bf204320bdcea5907ddb8d2102 (MD5)
Previous issue date: 2017-08-23 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / 2018-03-15 / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:bdtd.ufersa.edu.br:tede/841 |
| Date | 23 August 2017 |
| Creators | Silva, Jonathan Lopes da |
| Contributors | http://lattes.cnpq.br/7266011798625538, Aloise, Dario José, Lima Júnior, Francisco Chagas de, Liberalino, Carlos Heitor Pereira, Nascimento, Hugo Alexandre Dantas do |
| Publisher | Universidade Federal Rural do Semi-Árido, Programa de Pós-graduação em Ciência da Computação, UFERSA, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFERSA, instname:Universidade Federal Rural do Semi-Árido, instacron:UFERSA |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds