Uma Heurística Baseada em Programação Dinâmica para o Problema de Corte Bidimensional

Abstract

Problemas de corte e empacotamento fazem parte do processo de planejamento da produção em muitas indústrias (e.g. papel, vidro, moveis). Em algumas dessas indústrias, um objeto retangular grande deve ser cortado em itens retangulares menores e existe uma capacidade limitada para o estoque dos itens. Nesse caso, surge o problema de corte bidimensional de alocação de objeto único restrito (2DSLOPP). Alguns autores têm proposto algoritmos de programação dinâmica para resolver o problema no caso irrestrito. Para o caso restrito essa técnica ainda apresenta alguns desafios devido à dimensão do espaço de estados. Nesse artigo propõem-se duas heurísticas baseadas em programação dinâmica e no método de Gilmore e Gomory para resolver o 2DSLOPP restrito considerando restrições especiais associadas ao equipamento de corte. São apresentados resultados do estudo computacional realizado com três conjuntos de instâncias que mostram a eficiência da proposta. Em particular para instâncias similares às encontradas na indústria moveleira foram obtidas soluções com gap máximo médio de 4.4%.

Keywords

• problema de corte bidimensional restrito
• programação dinâmica
• heurística