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