Abstract FR:

Cette these traite de l'ordonnancement de taches sur des machines paralleles. Nous considerons un ensemble de taches de durees quelconques, liees par des contraintes de precedente. Elles doivent s'executer sur des machines identiques, qui ne sont pas toutes disponibles a chaque instant (ordonnancement sur profil variable); elles peuvent etre interrompues (preemptee) puis reprises sur n'importe quelle machine, a tout moment. Le critere d'optimisation est la minimisation, soit de la date de fin de la derniere tache, soit du plus grand retard quand des dates d'echeance sont associees aux taches. On trouve ce genre de problemes en informatique parallele comme en gestion d'atelier de production: les notions de profil variable et de preemption permettent la prise en compte d'aleas comme les pannes de machines. Les methodes utilisees pour construire l'ordonnancement doivent egalement faire preuve de flexibilite face a ces aleas, aussi avons-nous choisi d'etudier les algorithmes de liste. Nous les adaptons aux profils variables, avant de mettre en evidence les sous-problemes pour lesquels ils fournissent une solution exacte. Nous effectuons une analyse de leurs performances dans le plus mauvais cas, et proposons une etude statistique de leur valeur moyenne. Enfin un algorithme de ce type est utilise pour le probleme de l'ordonnancement stochastique sur profil variable: les temps de service des taches suivent une meme loi exponentielle