Cette thèse, réalisée en collaboration avec Sagem Défense Sécurité, porte sur l'élaboration d'une stratégie de recherche efficace pour la résolution de problèmes de planification d'itinéraires de véhicules. Nous considérons ici en particulier les problèmes de planification avec contraintes de points de passage et de "capacité" (énergie, bande passante radio) appliquées au véhicule. Ce document propose une approche originale, hybridant un algorithme de colonies de fourmis avec un solveur de Programmation par Contraintes existant. Le premier est utilisé pour résoudre rapidement une version relaxée du problème. La solution partielle obtenue est alors employée pour guider la recherche du second, par le biais d'une méthode de sonde, vers les zones les plus prometteuses de l'espace d'état. Cette approche permet ainsi de combiner la rapidité des métaheuristiques et la complétude de la programmation par contraintes. Nous montrons expérimentalement que cette approche satisfait les exigences pour une utilisation du planificateur dans un cadre embarqué.

Le management d'activités à risques implique de nombreuses décisions qui mettent en scène un collectif d'acteurs ayant chacun leur domaine d'expertise ou d'action pour concevoir ou exploiter un système complexe. D'abord, le rôle d'un système interactif d'aide à la décision de groupe (SIADG) dans le cadre du management d'activités à risques est analysé. Les fonctionnalités du système sont spécifiées de sorte à minimiser l'impact des erreurs humaines et organisationnelles qui peuvent affecter le processus de décision collectif. Le SIADG est vu comme le médiateur entre l'homme et le système qu'il cherche à maîtriser : il l'aide à percevoir une situation critique, la comprendre, l'interpréter et la diagnostiquer avant d'y remédier, mais il favorise également la résolution collective en constituant un support à la communication et à la coordination des intervenants. La décision est perçue comme un processus dynamique dont le temps de réponse dépend de l'efficacité avec laquelle est menée la phase de délibération. Plusieurs grandeurs et modèles pour contrôler la délibération sont proposés. Un premier type de situation décisionnelle met en scène un manager qui s'entoure d'experts pour prendre une décision sur la base d'un processus de fusion des avis exprimés. L'incertitude attachée à l'évaluation des alternatives est due d'une part, à l'imprécision des avis d'experts, d'autre part aux divergences d'opinions. Le contrôle de cette incertitude permet d'identifier les critères sur lesquels doit se focaliser le débat d'experts. Le concept d'influence dans un réseau social est alors introduit pour proposer deux modèles de pilotage de la phase de délibération d'une décision d'organisation, basé sur la délibération argumentée pour l'un, sur des simulations stochastiques pour l'autre, avec un formalisme d'équations d'état pour représenter l'évolution des convictions au fil du débat. Ensuite, les décisions qui concernent l'amélioration d'un système complexe, où se confrontent la vision stratégique des managers et la vision opérationnelle des exécutants sont abordées. Lorsque des objectifs atteignables ont été négociés, un modèle basé sur un problème de programmation par contraintes permet de calculer une mise en œuvre des actions pour les atteindre. Dans ce cas, soit le collectif est vu comme un ensemble d'agents collaboratifs et la délibération est pilotée par l'efficience de la décision ; soit comme un ensemble d'agents simplement coopératifs, dont nous modélisons la négociation où se mêlent objectifs collectifs et enjeux individuels, à l'aide de la théorie de l'argumentation. Ces modèles traitent tous du contrôle du processus cognitif que constitue la décision collective : l'automatisation cognitive vise ainsi à réduire les erreurs humaines et organisationnelles qui pourraient affecter la décision en particulier les erreurs d'évaluation et de coordination. Une conclusion et des perspectives achèvent ce manuscrit qui est illustré de plusieurs exemples relatifs au management d'activités à risques.

