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
- 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
- Uma meta-heurística de busca decomposta em vizinhança variável para o problema bidimensional de agrupamento de entregas em veículos de uma frota heterogênea
- O problema do corte bidimensional
- Uma heurística de decisão baseada na subtração de cubos para solucionadores DPLL do problema de satisfabilidade
