L’intérêt des différents langages de la famille des diagrammes de décisionvalués (VDD) est qu’ils admettent des algorithmes en temps polynomialpour des traitements (comme l’optimisation, la cohérence inverse globale,l’inférence) qui ne sont pas polynomiaux (sous l’hypothèse P 6= NP), si ilssont effectués sur le problème dans sa forme originale tel que les réseaux decontraintes ou les réseaux bayésiens.Dans cette thèse, nous nous intéressons au problème de configuration deproduit, et plus spécifiquement, la configuration en ligne avec fonction de valuationassociée (typiquement, un prix). Ici, la présence d’un utilisateur enligne nous impose une réponse rapide à ses requêtes, rapidité rendant impossiblel’utilisation de langages n’admettant pas d’algorithmes en temps polynomialpour ces requêtes. La solution proposée est de compiler hors-ligneces problèmes vers des langages satisfaisant ces requêtes, afin de diminuer letemps de réponse pour l’utilisateur.Une première partie de cette thèse est consacrée à l’étude théorique desVDD, et plus particulièrement les trois langages Algebraic Decision Diagrams,Semi ring Labelled Decision Diagrams et Affine Algebraic Decision Diagrams(ADD, SLDD et AADD). Nous y remanions le cadre de définition des SLDD,proposons des procédures de traductions entre ces langages, et étudions la compacitéthéorique de ces langages. Nous établissons dans une deuxième partie lacarte de compilation de ces langages, dans laquelle nous déterminons la complexitéalgorithmique d’un ensemble de requêtes et transformations correspondantà nos besoins. Nous proposons également un algorithme de compilationà approche ascendante, ainsi que plusieurs heuristiques d’ordonnancement devariables et contraintes visant à minimiser la taille de la représentation aprèscompilation ainsi que le temps de compilation. Enfin la dernière partie estconsacrée à l’étude expérimentale de la compilation et de l’utilisation de formescompilées pour la configuration de produit. Ces expérimentations confirmentl’intérêt de notre approche pour la configuration en ligne de produit.Nous avons implémenté au cours de cette thèse un compilateur (le compilateurSALADD) pleinement fonctionnel, réalisant la compilation de réseauxde contraintes et de réseaux bayésiens, et avons développés un ensemble defonctions adaptées à la configuration de produit. Le bon fonctionnement etles bonnes performances de ce compilateur ont été validés via un protocole devalidation commun à plusieurs solveurs. / The different languages from the valued decision diagrams (VDD) family benefitfrom polynomial-time algorithms for some tasks of interest (such as optimization,global inverse consistency, inference) for which no polynomial-timealgorithm exists (unless P = NP) when the input is a constraint network ora Bayesian network considered at start.In this thesis, we focus on configuration product problems, and more specificallyon-line configuration with an associated valuation function (typically, aprice). In this case, the existence of an on-line user forces us to quickly answerto his requests, making impossible the use of languages that does not admitpolynomial-time algorithm for this requests. Therefore, our solution consistsin an off-line compilation of these problems into languages that admit suchpolynomial-time algorithms, and thus decreasing the latency for the user.The first part of this thesis is dedicated to the theoretical study of VDDs,an more specifically Algebraic Decision Diagrams (ADDs), Semi ring LabelledDecision Diagrams (SLDDs) and Affine Algebraic Decision Diagrams(AADDs). We revisit the SLDD framework, propose translation proceduresbetween these languages and study the succinctness of these languages. In asecond part, we establish a knowledge compilation map of these languages,in which we determine the complexity of requests and transformations correspondingto our needs. We also propose a bottom-up compilation algorithmand several variables and constraints ordering heuristics whose aim is to reducethe size of the compiled form, and the compilation time. The last partis an experimental study of the compilation and the use of the compiled formin product configuration. These experimentations confirm the interest of ourapproach for on-line product configuration.We also implemented a fully functional bottom-up compiler (the SALADDcompiler), which is capable of compiling constraints network and Bayesian networkinto SLDDs. We also developed a set of functions dedicated to productconfiguration. The proper functioning and good performances of this programwas validated by a validation protocol common to several solvers.

Le système PLM est l'un des outils stratégiques de l'entreprise. Ces systèmes sont sujets à des changements récurrents dans l'entreprise. Les évolutions organisationnelles, le changement de l'offre produit ou encore le remplacement de logiciels PLM peuvent déclencher l'évolution du système d'information PLM. Une des structures les plus importantes dans les systèmes PLM est le modèle du produit, autour duquel s'articule les informations et processus. C'est autour du modèle produit que se concentrent nos recherches. Les causes d'évolution des modèles produits sont des éléments signifiants qui différencient les étapes de la démarche à suivre. Les méthodes d'IDM sont utilisées afin de formaliser la transformation des modèles. En plus, cette démarche bénéfice d'un cadre de similarité spécialement développé pour la configuration de produit. Un exemple industriel est illustré et résolu en appliquant cette démarche. Il s'agit de l'évolution d'un système gérant les modèles spécifiques de produit vers un système qui est capable de construire et d'utiliser les modèles génériques de produit. Un outil informatique support à nos travaux est développé dans le cadre d'Eclipse.

