Modèles et algorithmes en ordonnancement
2 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours
Publié Du 01-09-2024 au 31-08-9999
Notions de base en algorithmique, complexité et programmation mathématique
Le cours vise à découvrir la théorie de l'ordonnancement à travers l'étude et l'analyse de différents modèles et algorithmes du domaine. Il permet également d'assimiler les concepts fondamentaux à la démonstration des propriétés des méthodes de résolution.
Connaître les résultats fondamentaux en théorie de l'ordonnancement (complexité, modèles et algorithmes).
Savoir identifier les problèmes dans la typologie usuelle en ordonnancement.
Savoir analyser la complexité des problèmes d'ordonnancement.
Maîtriser les techniques de preuve utilisées en ordonnancement.
L'unité US331L apparaît dans 1 cursus.
Introduction à l'ordonnancement, critère minmax (problème central, ordonnancement à une machine): Introduction sur la nature des ressources, des contraintes et des critères d'ordonnancement. Présentation de la typologie à 3 champs utilisée en ordonnancement. Etude du problème central ainsi que quelques variantes.
Ordonnancement à une machine (critère minsum): Etude de problèmes de base polynomiaux ou difficiles (minimisation des temps de séjours ou des retards). Ouverture sur les problèmes à critère irrégulier (avance-retard).
Ordonnancement à machines parallèles: Présentation de quelques problèmes polynomiaux pour certaines classes de problèmes et analyse d'algorithmes de liste.
Applications en production: Ordonnancement d'atelier: Analyse de quelques problèmes rencontrés en production tels que les problèmes de flowshop, de jobshop ou le RCPSP.
Applications en informatique: Ordonnancement avec délais de communication: Analyse de quelques problèmes rencontrés en informatique tels que les problèmes avec délais de communication ou des problèmes avec contraintes énergétiques.