Algoritmos de aproximação e online competitivos para problemas de escalonamento

• Processo: 20/06106-9
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2020
• Data de Término da vigência: 31 de dezembro de 2020
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Mário César San Felice
• Beneficiário: João Victor Mendes Freire
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Assunto(s): Algoritmos de aproximação Otimização combinatória Problemas de escalonamento Pesquisa operacional
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Algoritmos Online Competitivos | Otimização Combinatória | Problema de Escalonamento | Otimização Combinatória

Resumo

Em problemas de escalonamento, busca-se encontrar a melhor forma de distribuir tarefas que devem ser realizadas por máquinas, de forma a minimizar algum aspecto do processo de produção. Muitos desses problemas possuem grande dificuldade teórica, pois são NP-Difíceis, não existindo algoritmos que encontram a solução ótima em tempo polinomial, a não ser que P=NP. Eles também possuem grande relevância prática, advinda principalmente das áreas de Ciência da Computação e Pesquisa Operacional. Esse projeto de iniciação científica tem o objetivo de estudar algoritmos de aproximação e online competitivos para Problemas de Escalonamento, bem como implementar e testar alguns dos algoritmos estudados. Estamos particularmente interessados no problema do escalonamento em máquinas idênticas com o objetivo de minimizar o makespan, mas também podemos considerar outras versões do problema. Assim, o candidato será introduzido à pesquisa científica enquanto aprofunda seus conhecimentos em otimização combinatória e em técnicas de projeto e análise de algoritmos, complementando sua formação na área de Ciência da Computação.