identifier: Lemesre, C. (2013). Gestion des interdépendances reliées à l'utilisation des produits pétroliers  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les travaux de recherche menés par le Centre risque & performance (CRP) de l'École Polytechnique de Montréal dans le domaine des interdépendances entre les infrastructures essentielles ont abouti au développement de DOMINO, un outil permettant d'anticiper la propagation spatio-temporelle des effets domino. Ce mémoire est issu de la volonté du CRP d'intégrer la gestion des interdépendances reliées à l'utilisation des produits pétroliers à ses travaux. Ainsi, il est nécessaire d'adapter la méthodologie du CRP afin de permettre la prise en compte de cette ressource dans le traitement des interdépendances. Développée en contact direct avec les gestionnaires d'une infrastructure essentielle, l'approche proposée dans ce mémoire intègre des paramètres de caractérisation des produits pétroliers afin de proposer des outils d'aide à la décision. L'approche par conséquence du CRP a permis de développer cette approche dans le cas général d'une pénurie de produits pétroliers, puis dans le cas particulier d'une panne électrique majeure.  Ce travail de recherche a permis de développer des outils adaptés aux besoins des gestionnaires d'infrastructures. Ces outils permettent aux gestionnaires d'augmenter leur niveau de connaissance de la zone à l'étude, d'initialiser des simulations et de prioriser les approvisionnements en produits pétroliers à partir de deux critères, soit la gravité des conséquences du manque de produits pétroliers et l'autonomie des équipements. L'application de l'approche dans le cadre d'une étude de cas réalisée sur une infrastructure a permis d'obtenir des résultats intéressants. Ainsi il apparait qu'en cas de perturbation les outils proposés permettent aux gestionnaires d'accéder rapidement à des informations pertinentes telles que l'évaluation des besoins en produits pétroliers, les requis pour fonctionner, le stock disponible et les ressources alternatives existantes. Les résultats obtenus constituent une aide à la décision  pour les gestionnaires qui ont pour missions de prioriser les équipements, d'assurer un approvisionnement supplémentaire adapté, de répartir la ressource entre les équipements ou encore d'adapter la consommation de produits pétroliers. Ce mémoire ouvre la voie à d'autres travaux de recherche tels que l'implémentation des outils dans DOMINO, l'implantation de l'approche à l'échelle municipale et le développement de nouveaux des critères d'analyse de cohérence.  ABSTRACT: The research conducted by the Centre risque & performance (CRP) of the Ecole Polytechnique of Montreal in the field of interdependencies among critical infrastructures have led to the development of DOMINO, a tool that anticipate the spatio-temporal propagation of domino effects. This dissertation comes from the will of CRP to integrate the management of interdependencies related to the use of petroleum products in its work. Thus, it is necessary to adapt the methodology of CRP to allow the integration of this resource in the treatment of interdependencies. Developed in contact with critical infrastructures managers, the approach integrates parameters characterizing petroleum products to provide decision support tools. The CRP consequences-based approach's has enabled the development of this approach in the general case of a shortage of petroleum products and in the event a major power outage. This research led to the development of tools adapted to the needs of the infrastructure managers. These tools allow managers to increase their knowledge of the study area, initialize simulations and prioritize petroleum product supplies from two criteria, the severity of the consequences of lack of petroleum products and the autonomy of equipment. The application of the approach in a case study on infrastructure has yielded interesting results. Thus, it appears that in case of disturbance the proposed tools allow manager to quickly access information such as needs assessment in petroleum products, required to operate, stock available and existing alternative resources. The results obtained are a decision support for managers who have to prioritize equipment, to provide adapted additional supply, allocate resources between equipment, or even adapt the consumption of petroleum products. This dissertation opens the way for further research, such as the implementation of the tools in DOMINO, the implementation of the approach at the municipal level and the development of new coherence analysis criteria.


identifier: Pahlavan Pour, M. (2013). Multi Scale Modeling of The Elastic Properties of Polymer-Clay Nanocomposites  [Thèse de doctorat, École Polytechnique de Montréal].

type:
Mémoire ou thèse
NonPeerReviewed

abstract: RÉSUMÉ: Les Nanocomposites Polymères-Argiles (NPA) sont reconnus pour leur capacité à améliorer les propriétés mécaniques de polymères bruts, et ce, même dans le cas de faibles fractions volumiques de nano-argiles. Cette amélioration est attribuable aux rapports de forme élevés ainsi qu'aux propriétés mécaniques des nano-argiles. En outre, la zone d'interphase résultant d'une modification des chaînes de polymère à proximité des nano-argiles joue un rôle important dans la rigidité de NPA. Plusieurs approches analytiques existent pour la prédiction des propriétés élastiques de NPA, allant des modèles simplifiés en deux étapes aux modèles plus sophistiqués. Il n'existe toutefois aucune étude ayant déjà vérifié l'exactitude de ces modèles. Par ailleurs, les modèles numériques servant à évaluer leurs homologues analytiques sont encore loin de pouvoir modéliser la microstructure réelle de NPA. Par exemple, la majorité des modèles n'ont pas tenu compte de la microstructure tridimensionnelle de particules aléatoirement réparties, du rapport de forme élevé des nano-argiles, ou de l'intégration explicite de phases constitutives. Plus important encore, la plupart des études numériques ont été développées sans tenir compte du Volume Élémentaire Représentatif (VER) en raison du coût énorme de calculs imposé par ce dernier. Par conséquent, l'exactitude des résultats de référence ainsi obtenus est contestable. Le but principal de cette thèse était d'évaluer l'exactitude des modèles d'homogénéisation pour la prédiction de comportement mécanique de NPA. Dans un premier temps, la validité des modèles micromécaniques analytiques couramment utilisés pour la prédiction de propriétés élastiqués de NPA exfoliés a été évaluée à l'aide de simulations Éléments Finis (EF) tridimensionnelles. Une attention particulière a été accordée à l'interphase autour des nano-argiles. La stratégie de modélisation était une procédure en deux étapes se basant sur la notion de Particule Effective (PE). Dans cette approche de modélisation, les renforts multicouches ont été remplacés par des particules homogènes à effets équivalents. L'exactitude des modèles numériques dans des limites de tolérances prédéfinies était garantie grâce à la détermination du VER. Cette étude a révélé que la méthode de Mori-Tanaka est la plus fiable à utiliser parmi les modèles en deux étapes pour les valeurs typiques de paramètres de NPA exfoliés (contraste de module, rapport de forme et la fraction volumique). Les propriétés mécaniques de l'interphase ainsi que son épaisseur ont été estimées à partir d'une comparaison entre une étude paramétrique numérique et des résultats expérimentaux.  ABSTRACT: Polymer-Clay Nanocomposites (PCN) are known to improve the mechanical properties of bulk polymers, even for modest clay loadings. This enhancement is due to the High aspect ratio and mechanical properties of the nanoclay platelets. Additionally, the interphase zone created by altered polymer chains in the vicinity of the nanoclays plays an important reinforcing role. Several analytical approaches exist for predicting the elastic properties of PCN, ranging from simplified two-step models to more complex one-step methods. However, no thorough study has yet rigorously verified the accuracy of these models. On the other hand, the numerical models that are commonly used to evaluate the analytical models are still far from modeling the real PCN microstructure reported in the literature. For example, most of the models have failed to model the detailed 3D microstructure considering randomly positioned reinforcing particles, the large nanoclay aspect ratio and the explicit incorporation of the constituent phases. More significantly, most of numerical studies have been reported without a thorough determination of the appropriate Representative Volume Element (RVE) due its computational burden, resulting in benchmark results of questionable accuracy. The main purpose of this thesis was to evaluate the accuracy of homogenization models for predicting the mechanical behavior of nanoclay nanocomposites. First, the validity of commonly used analytical micromechanical models for the prediction of exfoliated PCN elastic properties was evaluated with the help of 3D Finite Element (FE) simulations. In particular, special attention was devoted to the interphase around the nanoclays. The modeling strategy was a two-step procedure relying on the Effective Particle (EP) concept, in which the multi-layer reinforcing stacks were replaced by homogenized particles. The accuracy of the numerical models was guaranteed, within a given tolerance, by rigorous determination of the RVE. It was found that the Mori-Tanaka model was the most reliable method to be used in two-step models for the possible ranges of modulus contrasts, aspect ratios and volume fractions typical of exfoliated PCN. The properties and the thickness of the interphase were estimated from comparison between a numerical parametric study and experimental results. The importance of incorporating the interphase for predicting the axial Young's modulus was highlighted. Second, the evaluation was extended to a wider class of models applicable to both intercalated and exfoliated morphologies.


