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

摘要

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.