Detalhes bibliográficos
| Ano de defesa: |
2017 |
| Autor(a) principal: |
Velasco, André Soares |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Tese
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Não Informado pela instituição
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://app.uff.br/riuff/handle/1/7644
|
Resumo: |
O presente trabalho tem como objetos de estudo dois tipos de Problemas de Corte e Empacotamento, conhecidos na literatura como Problema de Corte Bidimensional Guilhotinado Restrito (PCBGR) e Problema de Corte de Estoque Bidimensional Guilhotinado (PCEBG), ambos pertencendo à classe NP-difícil, nos casos com e sem rotação de itens. Esses problemas possuem grande aplicabilidade em diversos setores produtivos que consideram as ações de corte na transformação de materiais em produtos semiacabados ou finais, tais como: metal mecânico, moveleiro, rochas ornamentais, entre outros. Primeiramente, são apresentadas as contribuições para o PCBGR: o algoritmo RG2D, fundamentado no Reactive Greedy Randomized Adaptive Search Procedure (GRASP Reativo) e implementado a partir de melhorias feitas no algoritmo GRASP-2D (G2D), para tratar o problema em destaque; o algoritmo X, baseado em Programação Inteira e capaz de provadamente obter os pesos ótimos para a relaxação de espaço de estados da Programação Dinâmica proposta em (CHRISTOFIDES; HADJICONSTANTINOU, 1995); o algoritmo X2, proposto como uma generalização de X que usa pesos bidimensionais para obter limites ainda mais fortes; o algoritmo X2H que consiste na adaptação de X2 para transformá-lo em uma heurística primal; o método X2D, resultante da combinação desses quatro elementos, foi testado em um grande conjunto de instâncias e mostrou ser capaz de encontrar soluções com garantias de qualidade ou mesmo certificado de otimalidade nas variantes com e sem rotação dos itens. A seguir, tendo como objeto de estudo o PCEBG, as contribuições são: a proposta de um algoritmo híbrido que combina a técnica de Geração de Colunas com Programação Dinâmica e o novo algoritmo RG2D. Os resultados computacionais obtidos até o momento foram bastante positivos. Em todas as instâncias testadas as soluções encontradas nunca ficaram mais do que 1 unidade além do limite inferior dado pela Geração de Colunas |