identifier: Olmiccia, J. (2013). Développement d'outils d'évaluation de la distribution des temps de séjour et de génération de maillages pour la modélisation de l'écoulement de fluides dans des mélangeurs continus  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Pour optimiser les procédés de mélange, la compréhension de la mécanique des fluides est indispensable. Des outils numériques permettant de caractériser le mélange dans les procédés opérant en continu ont été développés. Une des méthodes les plus fréquemment rencontrées en simulation numérique pour quantifier le mélange dans ce type de système, est la distribution des temps de séjour (DTS). Elle permet, entre autres, d'analyser l'homogénéité de l'âge du fluide sur une section de contrôle. Elle s'obtient en combinant une technique de résolution des équations de conservation de la masse et de la quantité de mouvement par éléments finis, servant à établir le champ de vitesse, avec une méthode de lâcher de particules sans masse. Ces dernières sont uniformément réparties sur la surface d'entrée et récupérées à la sortie, permettant ainsi de déterminer l'âge du fluide. Un des problèmes fréquemment rencontrés avec ces techniques est le phénomène de perte de particules. Pour atténuer ce phénomène, une technique consistant à évaluer une région proche de la paroi dans laquelle aucune particule n'est injectée est présentée. De même, une méthodologie qui permet de mieux approximer le temps de séjour moyen et d'améliorer l'allure des courbes de DTS est également développée. Les premiers tests ont été faits en considérant le cas d'un écoulement entre deux plaques puis le cas d'une conduite circulaire. Les résultats ont montré une concordance avec la théorie permettant d'étendre la méthodologie au cas d'un mélangeur statique. Par contre, la précision de ce type de résultats est grandement dépendante du maillage du domaine d'écoulement. Cela est particulièrement vrai pour des géométries complexes, comme c'est le cas pour une extrudeuse bi-vis. Or, l'étape de maillage est délicate à cause de la présence de parties mobiles et de petits entrefers dont la position varie dans le temps. Il est alors essentiel de trouver une stratégie de maillage flexible. Dans ce contexte, une technique pour mailler le fourreau d'une bi-vis à l'aide de tétraèdres a été développée. Elle consiste à créer un maillage de la surface transversale du fourreau à partir d'un nuage de points connectés pour former des éléments triangulaires. Ce maillage est ensuite extrudé pour former le volume du domaine d'écoulement avec des éléments prismes, à 6 noeuds, qui sont à leur tour divisés en tétraèdres. L'avantage de cette technique est qu'elle permet le raffinement local du maillage, ce qui est souvent très difficile à réaliser avec des logiciels commerciaux. Le volume du maillage a été évalué et comparé au volume théorique de la géométrie du fourreau pour valider le maillage obtenu. Par la suite, la modélisation de l'écoulement dans un fourreau vide a été faite avec des maillages issus de notre mailleur et du logiciel commercial Gambit (Ansys) pour comparer les résultats et vérifier ainsi la fonctionnalité du mailleur. Finalement, une étude de l'écoulement d'un fluide visqueux dans le fourreau avec les vis en rotation a été réalisée. Pour ce faire, la méthode des éléments finis virtuels (VFEM) a été utilisée pour modéliser les parties mobiles par des points de contrôle. La méthodologie développée pour mailler le fourreau de l'extrudeuse bi-vis s'est avérée utile pour simuler l'écoulement en régime transitoire avec des vis en mouvement. En effet, elle a conduit à des maillages fonctionnels, générés de façon systématique et quasi-instantanée. De plus, il est maintenant possible de pouvoir raffiner localement le maillage pour mettre plus d'éléments dans les entrefers, ce que nous n'avions pu faire avec les logiciels commerciaux.  ABSTRACT: A detailed understanding of fluid mechanics is required in order to optimize mixing processes. In this thesis numerical tools that allow the characterization of mixing in different continuous processes were developed. One of the methods often used in numerical simulations to quantify the level of mixing in these types of systems is Residence Time Distribution (RTD). One capability of this method is that it can analyze the uniformity of the time that elements of the fluid have spent in a control volume. RTD is obtained by combining the calculation of the velocity field through solving the equations of mass and momentum balance via the finite element method and the injection of massless particles. These particles are injected uniformly on the entry surface and are gathered at the exit, allowing the determination of their residence time. One of the problems encountered, when using this technique, is the loss of particles. To overcome the problem, a solution was presented that estimates the thickness of the near wall region, where no particles are injected. Also, a methodology was developed that allows a better approximation of the average residence time and improves the shape of RTD curves. The primary tests were carried out on the case of flow between two plates and in a circular conduit. The results showed good agreement with theory and permitted the application to a static mixer. It is worth noting that the precision of the generated results greatly depends on the mesh generation for the flow domain. This is particularly significant in the case of complex geometries such as flow in a twin-screw extruder, where the mesh generation step is a very delicate matter due to the presence of moving parts and small gaps with changing position in time. Thus, finding a flexible mesh generation strategy is essential. In this context, a technique to generate a mesh for the barrel utilizing tetrahedrons was developed. It consists of creating a mesh over the transversal surface of the barrel from a network of points interconnected to form triangular elements. This surface mesh is extruded to form the volume of the flow domain with prism elements holding six nodes, which are later on divided into tetrahedrons. The advantage of this technique is that it allows local refinement the mesh, something that cannot always be achieved easily using commercial software. The obtained mesh is validated by evaluation of its volume and comparison to the theoretical volume. Afterwards, flow inside an empty barrel is modeled using our mesh generation technique, and the commercial software Gambit to compare the results from the two and verify the functionality of our mesh generator. Finally, a study was carried out on the flow of a viscous fluid inside the barrel while the screws were rotating.  In order to carry out this study, the Virtual Finite Elements Method (VFEM) was applied to model the moving parts using control points. The methodology developed to mesh the barrel of a twin-screw extruder was found useful to simulate the flow with moving screws in transitory state. In fact, it generates functional meshes in a systematic and quasi-instantaneous manner. In addition, it is now possible to refine locally a mesh in order to place more elements in gaps, which was something we were not able to do with commercial software.


identifier: Al Attari, J. A. (2013). Innovative Millimeter-Wave Components Based on Mixed Substrate Integrated Dielectric-Metallic Waveguides  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: En recherche, un défi majeur pour l'onde millimétrique et les bandes Terahertz (THz) sont l'intégration des différents composants d'une manière compacte, efficace et à faible coût. La notion de circuits intégrés aux substrats (CIS) muni d'une variante de tradition pour une essentiel conception en simplifiant l'intégration du guide d'ondes rectangulaire (donc le GIS) avec d'autres lignes de transmission planaires telles que les lignes microbande et CPW. Bien que cette amélioré considérable conçue aux bandes de fréquences K et X, des limitations persistent dans des bandes plus élevées, en particulier la bande W. Nouvelles implémentations du concept de CIS en utilisant des guides d'ondes diélectriques, tels que le guide d'onde diélectrique non rayonnant (guide NRD), ont ainsi été proposées et avec un certain nombre de circuits à base de guide d'onde diélectrique non rayonnant intégrés aux substrats (SINRD) ont été conçus à des fréquences W-bande. Néanmoins, les critères de conception des guides rigides SINRD sont limités par leurs utilisations pratiques. Dans cette thèse, une version modifiée du guide SINRD, basée sur le guide image NRD (iNRD), est proposé. Ce travail sera le premier à étudier la faisabilité de la conception du guide iNRD avec le concept du CIS. La polyvalence du guide image SINRD résultant (iSINRD) sera démontrée par la conception d'un certain nombre de composants passifs qui fonctionnent à la fréquence centrale 94 GHz à la  bande W. Plus précisément, les contributions suivantes ont été étudiées aux deux fréquences 88 GHz et 94 GHz:1.Une méthodologie de conception pour l'optimisation des circuits du classe NRD. À date, Cette méthode est l'alternative le plus simple et la méthode la plus informative.2.Un certain nombre de lignes de transmission pour guidage iSINRD qui sont conçus avec des différents profils de perforation et avec un nombre différent de lacunes sur la paroi métallique de l'image vertical.3.Des Guides iSINRD  à angles aigus à large bande et à bande étroite.  ABSTRACT: A major challenge facing the millimetre-wave and terahertz (THz) research fields, is the integration of different components in a compact, efficient and low-cost fashion. The concept of substrate integrated circuits (SICs) provides a vital alternative to traditional design by simplifying the integration of the rectangular waveguide (thus the SIW) with other planar transmission lines such as microstrip and CPW lines. While this has substantially enhanced the design techniques at the X- and K-band frequencies, limitations still persist at higher bands, especially the W-band and beyond. New implementations of the SICs concept using dielectric waveguides such as the substrate integrated non-radiative dielectric (SINRD) guide, were thus proposed and a number of SINRD-based circuits were designed at the W-band frequencies. Nonetheless, the SINRD guide has rigid design criteria that limit its practical use.   In this thesis, a modified version of the SINRD guide, based on the image NRD (iNRD) guide, is investigated. This work will be the first to investigate the feasibility of designing the iNRD guide with the SICs concept. The versatility of the resulting image SINRD (iSINRD) guide will be demonstrated by designing a number of passive components that operate at the W-band centre frequency of 94 GHz.Specifically, the following contributions have been made at the W band frequencies of 88 GHz and 94 GHz: 1.An optimised design methodology of the NRD-class circuits. This method is a simpler alternative to earlier methods and is more informative.2.A number of iSINRD guide transmission lines that are designed with different perforation profiles and with a different number of gaps in the metal wall.3.Broadband and narrowband iSINRD guide sharp corners4. Two different configurations of iSINRD guide directional couplers that support dual mode (LSM10 and TE20 modes) and dual band operation (one band for 0-dB coupling while the other for 3-dB coupling). The band pertinent to the 0-dB coupling is exclusive for one of the configurations. Thus, a total of six directional couplers are presented.


