New Challenges on Scheduling Theory

Co-authorsEmmanuel Jeannot

We are considering the problem of scheduling task graphs when computation and communication durations are subject to uncertainties. The main objective is thus to minimize the makespan while 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 metaheuristic (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.