Algorithme d’ordonnancement optimal basé sur la programmation dynamique pour les applications aux données parallèles sur des plates-formes hétérogènes

This report discusses a new algorithm for makespan minimization on situations where the workload can be partitioned among heterogeneous resources. Without making any assumptions regarding the behavior or shape of the functions giving the execution time on a resource, we are able to provide optimal solutions with a dynamic programming algorithm in O(T^2n) for a workload of T tasks and n heterogeneous resources. This report includes a short state of the art, the problem's model, the algorithm, and its optimality proof.Ce rapport discute d'un nouvel algorithme pour la minimisation du makespan dans des situations où la charge de travail peut être partitionnée entre des ressources hétérogènes. Sans faire aucune hypothèse sur le comportement ou la forme des fonctions donnant le temps d'exécution sur une ressource, nous sommes capables de fournir des solutions optimales avec un algorithme de programmation dynamique en O(T^2n) pour une charge de travail de T tâches et n ressources hétérogènes.Ce rapport comprend un bref état de l'art, le modèle du problème, l'algorithme, et sa preuve d'optimalité