Mohamad EL SAYAH : "Génération Aléatoire pour l'Évaluation de Performance d'Algorithmes d'Ordonnancement

Travaux de thèse de Mohamad EL SAYAH : "Génération Aléatoire pour l'Évaluation de Performance d'Algorithmes d'Ordonnancement"

Résumé :

L’objectif du travail réalisé dans cette thèse consiste à mettre au point des techniques pour l’évaluation de la performance d’algorithmes dans le contexte de l’ordonnancement. Dans de nombreuses branches de la recherche en informatique, de très nombreuses publications mettent en avant de nouveaux algorithmes évalués comme plus performants que les précédents; mais le protocole expérimental utilisé est souvent mal ou trop peu décrit, voire biaisé, ne permettant ni une reproductibilité des résultats, ni de donner une confiance suffisante sur l’ampleur de l’amélioration. Cela suppose d’analyser finement les problèmes considérés afin de définir ce que peuvent être des instances pertinentes. Dans cette thèse nous étudions deux types d’instances, les DAGs et les matrices de coûts. Pour chaque type nous étudions un problème d’ordonnancement différent. Nous étudions des propriétés qui ont tendances à influencer la structure des instances générées aléatoirement, puis analysons des méthodes existantes de génération aléatoire vis-à-vis des propriétés sélectionnées. Ensuite, nous proposons un générateur aléatoire capable de générer de façon uniforme des instances tout en contrôlant leurs hétérogénéités, puis nous analysons l’impact des générateurs étudiés sur la performance de certaines heuristiques d’ordonnancement.

Composition du jury :

M. Beaumont Olivier, Directeur de recherche à Inria Bordeaux - Sud-Ouest, Rapporteur
M. LEGRAND Arnaud, Directeur de recherche à CNRS Grenoble, Rapporteur
M. NICOD Jean-Marc, Professeur à l’ENSMM Besançon, Examinateur
Mme DUFOSSÉ Fanny, Chargée de recherche à Inria Grenoble, Examinatrice
M. CANON Louis-Claude, Maître de Conférences à l'Université de Franche-Comté, Co-directeur de thèse
M. HÉAM Pierre-Cyrille, Professeur à l'Université de Franche-Comté, Directeur de thèse

Localisation : Amphithéâtre B, Bâtiment B de l'UFR Sciences et Techniques - 16, Route de Gray - 25000 Besançon