identifier: El Ghazali, Y. (2013). Incidences de RFID dans une chaîne d'approvisionnement : processus, gestion des connaissances et performance  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Objectif principal et motivations L'objectif principal de la thèse par article vise à évaluer, dans un contexte de chaîne d'approvisionnement, les impacts de la technologie RFID (“Radio Frequency Identification”) sur les processus, la gestion des connaissances et la performance. Cette recherche se distingue des travaux antérieurs en mettant une emphase particulière sur les incidences de RFID sur l'acquisition, la gestion, le partage et le transfert des connaissances, et ce, autant à l'interne (dans chaque organisation) qu'à l'externe (dans la chaîne d'approvisionnement). Nous proposons également que la gestion des connaissances ainsi améliorée permet l'ajout d'intelligence. Cet objectif est poursuivi dans le contexte spécifique de la construction industrielle. Un tel contexte est intéressant puisque le poids économique de l'industrie de construction est élevé (au Québec, un emploi sur 20 en dépend) et que la construction industrielle connait des investissements substantiels, de l'ordre au Canada de 86,9 milliards de dollars pour 2012. De plus, c'est un secteur à forte intensité de connaissances dans lequel les firmes de génie-conseil jouent un rôle déterminant. Finalement, le fait de s'intéresser à une chaîne d'approvisionnement plutôt qu'à des entreprises individuelles correspond à une tendance lourde. Nous avançons donc que l'objectif général de recherche présente une certaine pertinence pratique. Sur le plan théorique, le projet doctoral est motivé par plusieurs facteurs. Premièrement, le nombre d'articles de recherche qui visent un objectif de recherche similaire est très restreint. Deuxièmement, la gestion des connaissances nous apparait primordiale dans une économie dite basée sur les connaissances, les connaissances étant un facteur de production relativement plus important que les coûts de la main d'œuvre. Troisièmement, les connaissances représentent un actif intangible qui est à base même des avantages concurrentiels durables. Quatrièmement, la technologie RFID soulève des enjeux technologiques et non-technologiques qui ne sont pas entièrement résolus. Stratégie méthodologique privilégiée  Cette recherche est exploratoire car elle sert à combler le ‘vide' théorique et empirique concernant notre problématique spécifique. Elle correspond donc au paradigme qualifié d'empirico-inductif et est fondée sur des propositions de recherche. Plus précisément, elle a été conduite dans cinq entreprises membres de cette chaîne pendant les étapes de la construction et post-construction au sein d'une raffinerie). Le client final est l'entreprise propriétaire de cette raffinerie, le maître d'œuvre est la firme de construction et les fournisseurs et sous-traitants sont respectivement le fournisseur de matières premières, l'entreprise de fabrication de systèmes de tuyauterie et l'entreprise responsable de la préparation de la surface et du revêtement anticorrosif des systèmes de tuyauterie. Ces cinq entreprises correspondent à cinq niveaux de la chaîne d'approvisionnement. Au total, 57 participants ont été impliqués. Observations, entrevues semi- structurées et analyse de documents internes et externes représentent pour l'étude de terrain les techniques de collecte de données privilégiées tandis que les groupes de discussion ont permis d'atteindre certains consensus et de valider les données empiriques et  résultats obtenus. Un consensus s'est formé pour explorer le potentiel de RFID au niveau de 1) l'approvisionnement des systèmes de tuyauterie, 2) de leur fabrication, peinture et installation sur le site de construction (soit la raffinerie) et, 3) leur inspection et maintenance après que les systèmes de tuyauterie soient installés. Ceci constitue trois applications distinctes de RFID, chacune ayant par exemple leurs propres exigences sur le plan technologique, leurs contraintes sur le plan organisationnel et inter-organisationnel, etc. Ces trois applications sont aussi les trois études de cas.  Principaux résultats Les données empiriques confirment que RFID a en effet une influence positive sur les modèles de gestion que ce soit au niveau de l'amélioration des modèles existants ou de l'adoption de nouveaux modèles selon les résultats des trois articles de thèse. Par contre, l'incidence de RFID sur les modèles collaboratifs reçoit un soutien plus faible et mitigé : en effet, nous n'avons obtenu aucune évidence empirique sur la confiance tandis que l'amélioration des relations inter-organisationnelles est surtout démontrée dans le premier article de thèse. L'adoption de la technologie RFID dans une industrie aussi complexe que celle de la construction industrielle est prometteuse. En effet, les résultats empiriques de notre recherche démontent que la technologie RFID a des incidences positives sur l'uniformisation, l'intégration, l'amélioration et l'automatisation des processus. Cette technologie améliore également l'acquisition, la gestion, le partage, le transfert des connaissances et  permet d'ajouter de l'intelligence au niveau intra- et inter- organisationnel. Elle réduit certaines inefficacités et plusieurs coûts opérationnels. L'analyse inter-cas a permis de dégager des facteurs déterminants additionnels. En particulier, nous avons pu établir que trois types de pressions isomorphiques, soit mimétiques, coercitives et normatives, s'exercent de façon différencié selon le type d'application RFID et selon la perspective de chacune des cinq entreprises. La compatibilité des scénarios RFID avec les compétences technologiques des entreprises impliquées se révèle un facteur important. Les limites et contraintes ainsi que les principales contributions sont examinées dans le septième chapitre et la thèse conclut avec des avenues de recherche.  ABSTRACT: Main objective and motivations The main objective of the thesis is to evaluate, in the context of supply chain, the impacts of RFID (Radio Frequency Identification) technology on processes, knowledge management and performance. This research differs from previous work by placing a strong emphasis on the impacts of RFID on the acquisition, management, sharing and transfer of knowledge, that are assessed internally (within the organization) and externally (across the supply chain). We also propose that improved knowledge management allows added-intelligence. The above objective is pursued within the specific context of the industrial construction sector. Such a context is interesting because the economic weight of the construction industry is high (in Quebec, one out of 20 jobs) and because the Canadian industrial construction benefited, in 2012, from substantial investments in the order of 86.9 billion dollars. Moreover, industrial construction represents a knowledge-intensive where engineering firms play a decisive role. Finally, the focus on a supply chain rather than on individual companies corresponds to a heavy trend. We argue that the overall objective of research has some practical relevance. From a theoretical perspective, the thesis is motivated by several factors. First, the number of research articles that target a similar research goal is very limited. Second, knowledge management appears to be critical in the so-called knowledge-based economy where knowledge can be considered as an important production factor. Third, knowledge is an intangible asset that brings sustainable competitive advantages. Fourth, RFID technology raises technological and non-technological issues that are not fully resolved. Methodological strategy This research is exploratory as it serves to fill the existing theoretical and empirical gaps in the literature. It thus corresponds to the empirical-inductive paradigm and is based on research propositions. More specifically, the field study was conducted in five companies in one supply chain during the construction and post-construction stages within one refinery. The end customer is the owner of the refinery, the contractor is the construction firm and the suppliers and subcontractors are respectively the supplier of raw materials, the manufacturing company of the piping systems, and company responsible for surface preparation and coating of the piping systems. These five companies correspond to the five levels of the supply chain. A total of 57 participants were involved. Observations, semi-structured interviews and analysis of internal and external documents were used as data sources while the focus groups allowed to reach some consensus on key decision points and to validate the empirical data and the results. A consensus was formed to explore the potential of RFID for 1) the supply of piping systems, 2) the manufacturing, painting and installation of these systems in the construction site (the refinery), and 3) the inspection and maintenance of the piping systems after their installation. This represents three different RFID applications, each with its own requirements in terms of technological, organizational and inter-organizational constraints. These three applications are also the three case studies.  Main results Empirical evidence confirms that RFID has indeed a positive influence on business models, whether at improving existing models or at adopting new models. The impact of RFID on collaborative models receives a weaker and mixed support.  The adoption of RFID technology in a sector as complex as the industrial construction industry seems promising. Indeed, the empirical results demonstrate that RFID technology has a positive impact on the standardization, integration, improvement and automation of processes. This technology also enhances the acquisition, management, sharing, and transfer of knowledge and adds intelligence at the intra-and inter-organizational levels. Finally, it reduces several inefficiencies and lowers several operational costs. The cross-case analysis has identified additional factors. In particular, we have established that three types of isomorphic pressures or mimetic, coercive and normative, have a differentiated influence depending on the type of RFID application and on firms' perspective. The compatibility of RFID scenarios with organizational technology competences also proved to be a significant factor. The research limits as well as the main contributions are discussed in the seventh chapter and the thesis concludes with avenues of research.


identifier: Maillé, M. (2013). Outil d'optimisation des décisions de sélection et de configuration des opportunités de synergie industrielle  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Ce projet de recherche présente un système d'aide à la décision, qui vise l'identification d'opportunités efficaces de mise en valeur de sous-produits en contexte de symbiose industrielle. Cet outil tente de supporter les animateurs de réseaux éco-industriels, les agents de développement économique, les conseils municipaux, les consultants ou les centres de recherche dans l'évaluation des bénéfices économiques et environnementaux potentiels de synergies industrielles, ainsi que dans l'identification de structures optimales de réseaux éco-industriels. Les procédés de traitement des matières résiduelles, comme le tri, la transformation, et le transport ainsi que les flux et les coûts de matière et d'énergie qui leur sont associés ont été intégrés à un modèle de programmation mathématique. Ce modèle vise la minimisation des coûts d'approvisionnement et de gestion des matières résiduelles du réseau éco-industriel en entier, ou de n'importe quel sous-ensemble d'entreprises (incluant une seule compagnie). Le modèle permet aussi d'évaluer les variations de flux de matière et d'énergie dans un réseau éco-industriel lorsque les quantités offertes et demandées de sous-produits évoluent dans le temps, grâce à sa modélisation multi-périodes. Une procédure d'analyse multi-objectifs permet également l'utilisation du modèle afin d'évaluer l'impact financier de minimiser la consommation de matières premières vierges et d'énergie par le biais de la réutilisation des ressources et des synergies. Par la suite, une étude de cas expérimentale basée sur des données publiques relatives aux échanges d'eau de la symbiose industrielle de Kalundborg, au Danemark, est présentée. Le modèle proposé a été testé dans ce contexte afin, d'une part, de comparer les synergies proposées par le modèle à celles qui furent réellement mises en place et, d'autre part, d'analyser les efforts financiers nécessaires à la préservation des ressources. Des horizons de planification de trois et de cinq ans ont également été considérés dans le but d'évaluer l'influence de la durée de la période d'amortissement. Finalement, une analyse de sensibilité sur le prix de l'eau a également été menée pour analyser le rôle de la municipalité dans la promotion des synergies. Ce projet a été mené en collaboration avec le Centre de Transfert Technologique en Écologie Industrielle, situé à Sorel-Tracy, Québec, Canada.  ABSTRACT: This research project introduces a decision support tool, which aims to identify efficient industrial by-products reuse opportunities in industrial symbiosis. This tool aims to support eco-industrial network managers, economic development and city officers, consulting organizations, or research centers to evaluate potential environmental and economic benefits of industrial synergies, and identify optimal arrangements of synergies in eco-industrial networks. Therefore, waste management processes, such as sorting, transforming and transportation, and their associated flows and cost of material and energy have been integrated in a mathematical programming model. This model aims to minimize the cost of procurement and waste management activities of the entire eco-industrial network, or of any sub-sets of companies in the network (including a single company). This model also aims to evaluate material and energy flows variations in eco-industrial networks when the quantity of offered by-products and demand evolve over time, due to its multi-period structure. A procedure of multi-objective analysis also enables the model to be used to evaluate the financial impact of minimizing raw material and energy consumption through synergies and resource reuse. Next, an experimental case study developed from publicly available data related to water exchanges in the industrial symbiosis of Kalundborg, Denmark, is presented. The proposed model was tested in this context to, on the one hand, compare the synergies proposed by the model with actually synergies, and, on the other hand, analyze the financial effort necessary to preserve natural resources. Three and five years planning horizons were also tested in order to assess the impact of the length of recovery period. Finally, a sensitivity analysis on the price of water was also carried out to analyze the role of the municipality as a potential driving force to promote synergies. This project was carried out with the Centre de Transfert Technologique en Écologie Industrielle, Québec, Canada.