Le système PLM est l’un des outils stratégiques de l’entreprise. Ces systèmes sont sujets à des changements récurrents dans l’entreprise. Les évolutions organisationnelles, le changement de l’offre produit ou encore le remplacement de logiciels PLM peuvent déclencher l’évolution du système d’information PLM. Une des structures les plus importantes dans les systèmes PLM est le modèle du produit, autour duquel s’articule les informations et processus. C’est autour du modèle produit que se concentrent nos recherches. Les causes d’évolution des modèles produits sont des éléments signifiants qui différencient les étapes de la démarche à suivre. Les méthodes d’IDM sont utilisées afin de formaliser la transformation des modèles. En plus, cette démarche bénéfice d’un cadre de similarité spécialement développé pour la configuration de produit. Un exemple industriel est illustré et résolu en appliquant cette démarche. Il s’agit de l’évolution d’un système gérant les modèles spécifiques de produit vers un système qui est capable de construire et d’utiliser les modèles génériques de produit. Un outil informatique support à nos travaux est développé dans le cadre d'Eclipse. / PLM systems are among the strategic components of enterprise’s information system architecture. These systems undergo frequent evolutions of enterprise. Organizational evolution or product offer variation as well as PLM application replacement may launch PLM systems’ evolution.One of the important structures in PLM systems is the product configuration, which organize and structure all product’s information and processes. Our research activities concern product model evolution. Reasons of product model evolution specify the appropriate methodology and necessary steps in order to handle it. MDE methods are used to formalize the model transformation process.Moreover, our methodology contains a specific similarity framework dedicated to product configuration. An industrial example was illustrated and resolved by this methodology. The problematic of this example is the migration of a system which manage only specific product configuration to a new system that is capable to construct and use generic models of product.

Dans un contexte de personnalisation de masse, la configuration concourante du produit et de son processus d’obtention constituent un défi industriel important : de nombreuses options ou alternatives, de nombreux liens ou contraintes et un besoin d’optimisation des choix réalisés doivent être pris en compte. Ce problème est intitulé O-CPPC (Optimization of Concurrent Product and Process Configuration). Nous considérons ce problème comme un CSP (Constraints Satisfaction Problem) et l’optimisons avec des algorithmes évolutionnaires. Un état de l’art fait apparaître : i) que la plupart des travaux de recherche sont illustrés sur des exemples spécifiques à un cas industriel ou académique et peu représentatifs de la diversité existante ; ii) un besoin d’amélioration des performances d’optimisation afin de gagner en interactivité et faire face à des problèmes de taille plus conséquente. En réponse au premier point, ces travaux de thèse proposent les briques d’un modèle générique du problème O-CPPC. Ces briques permettent d’architecturer le produit et son processus d’obtention. Ce modèle générique est utilisé pour générer un benchmark réaliste pour évaluer les algorithmes d’optimisation. Ce benchmark est ensuite utilisé pour analyser la performance de l’approche évolutionnaire CFB-EA. L’une des forces de cette approche est de proposer rapidement un front de Pareto proche de l’optimum. Pour répondre au second point, une amélioration de cette méthode est proposée puis évaluée. L’idée est, à partir d’un premier front de Pareto approximatif déterminé très rapidement, de demander à l’utilisateur de choisir une zone d’intérêt et de restreindre la recherche de solutions uniquement sur cette zone. Cette amélioration entraine des gains de temps de calcul importants. / In a context of mass customization, the concurrent configuration of the product and its production process constitute an important industrial challenge: Numerous options or alternatives, numerous links or constraints and a need to optimize the choices made. This problem is called O-CPPC (Optimization of Concurrent Product and Process Configuration). We consider this problem as a CSP (Constraints Satisfaction Problem) and optimize it with evolutionary algorithms. A state of the art shows that: i) most studies are illustrated with examples specific to an industrial or academic case and not representative of the existing diversity; ii) a need to improve optimization performance in order to gain interactivity and face larger problems. In response to the first point, this thesis proposes a generic model of the O-CPPC problem. This generic model is used to generate a realistic benchmark for evaluating optimization algorithms. This benchmark is then used to analyze the performance of the CFB-EA evolutionary approach. One of the strengths of this approach is to quickly propose a Pareto front near the optimum. To answer the second point, an improvement of this method is proposed and evaluated. The idea is, from a first approximate Pareto front, to ask the user to choose an area of interest and to restrict the search for solutions only on this area. This improvement results in significant computing time savings.