Problemas de Alocação de Tarefas sob o Aspecto de Algoritmos e Teoria dos Jogos

• Processo: 08/03972-5
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2008
• Data de Término da vigência: 31 de agosto de 2009
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Eduardo Candido Xavier
• Beneficiário: Leandro Medina de Oliveira
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Problemas de programação de tarefas Teoria dos jogos Algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos | Alocação de Tarefas | Teoria de Jogos | Algoritmos

Resumo

Neste projeto estamos interessados em investigar problemas de alocação de tarefas em máquinas sob o aspecto de teoria dos jogos. Assumimos que as tarefas são controladas por seres autônomos e egoístas, no sentido de que buscam sempre a melhor solução para si. O problema de alocação de tarefas em máquinas é um problema computacional bem conhecido. Nos últimos anos, com o desenvolvimento da área de Algoritmos e Teoria dos Jogos, o problema tem recebido atenção dos pesquisadores segundo este foco. Sob o aspecto de teoria dos jogos assumimos que as tarefas são alocadas por seres autônomos (jogadores) que sempre buscam minimizar uma função objetivo local que representa uma atitude egoísta. As tarefas podem ser realocadas quantas vezes o ser autônomo precisar até atingir o seu ótimo local. Três questões surgem em relação a jogos deste tipo: 1) A alocação converge para um estado em que cada jogador não irá mais querer re-alocar sua tarefa? 2) Se tal estado de equilíbrio existir, qual o número de trocas máximo necessário para atingir o estado; e 3) Considerando uma função objetivo global, quão ruim é uma solução em equilíbrio em relação a uma solução ótima para o problema? O nosso objetivo neste projeto é o estudo de problemas de alocação de tarefas sob a ótica de Teoria dos Jogos. Também é nosso interesse a implementação de simuladores dos jogos estudados para avaliar resultados práticos com resultados teóricos existentes na literatura.