Escalonamento de tarefas com localidade de dados em grids

Resumo

Este trabalho estuda os problemas de alocação de tarefas e replicação de dados em sistemas computacionais distribuídos conhecidos como Data Grids. Os dois problemas já foram extensivamente estudados de forma independente na literatura, mas estamos concentrados na análise integrada de ambos, de forma a otimizar uma única função objetivo. Ainda não são conhecidos resultados teóricos expressivos para essa abordagem, que tem sido alvo de pesquisa mais recente. Temos interesse tanto na análise teórica, ao avaliar a dificuldade do problema e suas variações e propor um algoritmo de aproximação (quando viável), bem como no aspecto prático, ao propor e experimentar novas heurísticas eficientes para o problema. Nossos resultados até o momento incluem uma formulação concisa usando programação linear inteira e um algoritmo com fator de aproximação constante para uma versão reduzida do problema. O objetivo final deste trabalho consiste em apresentar um algoritmo robusto que tenha desempenho comparável, se não melhor, que os resultados presentes na literatura. (AU)