Uma Heurística Baseada em Programação Dinâmica para o Problema de Corte Bidimensional Guilhotinado 2-Estágios
AUTOR(ES)
ASSIS, N. S.; RANGEL, S.
FONTE
Trends in Computational and Applied Mathematics
DATA DE PUBLICAÇÃO
2022
RESUMO
RESUMO Problemas de corte e empacotamento fazem parte do processo de planejamento da produção em muitas indústrias (e.g. papel, vidro, móveis). 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 contexto, surge o problema de corte bidimensional guilhotinado 2-estágios restrito (PCBG-2est). 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 PCBG-2est restrito. 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%.
Documentos Relacionados
- Um método heurístico baseado em programação dinâmica para o problema de corte bidimensional guilhotinado restrito
- Teste de uma heurística para o problema de programação de trens em linhas singelas
- Solução do problema de corte bidimensional de peças retângulares tipo não-guilhotinado usando simulated annealing
- Uma heurística baseada em geração sequencial de padrões para o problema de corte de estoque unidimensional com um número reduzido de padrões
- Abordagem heurística para o problema de programação de horários de cursos