Problemas de empacotamento

Os problemas de empacotamento são uma classe de problemas de otimização matemática que envolvem organizar um conjunto de itens dentro de um ou mais recipientes, procurando otimizar algum critério, como a minimização do número de recipientes utilizados ou o espaço desperdiçado. Estes problemas são frequentemente encontrados em contextos como logística, planeamento da produção, transporte de bens e design de circuitos eletrónicos.

Cada problema de empacotamento tem um problema dual que aborda questões relacionados com os mesmos objetos e aplicado à cobertura de cada local do contentor, onde os objetos se podem sobrepor.

Em geral, num destes problemas, consideram-se:

• O(s) contentor(es) (geralmente uma região convexa bidimensional ou tridimensional, ou um espaço infinito)
• Um conjunto de objetos, alguns ou todos se deverão colocar no interior do(s) contentor(es) de modo a ocupar o menor espaço possível, ou outro critério de otimização.

Em geral, o contentor ou embalagem bidimensional não deve ter sobreposições entre os objetos, que podem ser tangentes ou fronteiros aos limites do contentor. Em algumas variantes, o objetivo passa por encontrar a configuração ideal de empacotamento com a máxima densidade, ou então empacotar todos os objetos na menor quantidade de contentores possível.^[1] Em outras variantes, a sobreposição de objetos é permitida mas deve ser minimizada.

• Empacotamento de conjuntos
• Puzzle de Slothouber-Graatsma
• Puzzle de Conway
• Tetris
• Problema de cobertura
• Problema da mochila
• Problema do corte de valores
• Número de osculação
• Empacotamento compacto
• Empacotamento aleatório
• Problema do empacotamento em contentores

Referências