Meta-heurísticas para o problema de empacotamento colorido

Resumo

O Problema do Empacotamento consiste em: dado um conjunto de itens de tamanhos diversos, temos como objetivo empacotar os mesmos em recipientes com capacidade limitada minimizando a quantidade de recipientes utilizados. Uma generalização para o Problema do Empacotamento é o Problema do Empacotamento Colorido, no qual além de cada item ter um tamanho, o mesmo também possuí uma cor, sendo que dois itens de mesma cor não podem ser empacotados lado a lado em um mesmo recipiente. Ambos os problemas pertencem a classe NP-difícil, ou seja, não existem algoritmos que os resolvam de forma exata em tempo polinomial, a menos que P = NP. Visto que, em geral, algoritmos não polinomiais são demasiadamente custosos, se sustenta o uso de meta-heurísticas para a solução de problemas NP-difícil, nas quais costumam entregar soluções próximas da ótima em tempo computacionalmente razoável. Neste projeto será estudado meta-heurísticas para o Problema do Empacotamento Colorido, abordagem esta ainda inexplorada na literatura. Ademais, o projeto também visa introduzir o candidato no ramo da pesquisa científica, além de complementar a sua graduação.