Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas

Resumo

Nesse projeto de pesquisa pretendemos contribuir para o avanço científico na área de Otimização Combinatória focando, em particular, em problemas de corte e empacotamento.Tais problemas foram introduzidos por Kantorovich em 1939 e Brooks et al. em 1940 com aplicações na indústria em mente e são muito comuns em situações onde é necessário cortar materiais (como metal, vidro, papel, etc) em itens menores para se atender uma determinada demanda ou quando é necessário realizar o carregamento de veículos e contêineres. Outras aplicações para problemas de corte e empacotamento incluem o escalonamento de tarefas computacionais e a divulgação de propagandas em páginas da internet.Apesar de muito comuns, mesmo as versões simples de problemas de corte e empacotamento são NP-difícieis, isto é, não existem algoritmos para tais problemas que encontram soluções ótimas em tempo polinomial, a menos que P=NP. Assim, em vista da importância prática de tais problemas, é necessário resolver problemas de corte e empacotamento, obtendo soluções ótimas ou próximas de soluções ótimas, dentre de um limite de tempo aceitável, já que, na prática, é comum termos urgência no cálculo da solução. Devida a complexidade dos problemas considerados neste projeto, faz-se necessário propor novos algoritmos exatos, de aproximação e heurísticas e adaptar técnicas já utilizadas com sucesso em outros problemas para obter novos patamares na resolução de tais problemas. (AU)