Nous analysons un type W de système de l’Assemble-à-commande avec des délais de livraison aléatoires, l'arrivée aléatoire de la demande et des ventes perdues, en temps continu. Nous formulons le problème en tant que processus de décision Markov à l'horizon infini. Nous nous éloignons de l'approche standard en caractérisant une région de l'espace d'état où toutes les propriétés de la fonction de coût tiennent. Nous caractérisons la politique optimale dans cette région. En particulier, nous montrons que, dans l'intérieur de la région récurrente, les composants sont toujours produits. Nous caractérisons également la politique d'allocation de composants optimale qui spécifie si une demande de produit arrivant devrait être remplie. Notre analyse révèle que la politique d'allocation optimale est contre-intuitive. Par exemple, même lorsqu'un produit domine l'autre, en termes de coût/taux de vente perdue, sa demande peut ne pas avoir une priorité absolue par rapport à la demande de l'autre produit. Une telle caractéristique n'a pas été observée dans de nombreux paramètres intégrés de production/inventaire où l'allocation d'inventaire suit une priorité fixe pour satisfaire les exigences. Nous montrons également que la structure de la politique optimale reste la même pour les systèmes à production par lots, les temps de production répartis par Erlang et la demande de produits non unitaire. Enfin, nous proposons des heuristiques efficaces qui peuvent être utilisées comme substitut à la politique optimale ou peuvent être utilisées comme une politique de départ pour les algorithmes communs utilisés pour obtenir une politique optimale dans le but de réduire leur temps de calcul. / We analyze a W-configuration assemble-to-order system with random lead times, random arrival of demand, and lost sales, in continuous time. We formulate the problem as an infinite-horizon Markov decision process. We deviate from the standard approach by first characterizing a region (the recurrent region) of the state space where all properties of the cost function hold. We then characterize the optimal policy within this region. In particular, we show that within the interior of the recurrent region components are always produced. We also characterize the optimal component allocation policy which specifies whether an arriving product demand should be fulfilled. Our analysis reveals that the optimal allocation policy is counter-intuitive. For instance, even when one product dominates the other, in terms of lost sale cost and lost sale cost rate (i.e., demand rate times the lost sale cost), its demand may not have absolute priority over the other product’s demand. Such a feature has not been observed in many integrated production/inventory settings where inventory allocation follows a fixed priority in satisfying demands. We also show that the structure of the optimal policy remains the same for systems with batch production, Erlang distributed production times, and non-unitary product demand. Finally, we propose efficient heuristics that can be either used as a substitute for the optimal policy or can be used as a starting policy for the common algorithms that are used to obtain the optimal policy in an effort to reduce their computational time

La présente thèse se déroule dans le cadre du projet ANR PRODIGE et est axée sur la recherche de stratégies permettant l’optimisation du transport en général et du transport routier de marchandises en particulier. Le problème de transport support de cette étude est le problème de collecte et livraison avec transbordement. Ce problème généralise plusieurs problèmes de transports classiques. Le transbordement y est utilisé comme levier de flexibilité et d’optimisation. Pour analyser et résoudre ce problème, les analyses sont effectuées suivant trois axes : le premier axe concerne l’élaboration d’un modèle analytique plus précisément d’un modèle mathématique en variables mixtes. Ce modèle permet de fournir dessolutions optimales au décisionnaire du transport mais présente l’inconvénient de nécessiter un temps de résolution qui croit exponentiellement avec la taille du problème. Cette limitation est levée par le deuxième axe d’étude qui permet de résoudre le problème de transport étudié par une méthode d’optimisation approchée tout en garantissant des solutions satisfaisantes.La méthode utilisée est une métaheuristique inspirée de la recherche à voisinages variables (VNS). Dans le troisième axe, l’ensemble des résultats obtenus dans la thèse sont testés en situation de transports réels via le projet PRODIGE. / The thesis is conducted under the ANR project PRODIGE and it is focused on seeking strategies allowing the optimization of transport in general and road freight transport in particular. The transportation problem support for this study is the pickup and delivery problem with transshipment.This problem generalizes several classical transportation problems.Transshipment is used as optimization and flexibility leverage. To study and solve this problem, analyzes are performed along three axes :the first objective concerns the development of an analytical model, more accurately a mathematical model with mixed variables. This model allows providing optimal solution to the decision maker, but has the disadvantage of requiring a time resolution that grows exponentially with the size of the problem. This limitation is overcome by the second line of the study that solves the transportation problem studied by an approximate optimization method while ensuring satisfactory solutions. The method used is a mataheuristic broadly followed the variables neighborhoods research principles. In the third objective, the overall results obtained in the thesis are tested in real transport situation via the PRODIGE project.

