UE Optimisation globale et applications en ordonnancement - 4GUL09D5

Objectif(s)

• L'élève connaîtra le formalisme de la théorie de l'ordonnancement et saura reconnaître lorsqu'un problème peut-être traité dans ce cadre ; il connaîtra également les techniques et outils de base (heuristiques de liste, preuve par argument d'échange, PLNE, programmation dynamique, théorie de la complexité).

• L'élève connaîtra les principes de la programmation par contraintes et sera capable de modéliser et résoudre un problème d'optimisation donné dans ce cadre.

Contenu(s)

La problématique de l'ordonnancement est d'utiliser au mieux les ressources dont on dispose (machines, camions, énergie, budget) afin de réaliser un ensemble d'activités (représentant des ordres de production, des transports à effectuer, les étapes d'un projet) en les planifiant dans le temps. Le domaine de l'ordonnancement est donc très vaste : comment finir au plus vite, en limitant les retards, en minimisant les encours, etc. Les ressources sont généralement en nombre et capacité limités, les contraintes nombreuses (respect des délais, précédences entre tâches, etc), ce qui fait des problèmes d'ordonnancement des problèmes combinatoires souvent très difficiles à résoudre en pratique.

.

Le cours présente les outils de modélisation et de résolution pour l'ordonnancement déterministe (quand tout est connu à l'avance). En plus de la théorie de l'ordonnancement proprement dite, le cours permet de découvrir la théorie de la complexité, qui permet de caractériser la difficulté intrinsèque d'un problème, et présenter différentes techniques pour obtenir des solutions aux problèmes qui se posent dans le monde industriel. En particulier le cours introduit les bases de la programmation par contraintes (PPC), qui s'avère un outil de modélisation et de résolution puissant pour les problèmes d'ordonnancement. Enfin, le rôle de l'ordonnancement au sein de l'entreprise et les particularités de l'ordonnancement en milieu industriel seront abordés.

.
Contenu détaillé indicatif :

• Ordonnancement déterministe
  • Exemples, définition et formalisme
  • Problèmes classiques de l'ordonnancement : séquencement sur une machine selon différents critères ; ordonnancement sur plusieurs machines (affectation des ressources, machines en parallèles, lignes de production et problèmes d'atelier)
  • Complexité de problèmes
  • Méthodes de résolutions (heuristiques, approximations, PLNE,...)

• Programmation par contraintes
  • Formalisme et modélisation en PPC
  • Algorithme de propagation : arc et noeud consistence.

• TP et Projet

• Programmation linéaire, programmation linéaire en nombres entiers
• Recherche opérationnelle (graphes, programmation dynamique)
• Informatique (programmation, langage Java)