identifier: Bai, X. (2013). Optimization of Underground Stope with Network Flow Method  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La thèse présente une série d'algorithmes originaux visant à optimiser la géometrie de chantiers souterrains en 3D, typiquement pour la méthode d'abattage par sous-niveaux (ou méthode des longs trous). Les algorithmes proposés s'inspirent des méthodes efficaces d'optimisation ayant été développées pour les mines à ciel ouvert. La clé de l'adaptation de cette methode pour la méthode des longs trous est de reconnaître que la cheminée verticale (ou monterie), servant à initier un chantier, joue un rôle similaire à la surface dans les mines à ciel ouvert. Un système de coordonnées cylindriques est défini autour de la monterie. Les valeurs économiques des blocs dans ce système sont determinées à partir des données en forage. Les angles limites pour le toit et le plancher sont contrôlés par les liens entre les blocs en coupe verticale. La longueur de chantier est contrôle dans le plan horizontal, à l'aide de deux paramètres : 1) R, la distance horizontale maximale entre un bloc et la cheminée et 2) yR, la largeur minimale de l'enveloppe créée pour exploiter le bloc se trouvant à cette distance maximale. La hauteur du chantier est déterminée par l'extension de la monterie, laquelle limite aussi les liens dans le plan vertical. L'ensemble des liens et des blocs constitue un réseau. Le réseau est complété par deux noeuds fictifs, la source et le puits. En maximisant le flux partant de la source vers le puits, on identifie le chantier optimal. Le chantier obtenu est optimal cependant conditionnellement à la monterie étudiée (localisation et extension), la discrétisation adoptee et les liens représentant les contraintes de pentes. Le problème revient alors à determiner les paramètres de la monterie qui maximisent le profit. Pour ce faire, on utilise une méthode de type génétique permettant d'explorer des solutions variées et surtout de s'échapper d'optimums locaux. La méthode est appliquée sur plusieurs gisements et les résultats sont comparés à ceux de la méthode du chantier flottant ("floating stope"). La méthode proposée démontre sa supériorité sur ces exemples.  ABSTRACT: The dissertation presents a series of algorithms to optimize the underground stope geometry in 3D, typically for sublevel stoping method or longhole stoping. The proposed algorithms are based on network flow method, an effective technique applied in open pit optimization. The key to adapt this method to underground mining is to recognize that the vertical raise to initiate a stope plays a similar role to the surface in open pit mining. Accordingly, a cylindrical coordinate system starting from the raise is introduced to redefine a ore block model. This facilitate the manipulation of geometric constraints. The slope limits of hanging wall and footwall are controlled by the links between the blocks in vertical section. The width of stope is controlled in horizontal plane, by defining two parameters: 1) R, the maximum distance to mine a block from raise, and 2) yR, the minimum width of envelope created to mine the farthest block. The height of stope is defined by the raise extension which limits the links in the vertical section. The blocks and links constitute a network ow graph. Solving the graph with efficient maximum ow method yields an optimal stope conditional to the specified raise. This is the core of proposed methods, an optimal stope generator for given raise parameters. With the stope generator, the global optimization of raise parameters produces a global optimal stope. The algorithm using a single raise is suitable for the relatively small sub-vertical ore bodies. It is shown to provide better results than floating stope algorithm in several scenarios tested.


identifier: Gan, Q. (2013). Efficient Implementation of Particle Filters in Application-Specific Instruction-Set Processor  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse considère le problème de l'implémentation de filtres particulaires (particle filters PFs) dans des processeurs à jeu d'instructions spécialisé (Application-Specific Instruction-set Processors ASIPs). Considérant la diversité et la complexité des PFs, leur implémentation requiert une grande efficacité dans les calculs et de la flexibilité dans leur conception. La conception de ASIPs peut se faire avec un niveau intéressant de flexibilité. Notre recherche se concentre donc sur l'amélioration du débit des PFs dans un environnement de conception de ASIP. Une approche générale est tout d'abord proposée pour caractériser la complexité computationnelle des PFs. Puisque les PFs peuvent être utilisés dans une vaste gamme d'applications, nous utilisons deux types de blocs afin de distinguer les propriétés des PFs. Le premier type est spécifique à l'application et le deuxième type est spécifique à l'algorithme. Selon les résultats de profilage, nous avons identifié que les blocs du calcul de la probabilité et du rééchantillonnage sont les goulots d'étranglement principaux des blocs spécifiques à l'algorithme. Nous explorons l'optimisation de ces deux blocs aux niveaux algorithmique et architectural. Le niveau algorithmique offre un grand potentiel d'accélération et d'amélioration du débit. Notre travail débute donc à ce niveau par l'analyse de la complexité des blocs du calcul de la probabilité et du rééchantillonnage, puis continue avec leur simplification et modification. Nous avons simplifié le bloc du calcul de la probabilité en proposant un mécanisme de quantification uniforme, l'algorithme UQLE. Les résultats démontrent une amélioration significative d'une implémentation logicielle, sans perte de précision. Le pire cas de l'algorithme UQLE implémenté en logiciel à virgule fixe avec 32 niveaux de quantification atteint une accélération moyenne de 23.7×  par rapport à l'implémentation logicielle de l'algorithme ELE. Nous proposons aussi deux nouveaux algorithmes de rééchantillonnage pour remplacer l'algorithme séquentiel de rééchantillonnage systématique (SR) dans les PFs. Ce sont l'algorithme SR reformulé et l'algorithme SR parallèle (PSR). L'algorithme SR reformulé combine un groupe de boucles en une boucle unique afin de faciliter sa parallélisation dans un ASIP. L'algorithme PSR rend les itérations indépendantes, permettant ainsi à l'algorithme de rééchantillonnage de s'exécuter en parallèle. De plus, l'algorithme PSR a une complexité computationnelle plus faible que l'algorithme SR. Du point de vue architectural, les ASIPs offrent un grand potentiel pour l'implémentation de PFs parce qu'ils présentent un bon équilibre entre l'efficacité computationnelle et la flexibilité de conception. Ils permettent des améliorations considérables en débit par l'inclusion d'instructions spécialisées, tout en conservant la facilité relative de programmation de processeurs à usage général. Après avoir identifié les goulots d'étranglement de PFs dans les blocs spécifiques à l'algorithme, nous avons généré des instructions spécialisées pour les algorithmes UQLE, SR reformulé et PSR. Le débit a été significativement amélioré par rapport à une implémentation purement logicielle tournant sur un processeur à usage général. L'implémentation de l'algorithme UQLE avec instruction spécialisée avec 32 intervalles atteint une accélération de 34× par rapport au pire cas de son implémentation logicielle, avec 3.75 K portes logiques additionnelles. Nous avons produit une implémentation de l'algorithme SR reformulé, avec quatre poids calculés en parallèle et huit catégories définies par des bornes uniformément distribuées qui sont comparées simultanément. Elle atteint une accélération de 23.9× par rapport à l'algorithme SR séquentiel dans un processeur à usage général. Le surcoût est limité à 54 K portes logiques additionnelles. Pour l'algorithme PSR, nous avons conçu quatre instructions spécialisées configurées pour supporter quatre poids entrés en parallèle. Elles mènent à une accélération de 53.4× par rapport à une implémentation de l'algorithme SR en virgule flottante sur un processeur à usage général, avec un surcoût de 47.3 K portes logiques additionnelles. Finalement, nous avons considéré une application du suivi vidéo et implémenté dans un ASIP un algorithme de FP basé sur un histogramme. Nous avons identifié le calcul de l'histogramme comme étant le goulot principal des blocs spécifiques à l'application. Nous avons donc proposé une architecture de calcul d'histogramme à réseau parallèle (PAHA) pour ASIPs. Les résultats d'implémentation démontrent qu'un PAHA à 16 voies atteint une accélération de 43.75× par rapport à une implémentation logicielle sur un processeur à usage général.  ABSTRACT: This thesis considers the problem of the implementation of particle filters (PFs) in Application-Specific Instruction-set Processors (ASIPs). Due to the diversity and complexity of PFs, implementing them requires both computational efficiency and design flexibility. ASIP design can offer an interesting degree of design flexibility. Hence, our research focuses on improving the throughput of PFs in this flexible ASIP design environment.  A general approach is first proposed to characterize the computational complexity of PFs. Since PFs can be used for a wide variety of applications, we employ two types of blocks, which are application-specific and algorithm-specific, to distinguish the properties of PFs. In accordance with profiling results, we identify likelihood processing and resampling processing blocks as the main bottlenecks in the algorithm-specific blocks. We explore the optimization of these two blocks at the algorithmic and architectural levels. The algorithmic level is at a high level and therefore has a high potential to offer speed and throughput improvements. Hence, in this work we begin at the algorithm level by analyzing the complexity of the likelihood processing and resampling processing blocks, then proceed with their simplification and modification. We simplify the likelihood processing block by proposing a uniform quantization scheme, the Uniform Quantization Likelihood Evaluation (UQLE). The results show a significant improvement in performance without losing accuracy. The worst case of UQLE software implementation in fixed-point arithmetic with 32 quantized intervals achieves 23.7× average speedup over the software implementation of ELE. We also propose two novel resampling algorithms instead of the sequential Systematic Resampling (SR) algorithm in PFs. They are the reformulated SR and Parallel Systematic Resampling (PSR) algorithms. The reformulated SR algorithm combines a group of loops into a parallel loop to facilitate parallel implementation in an ASIP. The PSR algorithm makes the iterations independent, thus allowing the resampling algorithms to perform loop iterations in parallel. In addition, our proposed PSR algorithm has lower computational complexity than the SR algorithm.  At the architecture level, ASIPs are appealing for the implementation of PFs because they strike a good balance between computational efficiency and design flexibility. They can provide considerable throughput improvement by the inclusion of custom instructions, while retaining the ease of programming of general-purpose processors. Hence, after identifying the bottlenecks of PFs in the algorithm-specific blocks, we describe customized instructions for the UQLE, reformulated SR, and PSR algorithms in an ASIP. These instructions provide significantly higher throughput when compared to a pure software implementation running on a general-purpose processor. The custom instruction implementation of UQLE with 32 intervals achieves 34× speedup over the worst case of its software implementation with 3.75 K additional gates. An implementation of the reformulated SR algorithm is evaluated with four weights calculated in parallel and eight categories defined by uniformly distributed numbers that are compared simultaneously. It achieves a 23.9× speedup over the sequential SR algorithm in a general-purpose processor. This comes at a cost of only 54 K additional gates. For the PSR algorithm, four custom instructions, when configured to support four weights input in parallel, lead to a 53.4× speedup over the floating-point SR implementation on a general-purpose processor at a cost of 47.3 K additional gates.  Finally, we consider the specific application of video tracking, and an implementation of a histogram-based PF in an ASIP. We identify that the histogram calculation is the main bottleneck in the application-specific blocks. We therefore propose a Parallel Array Histogram Architecture (PAHA) engine for accelerating the histogram calculation in ASIPs. Implementation results show that a 16-way PAHA can achieve a speedup of 43.75× when compared to its software implementation in a general-purpose processor.


