L’étude de la planification entre partenaires coopérant au sein d’une chaine logistique au niveau tactique fait l’objet de cette thèse. Le présent travail se focalise plus particulièrement sur la coordination des processus de planification des activités de transport et de production, autour d’une nouvelle approche fondée sur la théorie des jeux. Deux situations de coopération sont considérées, selon le caractère homogène ou hétérogène des partenaires ; ainsi une première étude est menée sur un ensemble d’opérateurs de transport pour ensuite être étendue à la relation entre l’entreprise manufacturière et les transporteurs qui travaillent avec elle. L’expérimentation s’appuie sur des modèles mathématiques en programmation linéaire pour simuler les processus de planification des différents groupes de partenaires (également appelés coalitions), un protocole de coopération utilisant certaines propriétés liées à la théorie des jeux et sur une répartition équitable des gains / coûts telle que préconisée par la valeur de Shapley. Les modèles et l’ensemble du protocole sont appliqués à deux cas d’étude basés sur des jeux de données réalistes. / This thesis focuses on the collaboration between partners inside supply chain at the tactical level of planning. This work aims to develop a new approach based on game theory to solve the problem of coordinating processes concerned by production and transportation planning decision making. Two types of coalitions cooperative games are implemented according to the nature of partners: the cooperation between homogeneous partners concerns multiple transport operators while the other case is more on the relationships between heterogeneous partners including one manufacturer and multiple transport operators. The coordination is supported by mathematical models implemented in linear programming which simulate the planning process within the various possible pools of partners, also called “coalitions”. These models are used in a gains/costs sharing protocol between the partners which is based on the Shapley value. Some basic properties are checked in order to verify if the cooperation is valid. The models and the protocol are assessed on theoretical test cases based on realistic data sets.

Cette thèse présente une étude des systèmes dynamiques polynomiaux motivée à la fois par le grand spectre d'applications de cetteclasse (modèles de réactions chimiques, modèles de circuits électriques ainsi que les modèles biologiques) et par la difficulté (voire incapacité)de la résolution théorique de tels systèmes. Dans une première partie préliminaire, nous présentons les polynômes multi-variés et nous introduisons les notions de forme polaire d'un polynôme (floraison) et de polynômes de Bernstein qui seront d'un grand intérêt par la suite. Dans une deuxième partie, nous considérons le problème d'optimisation polynomial dit POP. Nous décrivons dans un premier temps les principales méthodes existantes permettant de résoudre ou d'approcher la solution d'un tel problème. Puis, nous présentons deux relaxations linéaires se basant respectivement sur le principe de floraison ainsi que les polynômes de Bernstein permettant d'approcher la valeur optimale du POP. La dernière partie de la thèse sera consacré aux applications de nos deux méthodes de relaxation dans le cadre des systèmes dynamiques polynomiaux. Une première application s'inscrit dans le cadre de l'analyse d'atteignabilité: en effet, on utilisera notre relaxation de Bernsteinpour pouvoir construire un algorithme permettant d'approximer les ensembles atteignables d'un système dynamique polynomial discrétisé. Une deuxième application sera la vérification et le calcul d'invariants pour un système dynamique polynomial. Une troisième application consiste à calculer un contrôleur et un invariant pour un système dynamique polynomial soumis à des perturbations. Dans le contexte de l'invariance, on utilisera la relaxation se basant sur le principe de floraison.Enfin, une dernière application sera d'exploiter les principales propriétés de la forme polaire pour pouvoir étudier des systèmes dynamiques polynomiaux dans des rectangles. / This thesis presents a study of polynomial dynamical systems motivated by both thewide spectrum of applications of this class (chemical reaction models, electrical modelsand biological models) and the difficulty (or inability) of theoretical resolutionof such systems.In a first preliminary part, we present multivariate polynomials and we introducethe notion of polar form of a polynomial (blossoming) and Bernstein polynomialswhich will be of great interest thereafter.In a second part, we consider the polynomial optimization problem said POP.We first describe existing methods allowing us to solve or approximate the solution5TABLE DES MATI`ERES 6of such problems. Then, we present two linear relaxations based respectively on theblossoming principle and the Bernstein polynomials allowing us to approximate theoptimal value of the POP.The last part of the thesis is devoted to applications of the two relaxation methodsin the context of polynomial dynamical systems. A first application is in thecontext of reachability analysis. In fact, we use our Bernstein relaxation in order tobuild an algorithm allowing us to approximate the reachable sets of a discretizedpolynomial dynamical system. A second application deals with the verification andthe computation of invariants for polynomial dynamical systems. A third applicationconsists in calculating a controller and an invariant for a polynomial dynamicalsystem subject to disturbances. For the invariance problem, we use the relaxationbased on the blossoming principle. Finally, the last application consists in exploitingthe main properties of the polar form in order to study polynomial dynamicalsystems in rectangles.

