Journée du 5 juin 2007

INRIA Rocquencourt
JFPC'07 GOThA

Thème de la journée

Programmation par contraintes et ordonnancement.

Mardi 5 juin 2007, Amphithéatre Türing, INRIA Rocquencourt

Cette journée a été organisée en association avec le groupe de travail GOThA (merci à Francis Sourd), en parallèle des Journées Francophones de Programmation Par Contraintes JFPC 2007 (merci à Pierre Deransart et aux membres du comité d'organisation des JFPC'07).

Programme de la journée

11h00Philippe Laborie, Daniel Godard (ILOG)

Self-Adapting Large Neighborhood Search: Application to single-mode scheduling problems [.pdf]  [slides]

Providing robust scheduling algorithms that can solve a large variety of scheduling problems with good performance is one of the biggest challenge of practical schedulers today. In this talk we present a robust scheduling algorithm based on Self-Adapting Large Neighborhood Search and apply it to a large panel of single-mode scheduling problems. The approach combines Large Neighborhood Search with a portfolio of neighborhoods and completion strategies together with Machine Learning techniques to converge on the most efficient neighborhoods and completion strategies for the problem being solved. The algorithm is evaluated on a set of 20 scheduling benchmarks, most of which are well established in the scheduling community. Despite the generality of the approach, for 16 benchmarks out of 20, its mean relative distance to state-of-the-art problem specific algorithms is less than 4%. It even outperforms state-of-the-art problem-specific algorithms on 7 benchmarks clearly showing that our algorithm offers a valuable compromise between robustness and performance.

12h00Déjeuner (libre)

13h45Thierry Petit (EMN/LINA)

Propagation de critères relatifs à l'acceptation pratique des solutions [slides]

Le traitement de problèmes sur-contraints implique la nécessité de tolérer que certaines contraintes soient violées dans les solutions. Néanmoins, pour pouvoir être appliquées en pratique, ces solutions doivent respecter des critères relatifs aux violations. Un cas pratique intéressant est celui des problèmes d'ordonnancement cumulatifs dans lequel on tolère certains dépassements de ressource. Tandis que la somme des dépassements est limitée, un critère important consiste souvent à répartir ces dépassements le mieux possible sur toute la durée de l'ordonnancement. Ce travail met en évidence l'intérêt, en terme d'efficacité, de l'utilisation de variables pour exprimer les quantités de violation de ressource à chaque point de temps, et de contraintes globales pour gérer la répartition de ces violations. En outre, un algorithme de filtrage est proposé pour une contrainte cumulative telle que l'on tolère des dépassements de ressource.

14h30Mohand Ou Idir Khemmoudj (LIPN, Paris 13)

Étude de l'apport de la Programmation Par Contraintes à la résolution du problème de placement des arrêts et de la production des réacteurs nucléaires d'EDF [.pdf]

Les réacteurs du parc nucléaire français doivent être arrêtés périodiquement pour les recharger en combustible et effectuer certaines opérations de maintenance. Les plannings d'arrêts des réacteurs appartenant à un même site géographique doivent satisfaire un certain nombre de contraintes dites "contraintes de placement intra-site" (ordonnancement, espacement minimum, recouvrement maximum,...). De plus, les réacteurs en arrêt appartenant à des sites différents doivent satisfaire les "contraintes de placement inter-sites" (contraintes liées aux limitations des moyens). Les productions des différents réacteurs en chaque pas de temps constituent un plan de production et doivent satisfaire des "contraintes de production" (contraintes de stocks, lois de rechargement,...) et la contrainte de demande en énergie, à moindre coût. Le but de notre travail est d'étudier l'apport de la Programmation Par Contraintes à la résolution de ce problème.

15h15Wafa Karoui (LAAS)

Extensions de méthodes à divergences limitées pour la résolution de problèmes de décision [slides]

Nous nous intéressons à l'extension de méthodes basées sur les divergences dans le cadre de la résolution des problèmes de satisfaction de contraintes (CSP) discrets. Dans ce contexte, nous proposons une méthode baptisée YIELDS (Yet Improved Limited Discrepancy Search). YIELDS est basée sur le principe de la recherche à divergences limitées proposé en 1995 par Harvey et Ginsberg et constitue une amélioration de ses principales instances. YIELDS exploite les échecs rencontrés pour privilégier certaines variables dans les heuristiques d'instanciation en utilisant une pondération des variables. Cette méthode exploite également des techniques classiques de propagation de contraintes (Arc-Consistency). Nous évoquons également l'intégration de techniques de no-goods à la méthode YIELDS. La méthode ainsi conçue, NG-YIELDS, conjugue les bienfaits de la mémorisation des no-goods aux apports de YIELDS. L'évaluation de nos propositions est réalisée par des expérimentations sur des CSP aléatoires ainsi que sur des problèmes réels de type ordonnancement d'atelier (job shop) et carrés latins.

16h00Pause / Fin de la journée

17h00Session JFPC'07: Contraintes de temps