identifier: Groiez, M. (2013). Étude et séparation des inégalités valides pour des problèmes de partitionnement et de couverture  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse s'intéresse aux inégalités valides et leurs algorithmes de séparation pour  les problèmes de partitionnement et de couverture suivants : le problème d'horaires de véhicules avec plusieurs dépôts (Multiple Depot Vehicle Scheduling Problem, MDVSP), le problème de partitionnement d'ensemble (Set Partitioning Problem, SPP) et le problème du transversal de circuits de cardinalité minimale (MINimum cardinality Feedback Vertex Set problem, MIFVS). Notons que les inégalités valides introduites sont aussi applicables à d'autres problèmes ayant des structures similaires aux problèmes étudiés. Dans la première partie de cette thèse, nous présentons un algorithme combinant la méthode d'élimination de variables, la méthode de séparation et évaluation progressive et la méthode de génération de plans coupants pour la résolution du MDVSP. Nous utilisons la formulation mathématique de multi-flot dans les réseaux, proposée par Ribeiro et Soumis (1994). Pour réduire la taille du problème nous débutons par l'application de la méthode d'élimination de variables. Dans la première phase, nous appliquons une proposition énoncée par Nemhauser et Wosley (1988) et dans la deuxième phase, nous utilisons le principe introduit par Irnich et al.(2010) mais sans génération de colonnes. Ensuite, afin d'améliorer la valeur de la borne inférieure, nous décrivons une méthode de génération de plans coupants. Cette dernière est basée sur une généralisation des inégalités valides introduites par Hadjar et al. (2006). Pour séparer ces inégalités valides, nous proposons d'identifier deux structures particulières propres au MDVSP. Par la suite, nous comparons la performance de différentes stratégies de notre algorithme à l'aide des instances générées aléatoirement. Finalement, nous concluons qu'en général notre algorithme est meilleur que le solveur  commercial CPLEX. La première méthode de séparation proposée pour identifier la première structure, que nous nommons structure de cycle impair conflictuel, utilise la similitude entre le problème du stable et le MDVSP. Notre méthode consiste à construire un graphe de conflit à l'aide d'un sous-ensemble d'arcs possédant certaines propriétés  dans le multigraphe représentant le MDVSP. Nous prouvons qu'un trou impair dans le graphe de conflit  correspond à un  cycle impair conflictuel dans le multigraphe du MDVSP. Afin d'identifier les trous impairs nous adaptons l'algorithme proposé par Nemhauser et Sigismondi (1992). En outre, nous démontrons que chaque  cycle impair conflictuel permet d'obtenir une inégalité valide violée par la solution fractionnaire courante. Afin d'enrichir ces inégalités, nous décrivons une procédure de liftage. La deuxième méthode de séparation proposée pour identifier la deuxième structure, que nous nommons structure de coupe impaire, exploite la ressemblance entre le problème de couplage et le MDVSP et, par conséquent, entre les inégalités valides du MDVSP et les inégalités d'Edmonds (1965). La relation entre les deux problèmes est basée sur le principe de conflit, pour le problème de couplage, deux arêtes adjacentes sont toujours en conflit et pour le MDVSP deux sous-chemins adjacents peuvent être en conflit  s'ils ont la même source ou le même puits ou s'ils sont de couleurs différentes), donc si nous remplaçons un sous-chemin  par une arête, alors les inégalités d'Edmonds engendrent des inégalités valides du MDVSP. Afin d'identifier des structures de coupes impaires, nous construisons un graphe de chemins réguliers, où un chemin régulier est une suite d'arcs de même couleur. Ensuite, nous formulons le problème de séparation comme un programme linéaire en nombres entiers et nous prouvons que certaines solutions entières de ce dernier nous permettent d'identifier des inégalités de coupe impaire. Afin de l'enrichir, nous proposons une procédure de liftage. Nous démontrons  que chaque coupe impaire liftée correspond à une inégalité valide pour le MDVSP. Dans la deuxième partie de cette thèse, nous proposons la résolution du problème de partitionnement d'ensemble par une méthode combinant la méthode de séparation et évaluation progressive et la méthode de génération de plans coupants. Notons que nous nous intéressons au problème de partitionnement pur. Nous introduisons deux nouvelles classes d'inégalités valides: nommées les inégalités de type I et de type II, pour le problème de partitionnement. En outre, nous formulons le problème de séparation de chaque classe d'inégalités valides comme un programme linéaire en nombres entiers et nous montrons que certaines  solutions entières de ce dernier permettent d'identifier des inégalités valides pour le problème de partitionnement. Ensuite, nous proposons de séparer les inégalités de clique en résolvant un autre problème auxiliaire en nombres entiers. Enfin, nous analysons l'efficacité de notre algorithme en utilisant quelques instances de Hoffman et Padberg (1993) et d'autres générées aléatoirement à l'aide du générateur proposé par Lewis et al. (2008). Finalement, nous concluons que notre algorithme est plus efficace que CPLEX lorsque la densité du problème à résoudre est supérieure à 16% et ne l'est pas dans le cas contraire. Dans la dernière partie de cette thèse, nous présentons une méthode combinant la génération de contraintes et des plans coupants afin de résoudre une variante du problème de transversal de circuits de cardinalité minimale. Ce dernier est relié à l'analyse des dictionnaires des langues naturelles. Nous nous intéressons à un des problèmes de linguistique qui consiste à déterminer le nombre minimum de mots à connaître pour comprendre toutes les définitions d'un dictionnaire donné. Ce problème est formulé comme un problème de transversal de  circuits de cardinalité minimale. Nous décrivons des méthodes de séparation de trois classes d'inégalités valides : deux classes particulières des inégalités de Chvátal-Gomory et les inégalités de clique de cardinalité 3. Nous formulons le problème de séparation de chaque classe comme un programme linéaire en nombres entiers et nous démontrons que certaines solutions entières permettent d'identifier des inégalités valides pour le problème à résoudre. Enfin, nous présentons et nous analysons les résultats des tests effectués à l'aide des exemplaires extraits de dictionnaires de langue anglaise. Malheureusement, les résultats obtenus ne sont pas  concluants étant donné que pour certaines instances nous n'avons pas réussi à trouver les solutions optimales en utilisant le solveur commercial, ni à prouver l'optimalité en utilisant notre algorithme. Néanmoins, nous constatons que l'ajout des inégalités valides permet de trouver de meilleures solutions réalisables  dans le temps limite imparti et dans certains cas à trouver la solution optimale. Les travaux présentés dans cette thèse constituent une démarche basée sur les caractéristiques  du problème à résoudre. Notre objectif est de présenter de nouveaux algorithmes efficaces pour la séparation des inégalités valides, permettant l'amélioration  de la valeur de la relaxation linéaire, mais  « bien qu'on ait du cœur à l'ouvrage, l'art est long et le temps est court ». (Charles Baudelaire, Les fleurs du mal).  ABSTRACT: In this thesis, we study  valid inequalities and we propose branch-and-cut algorithms  for some classical problems such as : the  Multiple Depot Vehicle Scheduling Problem (MDVSP), the Set Partitioning Problem (SPP) and the MINimum cardinality Feedback Set problem (MINFVS). In the first part of this thesis, we present an algorithm combining branch-and-bound, cutting planes and variable fixing to solve the MDVSP. We use the  multicommodity flow model of the MDVSP, proposed by Reibero and Soumis (1994). In the first step, we apply a proposition to fix the variables that was introduced by Nemhauser and Wosley (1988) and used by Hadjar et al. (2006). In order to eliminate more variables, we use the same rule as  Irnich et al.(2010) but without column generation. In the second step, we describe a method for separating the valid inequalities introduced by Hadjar et al. (2006) and generalized in the present work. Our method identifies two special structures corresponding to valid inequalities. Then we present the results of computational experiments  comparing the performance of several strategies using the random instances. We conclude that our algorithm is better than the commercial software. The separation procedure that we propose to identify the first structure, called odd conflictual cycle,  uses the similarity between the MDVSP and the stable set problem. We start by creating  a conflict graph of the multigraph representing the MDVSP, we consider only the arcs in conflict. Then we prove that each odd hole in this conflict graph is an odd conflictual cycle in the multigraph representing the MDVSP. In order to identify  odd holes we adopt the polynomial algorithm proposed by Nemhauser and Sigismondi (1992). Moreover we prove that every  odd conflictual cycle identifies a valid inequality violated by the fractional solution. We also present a  lifting procedure in order to enrich the valid inequalities. The  separation procedure that we present to identify the second structure, called odd set, uses the relationship between the MDVSP and the matching problem, consequently the relationship between the valid inequalities for the MDVSP and the blossom inequalities introduced by Edmonds (1965).  In the matching problem two adjacent edges are always in conflict and for the MDVSP two  adjacent subpaths may be in conflict (if they are the same source or the same sink or of different colours). In order to identify the odd set, we use the regular path graph, where a regular path is a sequence of the arcs with the same colour. Then we formulate the separation problem as an integer program and we  prove that each integer solution identifies, under certain conditions, an odd set. In addition, we present a lifting procedure and we prove that each inequality obtained by lifted odd set  is a valid inequality for the MDVSP. In the second part of this thesis, we propose an algorithm combining branch-and-bound and the  cutting planes method to solve the set partitioning problem. Note that we are interested in the pure partitioning problem. We derive new classes of valid inequalities for the problem. Moreover, we present a separation procedure for each class by solving an auxiliary integer program using a fractional solution of the set partitioning problem. Then we prove that each integer solution of this program, under certain conditions, is a valid inequality for the problem. We lift this inequality with variables of value $0$. Also we propose to separate a clique inequality by  using another auxiliary integer program and we prove that each integer solution of this program, under certain conditions, is a clique inequality for the set partitioning problem. Finally, we present the results of a computational study and we compare our results with the commercial software. Note that we use instances of Hoffman and Padberg (1993) and other randomly generated instances using the generator proposed by Lewis et al. (2008). We conclude that our algorithm is better than  the commercial software when the density of the problem is  greater than 16% and is not otherwise. In the last part of this thesis, we present a method combining constraint generation and cutting planes generation in order to solve a class of feedback vertex set problem arising in the analysis of the natural language dictionaries. A dictionary is a set of definitions, where a definition consist of one or several sentences represented by  the sequence of words. We are interested in the linguistic problem of determining the minimum number of words to know in order to understand all definitions in the dictionary. We propose to separate two classes of Chvátal-Gomory inequalities and clique inequalities of cardinality 3  by solving an auxiliary integer program for each of them. Also we prove that each integer solution of the auxiliary program identifies a valid inequality for the feedback vertex set problem. Finally we present and  analyze the resultats of computational experiments using the dictionaries of the English language are available on the Word Wide Web. Unfortunately, the results are not conclusive because we are not able to find optimal solution using a solver commercial or prove optimality using our algorithm. However, we observe that adding the valid inequalities permits to find better feasibles solutions within the time limit prescribed. The work presented in this thesis is an approach based on the characteristics of the problem. Our objective is to present new efficient algorithms for the separation of valid inequalities in order to improve the value of the linear relaxation.


