NB: cette page montre la progression pour
l'année 2011-2012; elle sera mise à jour dès le
début des cours pour l'année 2012-2013.
Sauf mention contraire, les documents présentés sur cette page sont en anglais, au format PDF.
Présentation du cours: transparents
Cours 1: Introduction à l'ordonnancement, ordonnancement sur une machine (14 septembre)
- notes du cours
- transparents [ppt] de l'exposé "Complexity of scheduling" par Peter Brucker, lors d'EPIT 2007
- une classification très complète des problèmes d'ordonnancement: Complexity results for scheduling problems
Cours 2: Ordonnancement sur machines parallèles (21 septembre)
- notes du cours
- Les cours sur P||Cmax et les ordonnancement de liste d'où proviennent la plupart des résultats vus en cours
Cours 3: Ordonnancement de tâches divisible: réseau de type bus et étoile (28 septembre)
Cours 4: Ordonnancement de tâches divisible: réseaux hiérarchiques (arbres) et ordonnancement à plusieurs tournées (5 octobre)
- notes du cours
- un rapport de recherche avec la plupart des résultats vus en cours sur les tâches divisibles
Cours 5: Ordonnancement en régime permanent (12 octobre)
- notes du cours
- l'article de D. Bertsimas et D. Gamarnik sur le routage de paquets (première partie du cours)
- un article pour une opération de distribution de paquets (proche de la seconde partie du cours mais sans calcul)
- un rapport de recherche très complet pour l'ordonnancement de graphes de tâches en régime permanent
Cours 6: Dynamicité des plates-formes et robustesse des ordonnancements (19 octobre)
- notes du cours ou transparents (même contenu)
- l'article sur l'instabilité de l'ordonnanceur backfilling en présence de rafales de tâches
- l'article sur les ordonnancements maximisant le nombre de tâches prêtes (Internet-based Computing)
- l'article sur l'utilisation d'information ancienne pour l'ordonnancement
Cours 7: Ordonnancement en-ligne (3 novembre)
- slides à venir, voir la page du cours de l'an dernier (lien ci-dessous)
Cours 8: Ordonnancement multi-organisations (16 novembre)
- article sur l'ordonnancement multi-organisation sans coopération
- article présentant l'ordonnancement multi-organisation avec coopération
- Un article de S. Toledo sur la multiplication de matrices et la minimisation du nombre de communication (partie 2.1)
- L'article de R. Sethi (1973) sur le problème d'allocation de registre (version homogène).
- Un article J. Liu sur la version hétérogène de la minimisation de la mémoire dans le cas d'un arbre.
- Notes [fr] sur la partie gestion d'un cache de pages
- Transparents sur la partie minimisation de l'énergie (Guillaume Aupy) et le rapport de recherche correspondant.
- Ce cours est inspiré du chapitre "Algorithmic Game Theory and Scheduling" dans le livre "Handbook of Approximation Algorithms and Metaheuristics", (éditeur T. F. Gonzales, Chapman & Hall/CRC). Ce livre est disponible à la bibliothèque de l'ENS Lyon (espace Laurent Schwartz, cote I.2.6/GONZ). Je peux en fournir des copies si besoin.
- Des transparents [ppt] sur le même sujet, par un des auteurs du chapitre ci-dessus (version pdf).
Examen final
L'évaluation finale de ce module est une étude bibliographie, sur un article de recherche (fourni). Chaque étudiant doit choisir un article dans la liste ci-dessous, en m'envoyant un mail. Il doit écrire un rapport présentant l'article et le commentant (de 4 à 8 pages), puis le présenter devant la classe (20 minutes de présentation + 10 minutes de questions).
Si vous souhaitez une version papier de l'article choisi, envoyez-moi un mail, je laisserai une impression pour vous dans mon casier. Quelques outils de recherche bibliographique:
Les pages de ce cours pour les années précédentes : 2008/2009 et 2010/2011.