Description

• 
  

  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.

  
  

Finalité

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.

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.

  
  

Public

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