Cette page répertorie des articles d'intérêt général sur l'ordonnancement ou des problèmes voisins ainsi que sur les méthodes d'optimisation. Si vous voulez faire partager à la communauté le plaisir que vous avez eu à lire un article, publié ou non, ou une thèse, envoyez-moi les références.

---

• Approximation Schemes - A Tutorial par Petra Schuurman et Gerhard J. Woeginger. Tout ce que vous avez toujours voulu savoir sur les PTAS sans jamais avoir osé le demander.

---

• Deux modèles récents en Ordonnancement Présentation de Philippe Chrétienne aux JFRO du 21 novembre 2003.
• Polyhedral Approaches to Machine Scheduling de Maurice Queyranne et Andreas Schulz. Article de synthèse souvent cité mais non publié.
• Multicriteria scheduling de Han Hoogeveen. Version préliminaire d'un article invité à paraître dans le numéro spécial d'EJOR édité par J.C. Billaut et V. T'kindt.

---

• Traffic Networks and Flows Over Time par Ekkehard Köhler, Rolf H. Möhring, and Martin Skutella. Synthèse de travaux (2002).
• Semidefinite programming and integer programming : Survey de Monique Laurent et Franz Rendl.
• List scheduling in order of alpha-points on a single machine, chapitre de livre par Martin Skutella, récapitulatif des travaux de l'auteur avec Schulz et Queyranne.

---

• PRIME is in P: annonce d'un algorithme déterministe polynomial pour ce fameux problème. Voir aussi les notes de F. Morain et une FAQ. en Français.
• La conjecture forte des graphes parfaits a été démontrée en 2002 par Chudnovsky, Robertson, Seymour et Thomas. Un résumé de la preuve par Gérard Cornuéjols.
• Plus ancien, 11 auteurs pour un PTAS en ordonnancement: Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. Présenté à FOCS'99.

---

• Ravindra K. Ahuja - Özlem Ergun - James B. Orlin - Abraham P. Punnen
  A survey of very large-scale neighborhood search techniques
  Discrete Applied Mathematics Volume 123, Issues 1-3, 15 November 2002, Pages 75-102
  Explorations d'un voisinage de taille exponentielle en temps polynomiale. Résultats théoriques et retombées pratiques.
• Josep Díaz - Jordi Petit - María Serna
  A survey of graph layout problems
  ACM Computing Surveys Volume 34 , Issue 3 (September 2002)
  La problématique de la numérotation des sommets des graphes est très proche de ce que l'on rencontre en ordonnancement: complexité, approximation, heuristiques, différents types de critères... Tout est résumé dans cette synthèse.