Scheduling strategies for the bicriteria optimization of the robustness and makespan

In this paper we study the problem of scheduling a stochastic task graph with the objective of minimizing the makespan and maximizing the robustness. As these two metrics are not equivalent, we need a bicriteria approach to solve this problem. Moreover, as computing these two criteria is very time consuming we propose different approaches: from an evolutionary meta-heuristic (best solutions but longer computation time) to more simple heuristics making approximations (bad quality solutions but fast computation time). We compare these different strategies experimentally and show that we are able to find different approximations of the Pareto front of this bicriteria problem.

1 Introduction

The problem of scheduling an application modeled by a task graph with the objective to minimize its execution time is a well studied problem [6], [9]. However, in general the duration of the tasks that compose the application and the communications between these tasks are subject to some uncertainties (due to the unpredictability of the behavior of the application and its sensitiveness of the input data). A schedule is said robust if it is able to absorb part of the uncertainty and gives an allocation whose duration (makespan) is still close to a predicted value.