Meta-heurísticas para o problema de empacotamento colorido

• Processo: 20/06511-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2020
• Data de Término da vigência: 31 de agosto de 2021
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Rafael Crivellari Saliba Schouery
• Beneficiário: Renan Fernando Franco da Silva
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
• Assunto(s): Meta-heurística Otimização combinatória Problemas de corte e empacotamento
• Palavra(s)-Chave do Pesquisador: corte e empacotamento | meta-heurísticas | Otimização Combinatória | Otimização Combinatória

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.