identifier: Vidal Ibacache, G. (2013). Therapeutic Magnetic Microcarriers Characterization by Measuring Magnetophoretic Attributes  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Des micro/nano-robots sont considérés comme une approche prometteuse pour mener des interventions minimalement invasives. Nous avons proposé d'intégrer des nanoparticules magnétiques dans des agents thérapeutiques ou de diagnostic afin de les contrôler magnétiquement. Un scanner d'imagerie par résonance magnétique (IRM)  clinique modifié est utilisé afin de  fournir la force motrice qui permet à ces microporteurs magnétiques à naviguer dans le réseau vasculaire humain. En utilisant des séquences spécifiques des gradients de résonance magnétique (MR) cette méthode a été validée dans des travaux de recherche antérieurs. Magnétophorèse est le terme utilisé pour décrire le fait qu'une particule magnétique modifie sa trajectoire sous l'influence d'une force magnétique tout en étant portée par un flux de fluide. Ce mouvement dépend des caractéristiques de la particule magnétique, de sa forme géométrique, des attributs de l'écoulement de fluide et d'autres facteurs. Dans notre méthode proposée, les microporteurs magnétiques peuvent être réalisés de différentes manières, et donc leur réponse sera différente à la même force magnétique et dans les mêmes conditions d'écoulement de fluide. Le résultat du traitement thérapeutique utilisant notre méthode dépend de la sélection adéquate des agents thérapeutiques et/ou de diagnostic à utiliser. Le microporteur magnétique thérapeutique et /ou de diagnostic choisi influe également sur le choix de la séquence des gradients magnétiques que meilleur se ajustement pour un traitement donné. Ce mémoire de maîtrise présente la conception d'un dispositif destiné à évaluer les propriétés magnétophorétiques des agents microporteurs magnétiques thérapeutiques et/ou de diagnostic. Une telle caractérisation est essentielle pour déterminer les séquences optimales des gradients magnétiques pour dévier leur trajectoire à travers des réseaux vasculaires relativement complexes dans le but d'atteindre un objectif prédéfini. Un dispositif microfluidique est fabriqué pour valider la conception. Las vitesses magnétophorétiques sont mesurées et une méthode de suivi simple est proposée. Les résultats des experiences préliminaires indiquent que, malgré certaines limitations, la technique proposée a le potentiel d'être approprié pour caractériser n'importe quel microporteur magnétique thérapeutique et/ou de diagnostic contenant différents taux de nanoparticules magnétiques.  ABSTRACT: Micro/nano robots are considered a promising approach to conduct minimally invasive interventions. We have proposed to embed magnetic nanoparticles in therapeutic or diagnostic agents in order to magnetically control them. A modified clinical Magnetic Resonance Imaging (MRI) scanner is used to provide the driving force that allows these magnetically embedded microcarriers to navigate the vascular human network. By using specific Magnetic Resonance (MR) gradient sequences this method has been validated in previous research works. Magnetophoresis is the term used to describe the fact that a magnetic particle changes its trajectory under the influence of a magnetic force while being carried by a fluid flow. This movement depends on the particle's magnetic characteristics, the particle's geometric shape, the fluid flow's attributes and other factors.  In our proposed method, magnetic microcarriers can be produced in several different ways, and so their response will differ to the same magnetic force and fluid flow conditions. The outcome of the therapeutic treatment using our method depends on the adequate selection of the therapeutic and/or diagnosis agents to be used. The selected therapeutic and/or diagnosis magnetic microcarrier also influences the selection of the MR gradient sequence that best fit for a given treatment. This master's thesis presents the design of a device intended to assess the magnetophoretic properties of magnetic therapeutic microcarriers and/or diagnostic agents. Such characterization is essential for determining the optimal sequences of magnetic gradients to deflect their trajectory through relatively complex vascular networks in order to reach a pre-defined target. A microfluidic device was fabricated to validate the design. Magnetophoretic velocities are measured and a simple tracking method is proposed. The preliminary experimental results indicate that, despite some limitations, the proposed technique has the potential to be appropriate to characterize any drug and/or diagnosis magnetic microcarrier containing different magnetic nanoparticle content.


