Um método heurístico baseado em programação dinâmica para o problema de corte bidimensional guilhotinado restrito
AUTOR(ES)
Silveira, Rejane Joas, Morabito, Reinaldo
FONTE
Gestão & Produção
DATA DE PUBLICAÇÃO
2002-04
RESUMO
Neste artigo estudamos um caso particular dos problemas de corte, denominado problema bidimensional guilhotinado restrito (PGR). O PGR é um problema NP-difícil que aparece em diversos processos industriais de corte de chapas retangulares, em particular, na indústria de vidro e placas de circuito impresso. Para resolvê-lo, exploramos uma variação do método exato de CHRISTOFIDES & HADJICONSTANTINOU (1995), baseada numa relaxação do espaço de estados de uma formulação de programação dinâmica do PGR, num procedimento do tipo otimização do subgradiente, e numa heurística de factibilização. O resultado é um método sem garantia de otimalidade, porém bem mais rápido e capaz de resolver problemas maiores do que o método exato de Christofides e Hadjiconstantinou. O desempenho computacional do método é avaliado resolvendo-se diversos exemplos da literatura e exemplos aleatórios, e comparando-se as soluções obtidas com as de CHRISTOFIDES & HADJICONSTANTINOU (1995) e da conhecida heurística de WANG (1983).
ASSUNTO(S)
problema de corte padrões de corte bidimensionais guilhotinados restritos programação dinâmica heurísticas
Documentos Relacionados
- Uma Heurística Baseada em Programação Dinâmica para o Problema de Corte Bidimensional Guilhotinado 2-Estágios
- Um método heurístico baseado em relaxação Lagrangiana para o problema de carregamento de paletes do produtor
- Metodo para resolver um problema de programação linear dinamica
- Solução do problema de corte bidimensional de peças retângulares tipo não-guilhotinado usando simulated annealing
- Um metodo heuristico baseado em grafos para formação de celulas de manufatura em tecnologia de grupo