Modèles et algorithmes en ordonnancement (ORDO)

Safia Kedad-Sidhoum (CNAM)

Safia Kedad-Sidhoum (CNAM)
Christophe Picouleau (CNAM/CEDRIC)

2

Ordonnancement, Complexité, Dominance, Algorithmes exacts

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

  Objet: 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).

  Objet: 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.

  Objet: 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.

  Objet: 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.

  Objet: 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.

• Examen.

• Scheduling Algorithms. Peter Brucker, Springer, 2013.

• Modèles et Algorithmes en Ordonnancement: Exercices et problèmes corrigés. Groupe GOThA. Ellipses, 2004.

• Scheduling: Theory, Algorithms, and System. Pinedo, Springer, 200. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Joseph Y-T. Leung. CRC Press, 2004.

• Handbook on Scheduling: From Theory to Applications. Jacek Blazewicz, Klaus H. Ecker, Erwin Pesch, Günter Schmidt, Jan Weglarz. Springer, 2007.

• Multiagent Scheduling: Models and Algorithms. A. Agnetis, J.C. Billaut, S. Gawiejnowicz, D. Pacciarelli, A. Soukhal. Springer, 2014.

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

Examen écrit.

Une participation ponctuelle des étudiants à présenter un résultat extrait d'un article scientifique pourrait être envisagée.