Cette thèse s’intéresse au fonctionnement cyclique multi-produits des ateliers de traitement de surface, et au problème d’ordonnancement associé (HSP), caractérisé par des contraintes fortes et atypiques, dont certaines sont liées aux ressources de transport. Dans le cas de productions en grandes séries, une commande cyclique de ces systèmes est particulièrement adaptée, permettant notamment de réduire la combinatoire de résolution, et sous réserve que les ratios de produits soient connus à l’avance. Notre objectif est de trouver le meilleur ordonnancement des tâches de traitement et de transport en un temps raisonnable. Pour cela, nous proposons une première approche, basée sur un modèle linéaire et une méthode de résolution arborescente de type séparation et évaluation. Nous présentons des modélisations pour différentes extensions du problème dit de base et nous fournissons des exemples illustratifs et des résultats sur des benchmarks. Par la suite et compte tenu de l’analyse de la littérature relative aux ordonnancements cycliques mono-produit et multi-produits, nous proposons tout d’abord une heuristique dédiée au cas multi-produits étudié, et basée sur un algorithme de liste. Avec ce dernier, nous obtenons un ordonnancement cyclique dont le degré du cycle n’est pas fixé au préalable. Enfin, nous présentons une deuxième modélisation approchée sous la forme d’un algorithme génétique pour résoudre un HSP 2-cyclique. Ces différents modèles sont validés par des tests sur des benchmarks de la littérature pour lesquels nous avons obtenus des résultats prometteurs. Nous terminons par une analyse critique des avantages et inconvénients des modèles élaborés et par quelques propositions de perspectives pour ce travail. / In this thesis, we study the Cyclic Hoist Scheduling Problem (CHSP) in automated electroplating lines, when a mass production must be achieved. The CHSP is characterized by specific constraints related to processing and transport resources. To solve it in a multi-parts context, we first elaborate a 2-degree cyclic model and an associated branch and bound algorithm. Then we extend it to more complex configurations. Then, we develop a dedicated heuristic to find a feasible repetitive sequence of hoist moves that minimizes the cycle time, without a priori fixing the cycle degree. Comparisons with existing algorithms are presented to show the efficiency of the proposed heuristic. To reduce the cycle time, we integrate in the general heuristic an algorithm with a set of Minimum Part Set (MPS) configurations’. This one allows us to find the best order in which jobs should be introduced into the line. Finally, we describe a genetic algorithm approach to find a schedule which can reach the optimal 2-cycle. We finally discuss the interest of those various models, based on the promising results obtained and we provide some perspectives which could be explored.

