Problema de empacotamento em faixa com restrições de ordem e estabilidade / Strip packing problem with constraints in order and stability

AUTOR(ES)

Fabrício Luis Santos da Silva

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

17/12/2010

RESUMO

Neste trabalho lidamos com o problema de Empacotamento em Faixa Bidimensional considerando o caso em que os itens devem ser dispostos de forma a manter o empacotamento estável e satisfazer uma ordem de descarregamento imposta. Consideramos o caso em que a orientação dos itens é fixa. Definimos uma metodologia para analisar a estabilidade do empacotamento observando as condições de equilíbrio estático para corpos rígidos. Desenvolvemos heurísticas e formulamos um programa linear inteiro para o problema de Empacotamento em Faixa sujeito a tais restrições. A resolução da formulação inteira ocorre através de uma estratégia do tipo branch-and-cut. As restrições de estabilidade foram inseridas como planos de corte de maneira a remover empacotamentos que não são estáveis. Em nossos experimentos computacionais, vemos que o modelo proposto é adequado para lidar com instâncias de pequeno até médio porte, dentro de um tempo computacional razoável.

ASSUNTO(S)

problema de empacotamento programação inteira otimização combinatória algoritmos packing problem integer programming combinatorial optimization algorithms

Documentos Relacionados

• Algoritmos de aproximação para problemas de empacotamento em faixa com restrições de descarregamento
• O problema do caixeiro viajante com restrições de empacotamento tridimensional
• Um algoritmo exato para o problema de empacotamento bidimensional em faixas
• Empacotamento em quadráticas
• Algoritmos para resolução do problema de empacotamento de conjuntos utilizando poliedros quase inteiros