identifier: Beamonte, R. (2013). Traçage de systèmes linux multi-coeurs en temps réel  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le traçage est une méthode d'analyse de plus en plus populaire compte tenu de la précision des données qu'il permet de réunir concernant les activités d'un système. Nombre de systèmes demandent cependant aujourd'hui de fonctionner dans des conditions restreintes : c'est le cas des systèmes temps réel. Ces systèmes reposent sur le respect d'échéances dans le traitement de données. Autrement dit, une donnée exacte n'aura de valeur dans un système de ce type qu'à condition qu'elle soit obtenue dans les délais, sans quoi le système sera considéré défaillant. Ces conditions excluent par conséquent tout outil d'analyse impactant de manière significative la latence et les performances du système. Le traçage repose sur l'ajout de points de trace au sein de l'application ou du système d'exploitation tracé. Ces derniers vont générer des évènements lorsqu'ils sont atteints durant l'exécution et ainsi permettre de suivre l'état d'un système au fur et à mesure de son exécution. Cependant, la génération de ces données implique une modification dans le déroulement normal de l'application ou du système tracé, et par conséquent un impact. Il devient alors important de pouvoir quantifier cet impact de manière à savoir sous quelles conditions une application temps réel pourra ou ne pourra pas être tracée, autrement dit, de savoir si l'ajout de ce délai de traitement rendra le système défaillant, et par conséquent inadéquat au traçage. L'objectif de cette recherche est de montrer qu'il est tout à fait possible d'utiliser le traçage pour analyser de telles applications, et ce avec un impact en terme de latence que nous souhaitons quantifier pour le pire cas. Pour ce faire, nous allons définir un environnement de travail temps réel en étudiant les divers systèmes et configurations spéciales mis à disposition. Ensuite nous verrons quels sont les outils permettant de valider la qualité de notre environnement de travail et quel est leur fonctionnement. Nous comparerons par la suite les différents outils mettant à disposition des traceurs, et lesquels parmi eux nous permettent de corréler des traces du noyau et de l'espace utilisateur. Une fois l'environnement défini et vérifié et l'outil de traçage choisi, notre méthode expérimentale reposera sur un étalonnage du système temps réel permettant par la suite d'évaluer l'impact du traceur sous différents angles à l'aide de la création de différent scénarios d'analyse. Cette méthode expérimentale prendra en compte la latence ajoutée sur le système par l'instrumentation, le traçage mais aussi la qualité des traces obtenues. Ces éléments seront les marqueurs de qualité du traçage dans des conditions temps réel. L'hypothèse servant de point de départ de ce travail est qu'en isolant le fonctionnement du traceur de celui de l'application temps réel tracée, l'impact de l'outil de traçage sur l'application pourra être radicalement réduit. Les résultats de ce travail sont la découverte et l'intégration aux outils existants d'un modèle pour supprimer les communications entre l'application tracée et le traceur durant la période active de traçage, permettant ainsi de n'ajouter qu'une interférence minimale sur l'exécution normale de l'application, permettant ainsi de rendre le traçage apte à fonctionner dans nombre de conditions temps réel, du moment que le délai maximal qu'il ajoute entre dans l'échéance de celle-ci. De plus, l'outil npt créé comme outil d'étalonnage et d'analyse de l'impact a évolué au fur et à mesure de nos recherches et est maintenant un logiciel disposant de différentes options pour simuler de multiples scénarios d'exécution d'une application temps réel. Enfin, la méthodologie d'analyse de l'impact du traçage sur le système temps réel constitue elle aussi un des résultats de cette étude. Le résultat final est que l'utilisation du traçage pour une application temps réel s'exécutant dans l'espace utilisateur est viable pour la plupart des systèmes temps réel avec une latence ajoutée de seulement quelques microsecondes.  ABSTRACT: Tracing is an analysis method increasingly popular. It provides a lot of information of high precision about a system or application. However, many systems need to operate under restricted conditions. This is the case of real-time systems. These systems are based on meeting deadlines in data processing. In other words, accurate data will only have a value if we can poduce it in a timely fashion, otherwise we will consider the system as defective. These conditions therefore exclude any analysis tool which could impact significantly the system latency or performance. Tracing is based on the addition of tracepoints directly in the application or operating system source code. There tracepoints will generate events when they are reached as part of the execution, and allow to monitor the system or application state during its run. Still, the generation of this data involves a change in the normal course of the traced system, hence an impact. It then becomes important to quantify this impact in order to know the conditions for tracing a real-time application, in other words, to know whether the added latency will invalidate the real-time condition, hence force to consider tracing as inedequate or not. The objective of this research is to prove that it is possible to use tracing to analyze such applications, thus quantifying the maximum impact in terms of latency. In order to do that, we will define a real-time work environment by studying the various systems and special configurations available, then we will see what tools allow to validate the quality of our work environment and how they work. We will then compare the various tracing tools and identify which allow us to correlate the kernel and userspace traces. Once we have setup and verified our real-time environment and selected our tracing tool, our experimental method will be based on real-time system calibration to subsequently assess the impact of the tracer from different use cases, using different analysis scenarios. This experimental method will take into account the latencies added by the instrumentation and the tracing of the system, but also the quality of the generated traces. These elements will be considered as quality markers of real-time tracing. The hypothesis serving as starting point for this work is that, by isolating the work of the tracer from that of the real-time application, the impact of the tracing tool on the application can radically be reduced. The results of this work are the discovery and integration in existing tools of a model to remove the direct connections, between the traced application and the tracer, while the tracing operations are active. This allows to only add a minimal interference to the normal execution of the application, thereby making tracing able to operate multiple real-time cases, as long as the maximum latency added can be supported by the traced application. In addition, the npt tool created as the calibation and impact analysis tool has evolved during our research and now offers options allowing to simulate multiple execution scenarios of real-time applications. Finally, the real-time tracing impact analysis methodology we developed is also one of the results of this study. The final result is that using tracing to analyze real-time applications running in userspace is a valid and good option for most real-time systems, adding latencies in the low microsecond range.


identifier: Seguineau de Preval, C. (2013). Vers la simulation d'écoulements turbulents dans un convertisseur catalytique par la méthode de Boltzmann sur réseau  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Ce mémoire s'inscrit dans un effort plus large visant à évaluer et caractériser l'apport potentiel de la méthode de Boltzmann sur réseau (MBR) pour la simulation des convertisseurs catalytiques. Un modèle de turbulence - plus spécifiquement un modèle de simulation des grandes échelles (LES - Large Eddy Simulation) - est implémenté et validé par deux simulations d'écoulements turbulents : écoulement entre deux plans parallèles et écoulement au sein d'une conduite cylindrique. L'étude de l'écoulement à travers un bloc monolithe (ensemble de micro-canaux parallèles) est restreinte à celles de la longueur de transition au sein d'un canal et de la perte de charge induite par les micro-canaux. L'expression empirique de la longueur de transition au sein d'un canal est adaptée au cas des micro-canaux à section carrée via une étude paramétrique portant sur le régime d'écoulement. Et une méthode pour l'évaluation des pertes de charge au travers d'un bloc monolithe est proposée et appliquée à une géométrie simplifiée. Il s'avère que la résolution du champ de pression est plus contraignante que celle du champ de vitesse, puisqu'elle nécessite un nombre de Mach plus faible, et donc un facteur de relaxation plus faible. De même, l'impact du raffinement de maillage est plus important sur le champ de pression que sur le champ de vitesse. La dépendance quadratique en vitesse de la perte de charge singulière est validée. Finalement, la méthode de Boltzmann sur réseau (MBR) est utilisée pour simuler des écoulements turbulents de gaz à travers un cylindre comportant un bloc monolithe constitué de 1316 canaux à section carrée. Les différentes contraintes relevées lors des travaux pour garantir une convergence correcte de la vitesse et du champ de pression impliquent des temps de calculs et des ressources informatiques considérables et non envisageables pour une application industrielle. La nécessité d'un raffinement local de maillage, que ce soit sur un maillage structuré ou non structuré, est confirmée aussi bien pour le calcul du champ de vitesse d'écoulements turbulents que pour l'obtention correcte d'un champ de pression auprès d'une géométrie disruptive, comme l'expansion brusque en sortie des micro-canaux du bloc monolithe.  ABSTRACT: This work is part of a global effort aiming at characterizing the possible contribution of the Lattice Boltzmann Method (LBM) to the simulation of catalytic converters. A turbulence model, more specifically a Large Eddy Simulation (LES) model, is implemented and validated through two turbulent flow simulations : one between two parallel plans, and the other in a cylindrical tube. The study of the flow through a monolith (set of parallel micro-channels) is limited to that of the transition length within a canal and of the pressure drop induced by the micro-channels. A parametric study of the flow regime is done in order to develop the empirical expression of the transition length within micro-channels with a squared cross-section. A method to evaluate the pressure drop through a monolithic block is proposed and applied to a simplified geometry. It is found that the resolution of the pressure field is more constraining than that of the velocity field because it requires a lower Mach number, and hence a lower relaxation factor. Likewise, the impact of the mesh refinement is more important on the pressure field than on the velocity field. The quadratic dependency between velocity and minor head losses is validated. Finally, the Lattice Boltzmann Method (LBM) is used to simulate turbulent gas flows through a cylinder with a monolithic block composed of 1316 mico-channels with a squared cross-section. The difficulties encountered during this work to solve the velocity and pressure fields highlighted the significant and for industrial applications unconceivable calculation times and required computational ressources. The need of a local mesh refinement, be it for a structured or unstructured mesh, is confirmed for the calculation of the velocity field of turbulent flows as well as for obtaining the pressure field in the vicinity of a disruptive geometry, like a sudden expansion after the micro-channels of a monolithic block.