Dans cette thèse, nous nous intéressons principalement à l’étude du fonctionnement cyclique mono-produit des ateliers de traitement de surface. Notre contribution porte sur le problème d’ordonnancement associé connu dans la littérature sous le nom Cyclic Hoist Scheduling Problem (CHSP). L’objet de cette thèse est de proposer des méthodes efficaces pour la résolution des problèmes de traitement de surface dans le cas où les produits à traiter sont du même type. Nous traitons en particulier le cas où le nombre des robots présents sur la ligne est égal à deux, ce qui augmente le nombre des contraintes du problème, sachant que dans le cas mono robot, ce problème a été prouvé NP-Complet. Pour cela, nous proposons une méthode qui combine deux heuristiques et un programme linéaire mixte. Cette méthode permet notamment d’affecter les mouvements de transport à l’un des deux robots tout en gérant les risques de collision entre eux, lorsque la gamme opératoire des produits à traiter suit l’implantation des cuves.Par la suite, nous proposons une extension du modèle au cas de lignes complexes. Enfin, nous étudions le cas d’un fonctionnement mixte, pour lequel il est nécessaire de traiter dans une même installation des produits différents et des rafales de produits identiques. Dans ces conditions, la solution la plus intéressante pour les industriels est de pouvoir alterner des modes de production dynamiques et cycliques. Pour cela, nous proposons une méthode efficace permettant de résoudre le problème d’ordonnancement associé à la phase transitoire relative à ce type de fonctionnement. Elle consiste en particulier à chercher les dates d’entrée au plus tôt des produits. La principale difficulté identifiée consiste ici à passer du mode dynamique au mode cyclique, c’est-à-dire à rejoindre un cycle à partir d’une solution courante donnée, en supposant que ce cycle est connu à priori. Les méthodes élaborées dans les divers cas traités sont validées par des tests sur des benchmarks de la littérature. / In this thesis, our interest is focused on the Cyclic Hoist Scheduling Problem (CHSP) in automated electroplating lines. The aim of this study is to propose an algorithm to solve the two-hoists cyclic scheduling problem. This one consists in finding a repetitive sequence of hoists’ moves, while avoiding collision between the hoists which share a common track. The objective is to minimize the period of this repetitive cycle for single part-type production. This problem was proved to be NP-complete for lines with a single hoist. The fact that two hoists are available on the line increases the number of constraints of the problem. Then we propose a solving method combining two heuristics and a Mixed Integer Linear Program. It enables us to solve both assignment and sequencing problems, while considering spatial constraints related to hoist’moves.Subsequently, we propose an extension of the model which is adapted to complex lines. Finally, our interest is focused on solving a HSP for which it is necessary to treat in the same facility a batch of various products and a batch of identical products. Under these conditions, the most interesting solution for manufacturers is to be able to alternate the production of two batches. For this goal, we propose an efficient method to solve the scheduling problem associated. Finally, our proposed methods are validated by experimentations based on benchmarks from the literature.

