Algoritmos híbridos para o problema de corte bidimensional

Abstract

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