Le regroupement des blocs opératoires au sein d'un Plateau Médico-Technique (PMT) présente des enjeux dans la phase de conception (dimensionnement des ressources et choix d'organisation) et dans la phase de pilotage (planification de l'activité et affectation des ressources humaines et matérielles) face auxquels les décideurs hospitaliers manquent d'outils. En réponse à ces besoins, cette thèse propose une démarche globale d'aide à la décision pour la conception du PMT et le pilotage des ressources humaines mutualisées de ce secteur. Cette démarche aborde trois principaux problèmes. Dans un premier temps, nous nous intéressons à la modélisation des processus de PMT existants, dont le but est de faire émerger un diagnostic et d'engager une démarche d'amélioration de la performance. Ces modèles sont réutilisés dans un second temps pour la modélisation des processus cibles qui nous permettent d'obtenir, par simulation de l'activité, les courbes de charge exprimant les besoins en personnel. Nous abordons la question du dimensionnement du personnel regroupé du PMT par la construction des vacations couvrant cette charge prévisionnelle, à l'aide de la Programmation Linéaire en Nombres Entiers (PLNE) couplée à la simulation de flux. Dans un troisième temps, nous étudions deux problèmes de planication d'horaires de travail : celui des infirmiers anesthésistes et celui des médecins anesthésistes, pour lesquels nous développons plusieurs approches de résolution basées sur la Programmation Linéaire Mixte (PLM) et sur la Programmation Par Contraintes (PPC), expérimentées et validées dans le cadre d'applications réelles.

Les problèmes combinatoires basés sur le partitionnement de graphe permettent de modéliser un grand nombre d'applications pratiques. On retiendra des exemples aussi variés que la reconstruction de " super-arbres " en phylogénie, la planification de missions, ou la construction de tournées de véhicules en logistique. Ces applications, bien que provenant de domaines différents, peuvent toutes se voir comme un problème de partitionnement de graphe par des patrons tels que des cycles, des chemins, ou des arbres. Cependant, les problèmes pratiques se résument rarement à des problèmes " pur " comme peuvent l'être le problème de chemin Hamiltonien ou le problème des K-chemins disjoints. En effet, ils combinent bien souvent le problème de partitionnement avec un ensemble de restrictions sur la topologie des sommets et des arcs. La diversité des contraintes opérationnelles misent en jeu constitue souvent une limite à leur résolution par des approches considérant de manière séparée le problème de partitionnement et les restrictions supplémentaires imposées. Cette thèse se concentre sur les problèmes de satisfaction de contraintes li !es au partitionnement de graphe par des arbres mettant en jeu un certain nombre de restrictions sur la topologie des partitions autorisées. Notre travail se focalise d'une part sur la compréhension des propriétés structurelles inhérentes aux contraintes de partitionnement par des arbres, et d'autre part sur l'étude des interactions existantes entre le problème de partitionnement et les restrictions classiques (telles que les relations de précédences ou d'incomparabilités entre les sommets du graphe à partitionner). Nous nous attachons plus particulièrement à montrer comment prendre en compte de manière globale un certain nombre de ces restrictions au sein d'une contrainte de partitionnement de graphes par des arbres. Un autre aspect essentiel porte sur la mise en œuvre d'une telle contrainte : nous montrons en quoi une gestion dynamique des structures de données permet de s'abstraire significativement d'un problème récurrent à la plupart des contraintes globales liées aux graphes : la sensibilité des algorithmes de graphes à la densité des graphes manipulés par la contrainte.

Les gestionnaires de ressources reposant sur une gestion dynamique des tâches permettent une utilisation efficace des ressources des grappes de serveurs. Ils mettent en oeuvre pour cela des mécanismes manipulant à la volée l'état des tâches et leur placement sur les différents noeuds de la grappe. En pratique, ces stratégies d'ordonnancement ad-hoc s'adaptent difficilement aux grappes. En effet, celles-ci ne permettent pas nécessairement une manipulation fiable des tâches et peuvent imposer des contraintes d'ordonnancement spécifiques. Dans cette thèse, nous nous sommes fixés comme objectif de faciliter le développement de gestionnaires de ressources basés sur une gestion dynamique des tâches. Pour cela, nous avons retenu une architecture à base de machines virtuelles qui exécutent les tâches des utilisateurs dans leur propre environnement logiciel tout en proposant les primitives nécessaires à la manipulation de celles-ci de manière non-intrusive. Nous avons également proposé une approche autonome optimisant en continu l'ordonnancement des tâches. Les stratégies d'ordonnancement sont implémentées au moyen de la programmation par contraintes qui permet de définir de manière flexible des problèmes d'ordonnancement et de les résoudre. Nous avons validé notre approche par le développement et l'évaluation du prototype Entropy, support pour l'implémentation de différentes stratégies d'ordonnancement. Celles-ci ont pu répondre efficacement à des problèmes concrets et actuels.