Les réseaux électriques actuels connaîtront un profond changement dans les années à venir. La nouvelle génération est le Smart Grid (SG) ou le réseau électrique intelligent qui se caractérise par une couche d'information et de communication qui permet aux différents composants du réseau de communiquer. Il doit considérer tous les aspects du réseau électrique, le rendant plus intelligent et flexible. Cette notion est présentée comme une réponse à l'évolution du marché de l'électricité, visant à gérer l’augmentation de la demande tout en assurant une meilleure qualité de service et plus de sécurité.Premièrement, nous présentons une formulation de programmation linéaire mixte en entier pour optimiser les systèmes de production et de consommation d'énergie dans une maison intelligente avec un déploiement efficace de plusieurs ressources énergétiques distribuées. Ensuite, à travers la conception d'expériences avec la méthode de Taguchi, divers scénarios sont introduits en faisant varier des facteurs significatifs. Par la suite, une technique heuristique est proposée pour résoudre le problème de la gestion de l'énergie résidentielle en trouvant la solution optimale globale pendant plusieurs jours consécutifs avec une réduction significative du temps d'exécution.Deuxièmement, un modèle de gestion de l'énergie est assuré grâce à des modèles mathématiques pour optimiser l’utilisation du réseau, des ressources énergétiques renouvelables, des véhicules électriques et de la batterie, ainsi que pour différents types d'appareils thermiques et électriques. Une méthode de solution exacte est mise en œuvre pour réduire le coût de l'électricité dans une maison intelligente et pour trouver des modes de fonctionnement de différentes charges. Ensuite, un algorithme d'optimisation math-heuristique est proposé pour résoudre le problème avec un temps de simulation étendu.Enfin, nous étudions le problème de gestion de l'énergie dans un microréseau constitué de plusieurs maisons intelligentes. Chacune d'elles dépose de ressources énergétiques renouvelables, d’un véhicule électrique et d’appareils intelligents. Les ressources d'énergie renouvelable injectent l’excès de l'énergie dans un système de stockage d'énergie partagé. Un modèle mathématique linéaire mixte en entier pour la gestion d'énergie est proposé pour réduire le coût total de fonctionnement du microréseau. Des comparaisons avec des scénarios conventionnels où chaque maison intelligente possède son propre système de stockage d'énergie sont effectuées pour démontrer l’efficacité de la démarche proposée. / The current electricity grids will experience a profound change in the coming years. The new generation is the Smart Grid (SG) which is characterized by information and communication layer enabling the communication between the different components of the grid. It needs to consider all sides of power grid, making it more intelligent and flexible. This notion is presented as an answer to changes in the electricity market, aiming to manage the increased demand while ensuring a better quality of service and more safety.First, we present a mixed integer linear programming formulation to optimize the energy production and consumption systems in a smart home with an effective deployment of several distributed energy resources. Then through the design of experiments with the Taguchi method, diverse scenarios are introduced by varying significant factors. Afterward, a heuristic technique is proposed to solve the problem of residential energy management by finding the global optimum solution for many consecutive days with significant reduction of execution time.Second, an energy management model is proposed thanks to mathematical models to optimize the grid, renewable energy resources, battery and electric vehicles are presented as well as for different type of thermal and electrical appliances. An exact solution method is implemented to reduce the electricity cost in a smart home and find out operation modes of different loads. Then a math-heuristic optimization algorithm is proposed to solve the problem with extended simulation time horizon.Finally, we study a microgrid energy management problem which comprises multiple smart homes. Each of them owns renewable energy resources, one electric vehicle and smart appliances. The renewable energy resources inject the excess energy in the shared energy storage system. An optimized energy management model using mixed integer linear programming is proposed to reduce the total electricity cost in the microgrid. Comparisons with conventional scenarios where each smart home has its individual small energy storage system without sharing energy with their neighbors are done to ensure that the proposed formulation is well efficient.

En biologie structurale, il est couramment admit que la structure tridimensionnelle d'une protéine détermine sa fonction. Ce paradigme permet de supposer que deux protéines possédant des structures tridimensionnelles similaires peuvent partager un ancêtre commun et donc posséder des fonctions similaires. Déterminer la similarité entre deux structures de protéines est une tâche importante qui a été largement étudiée. Parmi toutes les méthodes proposées, nous nous intéressons à la mesure de similarité appelée “maximisation du recouvrement de cartes de contacts” (ou CMO), principalement parce qu'elle fournit des scores de similarité pouvant être utilisés pour obtenir de bonnes classifications automatiques des structures de protéines. Dans cette thèse, la comparaison de deux structures de protéines est modélisée comme une recherche de sous-graphe dans des graphes k-partis spécifiques appelés graphes d'alignements, et nous montrons que cette tâche peut être efficacement réalisée en utilisant des techniques avancées issues de l'optimisation combinatoire. Dans la seconde partie de cette thèse, nous modélisons CMO comme une recherche de sousgraphe maximum induit par les arêtes dans des graphes d'alignements, problème pour lequel nous proposons un solveur exact qui surpasse les autres algorithmes de la littérature. Même si nous avons réussi à accélérer CMO, la procédure d'alignement requière encore trop de temps de calculs pour envisager des comparaisons à grande échelle. La troisième partie de cette thèse est consacrée à l'accélération de CMO en utilisant des connaissances issues de la biologie structurale. Nous proposons une approche hiérarchique pour résoudre CMO qui est basée sur les structures secondaires des protéines. Enfin, bien que CMO soit une très bonne mesure de similarité, les alignements qu'elle fournit possèdent souvent de fortes valeurs de déviation (root mean squared deviation, ou RMSD). Pour palier à cette faiblesse, dans la dernière partie de cette thèse, nous proposons une nouvelle méthode de comparaison de structures de protéines basée sur les distances internes que nous appelons DAST (pour Distance-based Alignment Search Tool). Elle est modélisée comme une recherche de clique maximum dans des graphes d'alignements, pour laquelle nous présentons un solveur dédié montrant de très bonnes performances.

