Um Simulated Annealing no Problema do Corte Unidimensional Inteiro

Resumo

O presente trabalho trata o Problema do Corte Unidimensional Inteiro (PCUI). De- vido a sua vasta aplicabilidade nas metalúrgicas, indústrias têxtil, m´oveis, papel, alumínio, etc, este problema ´é um dos mais estudados em Otimização Combinatória. Embora seja facilmente entendido, o PCUI ´e altamente complexo de ser resolvido, devido a natureza e o número de variáveis envolvidas mesmo para pequenas instâncias, tornando inviável a aplicação direta dos algoritmos exatos do tipo Branch. Por este motivo, aplicou-se a metaheur´ıstica Simulated An- nealing (SA), com alguma modificações em relação ao proposto em [10], para resolvê-lo. Para tanto, duas heurísticas para (i) construir padrões de corte e (ii) soluções admissíveis para o problema, foram desenvolvidas. Para validá-las, gerou-se 1800 problemas testes e comparou-se a qualidade das soluções do m´método proposto com a solução do Problema Linear Inteiro (PLI) ob- tido com os padrões gerados pelo consagrado m´método de Geração de Colunas (GC) desenvolvido por [5]. Os resultados mostraram uma boa performance e robustez do m´método proposto, obtendo soluções sub-´ótimas num razoável tempo computacional.