Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

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

Link to this comparison view

cours:c-2-24 [2011/07/12 19:26] (current)
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]]
 +
 +
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA