Busca avançada
Ano de início
Entree

Meta-heurísticas para o problema de empacotamento colorido

Processo: 20/06511-0
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de setembro de 2020
Vigência (Término): 31 de agosto de 2021
Área do 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

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.