En août 2005, British Airways mit quatre jours à rétablir ses vols après une grève d'une journée d'un de ses sous-traitants. En interconnectant et intégrant leurs systèmes d'aide à la décision, les entreprises deviennent de plus en plus soumises aux changements. Parallèlement, avec le développement de technologies comme les puces RFID et la localisation par GPS les entreprises sont capables de suivre en temps réel le déroulement des opérations sur le terrain. Dans cette thèse nous nous intéressons au cas des problèmes de satisfaction de contraintes dans un cadre dynamique. En effet, depuis de nombreuses années la programmation par contraintes a fait la preuve de son efficacité pour résoudre des problèmes d'optimisation (tournées de véhicules, ordonnancements, etc) dans le cadre statique. Cependant le contexte dynamique soulève encore de nombreuses difficultés. Nous proposons donc un ensemble d'outils permettant la gestion et la prise en compte des événements, survenant de manière inattendue, dans le cadre de la programmation par contraintes. Chaque outil repose sur une approche particulière des problèmes dynamiques (tuples interdits, recherche locale, explications) et offre ainsi un éclairage différent et complémentaire.

Résoudre un problème d'ordonnancement consiste à organiser un ensemble de tâches, c'est-à-dire déterminer leurs dates de début et de fin et leur attribuer des ressources en respectant certaines contraintes. Dans cette thèse, nous proposons de nouvelles approches exactes basées sur la programmation par contraintes pour deux classes de problèmes d'ordonnancement NP-difficiles validées expérimentalement par l'implémentation d'un ensemble de nouvelles fonctionnalités dans le solveur de contraintes choco. Dans un problème d'atelier, n lots sont constitués chacun de m tâches à exécuter sur m machines distinctes. Chaque machine ne peut exécuter qu'une tâche à la fois. La nature des contraintes liant les tâches d'un même lot peut varier (séquencement global ou par lot, pas de séquencement). Le critère d'optimalité étudié est la minimisation du délai total. Nous proposons d'abord une étude et une classification des différents modèles et algorithmes de résolution. Ensuite, nous introduisons une nouvelle approche flexible pour ces problèmes classiques. Une machine à traitement par fournées peut traiter plusieurs tâches en une seule opération, une fournée. Les dates de début et de fin des tâches d'une même fournée sont identiques. Le problème étudié consiste à minimiser le retard algébrique maximal de n tâches de différentes tailles sur une machine de capacité b. Conjointement, la somme des tailles des tâches d'une fournée ne doit pas excéder la capacité b. Nous proposons, dans ce contexte, un modèle basé sur une décomposition du problème. Nous définissons ensuite une nouvelle contrainte pour l'optimisation basée sur une relaxation du problème qui améliore sa résolution.

La programmation par contraintes est une approche intéressante pour traiter des problèmes d'ordonnancement. En ordonnancement cumulatif, les activités sont définies par leur date de début, leur durée et la quantité de ressource nécessaire à leur exécution. La ressource totale disponible (la capacité) en chaque instant est fixe. La contrainte globale Cumulative modélise ce problème en programmation par contraintes. Dans de nombreux cas pratiques, la date limite de fin d'un projet est fixée et ne peut être retardée. Dans ce cas, il n'est pas toujours possible de trouver un ordonnancement des activités qui n'engendre aucun dépassement de la capacité en ressource. On peut alors tolérer de relâcher la contrainte de capacité, dans une limite raisonnable, pour obtenir une solution. Nous proposons une nouvelle contrainte globale : la contrainte SoftCumulative qui étend la contrainte Cumulative pour prendre en compte ces dépassements de capacité. Nous illustrons son pouvoir de modélisation sur plusieurs problèmes pratiques, et présentons différents algorithmes de filtrage. Nous adaptons notamment les algorithmes de balayage et d'Edge-Finding à la contrainte SoftCumulative. Nous montrons également que certains problèmes pratiques nécessitent d'imposer des violations de capacité pour satisfaire des règles métiers, modélisées par des contraintes additionnelles. Nous présentons une procédure de filtrage originale pour traiter ces dépassements imposés. Nous complétons notre étude par une approche par décomposition. Enfin, nous testons et validons nos différentes techniques de résolution par une série d'expériences.