Cette thèse présente la nouvelle implémentation de la Verified Polyhedra Library (VPL), une bibliothèque efficace de calcul polyédral.Elle fournit des opérateurs certifiés en Coq, s'appliquant sur des représentations en contraintes.La version précédente souffrait d'inefficacité lors d'opérateurs cruciaux, à savoir l'élimination de variables et l'enveloppe convexe.Dans ce document, je présente des améliorations importantes qui bénéficient à la modularité, la simplicité et au passage à l'échelle de la bibliothèque:le processus de certification est généralisé et simplifié;les conditions polynomiales sont maintenant traitées;Les calculs qui n'impliquent pas de certification sont effectués en flottant;de nouveaux algorithmes sont fournis pour la minimisation de représentation et la détection d'égalités implicites.D'un côté, l'implémentation d'un solveur de problèmes de Programmation Linéaire Paramétrique (PLP) a mené à une meilleure efficacité tant en nombre de contraintes que de générateurs.L'élimination de variables et l'enveloppe convexe sont tous deux encodés en problème PLP.Le PLP est un outil générique possédant de nombreuses applications, et qui permet d'éviter la génération de redondances grâce à l'utilisation d'une contrainte de normalisation.De plus, nous proposons de nouveaux opérateurs pour la gestion des contraintes polynomiales, l'un d'entre eux étant également encodé en tant que problème PLP.De l'autre, la certification de la bibliothèque a été grandement optimisée et simplifiée.La VPL suit un paradigme de vérification a posteriori, où les calculs non triviaux sont effectués par des oracles externes générant des témoins de correction.Ces témoins sont ensuite validés par un vérifieur écrit en Coq.Grâce à un cadre de certification puissant et innovant, le Polymorphic Factory Style (PFS), la plupart des aspects délicats de la génération de témoins sont maintenant évitée.La souplesse du PFS est démontrée par la création d'une tactique en COQ qui découvre les égalités implicites en arithmétique linéaire. / This thesis presents the design and implementation of the Verified Polyhedra Library (VPL), a scalable library for polyhedral calculus.It provides Coq-certified polyhedral operators that work on constraints-only representation.The previous version was inefficient on crucial operations, namely variable elimination and convex hull.In this work, I present major improvements that have been made in scalability, modularity and simplicity:The certification process is generalized and simplified;Polynomial guards can now be handled;Computations that do not involve certification use floating-points;New algorithms are presented for minimization and detection of implicit equalities.On the one hand, the implementation of a solver for Parametric Linear Programming (PLP) problems led to an improved scalability both in dimension and in number of constraints.Variable elimination and convex hull are now encoded as such.PLP is a generic tool that has many applications, and that avoids generating redundancies thanks to a normalization constraint.Additionally, we provide new operators for handling multivariate polynomials, one of which being also encoded as a PLP problem.On the other hand, the certification part of the library has been greatly optimized and simplified.The VPL follows a result-verification paradigm, where complex computations are performed by untrusted oracles that generate witnesses of correctness, themselves validated by a certified Coq checker.Thanks to an innovative and powerful certification framework known as Polymorphic Factory Style (PFS), most cumbersome parts of the witness generation are now avoided.The flexibility of PFS is attested by the creation of a Coq tactic for learning equalities in linear arithmetic.

