O Problema de Cutting Stock (PCS) é um problema clássico de otimização combinatória, caracterizado por pertencer à classe NP-difícil e servir de modelo para inúmeras aplicações de relevância prática ou téorica. Este trabalho investiga um procedimento de Busca Local (BL) para o PCS. Mais especificamente, uma BL que resulta da incorporação de Restrições de Soft Fixing (RSF) ao algoritmo padrão de Geração de Colunas aplicado ao problema. O procedimento foi testado em 1600 instâncias geradas artificialmente, tendo a formulação de Kantorovich como base de obtenção do valor ótimo dessas instâncias. Nos testes empíricos que conduzimos, a aplicação da metodologia resultou em melhores soluções viáveis para 44% das instâncias ainda sem valores ótimos conhecidos. Além disso, obteve soluções ótimas para 3% destas. Da mesma forma, o método se mostrou eficaz tanto na quantidade de soluções que conseguiu aprimorar quanto no tempo de execução. Embora apresente um custo computacional um pouco maior em comparação ao uso do algoritmo de Geração de Colunas de forma isolada, esse aumento é compensado pelos ganhos em qualidade das soluções. Em particular, a RSF que se mostrou mais atraente em nossos experimentos computacionais, combinou menores tempos de execução com um maior número de soluções que conseguiu melhorar. Nossos resultados indicam que a estratégia proposta é promissora para instâncias do PCS empiricamente mais difíceis de se resolver.
.png)
.png)