La programmation par contraintes, carrefour de diverses disciplines, a montré son intérêt dans de nombreux domaines d'application. De nombreux problèmes réels sont dynamiques : le système de contraintes les définissant n'est donc pas figé. Pour résoudre un problème dynamique, il faut assurer une certaine incrémentalité et être capable de traiter les systèmes de contraintes contradictoires. En effet, il est souvent indispensable de fournir une solution quitte à ne pas respecter certaines contraintes. On parle alors de relaxation de contraintes.<br /><br />Durant cette thèse, nous nous sommes intéressés à la définition d'un système de relaxation de contraintes permettant de maintenir une propriété donnée dans un environnement dynamique. Nous avons mené ces travaux depuis une présentation abstraite d'un tel système jusqu'à son implémentation.<br /><br />Nous présentons un schéma algorithmique général abstrait de la recherche d'une solution à un problème sur-contraint basée sur l'exploration en meilleur d'abord d'un espace de configurations. Nous en donnons trois instances pour traiter les contraintes linéaires sur les rationnels, les Constraint Satisfaction Problems et les CSP numériques. Les deux dernières sont définies à l'aide d'un système de maintien de déduction dont la ma\^\itrise raisonnée nous a permis de donner une implémentation de ces instances ayant une bonne complexité : le système DECorum.<br /><br />Nous montrons, par le biais d'un certain nombre d'expérimentations, que l'utilisation de DECorum permet de retrouver les résultats classiques sur la transition de phase, de résoudre raisonnablement des problèmes de grande taille et d'utiliser la structure du problème résolu pour améliorer la recherche.<br /><br />Enfin, nous proposons la contrainte one-of permettant de modéliser et de résoudre une disjonction de contraintes en tirant profit du mécanisme d'exploration de DECorum. Nous validons l'intérêt de la contrainte one-of sur des problèmes d'ordonnancement : les Open-Shop.

Dans le cadre de cette thèse, nous nous intéressons à l'acquisition automatique de réseau de contraintes, aussi appelée apprentissage automatique de réseau de contraintes, qui consiste à développer des solutions capables d'aider un utilisateur à modéliser un problème combinatoire sous la forme d'un réseau de contraintes. Notre travail se focalise plus précisément sur la plate-forme d'acquisition automatique de réseau de contraintes CONACQ. Dans son implémentation standard, CONACQ est passive vis-à-vis de l'utilisateur, c'est-à-dire basée sur la capacité de ce dernier à fournir des instances significatives de son problème. Dans la première partie de cette thèse, nous proposons une version interactive de CONACQ, capable de poser à l'utilisateur des questions dont le but est d'augmenter plus rapidement et de manière conséquente la connaissance acquise par la plate-forme. Afin de limiter le nombre d'interactions, nous proposons différentes stratégies de questionnement que nous validons ensuite empiriquement. Dans la seconde partie, nous nous intéressons à une utilisation pratique de l'acquisition automatique de réseau de contraintes qui vise à automatiser le processus de définitions de comportements sensorimoteurs en robotique. Dans cette optique, nous proposons une architecture logicielle, complémentaire aux architectures de contrôle existantes, qui utilise le paradigme de la programmation par contraintes pour modéliser, planifier et superviser l'exécution de comportements sensorimoteurs. Elle utilise la plate-forme CONACQ étudiée dans la première partie de cette thèse pour modéliser automatiquement les actions élémentaires d'un robot sous la forme de réseaux de contraintes. Notre architecture utilise par ailleurs un planificateur de tâches inspiré de CSP-Plan pour combiner les réseaux de contraintes acquis et ainsi définir automatiquement des comportements sensorimoteurs. Différents résultats expérimentaux sont par ailleurs présentés afin de valider notre approche.