Paper Info
Title
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.
Year
DOI
Venue
2012
10.1080/17445760.2011.590487
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
Keywords
Field
DocType
batch scheduling, heterogeneous platform, list-based scheduling, steady-state scheduling, genetic algorithm
Fork (system call),Job shop scheduling,Scheduling (computing),Computer science,Directed acyclic graph,Job scheduler,Workflow,Grid,Genetic algorithm,Distributed computing
Journal
Volume
Issue
ISSN
27
1
1744-5760
Citations 
PageRank 
References 
2
0.38
27
Authors
4
Name
Order
Citations
PageRank
Sékou Diakité141.11
Jean-Marc Nicod29518.10
Laurent Philippe37112.95
Lamiel Toch4132.40