Modèles et algorithmes en ordonnancement

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.

• 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.