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

Dans cette thèse, nous nous intéressons à deux composantes fondamentales de l'opération du rendez-vous orbital : la navigation relative et le guidage à consommation minimale de carburant. La première partie est consacrée à la modélisation du mouvement relatif de satellites dans un cadre linéaire. Une analyse bibliographique approfondie ainsi que les développements d'une méthode de modélisation et d'une transformation de variables d'état du mouvement relatif sont proposées dans cette partie. Ces développements sont entrepris dans le but de fournir des outils de navigation relative fiables et précis même en présence de perturbations orbitales. Le guidage est abordé dans la seconde partie de la thèse à travers l'élaboration de plusieurs algorithmes de génération de plans de manSuvres pour la mise en Suvre du rendez-vous en temps fixé. Chacun des algorithmes développés est fondé sur des outils théoriques différents tels que les méthodes indirectes de résolution de problèmes de commande optimale basées sur le principe du maximum ou les techniques directes exploitant la discrétisation des problèmes de commande optimale et la programmation linéaire. L'utilisation de ces outils permet de couvrir des objectifs divers, notamment la minimisation de la consommation de carburant et la robustesse vis-à-vis des erreurs de navigation. D'autres algorithmes sont conçus dans le but d'améliorer leur embarcabilité à travers l'utilisation des bases de la mécanique spatiale. Un ensemble de tests de validation et comparaison est réalisé, portant sur des missions réelles ou des exemples académiques issus de la littérature et permettant de mettre en valeur les avantages pratiques les plus pertinents des algorithmes développés.

Le but de cette synthèse est de présenter mon activité de recherche couvrant la période de temps écoulée à partir de l'année terminale de ma thèse (c'est à dire, la période octobre 2008 - février 2013). Mes thèmes de recherche correspondent, en majeure partie, à trois directions principales, chacune présentée dans une section dédiée : - méthodes de programmation linéaire dans l'étude des problèmes de contrôle déterministe ou stochastique ; - méthodes de contrôle des processus Markoviens déterministes par morceaux et leurs applications dans la théorie des réseaux stochastiques de gènes. - propriétés de contrôlabilité des systèmes linéaires stochastiques et sujets connexes. Dans le premier chapitre, nous étudions plusieurs classes de problèmes de contrôle déterministe ou stochastique à coût discontinu. Dans le contexte stochastique, nous considérons le problème de type Mayer et l'arrêt optimal des diffusions contrôlées (correspondant à l'article [G10]), les principes de la programmation dynamique (correspondant à l'article [G6]), ainsi qu'une classe de problèmes de contrôle impliquant des contraintes d'état (correspondant à l'article [G2]). Nous étudions également : des problèmes de contrôle à coût escompté et en horizon infini, ainsi que la moyennisation en temps long (correspondant à [G12]), des systèmes régis par des inégalités variationnelles stochastiques (dans [G3]) et une caractérisation de type Zubov pour les domaines de stabilité asymptotique (toujours dans [G3]). Nous investiguons l'existence d'une fonction valeur limite pour une classe de problèmes de contrôle stochastique sous des hypothèses de non-expansivité, ainsi que des théorèmes Tauberiennes uniformes (correspondant à [G19]). Dans le cadre déterministe, nous considérons la linéarisation et les principes de la programmation dynamique pour des problèmes de type coût supremum (ce qui correspond à [G9]) et pour des systèmes à contraintes d'état (dans [G1]). Nous proposons une méthode de linéarisation pour des problèmes de type min-max (correspondant à [G18]). Le point commun entre ces articles réside dans la méthode employée basée sur des formulation linéaires et des techniques de viscosité. Nous présentons également des résultats de viabilité pour les perturbations singulières des systèmes contrôlés (correspondant à [G13]). Le deuxième chapitre est axé sur quelques contributions à la théorie des processus de Markov déterministes par morceaux (PDMP, acronyme anglais de "piecewise deterministic Markov process"). Nous investiguons des conditions géométriques pour la viabilité et l'invariance des ensembles fermés par rapport aux dynamiques PDMP contrôlées (correspondant à l'article [G5]). Nous proposons également des formulations linéaires pour certains problèmes de contrôle dans ce contexte (correspondant aux articles [G8] et [G4]). Ces résultats permettent d'en inférer certaines conditions d'atteignabilité (dans l'article [G5]) ainsi que de caractériser les domaines de stabilité asymptotique en généralisant la méthode de Zubov (dans l'article [G4]). Les résultats théoriques sont appliqués à une classe de systèmes associés à des réseaux stochastiques de gènes (des modèles On/Off, le modèle proposé par Cook pour l'haploinsuffisance, ainsi que le modèle de Hasty pour la bistabilité du phage lambda). Le dernier chapitre présente l'étude de différentes classes de contrôlabilité pour des systèmes linéaires de type diffusion à sauts (correspondant à l'article [G7]) ou des systèmes linéaires de contrôle à dynamique champs-moyen (correspondant à l'article [G20]). Les arguments font intervenir des techniques de viabilité ainsi que des équations différentielles de type Riccati. Une première étape dans l'étude des propriétés de contrôlabilité des systèmes ayant comme espace d'état un espace d'Hilbert est franchie dans l'article [G11]. Nous y proposons une approche de type quasi-tangence dans l'étude de la propriété de (presque)viabilité des systèmes semi-linéaires dans un cadre infini-dimensionnel. Nous avons essayé de rendre le manuscrit aussi autonome que possible. Pour en assurer la lisibilité, nous avons également essayé de garder l'indépendance des chapitres. Afin de garder une dimension raisonnable du manuscrit, nous avons fait le choix de limitation de la redondance. Pour cette raison, les problèmes de contrôle sous contraintes d'état ont été présentés uniquement dans le contexte stochastique. Aussi, les détails précis de la méthode de Zubov ont été spécifiés uniquement dans le cas des processus Markoviens déterministes par morceaux et les contributions aux diffusions Browniennes ont été seulement mentionnées.