UE Optimisation globale et applications en ordonnancement - 4GUL09D5

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)

E1 : examen écrit (ordonnancement)
P1 : étude de cas (ordonnancement)
E2 : examen écrit (programmation par contraintes)
P2 : étude de cas et travaux pratiques (programmation par contraintes)

S2 : examen session 2 (oral ou écrit)

N1 = note finale session 1
N2 = note finale session 2

Le jury peut décider le passage en année supérieure sous réserve de validation différée de cette UE. Cette décision reste exceptionnelle ; le jury est souverain pour chaque étudiant.

N1 = 0,34*E1 + 0,16*P1 + 0,34*E2 + 0,16*P2
N2 = S2

Le cours est programmé dans ces filières :

• Cursus ingénieur - Ingénieur ICL - Semestre 8

Code de l'enseignement : 4GUL09D5
Langue(s) d'enseignement :

Vous pouvez retrouver ce cours dans la liste de tous les cours.

• M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer, 2012.
• P. Brucker, Scheduling Algorithms, Springer, 2007.
• G. Ausiello et al., Complexity and Approximation, Springer, 1999.