Modèles et Applications en Ordonnancement et optimisation combinAtoire

Cette UE présente les méthodes avancées et les applications
industrielles récentes en Optimisation Combinatoire et en Ordonnancement.
Elle s'intéresse à la résolution exacte des problèmes d'optimisation
combinatoire NP-difficiles (voyageur de commerce, tournées de véhicules,
coloration de graphes,...). Elle s'appuie sur la programmation linéaire
en nombres entiers et en particulier sur les formulations contenant un
nombre exponentiel de variables et de contraintes. Ces formulations sont
résolues par différentes méthodes comme les méthodes de coupes ou les
méthodes de décomposition (relaxation lagrangienne, génération de
colonnes). Des outils théoriques comme les approches polyédrales sont
également introduits dans le but de comprendre comment l'on peut obtenir
la solution exacte d'un problème d'optimisation combinatoire de grande
dimension et comment sont conçus les solveurs d'optimisation commerciaux.
Cette UE introduit également les problématiques de l'ordonnancement
(tâches, modes d'exécution, contraintes et critères d'optimisation). La
complexité et la résolution exacte et approchée des problèmes les plus
représentatifs sont abordées. Les problèmes fondamentaux classiques
ainsi que les modèles nouveaux et non-standards seront présentés. Des
exemples applicatifs ainsi que des études de cas dans les systèmes
manufacturiers et informatiques seront développés.
Un projet sera proposé pour appréhender la pratique de la recherche opérationnelle
en partant d'une application industrielle jusqu'à sa résolution pratique.

Documents

• Combinatorial Optimization, W. Cook, W. Cunningham, W. Pulleyblank et
  A. Schrijver , Wiley-Interscience, 1997.
• Integer Programming, L. Wolsey, Wiley-Interscience, 1998.
• Programmation mathématiques, Michel Minoux, Lavoisier 2008.
• Approches Polyédrales en Optimisation Combinatoire, A.R. Mahjoub,
  Optimisation combinatoire . 1 , concepts fondamentaux, Hermes science
  publ. Lavoisier, 2005.
• Modèles et Algorithmes en Ordonnancement: Exercices et problèmes
  corrigés. Groupe GOThA. Ellipses, 2004.
• Scheduling Algorithms. Peter Brucker, Springer, 2004.
• 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.

Liens
page annuelle du module