Cette thèse concerne à la gestion globale à base de modèle des flux énergétiques dans le bâtiment. L'objectif des systèmes de gestion de l’énergie proposés est d’aider les occupants à gérer leur système bâtiment en planifiant la consommation/production des différents équipements présents en fonction des tarifs, de la disponibilité de l'énergie et des usages de l'occupant. L’objectif de cette thèse est de proposer une approche de résolution multi-solveurs s'appuyant sur le paradigme multi-agent.Pour y parvenir, nous avons développé, dans un premier temps, un service multi-phase, qui représente plusieurs phases flexibles avec des niveaux de consommation différents, offrant un niveau de précision supérieure pour des équipements comme une machine à laver. Dans un second temps, notre travail a consisté à proposer une nouvelle approche d’optimisation combinant différents solveurs embarqués dans des agents logiciels. Le résultat est une approche d’optimisation hybride à base d’agents, s’appuyant sur des algorithmes PLNE et des méta-heuristiques. / This PhD focuses on the global energy management based on energetical flux models ofbuildings. The objective of the energy management system is to help the inhabitants to manage theirbuilding, by scheduling the consumption/production of the different appliances, taking into accountenergy costs, availability et inhabitants’ preferences. The PhD objective is to propose a resolution approach with several solvers inspired by the multi agent systems.A multi-phasis service representing several phasis has been developped. Each phasis is defined by its own consumption level. This type of service presents a better precision than singlephasis approaches to model some appliances. A new optimization approach has been developped. Itcombines different solvers embedded into software agents. The results is an hybrid approach forthe optimization based on the multi-agent system, using MILP algorithms and meta-heuristics.

La construction de modèles qui protègent contre les incertitudes dans les données, telles que la variabilité de l'information et l'imprécision est une des principales préoccupations en optimisation sous incertitude. L'incertitude peut affecter différentes domaines, comme le transport, les télécommunications, la finance, etc. ainsi que les différentes parts d'un problème d'optimisation, comme les coefficients de la fonction objectif et /ou les contraintes. De plus, l'ensemble des données incertaines peut être modélisé de différentes façons, comme sous ensembles compactes et convexes de l´espace réel de dimension n, polytopes, produits Cartésiens des intervalles, ellipsoïdes, etc.<p><p>Une des approches possibles pour résoudre des tels problèmes est de considérer les versions minimax regret, pour lesquelles résoudre un problème sous incertitude revient à trouver une solution qui s'écarte le moins possible de la valeur solution optimale dans tout les cas. <p><p>Dans le cas des incertitudes définies par intervalles, les versions minimax regret de nombreux problèmes combinatoires polynomiaux sont NP-difficiles, d'ou l'importance d'essayer de réduire l'espace des solutions. Dans ce contexte, savoir quand un élément du problème, représenté par une variable, fait toujours ou jamais partie d'une solution optimal pour toute réalisation des données (variables 1-persistentes et 0-persistentes respectivement), constitue une manière de réduire la taille du problème. Un des principaux objectifs de cette thèse est d'étudier ces questions pour quelques problèmes d'optimisation combinatoire sous incertitude.<p><p>Nous étudions les versions minimax regret du problème du choix de p éléments parmi m, de l'arbre couvrant minimum et des deux problèmes de plus court chemin. Pour de tels problèmes, dans le cas des incertitudes définis par intervalles, nous étudions le problème de trouver les variables 1- et 0-persistentes. Nous présentons une procédure de pre-traitement du problème, lequel réduit grandement la taille des formulations des versions de minimax regret.<p><p>Nous nous intéressons aussi à la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont incertains et l'ensemble des données incertaines est polyédral. Dans le cas où l'ensemble des incertitudes est défini par des intervalles, le problème de trouver le regret maximum est NP-difficile. Nous présentons des cas spéciaux ou les problèmes de maximum regret et de minimax regret sont polynomiaux. Dans le cas où l´ensemble des incertitudes est défini par un polytope, nous présentons un algorithme pour trouver une solution exacte au problème de minimax regret et nous discutons les résultats numériques obtenus dans un grand nombre d´instances générées aléatoirement.<p><p>Nous étudions les relations entre le problème de 1-centre continu et la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont évalués à l´aide des intervalles. En particulier, nous décrivons la géométrie de ce dernier problème, nous généralisons quelques résultats en théorie de localisation et nous donnons des conditions sous lesquelles certaines variables peuvet être éliminées du problème. Finalement, nous testons ces conditions dans un nombre d´instances générées aléatoirement et nous donnons les conclusions. / Doctorat en sciences, Orientation recherche opérationnelle / info:eu-repo/semantics/nonPublished