Cette étude est consacrée à l'optimisation géométrique du contrôle actif dans les gaines de ventilation. La première partie de ce travail concerne l'étude du contrôle hybride (actif+passif) dans les gaines de ventilation et de ses avantages suivant la géométrie de la gaine et la présence ou non de revêtements absorbants. Les effets du contrôle passif du bruit (dissipatif, réflexif et diffusif) dans une gaine de ventilation améliorent l'efficacité du contrôle actif. Un contrôle hybride (actif + passif) présente donc des avantages, même aux basses fréquences. La seconde partie de ce mémoire s'intéresse au placement des microphones d'erreur et des sources secondaires. Pour une excitation harmonique, une méthode de calcul par programmation linéaire et entière détermine un nombre suffisant de microphones d'erreur ainsi qu'une position optimale des microphones d'erreur et des sources secondaires. Cette méthode de placement est appliquée pour la réduction du bruit dans les gaines de ventilation.

Ce travail est destiné à mettre au point une méthode de dimensionnement à l'état limite ultime des structures en béton armé fondée sur le calcul à la rupture. La méthode propose une analyse bidimensionnelle, en contrainte plane, dans laquelle les armatures sont représentées comme des milieux continus unidimensionnels plongés dans le béton considéré comme un milieu continu bidimensionnel (modélisation mixte). Appliquant la méthode à la prise en compte de l'effort tranchant dans le dimensionnement des poutres en flexion, on propose de modéliser le renforcement transversal des poutres par la procédure d'homogénéisation en calcul à la rupture, tout en conservant une modélisation discrète des armatures longitudinales. Ayant choisi des critères de résistance simplifiés pour le béton et les armatures, on montre ensuite les limites d'une approche unidimensionnelle du dimensionnement des poutres par le calcul à la rupture. On développe donc une approche numérique fondée sur la programmation linéaire dans le cadre de la méthode des éléments finis. Cette dernière approche permet ainsi d'évaluer l'influence de l'effort tranchant sur la résistance des poutres et de déterminer le domaine de validité de l'approche unidimensionnelle proposée précédemment. La modélisation et l'approche numérique sont finalement validées par comparaison avec des résultats expérimentaux.

Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres optiques ou bien encore réseaux embarqués dans un satellite. Les problématiques varient en fonction de la partie du réseau considérée, du type de requêtes et de l'objectif. Le cas des requêtes de type paquets est abordé dans le cadre des réseaux en forme de grille, mais le thème principal est le routage de requêtes de type connections (unicast et multicast). Les objectifs considérés sont : la conception d'un réseau embarqué dans un satellite de télécommunication, de taille minimum et tolérant des pannes de composants; le dimensionnement des liens d'un réseau afin qu'il supporte des pannes corrélées ou qu'il offre une bonne qualité de service, ou s'il autorise des connections {\em multicast}; le dimensionnement de la taille des buffers d'un réseau d'accés radio; et l'optimisation de l'utilisation des ressources d'un réseau dynamique orienté connections. Dans tous ces cas la problématique du routage de connections est centrale. Mon approche consiste à utiliser la complémentarité de techniques algorithmique et d'optimisation combinatoire ainsi que d'outils issus de la théorie des graphes tels la pathwidth et des notions reliées -process number, jeux de captures et treewidth-, différents types de coloration -impropre et pondérée, proportionnelle, directed star colouring-, les graphes d'expansion et des techniques de partitions telle la quasi partition.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal