New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Scheduling a set of Workflows on a grid with a genetic approach

SpeakerLamiel Toch

Co-authorLaurent Philippe

In this talk, we propose an approach to schedule a batch of jobs on an heterogeneous set of resources like a grid. Each job, is modeled by a workflow where each task is a functional box with several inputs but only one output. So the workflow can be represented by a directed acyclic graph (DAG) with typed tasks. Since tasks have only one output, DAGs are limited to in-trees. All of the grid hosts are able to process a set of task types with unrelated processing costs and are able to transmit files through heterogeneous network links. The objective is to minimize the makespan of the batch of jobs execution. To solve this problem we propose an extension of the GATS algorithm take the communication costs into account. The GATS algorithm is a genetic based scheduling algorithm designed to optimize the execution of single DAG-shaped jobs. We will show the contributions of our work which are both the experimental analysis of the GATS extension and the way we approached its design problems.