Return to search

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

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.

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00010264
Date10 December 2003
CreatorsLopez, Pierre
PublisherInstitut National Polytechnique de Toulouse - INPT
Source SetsCCSD theses-EN-ligne, France
Languagefra
Detected LanguageFrench
Typehabilitation ࠤiriger des recherches

Page generated in 0.0021 seconds