Résumé : L'exposé commencera par une introduction à la programmation par contraintes, accessible aux personnes ne connaissant pas ce domaine. Plusieurs types d'applications, provenant essentiellement des domaines de la planification et de l'ordonnancement, seront presentées en exemples. L'exposé se terminera par une ouverture sur divers sujets de recherche et notamment les méthodes hybrides.

Résumé : L'application prétexte à notre exposé s'inscrit dans le cadre du dimensionnement des centres d'appels d'un opérateur téléphonique mobile, et de la gestion des emplois du temps de ses milliers de conseillers. Répartis sur une demi-douzaine de sites sur le territoire français, les conseillers de clientèle doivent assurer une couverture de la charge d'appels par type d'activité. Le dimensionnement des centres pose une succession de problèmes enchevêtrés aux équipes de planification, citons : - la prévision fine (jusqu'au quart d'heure) des appels à recevoir en fonction de l'historique, des évènements exceptionnels et de l'évolution significative du nombre de clients ainsi que de leur profil, - la gestion équitable des congés et des horaires hebdomadaires sous contraintes de qualité de service par type d'activité, - la création des horaires à proprement parler, dans le respect des contrats de travail, des conventions collectives et des usages - le routage dynamique des appels sur les sites et l'affectation en ligne aux conseillers. Depuis janvier 2000, la législation française a fixé à 35 heures la durée hebdomadaire du travail. Cette nouvelle contrainte (qui remplace la semaine dite « de 39 heures ») est dans plusieurs secteurs industriels assouplie en ne s'appliquant que de manière annualisée. C'est ainsi, par exemple, que chacun de nos conseillers devra avoir travaillé 1587 heures dans l'année, avec une flexibilité relative de la semaine de travail allant typiquement de 33 à 42 heures. Le fait de passer d'un mode 39 heures/semaine stricte à un mode 35 heures annualisées ajoute, pour les équipes de planification, une nouvelle dimension à la combinatoire déjà lourde de la planification d'emplois du temps dans les centres d'appels, à laquelle s'ajoute une variabilité du nombre de jours de repos hebdomadaire (2 ou 3). C'est cette problématique que nous avons choisi d'explorer en décrivant des schémas de coopération entre un solveur de contraintes, des relaxations (linéaire ou Lagrangienne) et des algorithmes de graphes dédiés (plus courts chemins dans un DAG). La planification s'effectue par périodes de 13, 26 ou 52 semaines, pour des sites d'environ 500 personnes, chacune ayant un objectif personnel de quantité de travail pour la période. Il s'agit donc de construire 500 séquences de semaines, telles qu'individuellement les quantités de travail et les contraintes de jours de congé soient respectées et que globalement les courbes de charges soient proches de la demande estimée. Après avoir insisté sur la structure de flot sous-jacente, nous en évoquerons les limites, en montrant que le problème général se ramène à des questions classiques (et NP-complètes) de coloration de tableaux à partir de leurs vues tomographiques. Dans un premier temps, nous présenterons des approches délibérément naïves et infructueuses reposant i) exclusivement sur un Programme Linéaire (implémentant un flot contraint) ii) exclusivement sur un solveur de contraintes. Nous présenterons ensuite un schéma général de coopération étroite à trois niveaux entre une relaxation lagrangienne (consistant à traiter isolément les individus et à relâcher les contraintes couplantes de couverture de charge), de la programmation dynamique (qui résout ici 500 problèmes individuels s,apparentant à des plus courts chemins contraints dans un graphe aux arêtes valuées par les multiplicateurs de Lagrange), et de la programmation par contrainte qui assure la consistance dans la fixation des variables et opère les stratégies de branchement idoines.

Résumé : Nous nous intéressons à la résolution et la modélisation de problèmes sur-contraints. Tout d'abord, nous présentons des méthodes exactes de résolution du problème Max-CSP, où l'objectif consiste à minimiser le nombre de violations; ces méthodes peuvent être généralisées à de nombreux autres problèmes. Les algorithmes existants sont basés sur le calcul de bornes inférieures du nombre de violations. Ils sont relatifs à des réseaux de contraintes binaires. Nous proposons une généralisation du meilleur algorithme existant au cas général (tel qu'aucune hypothèse ne soit posée sur la nature et l'arité des contraintes). Nous proposons également une nouvelle borne basée sur le calcul de conflict-sets, qui prend en compte des inconsistances ignorées dans les autres bornes. Nous montrons comment combiner ces deux méthodes. En outre, je présenterai nos travaux sur la modélisation de problèmes sur-contraints réels : quantification des violations, règles d'interaction entre violations, etc.

Résumé : L'utilisation de la programmation par contraintes s'est fortement développée ces dix dernières années et de nombreux problèmes industriels d'ordonnancement sont aujourd'hui résolus par cette technique. Au cours de cet exposé, nous montrerons que l'intégration de méthodes de Recherche Opérationnelle dans les outils de contraintes a été l'un des facteurs essentiels de leurs succès. Nous présenterons aussi les limites actuelles de ces outils et nous détaillerons quelques pistes de recherches qui pourraient améliorer sensiblement leurs performances sur des problèmes d'ordonnancement.