Assessing new approaches to schedule a batch of identical intree-shaped workflows on a heterogeneous platform

Abstract : In this paper, we consider the makespan optimisation when scheduling a batch of identical workflows on a heterogeneous platform as a service-oriented grid or a micro-factory. A job is represented by a directed acyclic graph (DAG) with typed tasks and no fork nodes (in-tree precedence constraints). The processing resources are able to process a set of task types, each with unrelated processing cost. The objective function is to minimise the execution makespan of a batch of identical workflows while most of the works concentrate on the throughput in this case. Three algorithms are studied in this context: a classical list algorithm and two algorithms based on new approaches, a genetic algorithm and a steady-state algorithm. The contribution of this paper is both on the adaptation of these algorithms to the particular case of batches of identical workflows and on the performance analysis of these algorithms regarding the makespan. We show the benefits of their adaptation, and we show that the algorithm performance depends on the structure of the workflow, on the size of the batch and on the platform characteristics.
Type de document :
Article dans une revue
International Journal of Parallel, Emergent and Distributed Systems, Taylor & Francis, 2011
Liste complète des métadonnées

https://hal.inria.fr/hal-00786236
Contributeur : Equipe Roma <>
Soumis le : vendredi 8 février 2013 - 10:42:25
Dernière modification le : jeudi 7 mars 2013 - 11:28:30

Identifiants

  • HAL Id : hal-00786236, version 1

Collections

Citation

Sékou Diakité, Jean-Marc Nicod, Laurent Philippe, Lamiel Toch. Assessing new approaches to schedule a batch of identical intree-shaped workflows on a heterogeneous platform. International Journal of Parallel, Emergent and Distributed Systems, Taylor & Francis, 2011. <hal-00786236>

Partager

Métriques

Consultations de la notice

186