Grades computacionais são sistemas distribuídos compartilhados potencialmente grandes compostos por recursos heterogêneos ligados através de uma rede com enlaces heterogêneos. Esses sistemas tornaram-se ambientes largamente difundidos para execução de tarefas que demandam alta capacidade de processamento. Por serem sistemas compartilhados, a submissão de tarefas nas grades é oriunda de diversos usuários independentemente, o que gera uma demanda concorrente pelos recursos computacionais que deve ser gerenciada pelo middleware da grade. O escalonador é o componente responsável por decidir de que forma a distribuição dessas tarefas será realizada, devendo tratar das peculiaridades desse ambiente, tais como a heterogeneidade e o comportamento dinâmico dos recursos que o compõem, com variações tanto em quantidade quanto em qualidade. A função objetivo mais comum encontrada no escalonamento de tarefas é a minimização do makespan, o que significa que o escalonador tenta minimizar o tempo de término de todas as tarefas que estão sendo escalonadas. Dentre os possíveis tipos de tarefas executadas em grades podemos destacar as tarefas independentes, que executam sem comunicação entre si, e as tarefas dependentes, que possuem dependências de dados que geram precedências de execução. Tarefas dependentes são freqüentemente modeladas como grafos acíclicos direcionados (DAGs - do inglês directed acyclic graphs), dentre as quais as aplicações de e-Ciência se sobressaem pela complexidade e necessidade crescente de recursos computacionais. Adicionalmente, o problema de escalonamento de tarefas, em sua forma geral, é NP-Completo, portanto não há algoritmo conhecido que gere soluções determinísticas ótimas em tempo polinomial. Dessa forma, o estudo do escalonamento de tarefas dependentes representadas por grafos acíclicos direcionados em grades computacionais é importante para o aprimoramento da execução de aplicações científicas utilizadas em diversas áreas do conhecimento.

O tema principal desta tese é o problema de escalonamento de tarefas dependentes representadas por DAGs em grades computacionais. Mais especificamente, apresentamos algoritmos para quatro tipos de problema. O primeiro é o escalonamento estático de DAGs, onde o escalonador realiza o processo de escalonamento com informações adquiridas antes do início do escalonamento. O segundo problema abordado é o escalonamento dinâmico, onde o escalonador utiliza informações atualizadas durante o processo de escalonamento para tomar decisões. O terceiro problema é o escalonamento bi-critério, onde a função objetivo do escalonador visa a otimização de dois critérios. O quarto problema é o escalonamento de múltiplos DAGs no mesmo conjunto de recursos. Além de algoritmos para esses problemas, apresentamos avaliações do makespan gerado em cada um deles após o escalonamento inicial e após a execução das tarefas com carga externa simulada nos recursos.