— |
cours:c-2-24 [2011/07/12 19:26] (current) |
| + | |
| + | ===== Ordonnancement (24h, 3 ECTS) ===== |
| + | |
| + | Responsable : Philippe Baptiste |
| + | |
| + | ==== Plan du cours et intervenants prévus pour 2005-2006 ==== |
| + | |
| + | - ??? (12h, Ph. Baptiste |
| + | - ??? (12h, C. Dürr |
| + | |
| + | ==== Objectifs ==== |
| + | |
| + | Le but de ce cours est de présenter les approches modernes |
| + | de la théorie des |
| + | problèmes d'optimisation combinatoire issus de l'informatique et des |
| + | télécommunications. |
| + | |
| + | ==== Plan du cours ==== |
| + | |
| + | <h4>Algorithmes d'approximation</h4> |
| + | Algorithmes combinatoires : couverture par ensembles, arbre de |
| + | Steiner et voyageur de commerce, coupes et //k//-coupes, //k//-centres, |
| + | //feedback vertex set//, sur-mot le plus court, sac à dos, bin |
| + | packing, voyageur de commerce Euclidien. |
| + | |
| + | Algorithmes basés sur la programmation linéaire: dualité, |
| + | arrondi et couverture par ensembles, paradigme primal-dual, |
| + | satisfiabilité maximale, multiflot sur des arbres, multi-coupes, |
| + | forêt de Steiner, placement de ressources, //k//-médian, |
| + | programmation semi-définie. |
| + | |
| + | Autres sujets: problèmes de comptage, plus court vecteur, |
| + | difficulté d'approximation, problèmes ouverts. |
| + | |
| + | <h4>Théorie de l'ordonnancement</h4> |
| + | Les problèmes d'ordonnancement viennent le plus souvent de la |
| + | Productique et de l'Informatique. Il s'agit de planifier alors |
| + | l'exécution d'une réalisation en attribuant des ressources aux tâches |
| + | et en fixant leurs dates d'exécution. La réalisation peut être un |
| + | programme informatique ou le carnet de commandes d'un atelier. Les |
| + | tâches sont des traitements de pièces par des machines, la ressource, |
| + | des processeurs et de la mémoire, ou des machines et du personnel. En |
| + | Productique, l'ensemble des tâches à exécuter au cours du temps est |
| + | donné a priori, les tâches prédécesseurs de chaque tâche sont |
| + | également connues, ainsi que les quantités de ressource qu'elles |
| + | requièrent lors de leur exécution. L'objectif est de mettre au point |
| + | des méthodes permettant de minimiser une fonction économique dépendant |
| + | des dates d'achèvement des tâches. |
| + | |
| + | Ces problèmes d'ordonnancement étant très combinatoires, une étude |
| + | théorique est souvent nécessaire pour pouvoir élaborer des |
| + | énumérations implicites de nature arborescente utilisant des outils |
| + | réduisant fortement la combinatoire. Ce module a pour objet de donner |
| + | aux étudiants une culture large et récente en ordonnancement. Après |
| + | une introduction générale aux problèmes d'ordonnancement (typologie et |
| + | notation), ils aborderont les problèmes à une machine, à machines |
| + | parallèles, les problèmes de type //flowshop//, //jobshop// et |
| + | les problèmes à ressources multiples. |
| + | |
| + | <h4>Programmation mathématique</h4> |
| + | L'objectif de ce module este de présenter les notions de base |
| + | concernant la programmation linéaire ainsi que l'optimisation non |
| + | linéaire, avec ou sans contraintes. |
| + | |
| + | <ol> |
| + | <li> Programmation linéaire : Définition, forme standard, algorithme du |
| + | simplexe, dualité </li> |
| + | <li> Optimisation sans contrainte : Notions de base sur les minima et |
| + | maxima locaux ou globaux et sur les fonctions convexes. Méthodes |
| + | numériques : méthode de Newton, méthodes de descente, algorithme du |
| + | gradient conjugué, Méthodes de Quasi-Newton.</li> |
| + | <li> Optimisation avec contraintes : Conditions nécessaires d'optimalité : |
| + | conditions de Lagrange ou de Kuhn-Tucker. Suffisance de ces conditions |
| + | lorsque le programme est convexe. Autres conditions suffisantes |
| + | d'optimalité. Algorithmes de pénalité.</li> |
| + | <li> Relaxation Lagrangienne, //Surrogate// Duality, utilisation de |
| + | relaxations continues pour la résolution de problèmes discrets. </li> |
| + | </ol> |
| + | |
| + | ==== Pré-requis ==== |
| + | |
| + | Algorithmique, théorie de la complexité, éléments de la théorie des |
| + | graphes. |
| + | |
| + | ==== Bibliographie ==== |
| + | |
| + | <ul> |
| + | <li> Christos H. Papadimitriou, //Combinatorial Optimization: Algorithms |
| + | and Complexity//. Prentice Hall, 1982. </li> |
| + | <li> Peter Brucker, //Scheduling Algorithms//. Springer-Verlag. </li> |
| + | <li> Philippe Baptiste, Claude Le Pape, and Wim |
| + | Nuijten, //Constraint-based Scheduling//. Kluwer Academic |
| + | Publishers, 2001. </li> |
| + | <li> Vijay Vazirani, //Approximation Algorithms//. Springer, 2001. </li> |
| + | </ul> |
| + | |
| + | ==== Équipe pédagogique ==== |
| + | <html><table border="2"> |
| + | <tr><td>Ph. Baptiste</td> |
| + | <td>CR</td> |
| + | <td>CNRS</td> |
| + | <td>LIX</td> |
| + | </tr> |
| + | <tr><td>C. Kenyon</td> |
| + | <td>PU</td> |
| + | <td>École Polytechnique</td> |
| + | <td>LIX</td> |
| + | </tr></table></html> |
| + | |
| + | |
| + | ==== Les années précédentes ==== |
| + | |
| + | * [[2009-2010-C-2-24|Année 2009-2010]] |
| + | ** Année [[2008-2009-C-2-24|2008-2009]] |
| + | |
| + | |
| | | |