Algorithms for scheduling problems in grid

Author(s)

Robson Roberto Souza Peixoto

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2011-04-15

Examining board members

Eduardo Candido Xavier; Daniel Macêdo Batista; Edmundo Roberto Mauro Madeira

• Advisor: Eduardo Candido Xavier

Abstract

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-min (AU)

• FAPESP's process: 08/07589-1 - Algorithms for scheduling problems
• Grantee: Robson Roberto Souza Peixoto
• Support Opportunities: Scholarships in Brazil - Master