Approche par contraintes des problèmes d'ordonnancement et d'affectation : structures temporelles et mécanismes de propagation

- Jacques ERSCHLER, Professeur, INSA, Toulouse (directeur de recherche) - Gérard FONTAN, Professeur, INP/ENSEEIHT, Toulouse (examinateur, correspondant INP) - Claude LE PAPE, Directeur R & D, Ilog, Gentilly (examinateur) - Philippe MICHELON, Professeur, Université d'Avignon et des Pays de Vaucluse (rapporteur) - Eric PINSON, Professeur, Université Catholique de l'Ouest, Angers (rapporteur) - Roman SLOWINSKI, Professeur, Université de Technologie de Poznan, Pologne (rapporteur)This work presents a class of constraint-based approaches for task scheduling and resource allocation. The research aims at designing general constraint propagation mechanisms. Akin techniques coming from Constraint Satisfaction Problems are reviewed. Throughout the presentation are respectively presented pure temporal scheduling problems, then problems dealing with time and resource sharing constraints, finally problems considering also resource allocation constraints. The focus is done on works of which the objective is to design constraint propagation rules where time and resource constraints interact. Three kinds of methods are particularly studied, and extensions from their original formulation are proposed: local operations (such as "edge-finding" techniques), global operations ("shaving"), and energetic reasoning. The use and the control of the various mechanisms to detect a global inconsistency or simplify the resolution are discussed; thus, elements for problem decomposition as well as strategies for solving the problems under consideration are proposed.Ces travaux présentent une classe d'approches par contraintes pour aborder les problèmes d'ordonnancement de tâches et d'affectation de ressources. Ils présentent notamment les recherches menées sur la conception de mécanismes généraux de propagation de contraintes. Des rapprochements sont faits avec des techniques issues des problèmes de satisfaction de contraintes. Le cas des problèmes d'ordonnancement purement temporels est rapidement abordé, puis la présentation se consacre à des problèmes dans lesquels les tâches doivent respecter à la fois des contraintes temporelles et des contraintes de partage et d'affectation de ressources. On présente notamment une synthèse des travaux ayant pour but l'élaboration de règles de propagation faisant interagir des contraintes temporelles simples et des contraintes de ressources. Trois types de raisonnement sont étudiés et dans certains cas étendus par rapport à leur formulation originale. Le premier, les opérations locales, nécessite une analyse préalable des conflits entre tâches et infère des conditions de séquencement locales à une ressource. Le deuxième, les opérations globales, agit suivant le principe d'une contrainte posée sur l'ensemble du problème. Le troisième, le raisonnement énergétique, intègre simultanément les contraintes de temps et de ressources et permet de limiter l'intervalle de temps sur lequel peut être réalisée une tâche. L'utilisation et le contrôle des mécanismes de propagation de contraintes sont discutés. Ils peuvent servir à découvrir rapidement une inconsistance globale dans la formulation du problème, ou à simplifier sa résolution. Nous fournissons ainsi des éléments sur la décomposition et la stratégie de résolution des problèmes