Module : Théorie de l'approximabilité et théorie de l'ordonnancement. CODE UMINR319
Responsable
R. Giroudeau et S. Durand
Parcours intégrant UV
aucun.
Parcours possibles
tous. UE conseillée pour le parcours ACR.
Pré-Requis
Controle connaissances
3
Description de l'UE :
Semestre
Code
Intitulé
Cours
TD
TP
TER
S3
UMINR319
Théorie de l'approximabilité et théorie de l'ordonnancement
15
-
-
Detail du programme
Objectifs : Contenu :
Une des solutions proposées pour faire face aux problèmes NP-difficiles est de construire des algorithmes polynomiaux approchés
avec garantie de performance. Il est possible, selon le type de garantie obtenu de classifier les problèmes et les algorithmes
approchés. Ainsi, le développement récent de la théorie de l'approximabilité peut être considéré comme un prolongement naturel
de la théorie de la complexité en optimisation combinatoire. Cette classification sera illustrée à l'aide de nombreux exemples
(min vertex cover, max stable, sac-à-dos, ?). Nous verrons ensuite comment cette théorie peut s'appliquer pour des problèmes
d'ordonnancement.
La théorie de l'ordonnancement s'intéresse à l'allocation optimale des différentes parties d'une application sur les ressources
machines afin que l'application soit accomplie le plus rapidement et/ou au moindre coût. Devant la diversité des machines
parallèles existantes et dans un souci d'indépendance de la machine cible, nous avons essayé de classifier et d'étudier les
modèles de machines en prenant en compte les paramètres les plus importants des systèmes considérés (architectures parallèles,
réseaux hiérarchiques, etc.).
Exemple : On considère une équipe de cinq astronautes qui se préparent à faire une sortie dans l'espace. Ils doivent effectuer
un certain nombre de tâches. Chaque tâche ne peut être " faite " que par un seul astronaute, et certaines tâches ne peuvent
se faire qu'après que certaines tâches se soient terminées. Quelle tâche devra être traitée par quel astronaute pour que l'ensemble
des tâches soit traité le plus tôt possible ?
Dans ce cours, nous intéressons dans un premier temps aux problèmes d'ordonnancement sans communications tant au niveau de
la complexité qu'au niveau de l'approximabilité. Ensuite nous introduirons les délais de communications entre deux tâches
adjacentes du graphe de précédence modélisant une application, et nous allons mesurer l'impact de l'introduction des délais
de communications sur la complexité et l'approximation des problèmes d'ordonnancement.
Mots clés : ordonnancement avec et sans communications, Np-complétude, approximabilité,
