Modèles et algorithmes en ordonnancement (ORDO)

dernière modif : le 18/12/2023 à 18:40:05
Titre :
Modèles et algorithmes en ordonnancement (ORDO)
Section :
Optionnel
État pour cette année :
OPEN
Mots clés :
Ordonnancement, Complexité, Dominance, Algorithmes exacts
Ects :
2
Responsable :
Safia Kedad-Sidhoum (CNAM)
Intervenants :
Safia Kedad-Sidhoum (CNAM)
Christophe Picouleau (CNAM/CEDRIC)
Prérequis :

Notions de base en algorithmique, complexité et programmation mathématique

Objectif :

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.

Contenu / Plan :
  • 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.

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

Liens :
(aucun)
Compétences visées :
  • 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.

Modalités de contrôle :

Examen écrit.

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