Le secteur des semi-conducteurs a connu un développement considérable ces dernières décennies, du fait des nouvelles applications de la microélectronique dans l'industrie. Le processus de fabrication est réputé pour sa complexité. L'un des ateliers les plus critiques de la production, l'atelier de photolithographie, est régi par un ensemble conséquent de contraintes de production. La multiplicité des ressources utilisées, le nombre important de produits traités, en font une zone importante à optimiser. Les objectifs de la thèse ont été de modéliser cet atelier sous la forme d'un problème d'ordonnancement sur machines parallèles et d'optimiser plusieurs critères jugés pertinents pour évaluer la qualité des solutions. Des résultats en termes de complexité, et d'algorithmes de résolution, ont permis une application industrielle, dans la mesure où un logiciel d'optimisation destiné à l'ordonnancement des lots en photolithographie a été développé. / Semiconductor manufacturing has grown considerably in recent decades, due to new industrial applications of microelectronic devices. The related manufacturing process is known to be complex. A bottleneck process step, the photolithography workshop, gathers various types of constraints, related to the number of auxiliary resources and the tools characteristics. The aims of the thesis were to model this workstation as a parallel machine scheduling problem and to optimize various criteria, determined by industrial needs. Some complexity results are provided and optimization algorithms led to an industrial application, i.e. a software providing optimized schedules in a specific fab.

No description available.

L’écologie industrielle a pour objectif de résoudre les questions liées à l'utilisation des ressources technologiques dans les sociétés, dans le but d'ajouter à la partie des connaissances nécessaires pour commencer à évaluer les problèmes de qualité liés à l'environnement et les questions de disponibilité des ressources. Le concept d’écologie industrielle peut être réalisé et pratiqué à travers d’établissement des parcs éco-industriels. Un parc éco-industriel est une communauté de fabrication et de service des entreprises situées ensemble sur une propriété commune. Les membres cherchent la performance environnementale, économique et sociale accrue grâce à la collaboration dans la gestion des questions environnementales et de ressource. L’objectif principal de la thèse est de créer des modèles mathématiques d’optimisation pour maximiser des flux des échanges dans un parc éco-industriel et pour réduire les impacts négatifs des industries sur l’environnement. Les sept parcs éco-industriels symboliques et emblématiques dans le monde ont été étudiés durant la thèse pour obtenir une vision pratique de la problématique et pour acquérir les informations du développement des éco-parcs de la réalité. Les dix outils informatiques et les modèles d’optimisation pour les parcs éco-industriels ont été étudiés. Trois modélisations d’optimisation sont proposées avec les simulations numériques effectuées. / Industrial ecology aims to resolve issues related to the use of technological resources in societies in order to add to the party the knowledge to begin to assess quality issues related to the environment and resource availability issues. The concept of industrial ecology can be realized and practiced through the establishment of eco-industrial parks. An eco-industrial park is a manufacturing community and service businesses located together on a common property. Members seek environmental performance, increased economic and social through collaboration in managing environmental and resource. The main aim of this thesis is to create mathematical optimization models to maximize trade flows in an eco-industrial park and to reduce the negative impacts of industry on the environment. The seven symbolic eco-industrial parks have been studied in this thesis in order to get a practical view of the issues and to acquire information from the development of eco-parks in reality. The numerical tools and optimization models for eco-industrial parks were studied. Three optimization models have been proposed with numerical simulations in this thesis.

La structure de projet se retrouve dans de nombreux contextes de l'industrie et des services. Il s'agit de réaliser un ensemble d'activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L'objectif est la minimisation d'un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d'ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d'exécution des activités et pour l'évaluation instantanée du respect des capacités des ressources qu'elles utilisent. Or, s'il est souvent nécessaire en pratique d'obtenir un calendrier détaillé des plages d'exécution des activités, l'utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d'ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d'ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l'intérêt de ces différentes méthodes et illustrent la difficulté du problème. / The project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem.

Dans cette thèse, nous étudions deux problèmes de planification de production motivés par des applications du monde réel. Tout d'abord, un problème de planification de production pour un projet de fabrication de vêtements est étudié et un outil d'optimisation est développé pour le résoudre. Deuxièmement, une version restreinte du problème de dimensionnement du lot de capacité avec des configurations dépendantes de la séquence est explorée. Diverses formulations mathématiques sont développées et une analyse de complexité est effectuée pour donner une première analyse du problème. / In this thesis, we study two production planning problems motivated by challenging real-world applications. First, a production planning problem for an apparel manufacturing project is studied and an optimization tool is developed to tackle it. Second, a restricted version of the capacitated lot sizing problem with sequence dependent setups is explored. Various mathematical formulations are developed and complexity analysis is performed to offer a first glance to the problem.