A two-step bicriteria scheduling approach for distributed real time systems

In this paper, we propose a scheduling approach to automatically generate a distributed schedule for parallel heterogeneous and distributed architectures. The approach is list scheduling heuristics based on two criteria: minimization of the schedule length (Makespan), and maximization of the system reliability. It is based on the hierarchization of the criteria, which allows the total ordering of the criteria and then the solving of the problem by optimizing one criterion at a time. The proposed strategy consists in transforming the bicriteria scheduling problem into two sub-problems each of them addressed by one heuristic. In the first heuristic, the reliability is considered as a constraint in order to produce an optimal value of Makespan. This one is then given as a constraint to the second heuristic whose objective is to find an optimal value of reliability.