Differences

This shows you the differences between two versions of the page.

@@ Line 1: / Line 1: @@
+===== 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]]