Algorithms for scheduling problems in grid

Orientador: Eduardo Candido XavierDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Nesta dissertação estudamos algoritmos para resolver problemas de escalonamento de tarefas em grades computacionais. Dado um conjunto de tarefas submetidas a uma grade computacional, deve-se definir em quais recursos essas tarefas serão executadas. Algoritmos de escalonamento são empregados com o objetivo de minimizar o tempo necessário para executar todas as tarefas (makespan) que foram submetidas. Nosso foco é estudar os atuais algoritmos de escalonamento usados em grades computacionais e comparar estes algoritmos. Nesta dissertação apresentamos algoritmos onlines, aproximados e heurísticas para o problema. Como resultados novos, provamos fatores de aproximação para o algoritmo RR quando utilizado para resolver os problemas R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax e R; sit|Tj = L|TPCC é justo. Por fim, definimos uma interface que adiciona replicação de tarefas a qualquer algoritmo de escalonamento, onde nós mostramos a aproximação desta interface, e apresentamos uma comparação via simulação dos algoritmos sem e com replicação. Nossas simulações mostram que, com a utilização de replicação, houve a redução no makespan de até 80% para o algoritmo Min-min. Nas nossas análises também fazemos uso da métrica RTPCC que calcula exatamente a quantidade de instruções que foram usadas para executar todas as tarefasAbstract: In this dissertation, we studied algorithms to solve task scheduling problems in computational grids. Given a task set that was submitted to a computational grid, the problem is to define in which resources these tasks will be executed and the order they will be executed. Scheduling algorithms are used in order to minimize the time required to execute all tasks (makespan). We studied the most recent scheduling algorithms proposed to be used in computational grids, and then compare them using simulations. In this dissertation we also present approximate algorithms and new heuristics for the problem. As new results, we proved approximation factors to the RR algorithm when applied to solve the problems R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax and R; sit|Tj = L|TPCC. Finally, we defined an interface that adds task replication capability to any scheduling algorithm. We then show approximation results for algorithms using this interface, and present a comparison of well know algorithms with and without replication. This comparison is done via simulation. Our simulations show that, with replication, there was up to 80% of reduction in the makespan to some algorithms like the Min-minMestradoTeoria da ComputaçãoMestre em Ciência da Computaçã