Algoritmos e modelos para problemas de corte e empacotamento

Resumo

Problemas de corte e empacotamento são frequentemente considerados como aplicações no mundo real. Ambas classes de problemas podem ser consideradas teoreticamente equivalentes, sendo que cortar um item de um recipiente pode ser equivalente a posicionar um item em um recipiente. Nesse projeto, nós consideramos problemas de empacotamento ortogonal, principalmente em suas versões bidimensionais e tridimensionais. Esses problemas consideram o posicionamento de hiper-retângulos chamados de items em hiper-retângulos maiores chamados de recipientes. Muitos dos problemas de empacotamento apresentados na literatura podem ser resolvidos por algoritmos que dependem de um problema de decisão, que determina a existência de um empacotamento de items factíveis dentro de um recipiente. Esse problema de decisão, chamado de orthogonal packing problem, é um problema NP-completo que vem sido estudado extensivamente na literatura. Ao melhor de nossos conhecimentos, a última survey em problemas de empacotamento bidimensional foi proposta a mais de uma década atrás. Desde então, a literatura mudou muito, no que diz respeito aos problemas de empacotamento bidimensional. Portanto, um dos objetivos deste projeto é propor um extenso estudo sobre problemas de empacotamento bidimensional, com o objetivo de escrever uma pesquisa abordando esses problemas. A partir deste extenso estudo, pretendemos também propor algoritmos e modelos eficientes para problemas de empacotamento bidimensionais e tridimensionais, principalmente para o orthogonal packing problem, com a motivação de que ele possa ser usado como uma sub-rotina para resolver outros problemas. Pretendemos fazer um extenso estudo computacional dos métodos propostos, para analisar sua eficiência, visando melhorar os resultados dos métodos propostos na literatura. (AU)