identifier: Chouinard, J.-M. (2013). Nanoparticules d'alliage or-étain pour le remplissage des trous d'interconnexion  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le présent mémoire porte sur la possibilité d'utiliser des nanoparticules d'alliage or-étain à l'eutectique, dont la température de fusion est de 280ºC, pour un procédé via-last de remplissage de trous d'interconnexions (TSV – Through Silicon Via). Les principaux objectifs sont de déterminer la meilleure approche pour suspendre les nanoparticules dans un solvant ainsi que d'analyser et de comprendre le comportement des nanoparticules d'alliage Au-Sn lors de traitements thermiques. Dans un premier temps, la préparation de suspensions stables de nanoparticules dans un solvant a été étudiée. Trois techniques ont été analysées soit de charger les particules, de fonctionnaliser leur surface et d'utiliser un surfactant. Puisque les nanoparticules sont relativement grosses (de l'ordre de 30 nm) et qu'elles sont agglomérées entre elles, seul l'ajout d'un surfactant permet d'obtenir une solution stable et homogène sur une période de plusieurs mois. Le surfactant qui a donné les meilleurs résultats est le PVP (PolyVinylPyrrolidone). Les nanoparticules Au-Sn préparées par une technique de plasma chaud se devaient d'avoir la composition précise de l'alliage eutectique 80Au-20Sn car une légère déviation dans leur composition peut faire augmenter considérablement la température de fonte. Des analyses XPS ont démontré que les nanoparticules avaient une concentration en or plus élevée que ce qui était désiré. Ainsi, la fusion complète des particules, afin de former un matériau uniforme à l'intérieur des TSV, s'est avérée impossible pour des températures de recuit compatibles avec un procédé via-last. Des mesures de calorimétrie différentielle à balayage (DSC) et de diffraction des rayons X (DRX) ont en effet démontré que les nanoparticules n'ont pas toutes la composition de l'eutectique. Aussi, l'enthalpie de fusion est 11,5 fois plus faible pour les nanoparticules que pour des microparticules du même alliage. Des phases qui n'entrent pas dans la composition de l'eutectique ont également été observées lors des mesures. Le fait que les nanoparticules ne fusionnent pas, et ce même à une température de 600ºC, a été attribué à deux facteurs. Le premier est que la technique de fabrication des nanoparticules ne permet pas d'obtenir une composition exacte et uniforme. Des phases riches en étain ainsi que la phase d'or non lié à l'étain sont présentes dans les nanoparticules. Le deuxième facteur est que les particules sont trop petites pour pouvoir être composées de l'alliage eutectique proprement  ABSTRACT: This master thesis focuses on evaluating the feasibility of using nanoparticles of gold-tin alloy at the eutectic composition, for which the melting point is 280 °C, for a via-last through silicon via (TSV) filling process. The main objectives are to determine the best approach for suspending nanoparticles in a solvent, as well as analyzing and understanding their behavior during heat treatments. First, the preparation of stable nanoparticle suspensions in a solvent was studied. Three approaches were investigated: charging the particles, functionalizing their surface, and using a surfactant. As nanoparticles are relatively big (in the order of 30 nm), and because they are agglomerated, only the addition of a surfactant produces a stable and homogeneous solution over a period of several months. The surfactant which yielded the best results is PVP (PolyVinylPyrrolidone). The Au-Sn nanoparticles prepared by a hot-plasma technique should have the precise composition of the 80Au-20Sn eutectic alloy since a slight deviation in composition can considerably increase the melting temperature. X-ray photoelectron spectroscopy (XPS) analyses revealed that the nanoparticles had a slightly higher gold content than anticipated. Therefore, the complete melting of the particles, required for forming a uniform material inside the TSV, has proven impossible for annealing temperatures compatible with a via-last process. Differential scanning calorimetric (DSC) and X-ray diffraction (XRD) analyses indeed demonstrated that composition of nanoparticles is not exactly that of the eutectic. Also, the enthalpy of fusion is 11.5 times lower for nanoparticles than microparticles of the same alloy. Phases which do not form part of the composition of the eutectic were also observed in these measurements. The fact that nanoparticles do not melt, even at temperatures of 600 °C, was attributed to two factors. First, the nanoparticle fabrication technique does not allow for a precise and uniform composition as tin-rich as well as pure gold phases were detected. Secondly, the results indicate that the nanoparticles too small to be composed of the eutectic alloy. Indeed, due to their small size, both phases of the eutectic are not present in adequate proportions inside the nanoparticles. It is therefore impossible for this material to have a melting point of 280 °C when it is in the form of nanoparticles.


identifier: Blanchet, G. (2013). Optimisation de la conception d'un réseau de collecte d'énergie éolienne par recherche locale  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le problème de l'optimisation de la conception de réseaux, plus particulièrement d'un parc éolien, intervient lorsqu'une compagnie souhaite louer une partie des câbles de transmission d'un réseau appartenant à un tiers parti (l'État ou une autre compagnie) et construire/acheter l'autre partie manquante. Il est possible de reformuler ce problème comme le problème de l'arbre de Steiner en adaptant la fonction de coût des câbles de transmission.  Une fois cette adaptation faite, une heuristique employant une méthode exacte est développée. L'heuristique développée se découpe en deux pans : 1) la construction d'une solution réalisable initiale itérativement en utilisant un algorithme de plus court chemin, et 2) l'amélioration de cette solution par une série de déconnexions de certaines parties de la solution et de leur reconnexion à l'autre partie restante non déconnectée de la solution en question. Les résultats montrent que la méthode de construction de la solution initiale échoue parfois à trouver une solution réalisable. Ils montrent également que pour de larges exemplaires, le prototype d'amélioration de la solution initiale s'avère très efficace et pourra vraisemblablement s'attaquer à de très gros problèmes, impensables à résoudre avec les méthodes actuelles, si quelques ajustements sont faits.  ABSTRACT: The problem of optimizing the design of network, in particular wind farm network, occurs when a company wishes to rent cables from a part of an existing transmission network owned by a third party (the government or another company) and construct or buy cables from the other part missing. It is possible to reformulate this problem as the Steiner tree problem in graph by adjusting the cost function of the transmission cables.  Once this adaptation made, a heuristic using an exact method is developed. The heuristic developed is divided into two sections: 1) the construction of an initial feasible solution iteratively using the shortest path algorithm, and 2) improving this solution by a series of disconnection of parts of the solution and their connection to the other remaining portion not disconnected from the solution at hand. The results show that the method of construction of the initial solution sometimes fails to find a feasible solution. They also show that for large instances, the heuristic is very effective and will probably find good solutions also for very large problems, unthinkable to solve with current methods, if some adjustments are made.


identifier: Collard, J. (2013). Planification stratégique d'une mine souterraine avec teneur de coupure variable  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La planification stratégique d'une mine souterraine est une activité complexe qui nécessite plusieurs étapes. Comme son nom l'indique, ce niveau de planification sert à définir la stratégie de l'entreprise durant les prochaines années. L'horizon de planification est relativement long, mais il dépend des ressources géologiques et des réserves minières. Lors de la construction de l'échéancier d'une mine souterraine, plusieurs aspects doivent être évalués tels le départ et la fin de la mine, le taux de production, l'ordonnancement des activités, la teneur de coupure, etc. Lorsque plusieurs mines peuvent débuter en même temps et qu'elles consomment les mêmes ressources humaines et matérielles, la difficulté du problème augmente. Dans ces conditions, les méthodes manuelles ne permettent pas d'obtenir de bonnes solutions rapidement. La teneur de coupure fait aussi partie des décisions stratégiques et est intimement liée à la planification. Il est donc nécessaire de l'incorporer au plan d'exploitation. Une fois de plus, la complexité augmente puisque la durée des tâches est liée à la teneur de coupure sélectionnée. La planification stratégique pour les mines à ciel ouvert est largement documentée mais, elle l'est très peu pour ce qui est des mines souterraines. Dans ce mémoire, un programme linéaire en nombres entiers (PLNE) est proposé pour résoudre un problème de planification stratégique d'une mine souterraine. Le modèle est spécifiquement développé pour Mine Raglan située dans le nord québécois. Le modèle servira d'outil d'aide à la décision aux ingénieurs de Mine Raglan. Le site possède plusieurs mines en opération et plusieurs projets miniers potentiels. Il devient difficile de déterminer quel projet débuter et quand il est propice de le faire. À l'aide du modèle, plusieurs scénarios pourront être testés. Il est à noter que le modèle est général et peut facilement être modifié pour s'adapter à d'autres mines. Ce mémoire peut se diviser en deux grands thèmes soit : l'évaluation des paramètres et le modèle mathématique. L'évaluation des paramètres est importante, car de nombreuses étapes doivent être effectuées avant de planifier une mine. Normalement, la conception doit être faite pour pouvoir définir les activités et construire un échéancier. Dans ce mémoire, la conception minière est évaluée par des courbes statistiques. Cette méthode permet, entre autres, d'obtenir rapidement une solution selon les critères de conception établis dans le passé. Lorsque la conception d'une mine est faite, les activités peuvent être ajoutées au modèle pour obtenir une meilleure estimation du profit réalisé par la mine. Une fois les paramètres évalués, le modèle permet de définir l'échéancier optimal ainsi que la meilleure teneur de coupure. La théorie actuelle sur la teneur de coupure est difficilement applicable au contexte de Mine Raglan. En effet, chaque mine de Mine Raglan possède plusieurs gisements de tonnage et teneur différents. Le choix de la teneur de coupure est donc fait par le modèle qui permet à chaque gisement d'avoir sa propre teneur de coupure.  ABSTRACT: Strategic planning of an underground mine is a complex activity that requires several steps. This level of planning defines the strategy of the company for the next years. The planning horizon is relatively long but it depends on the resources and reserves of the mine. During the scheduling of an underground mine, several aspects must be evaluated such as the start and the end of the mine, the production rate, the cut-off grade, etc.. When several mines can begin at the same time and are using the same human and material resources, the difficulty of the problem increases. Under these conditions, it is hard to get a good solution quickly with manual methods. The cut-off grade is also a strategic decision and is closely related to planning. It is therefore necessary to incorporate this decision into the strategic plan. Once again, the complexity increases as the duration of the work is related to the content of selected cut-off grade. Strategic planning for open pit mining is well documented but the application of the operational research in underground is newer. In this paper, a mixed integer program (MIP) is proposed to solve a problem of strategic planning of an underground mine. The model is specifically developed for Raglan Mine in northern Quebec. The model will serve as a tool for decision support for the Raglan Mine's engineers. Raglan Mine has four mines in operation and several potential mining projects. It becomes difficult to determine when a project must start. Using the model, several scenarios can be tested. It should be noted that the model is general and can be easily modified to fit with other mines. This master thesis can be divided into two main themes: the parameters evaluation and mathematical model. The parameters evaluation is important because many steps must be performed before the planning. Normally, the design must be done before the planning. In this paper, the design for a new mine is evaluated by statistical curves. This method can get a solution to the design criteria established in the past. If a real design is made, the activities can be added to the model to get a better estimate of the mine profit. Once the parameters evaluated, the model is used to define the optimal schedule and the best cut-off grade. The current theory of the cut-off grade is difficult to apply in the context of Raglan Mine. In fact, each deposit at Raglan Mine has is own grade-tonnage curve. The choice of cut-off is made by the model that allows each deposit to have its own cut-off grade.