Search

National audience; Solving a scheduling problem consists in organizing the realization of tasks in the course of time: determining their distribution on the various available resources as well as their execution dates. Scheduling problems are encountered in all domains of industry and services, and are often studied in the literature. This thesis focuses on disjunctive scheduling and/or packing problems, with or without flexibility on the resources. All the algorithmic contributions of this thesis have been implemented within the mathematical optimization solver LocalSolver, whose resolution techniques combine exact methods, such as linear, nonlinear and constraint programming, and heuristics, such as local search and constructive algorithms.This thesis addresses two main issues related to the treatment of this type of scheduling problems by LocalSolver. The first objective is to easily allow users to model many disjunctive scheduling problems. By taking advantage of LocalSolver's set-based modeling formalism, we propose generic formulations, adaptable to different disjunctive scheduling problem families, in order to simply express the concepts of tasks, precedence relations, or non-overlap constraints on the tasks assigned to the same disjunctive resource. These generic formulations are based on the combined use of two types of decision variables offered by LocalSolver: integer variables, representing the start dates and durations of tasks, and list variables, representing their order on the various disjunctive resources.The second objective of the thesis is to improve the performance of LocalSolver on the considered scheduling problems, by integrating different resolution algorithms, as generic as possible, to the local search component of the solver. The genericity of the contributions is crucial: indeed, we do not aim at improving the performance of the solver on a single problem, nor even only on scheduling problems, but on all problems presenting certain characteristic structures often encountered in disjunctive scheduling or in packing.The algorithmic contributions of this thesis can be grouped into three main categories: initialization algorithms, local search moves, and a constraint propagation algorithm. We present two constructive initialization algorithms for set and list variables, which help the solver to immediately find a feasible solution to problems such as the Aircraft Landing or Assembly Line Balancing Problems, and thus accelerate the search for good quality solutions. We also present several local search moves, based on the detection of specific structures in the model (non-overlap constraints, precedence relations, packing constraints). We also present a solution repair algorithm by constraint propagation, integrated into the solver's local search component, and called after each local move leading to an infeasible solution. Our algorithm differs from classical constraint propagation in several ways. For example, it only propagates domain reductions that exclude the current values of the va! riables, and can make arbitrary decisions when it encounters a constraint that can be repaired in different ways. We prove that in some cases the algorithm has properties that ensure that the propagation will succeed if the solution can be repaired. This algorithm overcomes the difficulties encountered by local search on tightly constrained scheduling problems (moving from a good solution to another requires making changes on a large number of variables). The integration of these local moves and this repair algorithm into LocalSolver's local search component brings significant performance gains on various problems (Job Shop and variants, Unit Commitment, Assembly Line Balancing, or Bin Packing).; Résoudre un problème d'ordonnancement consiste à organiser la réalisation de tâches au cours du temps : déterminer leur répartition sur les différentes ressources disponibles ainsi que leurs dates d'exécution. Les problèmes d'ordonnancement se rencontrent dans tous les domaines de l'industrie et des services, et sont très étudiés dans la littérature. Le travail de cette thèse se concentre sur les problèmes d’ordonnancement de type disjonctif et/ou packing, avec ou sans flexibilité des ressources. L'ensemble des contributions algorithmiques de la thèse ont été implémentées au sein du solveur d'optimisation mathématique LocalSolver, dont les techniques de résolution combinent des méthodes exactes, telles que la programmation linéaire, non linéaire et par contraintes, et heuristiques, comme la recherche locale et des algorithmes constructifs.Le travail de cette thèse répond à deux problématiques principales, liées au traitement de ce type de problèmes d'ordonnancement par LocalSolver. Le premier objectif se dégageant de ces problématiques consiste à permettre aux utilisateurs du solveur de modéliser simplement un grand nombre de problèmes d'ordonnancement disjonctif. En tirant profit de la richesse du formalisme de modélisation ensembliste de LocalSolver, on propose des formulations génériques, adaptables à différentes familles de problèmes d'ordonnancement disjonctif, permettant d'exprimer simplement les notions de tâches, de relations de précédence, ou encore de contraintes de non-chevauchement des tâches affectées à une même ressource disjonctive. Les formulations génériques ainsi choisies reposent sur l'utilisation combinée de deux types de variables de décision offertes par LocalSolver : les variables entières, permettant de modéliser les dates de début et durées de tâches, ! et les variables de listes, représentant leur ordre sur les différentes ressources disjonctives.Le second objectif de la thèse consiste à améliorer les performances de LocalSolver sur les problèmes d'ordonnancement étudiés, en intégrant différents algorithmes de résolution les plus génériques possibles à la composante de recherche locale du solveur. Cette généricité des contributions est cruciale : en effet, on ne cherche pas à améliorer les performances du solveur sur un unique problème, ni même seulement sur les problèmes d'ordonnancement, mais sur tous les problèmes présentant des structures caractéristiques de l'ordonnancement disjonctif ou du packing.Les contributions algorithmiques de cette thèse peuvent être regroupées en trois grandes catégories : des algorithmes d'initialisation, des mouvements de recherche locale, et un algorithme de propagation de contraintes. On présente deux algorithmes constructifs d'initialisation des variables ensemblistes (sets et listes), aidant le solveur à trouver une solution réalisable immédiatement sur des problèmes comme ceux de l'Aircraft Landing ou de l'Assembly Line Balancing, et accélérant ainsi la recherche de solutions de bonne qualité sur ces problèmes. On présente également des mouvements de recherche locale, reposant sur la détection de structures spécifiques dans le modèle (contraintes de non-chevauchement des tâches, relations de précédence, contraintes de packing). On présente également un algorithme de réparation de solutions par propagation de contraintes, appelé au cours de la recherche locale après chaque mouvement conduisant à une solution in! faisable. Notre algorithme diffère de la propagation classique de la programmation par contraintes par plusieurs points. Par exemple, il ne propage que les réductions de domaine excluant la valeur courante des variables, et peut prendre des décisions arbitraires lorsqu'il rencontre une contrainte pouvant être réparée de différentes manières. On démontre que dans certains cas l’algorithme présente des propriétés lui assurant de trouver une réparation s'il en existe une. Cet algorithme permet de pallier les difficultés rencontrées par la recherche locale sur les problèmes d'ordonnancement aux contraintes très serrées (passer d'une bonne solution à une autre nécessite de réaliser des changements sur un grand nombre de variables). L'intégration de ces mouvements et de cet algorithme de réparation au sein de la recherche locale de LocalSolver apporte des gains de performance importants sur divers problèmes (Job Shop et variantes, Unit Commitment, Assemb! ly Line Balancing, ou encore Bin Packing).

Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance P and a sub-instance of another instance P′. In this paper, we study the complexity of both problems. We show that the former is GI-complete, and we prove the latter to be NP-complete. Nonethelss, we propose an algorithm to build an isomorphism, when possible. We report experimental trials on benchmark problems which demonstrate that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver., Dans le domaine de la planification automatique, décider si deux instances encodées en STRIPS sont isomorphes est la manière la plus élémentaire de comparer deux instances. C'est aussi un cas particulier du problème où l'on se donne deux instances P et P ′ , et l'on cherche un isomorphisme entre P et une sous-instance de P ′. Dans cet article, nous nous proposons d'étudier la complexité de ces deux problèmes. On montre que le premier est GI-complet, tandis que le second est NP-complet. Malgré cela, nous proposons un algorithme qui permet de construire un tel isomorphisme, lorsqu'il existe. De même, nous montrons expérimentalement que, sur nos jeux de tests, un pré-traitement basé sur des méthodes de propagation de contraintes permet d'améliorer significativement l'efficacité du solver SAT utilisé par notre algorithme.

In this thesis we show that symbolic reasoning associated with arc consistency checking is an efficient tool for images interpretation. We first show that this theoretical framework makes it possible to verify the spatial organization of different components of a complex object in an image. We then propose to extend the use of this framework to the selective recognition of shapes described by mathematical equations, thanks to the notion of hyper-arc consistency with bi-levels constraint. The relevance and feasibility of this approach have been validated by multiple tests. In addition, the results obtained on over-segmented images show that the proposed method is noise-resistant, even under conditions where humans (in some cases visual agnosia) may fail. These results support the interest of symbolic reasoning in image understanding.; Dans cette thèse nous montrons que le raisonnement symbolique associé à la vérification de la consistance d'arc avec propagation de contraintes est un outil efficace pour interpréter les images. Nous montrons dans un premier temps que ce cadre théorique permet de vérifier l'organisation spatiale de différentes composantes d'un objet complexe dans une image. Nous proposons ensuite d'étendre l'utilisation de celui-ci à la reconnaissance sélective des formes décrites par des équations mathématiques, grâce à la notion de consistance d'hyper-arc à deux niveaux de contraintes. La pertinence et la faisabilité de cette approche ont été validées par de multiples tests. En outre, les résultats obtenus sur des images sur-segmentées montrent que la méthode proposée est résistante au bruit, même dans des conditions où les humains (dans certains cas d'agnosie visuelle) peuvent échouer. Ces résultats soutiennent l'intérêt du raisonnement symbolique dans la compréhension de l'image.

In this thesis we show that symbolic reasoning associated with arc consistency checking is an efficient tool for images interpretation. We first show that this theoretical framework makes it possible to verify the spatial organization of different components of a complex object in an image. We then propose to extend the use of this framework to the selective recognition of shapes described by mathematical equations, thanks to the notion of hyper-arc consistency with bi-levels constraint. The relevance and feasibility of this approach have been validated by multiple tests. In addition, the results obtained on over-segmented images show that the proposed method is noise-resistant, even under conditions where humans (in some cases visual agnosia) may fail. These results support the interest of symbolic reasoning in image understanding., Dans cette thèse nous montrons que le raisonnement symbolique associé à la vérification de la consistance d'arc avec propagation de contraintes est un outil efficace pour interpréter les images. Nous montrons dans un premier temps que ce cadre théorique permet de vérifier l'organisation spatiale de différentes composantes d'un objet complexe dans une image. Nous proposons ensuite d'étendre l'utilisation de celui-ci à la reconnaissance sélective des formes décrites par des équations mathématiques, grâce à la notion de consistance d'hyper-arc à deux niveaux de contraintes. La pertinence et la faisabilité de cette approche ont été validées par de multiples tests. En outre, les résultats obtenus sur des images sur-segmentées montrent que la méthode proposée est résistante au bruit, même dans des conditions où les humains (dans certains cas d'agnosie visuelle) peuvent échouer. Ces résultats soutiennent l'intérêt du raisonnement symbolique dans la compréhension de l'image.

Resource constraint scheduling problems have been extensively studied in the literature. However, in most cases it is assumed that the activities have a fixed duration and require a constant amount of the resource throughout their execution. In this thesis, we propose to deal with a scheduling problem in which the tasks have a duration and a variable consumption consumption profile. This profile, which can vary as a function of time, is a decision variable of the problem on which the duration of the associated task depends. On the other hand, the consideration of linear and non-linear output functions for representing the use of resources complicates the problem and makes it possible to realistically model transfers of energy resources. For this NP-complete problem, we present several properties allowing to derive models and methods of resolution. These methods of resolution are divided into two parts. The first part shows the problem from the perspective of Constraint Programming and several methods derived from this paradigm are detailed including the development of energy thinking about the problem studied. The second part of the thesis is dedicated to approaches to Linear Programming and Mixed several models, including a continuous-time model based on the events, as well as theoretical analyzes and models of these enhancement techniques are presented. Finally, experiments come support the results presented in this manuscript.; Les problèmes d’ordonnancement à contraintes de ressource ont été largement étudiés dans la littérature. Cependant, dans la plupart des cas, il est supposé que les activités ont une durée fixe et nécessitent une quantité constante de la ressource durant toute leur exécution. Dans cette thèse, nous nous proposons de traiter un problème d’ordonnancement dans lequel les tâches ont une durée et un profil de consommation de ressource variables. Ce profil, qui peut varier en fonction du temps, est une variable de décision du problème dont dépend la durée de la tâche associée. Par ailleurs, la considération de fonctions de rendement linéaires et non linéaires pour la représentation de l’utilisation des ressources complexifie le problème et permet de modéliser de manière réaliste les transferts de ressources énergétiques. Pour ce problème NP-complet, nous présentons plusieurs propriétés permettant de dériver des modèles et méthodes de résolution. Ces méthodes de résolution sont divisées en deux parties. La première partie visualise ce problème du point de vue de la Programmation Par Contraintes et plusieurs méthodes dérivées de ce paradigme sont détaillées dont le développement du raisonnement énergétique sur le problème étudié. La seconde partie de la thèse est dédiée à des approches de Programmation Linéaire Mixte et plusieurs modèles, notamment un modèle à temps continu basé sur les événements, ainsi que des analyses théoriques et des techniques d’amélioration de ces modèles sont présentés. Enfin, des expérimentations viennent appuyer les résultats présentés dans ce manuscrit.

Historiquement, la programmation par contraintes est une discipline située à la croisée de nombreux domaines comme la recherche opérationnelle, l’analyse numérique, le calcul symbolique, la programmation logique et l’intelligence artificielle.Raisonner par « contraintes » c’est s’interroger sur les propriétés intrinsèques caractérisant la sémantique d’un problème. Nous entendons par là que cette discipline a pour vocation de s’abstraire autant que possible de tout raisonnement opérationnel afin de se concentrer sur une spécification conceptuelle de chaque problème. En cela, la programmation par contraintes est un paradigme déclaratif. Aujourd’hui, tout système de programmation par contraintes se doit de proposer trois composantes essentielles que sont la propagation, la recherche et la modélisation. Dans ce contexte, parler de flexibilité et d’efficacité c’est s’interroger sur la part qu’occupe chacun des éléments de ce triptyque du point de vue d’un utilisateur. L’objet de cette habilitation est donc de synthétiser différents éléments et questionnements autour d’aspects liés à la propagation, aux filtrages et à la stratégie de recherche dans les systèmes de contraintes. Plus précisément, mon intérêt s’est porté sur l’analyse des stratégies de propagation dans les systèmes de contraintes, le comportement des algorithmes de filtrages au sein de ces stratégies de propagation, mais aussi la prise en compte de besoin métiers de plus en plus pressants autour de stratégies de recherche pour les problèmes d’optimisation. Le lien entre ces éléments a été porté par une interrogation permanente sur la dichotomie entre une vision très conceptuelle de la programmation par contraintes, reposant sur la notion de déclarativité (l’outil de résolution étant alors entièrement caché à l’utilisateur), et une vision très opérationnelle où l’utilisateur final souhaite maitriser parfaitement son processus de résolution : Quelle stratégie de recherche adopter et pour quel problème ? Quelle contrainte / filtrage utiliser et dans quel contexte ? L’optimalité est-elle un besoin ou la recherche d’une solution de bonne qualité est-elle suffisante ?

This thesis deals with the vehicle locationand addresses the problem of SLAM (simultaneous localization and mapping). Several methods are used to solve this kind of problem. They can be classified into two broad categories of approaches: probabilistic approach and deterministic approaches. This work addresses the deterministic approaches and more precisely the approach based on interval analysis. The work has been conducted on real data sets collected in outdoor environments with proprioceptive and exteroceptive sensors.When multiple sensors providing complementary or redundant information are put into play, it is important to merge the data to improve the estimated pose. The approach detailed in this document uses the intervals methods and presents the localization problem as a constraint satisfaction problem.The resolution is done using a solver interval. Several solvers were compared. One thing is clear: local consistency algorithms do not address the uncertainty of the orientation. This thesis proposes a method of locating usable in real time applications and corrects the uncertainty in the heading of the vehicle. We compared our results with those of the extended Kalman filter (probabilistic reference method) and highlighted one of the interests of our method: the assurance of consistency of the pose (position and orientation of the mobile).This thesis proposes two contributions. The first is methodological. In the state of the art all works affirm the need (or obligation) to pre-decompose the constraints of the problem before the resolution step. Our work allows to prove otherwise. The second contribution relates to the reduction of the orientation uncertainty by combining constraint propagation and a bisection approach.; Cette thèse traite de la localisation de véhicule. Plusieurs méthodes sont utilisées pour résoudre ce type de problème. Elles peuvent être classées en deux grandes catégories d’approches : les approches probabilistes et les approches déterministes.Ce travail aborde les approches déterministes et plus précisément l'approche ensembliste basée sur l'analyse par intervalles. Les travaux ont été conduits sur des jeux de données réelles collectées en environnements d'extérieur comprenant des capteurs proprioceptifs et extéroceptifs.Lorsque l'on met en jeu plusieurs capteurs fournissant des informations complémentaires ou redondantes, il est important de fusionner les données afin d'améliorer la pose estimée. L'approche détaillée dans ce document utilise les méthodes intervalles et présente le problème de la localisation sous la forme d'un problème de satisfaction de contraintes.La résolution se fait à l'aide d’un solveur à intervalles. Plusieurs algorithmes ont été comparés. Un constat s'est dégagé : les algorithmes de consistance locale ne corrigent pas l'incertitude sur l’orientation. Cette thèse propose une méthode de localisation utilisable dans des applications temps réel et qui corrige l'incertitude sur le cap du véhicule. Nous avons comparé nos résultats à ceux du filtre de Kalman étendu (méthode probabiliste de référence) et mis en avant un des intérêts de notre méthode : l'assurance d'une consistance de la pose (position et orientation du mobile).Cette thèse propose deux contributions. La première est d'ordre méthodologique. Dans l'état de l'art tous les travaux affirment la nécessité (voire l'obligation) d'une décomposition préalable des contraintes du problème avant l'étape de résolution. Nos travaux permettent de prouver le contraire. La deuxième contribution concerne la réduction du domaine de l'incertitude en orientation en couplant la propagation de contraintes et une approche de bissection.

Prix jeune chercheur; International audience; Sequence constraints are useful in a number of applications. Constraints of this class enforce upper and/or lower bounds on all sub-sequences of variables of a given length within a main sequence. For instance, in Crew-Rostering problems, we may want to have an upper bound on the number of worked days in every sub-sequence to meet working regulations. Several constraints of this class have been studied in the Constraint Programming (CP) literature such as GenSequence, AmongSeq, etc. An even more general constraint, Regular, can be used to enforce arbitrary patterns on all sub-sequences. However, the more general a constraint is, the higher is the complexity of reasoning about it. We therefore investigate the AtMostSeqCard constraint, a particular case where the sequence of variables is subject to a chain of AtMost constraints (all subsequences of size q have at most u values in a set v) along with a global cardinality. This constraint is useful in Car-Sequencing and Crew-Rosterning problems. In [van Hoeve et al.], two algorithms designed for the AmongSeq constraint were adapted to this constraint with an O(2^q . n) and O(\n^3) worst case time complexity, respectively. In [Maher et al.], another algorithm similarly adaptable to filter the AtMostSeqCard constraint with a time complexity of O(n^2) was proposed. We summarize our contributions regarding this constraint in three different axis. We first introduce an algorithm for achieving arc consistency on the AtMostSeqCard constraint with an O(n) (hence optimal) worst case time complexity. Next, we present practical extensions of this constraint and show how the propagator scales accordingly. We finally propose a novel linear time mechanism for explaining this constraint in a hybrid CP/SAT context.Our experiments show significant improvements on Car-sequencing and Crew-Rostering problems.

Hybridization of incomplete and constraint programming techniques for solving Constraint Satisfaction Problems is generally restricted to some kind of master-slave combinations for specific classes of problems. In this PhD thesis, we are concerned with the design of a hybrid resolution framework based on K.R. Apt's chaotic iterations. In this framework, basic resolution processesare abstracted by functions over an ordered structure. This allows us to consider the different resolution agents at a same level and to study more precisely various strategies for hybridization of local search, genetic algorithms and constraint propagation.Hybrid resolution can be achieved as the computation of a fixed point of some specific reduction functions. Our framework opens up new and finer possibilities for hybridization/combination strategies. Our prototype implementation gave experimental results showing the interest of the model to design such hybridizations.; L'hybridation des mécanismes de méthodes incomplètes et des techniques de programmation par contraintes est souvent basée sur des combinaisons de type maître-esclave, dédiées à la résolution de classes de problèmes spécifiques. Dans cette thèse, nous nous intéressons à la définition d'un modèle théorique uniforme, basé sur les itérations chaotiques de K.R. Apt qui définissent un cadre mathématique pour l'itération d'un ensemble fini de fonctions sur des domaines abstraits munis d'un ordre partiel. Ce cadre permetde prendre en compte une hybridation entre les méthodes incomplètes et les méthodes complètes. Dans ce contexte, la résolution s'apparente à un calcul de point fixe d'un ensemble de fonctions de réductions spécifiques. Notre cadre générique permet alors d'envisager des stratégies de combinaisons et d'hybridation de manière plus fine et d'étudier leurs propriétés. Nous avons employé un cadre général approprié pour modéliser la résolution des problèmes d'optimisation et nous présentons des résultatsexpérimentaux qui mettent en avant les atouts de tellescombinaisons en regard d'une utilisation indépendante des techniques de résolution.

Jean-Pierre Campagne et Jean-Paul Bourrières : rapporteurs; Damien Trentesaux : examinateur; Gérard Authié : président du jury; Yves Jeannerod (Ordosoftware) : invités. Thèse sous convention CIFRE avec la société Ordosoftware; This work proposes a method which assists the firms for cooperating in make-to-order production. The method organizes a production process which is distributed over several companies, by lowering the production stocks with the aim of decreasing production costs. In the selected approach, the global organization is achieved progressively by a set of cooperations between pairs of actors of the supply chain. We study in particular the customer-supplier relationship for which the cooperation process concerns the attributes of the orders transmitted by the customer to the supplier. We assume that the relation is governed by a cooperation contract which defines a more contractual framework to the cooperation between the decision-makers. Our objective is to design support tools that assist them during this cooperation process.; Ce travail propose une méthode d'aide à la coopération inter-entreprises dans un contexte de production à la commande. L'objectif est de tendre les flux de production inter-entreprises grâce à une coopération entre les décideurs de chaque entreprise. L'approche retenue assimile le problème d'organisation globale à un processus de décision distribuée dans lequel l'organisation est progressivement construite par un ensemble de coopérations entre des couples d'acteurs du réseau d'entreprises. Nous étudions en particulier les couples d'entreprises client-fournisseur pour lesquels la coopération concerne les attributs des commandes passées entre eux. Nos objectifs sont de fournir aux décideurs un cadre plus formel qui contractualise la coopération et des outils d'aide à la décision pour la coopération permettant de les assister dans les diverses phases du processus.

Jean-Pierre Campagne et Jean-Paul Bourrières : rapporteurs; Damien Trentesaux : examinateur; Gérard Authié : président du jury; Yves Jeannerod (Ordosoftware) : invités. Thèse sous convention CIFRE avec la société Ordosoftware; This work proposes a method which assists the firms for cooperating in make-to-order production. The method organizes a production process which is distributed over several companies, by lowering the production stocks with the aim of decreasing production costs. In the selected approach, the global organization is achieved progressively by a set of cooperations between pairs of actors of the supply chain. We study in particular the customer-supplier relationship for which the cooperation process concerns the attributes of the orders transmitted by the customer to the supplier. We assume that the relation is governed by a cooperation contract which defines a more contractual framework to the cooperation between the decision-makers. Our objective is to design support tools that assist them during this cooperation process.; Ce travail propose une méthode d'aide à la coopération inter-entreprises dans un contexte de production à la commande. L'objectif est de tendre les flux de production inter-entreprises grâce à une coopération entre les décideurs de chaque entreprise. L'approche retenue assimile le problème d'organisation globale à un processus de décision distribuée dans lequel l'organisation est progressivement construite par un ensemble de coopérations entre des couples d'acteurs du réseau d'entreprises. Nous étudions en particulier les couples d'entreprises client-fournisseur pour lesquels la coopération concerne les attributs des commandes passées entre eux. Nos objectifs sont de fournir aux décideurs un cadre plus formel qui contractualise la coopération et des outils d'aide à la décision pour la coopération permettant de les assister dans les diverses phases du processus.

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.

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.

Building a parametric model from experimental data raises numerous questions that one would wish to solve in a guaranteed way, as they condition the success of the operation:- is the model structure appropriate?- is the selected sensor able to fulfill the experimenters' requirements?- have all the values of the parameters consistent with the data and the hypotheses been found?- may numerical errors have falsified the results?In order to attempt to answer these questions, the direction followed in this thesis is to formulate each of them in a set-theoretical framework. Branch and bound algorithms using interval analysis then provide guaranteed inner and outer approximations of the resulting sets. We show that the size of the problems that can be treated ùay be significantly increased by using contractors developed in the context of constraint satisfaction programming.The estimation of unidentifiable kinetic parameters of an electrochemical reaction illustrates the performances of this approach. THe characterization of a new experimental set-up to measure thermal properties of materials taking into account intrinsic uncertainty is made possible by a new algorithm to project sets in a guaranteed way.The set-theoretical formulation of the analysis of structural properties of models leads to new definitions of identifiability and distinguishability, which seem more appropriate than the traditional ones. Algorithms to test such properties are also presented. We finally propose a new way to evaluate the characteristics of a sensor in terms of accuracy.; La construction d'un modèle paramétrique à partir de données expérimentales soulève de nombreuses questions auxquelles l'expérimentateur souhaiterait répondre de façon garantie, car elles conditionnent le succès de l'opération :- la structure de modèle retenue est-elle pertinente?- le capteur sélectionné permet-il de satisfaire les contraintes du cahier des charges de l'expérience?- toutes les valeurs des paramètres compatibles avec les données et les hypothèses ont-elles été trouvées?- les erreurs d'arrondi du calculateur faussent-elles les résultats?Pour tenter de répondre à ces questions, cette thèse prend le partir de les aborder dans une perspective ensembliste. L'obtention d'approximations intérieure et extérieur des ensembles résultants, à l'aide de l'analyse par intervalles, assure alors cette garantie. Nous montrons que la taille des problèmes qu'il est possible de traiter peut être significativement augmentée par l'emploi de contracteurs issus de la programmation par contraintes.L'estimation de paramètres cinétiques non-identifiables en électrochimie illustre les performances de cette approche. La caractérisation d'un nouveau dispositif de mesure en thermique,en tenant compte des incertitudes intrinsèques à ce dispositif, est rendue possible par un nouvel algorithme de projection garantie d'ensembles.La formulation ensembliste du problème de la caractérisation de structures de modèles permet également de proposer de nouvelles définitions de l'identifiabilité et de la discernabilité, qui semblent plus pertinentes que les notions traditionnelles. Des algorithmes qui permettent le test effectif de ces propriétés sont également proposés. Enfin, une évaluation des caractéristiques d'un capteur en terme de précision est présentée.

Not available, Nous avons choisi un nouveau modèle de représentation des informations temporelles fondé sur la logique réifiée (l'algèbre d'intervalles). Nous avons étendu cette algèbre pour qu'elle intègre aussi bien les informations numériques que les informations symboliques. Cette représentation se base sur un domaine discret du temps ainsi que sur la notion de multi-granularité pour représenter les différentes granularités du temps. Les différentes tâches de raisonnement à effectuer par un gestionnaire de graphes temporels (TMM), ainsi que la nature hétérogène des contraintes temporelles nous ont amené à implanter une nouvelle méthode de propagation de contraintes temporelles. Elle consiste à séparer la propagation de ces deux types de contraintes et à échanger leurs résultats via un module de communication. Notre choix s'est porté sur l'algorithme optimal GAC4 que nous avons étendu pour prendre en compte le raisonnement temporel. Cependant, GAC4 souffre d'inconvénients tels que la consommation importante d'espace mémoire pendant le processus d'énumération. Nous avons implanté l'algorithme ANGEL pour vérifier la cohérence d'arcs. C'est un algorithme dynamique capable de faire face à un monde évolutif. Grâce à son aspect fonctionnel, un compromis entre l'espace mémoire, la vitesse d'exécution et la complexité a été trouvé. Un outil de raisonnement, TemPro, a été construit à partir de ces principes. Nous avons aussi défini un langage afin de gérer et d'interroger le graphe temporel. TemPro fonctionne en tant que boîte noire et ce langage sert d'interface entre l'outil et un moteur d'inférences. TemPro peut être utilisé pour des applications telles que l'ordonnancement de tâches, l'allocation de ressources, etc.