identifier: Astolfi, M. (2015). Tumeurs micro-disséquées sur puce microfluidique  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le cancer est une maladie complexe et très difficile à éliminer, en grande partie en raison des nombreux types différents de cancers et du caractère unique de chaque individu, faisant en sorte que les patients répondent différemment à la gamme grandissante de traitements disponibles. D'associer à chaque patient le meilleur traitement possible constitue l'un des grands défis de la médecine personnalisée d'aujourd'hui. Cela permettra d'éviter les effets secondaires et les coûts liés à des traitements inefficaces. En même temps, les chances de succès seront plus élevées puisqu'en appliquant le traitement optimal plus tôt, le cancer aura moins le temps de développer les mécanismes de résistance qui le rendent de plus en plus difficile à traiter. Cependant, les modèles actuels de culture de cellules cancéreuses ne permettent pas de recréer parfaitement toutes les caractéristiques des patients qui seront ultimement traités par les chimiothérapies testées. Les modèles animaux ne répliquent pas bien le système immunitaire humain, ni la complexité et l'instabilité génétique des cancers humains alors que la plupart des modèles de culture in vitro négligent en plus le caractère tridimensionnel (3D) du tissu. Les sphéroïdes – des amas cellulaires tridimensionnels synthétisés en laboratoire – sont un modèle de tissu simple et prometteur, mais ceux formés à partir de lignées cellulaires établies ne reproduisent pas bien la complexité et les particularités des cancers de patients. L'objectif de ce projet est de proposer une procédure permettant d'effectuer des tests de réponses aux chimiothérapies directement sur le tissu tumoral de patients, extrait par biopsie ou par chirurgie. En préservant l'architecture 3D et la composition cellulaire du tissu primaire, cette technique a le potentiel de mieux prédire la réponse du patient comparativement aux autres méthodes de culture des cellules. L'approche retenue consiste à miniaturiser les échantillons ainsi que le dispositif dans lequel ils sont gardés en culture, ce qui lui confère des avantages importants relatifs au contexte clinique dans lequel le projet s'inscrit. Premièrement, en coupant petit, il est possible d'obtenir plusieurs échantillons à partir d'une quantité minime de tissu, lesquels pourront ensuite être exposés à différentes options de traitements. Deuxièmement, en employant un système microfluidique comme dispositif d'incubation, le volume est grandement réduit, minimisant par le fait même les coûts en réactifs (par exemple, les chimiothérapies ou les marqueurs fluorescents). Enfin, la petite taille des systèmes réduit les temps de diffusion, ce qui facilite le transport d'oxygène, de nutriments et d'autres molécules jusqu'au centre du tissu.  ABSTRACT: Cancer is a complex disease and very difficult to eradicate, mainly because there are many different subtypes of cancer and each individual responds differently to the increasing number of available treatments. Associating the best treatment to each and every patient is one of the greatest challenges of personalized medicine today. Personalizing treatment will enable doctors to avoid the side effects and costs related to inefficient treatments. At the same time, therapy success rates will increase by applying an efficient treatment earlier when the disease has not yet had time to develop resistance mechanisms making it more difficult to treat. However, currently available cancer cell culture models do not perfectly recreate all the characteristics of patients' tumors that will ultimately be treated by the tested therapeutics. Animal models do not replicate the human immune system, nor the complexity and instability of human cancers, while most in vitro models also neglect the three dimensionality of tissue. Spheroids – laboratory-synthesized three dimensional (3D) clusters of cells – constitute a simple and promising tissue model, but those grown from established cell lines do not reproduce the complexity and characteristics of specific patients' cancers. The aim of the current research is to propose a new procedure whereby different drugs could be tested directly on tumor tissue extracted from patients through biopsy or surgery. By preserving the 3D architecture and cellular composition of primary tissue, this technique could potentially offer better prediction of patients' response compared to other cell culture models. The chosen approach, which consists in miniaturizing the tissue samples and the device in which they are cultured, has many important advantages relative to the clinical application of the project. First, by cutting the tissue into small pieces, many samples are obtained from a small quantity of tissue which can then be exposed to different treatment options. Second, through the use of a microfluidic system as an incubation device, the volume is reduced, thereby minimizing the cost of reagents (for example, chemotherapy agents or fluorescent markers). Finally, the small size of the systems reduces diffusion times, which facilitates the transport of oxygen, nutrients and other molecules to the center of the tissue. Four different types of mouse tumor xenografts – grown from human prostate and ovarian cancer cell lines – were used to establish all the steps of the procedure. First, a cutting technique was developed to produce many submillimeter-sized micro-dissected tumor samples (MDTs) from small amounts of primary tissue. Disk-like MDTs of approximately 380 µm in diameter by 300 µm high were produced using a vibratome to cut thin slices of agar-embedded tissue followed by a biopsy punch to reduce their size to the desired diameter.


identifier: Rasouli, M. (2015). Dynamics of Cylindrical Particles in a Rotating Drum Using Multiple Radioactive Particle Tracking  [Thèse de doctorat, École Polytechnique de Montréal].

type:
Mémoire ou thèse
NonPeerReviewed

abstract: RÉSUMÉ: Les écoulements granulaires sont d'une grande importance par rapport à plusieurs domaines allant des sciences planétaires à la géophysique ainsi qu'à plusieurs industries telles que l'industrie métallurgique, des céramiques, chimique, alimentaire, des cosmétiques, du charbon et pharmaceutique. La fabrication, l'analyse des procédés et le contrôle des produits granulaires dépendent fortement d'une maitrise fondamentale des écoulements granulaires. Les régimes d'écoulements granulaires englobent les classes générales suivantes : quasi-statique, dense (écoulements liquides) et rapide (écoulements gazeux). Le régime dense est considéré comme le plus compliqué des trois classes et aussi le moins étudié dans la littérature comparé aux deux autres régimes. Le tambour rotatif représente l'équipement expérimental standard utilisé pour étudier l'écoulement granulaire dense. De plus, les tambours rotatifs possèdent plusieurs applications industrielles et sont utilisés dans plusieurs procédés (le mélangeage, la réduction de taille, le frittage, le chauffage, le refroidissement, le séchage ainsi que les réactions chimiques). Afin de réaliser le dimensionnement approprié des tambours rotatifs et d'ajuster les conditions opératoires optimales, il est essentiel d'étudier la phénoménologie intrinsèque à ce type d'équipement de manière fondamentale. Dans les procédés industriels, les tambours rotatifs fonctionnent dans le régime de roulement étant donné que ce régime assure un fort mélangeage des particules et un bon transfert de chaleur. Plusieurs études expérimentales ont été menées pour déterminer le régime d'écoulement régnant dans le tambour rotatif. Néanmoins, la majeure partie de ces recherches ont considéré des particules sphériques ou quasi-sphériques. Pourtant, l'étude des particules non sphériques est d'une très grande importance vu que les particules trouvées dans la nature et celles provenant des procédés de broyage sont de forme irrégulière. Aussi, les particules non sphériques ayant une forme spécifique (ellipsoïdale par exemple) ont plusieurs utilités. En outre, il est très important de mentionner que la forme des particules possède une influence majeure sur le régime d'écoulement. Ainsi, le présent travail a pour objectif d'étudier l'effet de la forme des particules sur la dynamique des écoulements granulaires. Afin d'y parvenir, des particules cylindriques ont été considérées pour deux principales raisons. Premièrement, il existe plusieurs applications industrielles qui utilisent des particules cylindriques comme les capsules et les pastilles. vii Deuxièmement, la forme des particules étudiées doit être facilement identifiable et distincte d'une sphère pour pouvoir tirer une bonne conclusion sur l'effet de la forme des particules sur le régime d'écoulement granulaire. À ce titre, le cylindre représente l'une des formes curvilignes les plus basiques. Ainsi, plusieurs autres formes comprenant celles ayant un facteur de forme élevé, peuvent être approchées par la forme cylindrique. Plusieurs techniques de mesure non intrusives comme les méthodes optiques et radioactives ont été utilisées pour étudier l'écoulement granulaire dans un tambour rotatif. Comme la matière particulaire est opaque, les techniques optiques sont limitées à l'observation au niveau des écoulements surfaciques. Par contre, les techniques de mesure radioactives sont plus adaptées pour fournir des informations sur l'intérieur du lit de particules. En effet, les rayons gamma ont la particularité de traverser la matière avec une grande facilité. La technique de suivi de particules radioactives (RPT) est l'une des techniques appropriées pour cette étude. Cependant, la RPT est limitée au suivi de la position d'un seul traceur à la fois. Étant donné que des particules de forme cylindrique présentent le cas d'étude, il est essentiel de trouver une technique de mesure permettant de repérer la position ainsi que l'orientation d'une particule de manière simultanée. Ainsi, la première partie de cette thèse introduit une technique de suivi d'une multitude de particules radioactives (MRPT) qui permet de déterminer la trajectoire de deux traceurs en mouvement dans le système. Ces derniers peuvent être libres ou attachés à la même particule. L'exactitude (<5 mm) et la précision (<5 mm) des mesures obtenues par la technique proposée ont été évalués en suivant deux traceurs immobiles et deux traceurs en mouvement. Les résultats obtenus démontrent la fiabilité et la validité de la MRPT lorsque les deux traceurs possèdent le même isotope et lorsque la distance entre ces deux traceurs n'est pas très petite (>2 cm). Le suivi de deux traceurs fixés aux deux extrémités d'une particule cylindrique dans un tambour rotatif est également étudié afin d'illustrer le potentiel de cette méthode de caractérisation. La deuxième partie de cette thèse présente la comparaison entre l'écoulement de particules cylindriques (2 cm de longueur et 6 mm de diamètre) et l'écoulement de particules sphériques (6 mm de diamètre). Cette comparaison est réalisée à l'aide de la MRPT afin de détecter la position et l'orientation des particules cylindriques de manière simultanée. Deux composantes principales de la dynamique de l'écoulement transversal ont été analysées. La première est la frontière entre viii la couche active et la couche passive. La deuxième est le profil de vitesse sur la surface libre en régime de roulement (7,5 à 15 tours/min pour les particules cylindriques dans les conditions de cette étude). La dynamique de l'écoulement des particules cylindriques est différente de manière significative de celle des particules sphériques. Pour la première fois, l'orientation des particules cylindriques à l'intérieur du lit a été mesurée. Les résultats confirment l'existence d'une orientation spatiale préférentielle pour les particules cylindriques dans la couche active (elle correspond à une déviation d'environ 25° de l'angle de repos dynamique). Il a également été démontré que cette orientation spatiale préférentielle n'est pas sensible à la vitesse de rotation du tambour. Ainsi, pour les particules cylindriques, la dilatation du lit de particules était constante (environ 25%) pour toutes les vitesses de rotation, alors qu'elle était d'environ 1% pour les particules sphériques. Aussi, les profils de vitesse obtenus pour la surface libre des particules cylindriques montrent une forme asymétrique (le pic du profil de vitesse est situé à 70% de la longueur de la surface libre). En ce qui concerne les particules sphériques, les profils de vitesse démontrent une forme symétrique (le pic du profil de vitesse est situé à 50% de la longueur de la surface libre). Pour la première fois pour des particules cylindriques, deux modèles généraux ont été proposés pour calculer le profil de vitesse à la surface libre ainsi que la taille effective des particules dans les couches active et passive. Finalement, la troisième partie de ce projet doctoral présente une analyse plus poussée des données obtenues dans les deux parties précédentes à l'aide de la MRPT et de la RPT. Les équations de mouvement pour les particules sphériques et cylindriques dans les couches active et passive ont été obtenues. En outre, les équations des lignes de courbe représentant le point d'inflexion de la vitesse ainsi que les équations du yield ont été développées. L'utilisation potentielle de ces équations de mouvement a été illustrée à l'aide des simulations numériques considérant l'effet de l'advection sur la qualité de mélangeage des particules sphériques et cylindriques.  ABSTRACT: Granular flows are important in a wide range of fields, ranging from planetary science to geophysics, and industries such as metallurgy, ceramics, chemicals, food, cosmetics, coal and pharmaceuticals. The manufacturing, processing, and control of granular products depend on a fundamental understanding of the granular flows. The quasi-static, dense (liquid) and fast (gaseous) flow regimes are general granular flow regimes. Of these, the dense granular flow regime is the most complicated, and the one with the least investigation. The rotating drum is one of the standard experimental systems for studying the dense granular flow regime. In addition, rotating drums have many industrial applications, and are used in a great variety of processes (mixing, size reduction, sintering, coating, heating, cooling, drying, and reaction). To design and operate rotating drums optimally, it is essential to study the phenomena that occur inside such devices on a fundamental level. In industrial operations, rotating drums mainly use the rolling regime, which provides superior solid mixing and heat transfer. Many experimental studies have been conducted to obtain the flow behavior of particles inside a rotating drum, though a majority of them used spherical or nearly spherical particles. However, an investigation of non-spherical particles is very important because natural or crushed particles usually have an irregular shape, non-spherical particles with certain shapes have many usages, and more importantly, particle shape greatly affects the flow behaviour. Therefore, this work aims to study of the effect of particle shape on flow dynamics. To do so, the cylinder was chosen as the particle shape for two main reasons. Firstly, there are lots of industrial applications for cylindrical particles, such as capsules, candies, biomass pellets, etc. Secondly, to be able to identify the effect of particle shape on flow behaviour, the shape should be readily identified, and distinct from a sphere. The cylinder is one the most basic curvilinear geometric shapes, and many other curvilinear shapes, especially those with a high aspect ratio, can be approximated as a cylinder. Many nonintrusive techniques have been used to study granular flow in a rotating drum, including optical methods and radioactive techniques. Since particulate matter is principally opaque, optical methods are essentially limited to surface flow. Conversely, radioactive x techniques are well suited for providing information about inside the bed in such systems, because gamma rays can penetrate relatively easily through materials. Radioactive particle tracking (RPT) is one suitable measurement techniques for this investigation. However, RPT is limited to tracking the position of a single tracer. As cylindrical particles are used for this study, it is essential to employ a measurement technique capable of simultaneously tracking the position and orientation of a cylindrical particle. The first part of this thesis introduces a multiple radioactive particle tracking technique (MRPT) that can determine the trajectory of two free or restricted moving tracers in a system (attached to the same particle). The accuracy (<5 mm) and precision (<5 mm) of the proposed technique is evaluated by tracking two stationary tracers and two moving tracers. The results confirm the reliability and validity of the MRPT technique when the two tracers have the same isotope and the distance between them is not too small (>2 cm). The tracking of two sticking tracers at the two ends of a cylindrical particle in a rotating drum is also considered to illustrate the potential of this characterization method. In the second part of this thesis, we compare the flow behavior of cylindrical (2 cm long and 6 mm in diameter) and spherical (6 mm in diameter) particles using the multiple radioactive particle tracking (MRPT) technique to capture the positions and orientations of cylindrical particles simultaneously. We analyzed two important components of the transverse flow dynamic, namely, the boundary between the active and passive layers and the velocity profile on the free surface, in the rolling regime (7.5-15 RPM for cylindrical particles under the conditions of this study). For the first time, we measured the orientation of cylindrical particles inside the bed. The results confirm the existence of a preferred spatial orientation (about a 25-degree deviation from the dynamic repose angle) for cylindrical particles in the active layer. The results show that the spatial orientation of cylindrical particles within the bed are insensitive to the rotational speed of the drum. Therefore, for cylindrical particles at all rotational speeds, bed dilation was constant (about 25%), while the bed dilation of spherical particles is about 1%. Velocity profiles on the free surface for cylindrical particles show an asymmetrical shape (the peak of velocity profile is located at 70% of the free surface length) while that of spherical particles is symmetrical; (the peak of velocity profile is located at 50% of the free surface length). For the first time, two general models are proposed to calculate the velocity profiles for xi cylindrical particles on the free surface and the effective particle sizes in the active and passive layers. Finally, the third part of this thesis presents a further analysis of the data obtained by the MRPT and RPT techniques in the previous part. We obtain the equations of motion for cylindrical and spherical particles in the active and passive layers, as well as equations of the yield and turning point curve lines. Using numerical simulation, the effect of advection on the quality of mixing for both cylindrical and spherical particles is also considered to illustrate the potential use of these equations of motion.


identifier: David, A. (2015). Localisation optimale de produits dans un centre de distribution  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Dans le monde des marges de profit, les compagnies cherche des alternatives pour se démarquer de la compétition. Depuis quelques années, une attention particulière a été portée sur l'optimisation de la chaîne d'approvisionnement, créant ainsi une demande sans précédent sur les compétences logistiques. Afin de surmonter le défi, les centres de distribution ont commencé à revoir leur approche face au positionnement et aux stratégies d'entreposage. Suite à l'acquisition de T&B par ABB, le centre de distribution de Bromont doit intégrer les produits qui appartiennent à la famille ABB. Avec la nouvelle relation d'affaires entre ABB et T&B, le centre de distribution de Bromont doit accueillir plusieurs nouveaux produits d'ABB tout en respectant les capacités existantes du centre. Le stock disponible dans la zone ABB n'a pas fait l'objet d'une analyse de gestion des localisations très élaborée, lors de l'intégration de cette gamme de produits le 4 novembre 2013. L'attribution a été aléatoire et donc les UGS n'ont pas été placées selon le taux de rotation. Cette configuration a un impact sur la productivité des caristes, car il y a un gaspillage de temps rattaché aux mouvements. Les deux principaux objectifs du mémoire sont de résoudre la problématique de positionnement dans un centre de distribution et de concevoir un programme linéaire qui servira d'aide à la prise de décision.  ABSTRACT: In the world of profit margins, companies are looking for any alternative to get an edge over competitors. Within the past few years, a lot of that attention has been directed straight at the management of the supply chain, creating unprecedented demands on logistics competencies. In an attempt to meet this challenge, distribution centers have become concerned with proper slotting and storage techniques. Thomas & Betts wanted an automated solution that would reconfigure and correctly slot the new products from the merger with ABB in order to improve picking productivity. The approach undertaken was to develop a linear program in Excel, which would suggest the best configurations in order to house all the different stock-keeping units (SKUs). Utilizing the concept of “golden zone” picking, that places high demand SKUs at the height between the picker's waist and shoulders, a file is created in order to prioritize the reassignment of the SKUs to their optimal locations. Results showed a 14,7% increase in picking productivity within the first eight months.


identifier: Arnold, E. (2015). Surexpression de la glucose-6-phosphate déshydrogénase pour l'étude du métabolisme primaire de cellules de mammifères en mode cuvée  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les cellules de mammifères sont l'hôte privilégié pour la production de protéines recombinantes d'intérêt thérapeutique, et parmi elles, les cellules CHO qui dominent le marché et les cellules HEK qui connaissent un regain d'intérêt. Même si elles présentent l'avantage de performer les modifications post-traductionnelles appropriées pour la compatibilité des molécules avec l'être humain, les coûts de production demeurent important devant la demande croissante. De plus, ces cellules présentent un métabolisme lent et n'atteignent pas des densités cellulaires aussi élevées comparé aux microorganismes. De nombreuses améliorations ont été obtenues grâce à l'optimisation des milieux de culture et stratégies de culture, l'amélioration des lignées, et plus récemment l'essor des études sur le métabolisme cellulaire. L'identification des limitations du métabolisme a permis d'orienter les stratégies d'ingénierie des lignées, notamment pour limiter l'effet des sous-produits toxiques de culture ou l'activation des voies apoptotiques. Récemment, des études ont montré un changement de métabolisme entre la phase de croissance et la phase de production. En phase exponentielle, la majorité des flux sont dirigés vers la glycolyse alors que le pic de production correspond à une activité majoritaire des branches oxydatives comme le cycle des acides tricarboxyliques et la voie des pentoses phosphates. C'est dans ce cadre que s'inscrit le présent projet qui consiste en la redirection des flux métaboliques vers la voie des pentoses phosphates. En accord avec les prévisions d'un modèle métabolique disponible dans notre laboratoire, il a été supposé qu'une augmentation de l'activité de la glucose-6-phosphate déshydrogénase, première enzyme de la voie, permettrait de rediriger les flux vers la voie des pentoses phosphates et de soulager la charge métabolique imposée par la production de protéines recombinantes. Cette enzyme a donc été transfectée de manière transitoire dans des cellules HEK293, une lignée parentale et une lignée dérivée exprimant la pyruvate carboxylase, et des cellules CHO afin d'observer son effet sur la production de protéines et la croissance cellulaire en mode cuvée. Les résultats en termes de croissance cellulaire, viabilité, production de protéines et concentrations de métabolites intracellulaires comme extracellulaires ont révélé la robustesse du métabolisme de ces cellules face à la perturbation étudiée. En revanche, les signatures métaboliques des deux lignées cellulaires HEK293 sont très caractéristiques, en raison des changements importants apportés par la pyruvate carboxylase.  ABSTRACT: Mammalian cells are the prefered host for the production of recombinant proteins of therapeutic interest. Among them, CHO cells are prevailing on the market and HEK are raising interest. Even if they possess the advantage of performing appropriate post-translational modifications for human compatibility of those molecules, production costs are still inhibitory regarding the growing demand. Moreover, mammalian cells possess a slow metabolism and can't reach high cell densities compared to what is observed in microorganisms. Numerous significant improvements have been made thanks to media and culture strategies optimization, cell lines improvement, and more recently the advances in cell metabolism studies. The identification of metabolism bottlenecks allowed to guide cell line engineering, especially to avoid toxic effects of metabolic by-products or activation of pro-apoptotic signals. Recently, studies have shown a metabolic switch between growth phase and production phase. In exponential phase, most of the flux are routed towards glycolysis. However, pic protein production was associated with an elevated oxidative metabolism in the TCA cycle and the pentose phosphate pathway. Given that, the present work aims at redirecting metabolic fluxes through the pentose phosphate pathway. According to a predictive metabolic model developped in our laboratory, we hypothetized that an increase in glucose-6-phosphate dehydrogenase – the first enzyme in the pathway- activity could reroute the fluxes and aleviate the metabolic burden imposed by recombinant protein secretion. This enzyme was thus transient transfected in two HEK293 cell lines, the parental cells and the derived cell line stably expressing pyruvate carboxylase, and CHO cells in order to assess its effect on protein production and cell growth in batch mode. The results, in terms of growth, viability, recombinant protein production, and the concentrations of intra- and extracellular metabolites demonstrated the robustness of these cells regarding the pertubation studied in this work. However, metabolic signatures of the two HEK293 cell lines is really characteristic of the changes brought by the expression of pyruvate carboxylase in one of the cell lines.


identifier: Abdollahifakhr, H. (2015). Power-Efficient Hardware Architecture for Computing Split-Radix FFT on Highly Sparse Spectrum  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le problème du transfert des signaaux du domaine temporel au domaine fréquentiel d'une manière efficace, lorsque le contenu du spectre de fréquences a une faible densité, est le sujet de cette thèse. La technique bien connue de la transformée de Fourier rapide (FFT) est l'algorithme de traitement de signal privilégié pour observer le contenu fréquentiel des signaux entrants à des émetteurs-récepteurs de télécommunication, tels que la radio cognitive, ou la radio définie par logiciel qu‟on utilise habituellement pour l‟analyse du spectre dans une bande de fréquences. Cela peut représenter un lourd fardeau de calcul sur des processeurs lorsque la FFT ordinaire est mise en oeuvre, ce qui peut impliquer une consommation d'énergie considérable. L'alimentation en énergie est une ressource limitée dans les appareils mobiles et, par conséquent, cette ressource peut être critique pour des dispositifs de télécommunications mobiles. Dans le but de développer un processeur économe en énergie pour les applications de transformation temps-fréquence, un algorithme de transformée de Fourier plus efficace, en termes du nombre de multiplications et d'additions complexes, est sélectionné. En effet, la Split-Radix Fast Fourier Transform (SRFFT) offre une performance meilleure que la FFT classique en termes de réduction du nombre de multiplications complexes nécessaires et elle peut donc conduire à une consommation d'énergie réduite. En appliquent le concept d'élagage des calculs inutiles, c'est-à-dire des multiplications complexes avec entrées ou sorties à zéro, tout au long de l'algorithme, on peut réduire la consommation d'énergie.Ainsi, une architecture matérielle énergétiquement efficace est développée pour le calcul de la SRFFT. Cette architecture est basée sur l'élagage des calculs inutiles. En fait, pour tirer parti du potentiel de la SRFFT, une nouvelle architecture d'un processeur de SRFFT configurable est d'abord conçue, puis l'architecture est développée afin d'éliminer les calculs inutiles. Cela se fait par l'utilisation appropriée d'une matrice d'élagage.  ABSTRACT: The problem of transferring a time domain signal into the frequency domain in an efficient manner, when the frequency contents are sparsely distributed, is the research topic covered in this thesis. The well-known Fast Fourier Transform (FFT) is the most common signal processing algorithm for observing the frequency contents of incoming signals in telecommunication transceivers. It is notably used in cognitive or software defined radio which usually demands for monitoring the spectrum in a wide frequency band. This may imply a heavy computation burden on processors when the ordinary FFT algorithm is implemented, and hence yield considerable power consumption. Power and energy supply is a limited resource in mobile devices and therefore, efficient execution of the Fourier transform has turned out to be critical for mobile telecommunication devices.With the purpose of developing a power-efficient processor for time-frequency transformation, the most computationally efficient Fourier transform algorithm is selected among the existing Fourier transform algorithms upon studying them in terms of required arithmetic operations, i.e. complex multiplications and additions. Indeed, the Split-Radix Fast Fourier Transform (SRFFT) offers a performance that is better than conventional FFT in terms of reduced number of complex multiplications and hence, can reduce power consumption.Appling the concept of pruning of the unnecessary computations, i.e. complex multiplications with either zero inputs or outputs, throughout the whole algorithm may reduce the power consumption even further.


identifier: Monroy Licht, I. M. (2015). Arc Routing Problems for Road Network Maintenance  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse présente deux problèmes rencontrés dans l'entretien des réseaux routiers, soit la surveillance des réseaux routiers pour la détection de verglas sur la chaussée et la reprogrammation des itinéraires pour les activités de déneigement et d'épandage de sel. Nous représentons ces problèmes par des modèles de tournées sur les arcs. La dépendance aux moments et la nature dynamique sont des caractéristiques propres de ces problèmes, par conséquence le cas de surveillance des réseaux routiers est modélisé comme un problème de postier rural avec fenêtres-horaires (RPPTW), tandis que le cas de la reprogrammation utilise des modèles obtenus à partir des formulations de problèmes de tournées sur les arcs avec capacité. Dans le cas du problème de surveillance, une patrouille vérifie l'état des chemins et des autoroutes, elle doit principalement détecter le verglas sur la chaussée dans le but d'assurer de bonnes conditions aux chauffeurs et aux piétons. Étant donné un réseau routier et des prévisions météo, le problème consiste à créer une tournée qui permette de détecter opportunément le verglas sur les rues et les routes. L'objectif poursuivi consiste à minimiser le coût de cette opération. En premier, on présente trois formulations basées sur la programmation linéaire en nombres entiers pour le problème de surveillance des réseaux qui dépend du moment et deux méthodes de résolution: un algorithme de coupes et un algorithme heuristique appelé adaptive large neighborhood search (ALNS). La méthode exacte inclut des inéquations valides tirées du problème du voyageur de commerce avec fenêtres-horaires et aussi du problème de voyageur du commerce avec contraintes de précédence. La méthode heuristique considère deux phases: en premier, on trouve une solution initiale et après dans la deuxième phase, l'algorithme essaie d'améliorer la solution initiale en utilisant sept heuristiques de destruction et deux heuristiques de réparation choisies au hasard. La performance des heuristiques est évaluée pendant les itérations. Une meilleure performance correspond à une plus grande probabilité de choisir une heuristique. Plusieurs tests ont été faits sur deux ensembles d'exemplaires de problèmes. Les résultats obtenus montrent que l'algorithme de coupes est capable de résoudre des réseaux avec 104 arêtes requises et des fenêtres-horaires structurées par tranches horaires ; l'algorithme peut aussi résoudre des réseaux avec 45 arêtes requises et des fenêtres-horaires structurées pour chaque arête requise. Pour l'algorithme ALNS, différentes versions de l'algorithme sont comparées. Les résultats montrent que cette méthode est efficace parce qu'elle est capable de résoudre à l'optimalité 224 des 232 exemplaires et de réduire le temps de calcul significativement pour les exemplaires les plus difficiles. La dernière partie de la thèse introduit le problème de la reprogrammation de tournées sur les arcs avec capacité (RCARP), lequel permet de modéliser la reprogrammation des itinéraires après une panne d'un véhicule lors de la phase d'exécution d'un plan initial des activités de déneigement ou d'épandage de sel. Le planificateur doit alors modifier le plan initial rapidement et reprogrammer les véhicules qui restent pour finir les activités. Dans ce cas, l'objectif poursuivi consiste à minimiser le coût d'opération et le coût de perturbation. La distance couverte par les véhicules correspond au coût d'opération, cependant une nouvelle métrique est développée pour mesurer le coût de perturbation. Les coûts considérés sont des objectifs en conflit. On analyse quatre politiques à la phase de re-routage en utilisant des formulations de programmation linéaire en nombres entiers. On propose une solution heuristique comme méthode pour résoudre le RCARP quand les coûts d'opération et de perturbation sont minimisés en même temps et quand une réponse rapide est nécessaire. La méthode consiste à fixer une partie de l'itinéraire initial et après à modifier seulement les itinéraires des véhicules les plus proches de la zone de l'interruption de la tournée du véhicule défaillant. La méthode a été testée sur des exemplaires obtenus d'un réseau réel. Nos tests indiquent que la méthode peut résoudre rapidement des exemplaires avec 88 arêtes requises et 10 véhicules actifs après la panne d'un véhicule. En conclusion, la principale contribution de cette thèse est de présenter des modèles de tournées sur les arcs et de proposer des méthodes de résolution d'optimisation qui incluent la dépendance aux temps et l'aspect dynamique. On propose des modèles et des méthodes pour résoudre le RPPTW, et on présente des résultats pour ce problème. On introduit pour la première fois le RCARP. Trois articles correspondant aux trois principaux chapitres ont été acceptés ou soumis à des revues avec comité de Lecture: “The rural postman problem with time windows” accepté dans Networks, “ALNS for the rural postman problem with time windows” soumis à Networks, and “The rescheduling capacitated arc routing problem” soumis à International Transactions in Operational Research.  ABSTRACT: This dissertation addresses two problems related to road network maintenance: the road network monitoring of black-ice and the rescheduling of itineraries for snow plowing and salt spreading operations. These problems can naturally be represented using arc routing models. Timing-sensitive and dynamic nature are inherent characteristics of these problems, therefore the road network monitoring is modeled as a rural postman problem with time windows (RPPTW) and in the rescheduling case, models based on capacitated arc routing formulations are suggested for the rerouting phase. The detection of black-ice on the roads is carried out by a patrol to ensure safety conditions for drivers and pedestrians. Specific meteorological conditions cause black-ice on the roads; therefore the patrol must design a route covering part of the network in order to timely detect the black-ice according to weather forecasts. We look for minimum-cost solutions that satisfy the timing constraints. At first, three formulations based on mixed integer linear programming are presented for the timing-sensitive road network monitoring and two solution approaches are proposed: a cutting plane algorithm and an adaptive large neighborhood search (ALNS) algorithm. The exact method includes valid inequalities from the traveling salesman problem (TSP) with time windows and from the precedence constrained TSP. The heuristic method consists of two phases: an initial solution is obtained, and then in the second phase the ALNS method tries to improve the initial solution using seven removal and two insertion heuristics. The performance of the heuristics is evaluated during the iterations, and therefore the heuristics are selected depending on their performance (with higher probability for the better ones). Several tests are done on two sets of instances. The computational experiments performed show that the cutting plane algorithm is able to solve instances with up to 104 required edges and with time windows structured by time slots, and problems with up to 45 required edges and time windows structured by each required edge. For the ALNS algorithm, several versions of the algorithm are compared. The results show that this approach is efficient, solving to optimality 224 of 232 instances and significantly reducing the computational time on the hardest instances. The last part of the dissertation introduces the rescheduling capacitated arc routing problem (RCARP), which models the rescheduling of itineraries after a vehicle failure happens in the execution of an initial plan of snow plowing or salt spreading operations. A dispatcher must quickly adjust the remaining vehicles and modify the initial plan in order to complete the operations. In this case we look for solutions that minimize operational and disruption costs. The traveled distance represents the operational cost, and a new metric is discussed as disruption cost. The concerned objectives are in conflict. Four policies are analyzed in the rerouting phase using mixed integer linear programming formulations. A heuristic solution is developed to solve the RCARP when operational and disruption costs are minimized simultaneously and a quick response is needed. The idea is to fix part of the initial itinerary and only modify the itinerary of vehicles closer to the failure zone. The method is tested on a set of instances generated from a real network. Our tests indicate that the method can solve instances with up to 88 required edges and 10 active vehicles after the vehicle breakdown. In short the main contribution of this dissertation is to present arc routing models and optimization solution techniques that consider timing-sensitive and dynamic aspects. Formulations and solution methods with computational results are given for the RPPTW, and the RCARP is studied for the first time here. Three articles corresponding to the main three chapters have been accepted or submitted to peer review journals: “The rural postman problem with time windows” accepted in Networks, “ALNS for the rural postman problem with time windows” submitted to Networks, and “The rescheduling capacitated arc routing problem” submitted to International Transactions in Operational Research.


identifier: Bensalah, H. (2015). Invariance positive et observateur intervalles appliqués aux systèmes linéaires à retards sous contraintes  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse porte sur l'étude du problème de la commande avec contraintes des systèmes linéaires continus à retards. Deux approches dans la littérature se sont données à développer des méthodes adéquates pour examiner la stabilité et contribuer à des procédures et outils de stabilisation. La première, considère l'effet de la saturation, tandis que la deuxième approche, basée sur la théorie d'invariance positive, repose principalement sur la conception d'une loi de contrôle non saturante ayant un comportement linéaire dans le domaine des contraintes. Des résultats concernant l'application du concept d'invariance positive à la stabilisation des systèmes à retards soumis à des contraintes ont été développés, mais restent restrictifs, de fait qu'ils sont indépendants du retard, un paramètre essentiel du système. On développe alors, dans la première partie de cette thèse des conditions nécessaires et suffisantes dépendantes du retard afin de garantir l'invariance positive de domaine des contraintes par rapport aux trajectoires de systèmes autonomes à retard. Ce résultat repose sur la transformation de premier ordre, basée sur la formule de Newton-Leibniz, de système original à retard discret, en un système à retard distribué. Une fonction de Lyapunov-Razumikhin associée au système à retard distribué garantissant la stabilité asymptotique dépendante de retard de système original est proposée. L'objectif principal visé dans la deuxième partie de cette thèse est d'appliquer le résultat du concept d'invariance positive dépendante du retard au problème de la commande sous contraintes, dissymétriques ainsi que symétriques, des systèmes à retards. Ainsi des conditions permettant la synthèse d'un régulateur par retour d'état stabilisant le système en boucle fermée en présence des contraintes, sont données. Ces conditions permettent de formuler un algorithme basé sur des schémas de Programmation Non Linéaire (NLP), ayant pour objectif la détermination du régulateur stabilisant le système en boucle fermée avec une borne maximale du retard. En effet la loi de retour d'état calculée assure, d'une part, la stabilité asymptotique de système sans retard, et d'autre part, la maintenir pour une valeur d'une borne maximale de retard, tout en respectant les contraintes : c'est la loi de commande sous contraint robuste vis à vis le retard. Les résultats obtenus sont intéressants et plus généraux que ceux développés dans la littérature. La troisième partie de cette thèse montre, pour la première fois à notre connaissance, que les observateurs intervalles, en appliquant le concept d'invariance positive, peuvent apporter des réponses intéressantes au problème de la commande sous contraintes des systèmes linéaires à retards, variable dans le temps.  ABSTRACT: In this thesis, the stabilization problem of linear continuous-time delay system with constrainted control is studied. There are two main approaches in the literature dealing with the problem of performance and stability of dynamical constrained control systems. The first one considers the effect of saturation while guaranteeing asymptotic stability. The second one, so-called positive invariance approach, is based on the design of the control law which works inside a region of linear behavior where saturations do not occur. Most of the works related to positive invariance concept have been developed for time delay systems with constrained control, but remain so restrictive, given that they are independent of delay, which is an essential parameter of the system. In the first part of this thesis, the necessary and sufficient algebraic conditions with delay dependence allowing to obtain the largest positively invariant set of delay system are given. The results can include information on the size of delay, and therefore, can be delay dependence positively invariant conditions. Based on the Newton-Leibniz formula, these results use a transformation form an original system with discrete delay to a system with distributed delay. A Lyapunov-Razumikhin function for system with distributed delay, in order to guarantee the asymptotic stability of the original system is proposed. The second part of this thesis, is to apply the concept of the delay dependent positive invariance to the robust regulator problem of continuous time delay system with symmetric and non-symmetric constraints. In fact the synthesis of state-feedback controllers is solved based on delay-dependent positively invariant set of system in closed-loop. We first obtain the necessary and sufficient algebraic conditions with delay dependence allowing to obtain the largest positively invariant set of delay systems, then we convert the constrained control problem into a Non-Linear Programming (NLP) problem with delay the objective function to be maximized. Indeed the control is firstly chosen in order to stabilize the closed loop system, free of delay, then to guarantee the asymptotic stability of the closed loop system with delay-dependence. To the best of our knowledge, it is the first time, that the output stabilization problem for time-varying delay systems with constrained control based on the interval observer technique by using the dependent delay positive invariance concept is studied. Hence, first both matrices observer gain, the lower and the upper, are obtained by solving a Sylvester's matrix equation. Second, the interval observer is developed and guaranteed the positivity of the upper and lower observations errors.


identifier: Pierre Doray, F. (2015). Analyse de variations de performance par comparaison de traces d'exécution  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La performance est un requis très important pour bon nombre d'applications. Malheureusement, plusieurs facteurs affectent cette performance : contention pour l'accès à une ressource, mauvais algorithmes de synchronisation, attente de données en provenance du disque, etc. En raison de la taille du code source de certaines applications et des multiples niveaux d'abstraction entre le code applicatif et le matériel, plusieurs développeurs ne soupçonnent pas l'existence de toutes ces sources de latence. Le traçage est une technique qui consiste à enregistrer des événements qui surviennent dans un système informatique. Un grand nombre de problèmes de performance peuvent être diagnostiqués à partir de l'information contenue dans une trace d'exécution. En raison de leur faible surcoût, les traceurs modernes peuvent être activés en continu sur des systèmes en production pour capturer des problèmes survenant rarement. Des outils spécialisés facilitent la navigation à travers le grand nombre d'événements contenus une trace d'exécution. Malheureusement, même avec ces outils, il peut être difficile de juger si le comportement observé est celui attendu sans une connaissance exhaustive du système analysé. L'objectif de ce travail de recherche est de vérifier si le diagnostic de variations de performance peut être facilité par un algorithme qui identifie automatiquement les différences entre deux groupes de traces d'exécution. L'algorithme doit mettre en évidence les latences présentes dans un groupe d'exécutions anormalement longues, mais pas dans un groupe d'exécutions normales. Un développeur peut alors tenter d'éliminer ces latences. Pour ce faire, nous introduisons d'abord deux nouveaux événements pour le traceur LTTng. L'événement cpu_stack rapporte périodiquement la pile d'appels des fils d'exécution utilisant le processeur. L'événement syscall_stack rapporte la pile d'appels des longs appels système. Ces deux événements nous permettent de déterminer si des latences présentes dans des traces d'exécution différentes ont été causées par le même code applicatif. Le traçage de l'événement syscall_stack a un surcoût moindre que celui du traçage traditionnel des appels système. Nous proposons aussi une nouvelle structure de données appelée « enhanced calling context tree » (ECCT) pour représenter les latences affectant le temps de complétion d'une tâche. Ces latences peuvent être au niveau du matériel, du système d'exploitation ou du code applicatif. En présence d'interactions entre plusieurs fils d'exécution, nous utilisons un algorithme de calcul du chemin critique pour inclure dans le ECCT les latences introduites par chacun de ces fils. Nous utilisons les ECCTs à la fois pour stocker des métriques de performance de façon compacte et comme entrée de notre algorithme de comparaison. Ensuite, nous présentons une interface graphique permettant de visualiser les différences entre des groupes d'exécution. Les groupes à comparer sont définis par l'utilisateur à l'aide de filtres. Les différences sont montrées à l'aide d'un outil de visualisation appelé « flame graph » différentiels ainsi que d'histogrammes. Les vues sont rafraîchies rapidement lorsque les filtres sont modifiés grâce à un algorithme de « map-reduce ». L'efficacité de notre solution pour détecter, diagnostiquer et corriger des problèmes de performance majeurs est démontrée grâce à quatre études de cas menées sur des logiciels libres et d'entreprises. Nous mesurons aussi le surcoût du traçage des événements requis par notre analyse sur différents types d'applications et concluons qu'il est toujours entre 0.2% et 9%. Enfin, nous démontrons que notre solution développée pour Linux peut être adaptée pour fonctionner sur les systèmes d'exploitation Windows et Mac OS X.  ABSTRACT: Performance is a critical requirement for many applications. Unfortunately, many factors can affect performance: resource contention, bad synchronization algorithms, slow disk operations, etc. Because of the large codebase of some applications and because of the multiple levels of abstraction between application code and hardware, many developers are not aware of the existence of these sources of latency. Tracing is a technique that consists of recording events that occur in a system. Many performance problems can be diagnosed using the information contained in an execution trace. Popular tracers achieve low overhead, which allows them to be enabled on production systems to capture bugs that occur infrequently. Specialized tools allow efficient navigation in the large number of events contained in execution traces. However, even with these tools, it is hard to determine whether the observed behavior is normal without a deep knowledge of the analyzed system. The objective of this research project is to verify whether we can facilitate the diagnosis of performance variations with an algorithm that automatically identifies differences between two groups of execution traces. The algorithm must highlight delays that appear in a group of slow executions, but not in a group of normal executions. A developer can then try to eliminate these delays. First, we introduce two new events for the LTTng tracer. The cpu_stack event periodically reports the call stack of threads running on the CPU. The syscall_stack reports the call stack of long system calls. Call stacks allow us to determine whether delays that appear in different execution traces are caused by the same application code. The overhead of tracing the syscall_stack event is less than that of traditional tracing of system calls. Second, we propose a new data structure called enhanced calling context tree (ECCT) to describe delays that affect the completion time of a task execution. These delays can be at the hardware, operating system or application levels. When a task execution involves interactions between several threads, a critical path algorithm is used to include delays caused by each of them in the ECCT. We use ECCTs to store performance metrics compactly and as an input to our comparison algorithm. Third, we present a GUI that shows differences between groups of executions. The user defines two groups of executions to compare using filters. Differences are shown using a visualization tool called differential flame graph along with histograms. A map-reduce algorithm is used to quickly refresh the views when filters are modified. We present four case studies, carried on open-source and enterprise software, to demonstrate that our solution helps to detect, diagnose and fix major performance problems. We measure the overhead of tracing the events required by our analysis on different kinds of applications and conclude that it is always between 0.2% and 9%. Finally, we show that our solution, developed for Linux, can be adapted for the Windows and Mac OS X operating systems.


identifier: Najafi Chaloupli, N. (2015). Development of Polylactide (PLA) and PLA Nanocomposite Foams in Injection Molding for Automotive Applications  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les matériaux plastiques sont largement utilisés dans l'automobile, car ils permettent la fabrication de véhicules qui consomment moins d'énergie. Actuellement, l'industrie automobile cherche des solutions de rechange à base de matières bio-ressourcées et renouvelables comme alternative aux plastiques issus du pétrole et ce, afin de réduire la dépendance aux combustibles fossiles. Parmi les polymères issus de sources renouvelables, le polylactide (PLA) a suscité un vif intérêt en tant que polymère vert très prometteur. Aussi, l'utilisation de ce polymère dans les industries durables estelle en plein essor. Par ailleurs, les automobiles économiques en carburant sont aujourd'hui très demandées en raison de l'inquiétude croissante sur les questions environnementales. La consommation de carburant peut être améliorée en réduisant le poids de l'automobile et en utilisant un matériau léger. Une méthode potentielle pour atteindre cet objectif est l'utilisation de la technologie des mousses. La mousse est un matériau où une phase gazeuse est encapsulée par une phase solide. Le processus de moussage consiste en l'incorporation de gaz, la formation d'une solution uniforme polymère-gaz, la nucléation cellulaire, la croissance cellulaire et enfin la stabilisation des cellules. La technologie de moussage permet de fabriquer des pièces allégées avec des propriétés supérieures en comparaison avec leurs homologues solides.  Cependant, le moussage du PLA s'est révélé être une tâche difficile principalement en raison des faibles propriétés rhéologiques, d'une fenêtre de mise en forme restreinte et d'une cinétique de cristallisation lente. Le but ultime de ce projet est de réduire de 30 % le poids des nanocomposites de polylactide (PLA)-argile par la fabrication de pièces en mousse moulées par injection. Afin d'utiliser un équipement de mise en forme standard, un agent de soufflage chimique (ASC) a été employé dans le cadre de cette étude. La technique de moulage par injection a été employée, car c'est le procédé de fabrication le plus largement utilisé dans l'industrie et qui peut produire des pièces de formes complexes. Cependant, ce procédé est plus difficile que d'autres procédés de moussage car il possède de nombreux paramètres supplémentaires à contrôler. Dans la première partie de ce projet, nous avons illustré la façon dont la ramification à longues chaînes (RLC) et la structure moléculaire influencent la rhéologie à l'état fondu, la cristallisation et le comportement moussant en discontinu du PLA.  ABSTRACT: Plastic materials are extensively used in automotive structures since they make cars more energy efficient. Recently, the automotive industry is searching for bio-based and renewable alternatives to petroleum-based plastics to reduce the dependence on fossil fuels. Among polymers originating from renewable sources, polylactide (PLA) has attracted significant interest. The use of this polymer in durable industries is promising. Fuel-efficient automobiles are nowadays demanded due to the increasing concerns about environmental and fuel issues. The automobile fuel efficiency can be improved by using a lightweight material and, thereby, reducing the automobile weight. A potential method to achieve this objective is the use of the foaming technology. Foam is a material where a gas phase is encapsulated by a solid phase. Foaming technology helps to manufacture lightweight parts with superior properties in comparison with their solid counterparts. The basic mechanisms of foaming process normally consists of gas implementation, formation of uniform polymer-gas solution, cell nucleation, cell growth and, finally, cell stabilization. PLA foaming has, however, proved to be difficult mainly due to poor rheological properties, small processing window, and slow crystallization kinetics. The ultimate purpose of this work is to reduce by 30 % the weight of polylactide (PLA)-clay based nanocomposites by manufacturing injectionmolded foamed parts. To use standard processing equipment, a chemical blowing agent (CBA) was employed. The injection molding technique was utilized in this project because it is the most widely used fabrication process in industry that can produce complex shaped articles. This process, however, is more challenging than other foaming processes since it deals with many additional controlling parameters. In the first part of this project, we illustrated how long chain branching (LCB) and molecular structure impact the melt rheology, crystallization and batch foaming behavior of PLA. To this end, LCB-PLAs were prepared in the presence of a multifunctional chain extender (CE) using two different processing strategies. In the first strategy, the dried PLA was directly mixed in the molten state with various quantities of CE (the formation of LCB structure). To further examine the impact of CE and molecular topology, a LCB-PLA was also prepared using a second approach, strategy S2. In this approach, a highly branched PLA was first prepared and then mixed with the neat PLA at a weight ratio of 50:50 (the introduction of LCB structure).


identifier: Ibrahim, M. (2015). Using Constraint Satisfaction Techniques and Variational Methods for Probabilistic Reasoning  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse présente un certain nombre de contributions à la recherche pour la création de systèmes efficaces de raisonnement probabiliste sur les modèles graphiques de problèmes issus d'une variété d'applications scientifiques et d'ingénierie. Ce thème touche plusieurs sous-disciplines de l'intelligence artificielle. Généralement, la plupart de ces problèmes ont des modèles graphiques expressifs qui se traduisent par de grands réseaux impliquant déterminisme et des cycles, ce qui représente souvent un goulot d'étranglement pour tout système d'inférence probabiliste et affaiblit son exactitude ainsi que son évolutivité. Conceptuellement, notre recherche confirme les hypothèses suivantes. D'abord, les techniques de satisfaction de contraintes et méthodes variationnelles peuvent être exploitées pour obtenir des algorithmes précis et évolutifs pour l'inférence probabiliste en présence de cycles et de déterminisme. Deuxièmement, certaines parties intrinsèques de la structure du modèle graphique peuvent se révéler bénéfiques pour l'inférence probabiliste sur les grands modèles graphiques, au lieu de poser un défi important pour elle. Troisièmement, le re-paramétrage du modèle graphique permet d'ajouter à sa structure des caractéristiques puissantes qu'on peut utiliser pour améliorer l'inférence probabiliste. La première contribution majeure de cette thèse est la formulation d'une nouvelle approche de passage de messages (message-passing) pour inférer dans un graphe de facteurs étendu qui combine des techniques de satisfaction de contraintes et des méthodes  variationnelles. Contrairement au message-passing standard, il formule sa structure sous forme d'étapes de maximisation de l'espérance variationnelle. Ainsi, on a de nouvelles règles de mise à jour des marginaux qui augmentent une borne inférieure à chaque mise à jour de manière à éviter le dépassement d'un point fixe. De plus, lors de l'étape d'espérance, nous mettons à profit les structures locales dans le graphe de facteurs en utilisant la cohérence d'arc généralisée pour effectuer une approximation de champ moyen variationnel. La deuxième contribution majeure est la formulation d'une stratégie en deux étapes qui utilise le déterminisme présent dans la structure du modèle graphique pour améliorer l'évolutivité du problème d'inférence probabiliste. Dans cette stratégie, nous prenons en compte le fait que si le modèle sous-jacent implique des contraintes inviolables en plus des préférences, alors c'est potentiellement un gaspillage d'allouer de la mémoire pour toutes les contraintes à l'avance lors de l'exécution de l'inférence. Pour éviter cela, nous commençons par la relaxation des préférences et effectuons l'inférence uniquement avec les contraintes inviolables. Cela permet d'éviter les calculs inutiles impliquant les préférences et de réduire la taille effective du réseau graphique. Enfin, nous développons une nouvelle famille d'algorithmes d'inférence par le passage de messages dans un graphe de facteurs étendus, paramétrées par un facteur de lissage (smoothing parameter). Cette famille permet d'identifier les épines dorsales (backbones) d'une grappe qui contient des solutions potentiellement optimales. Ces épines dorsales ne sont pas seulement des parties des solutions optimales, mais elles peuvent également être exploitées pour intensifier l'inférence MAP en les fixant de manière itérative afin de réduire les parties complexes jusqu'à ce que le réseau se réduise à un seul qui peut être résolu avec précision en utilisant une méthode MAP d'inférence classique. Nous décrivons ensuite des variantes paresseuses de cette famille d'algorithmes. Expérimentalement, une évaluation empirique approfondie utilisant des applications du monde réel démontre la précision, la convergence et l'évolutivité de l'ensemble de nos algorithmes et stratégies par rapport aux algorithmes d'inférence existants de l'état de l'art.  ABSTRACT: This thesis presents a number of research contributions pertaining to the theme of creating efficient probabilistic reasoning systems based on graphical models of real-world problems from relational domains. These models arise in a variety of scientific and engineering applications. Thus, the theme impacts several sub-disciplines of Artificial Intelligence. Commonly, most of these problems have expressive graphical models that translate into large probabilistic networks involving determinism and cycles. Such graphical models frequently represent a bottleneck for any probabilistic inference system and weaken its accuracy and scalability.  Conceptually, our research here hypothesizes and confirms that: First, constraint satisfaction techniques and variational methods can be exploited to yield accurate and scalable algorithms for probabilistic inference in the presence of cycles and determinism. Second, some intrinsic parts of the structure of the graphical model can turn out to be beneficial to probabilistic inference on large networks, instead of posing a significant challenge to it. Third, the proper re-parameterization of the graphical model can provide its structure with characteristics that we can use to improve probabilistic inference.     The first major contribution of this thesis is the formulation of a novel message-passing approach to inference in an extended factor graph that combines constraint satisfaction techniques with variational methods. In contrast to standard message-passing, it formulates the Message-Passing structure as steps of variational expectation maximization. Thus it has new marginal update rules that increase a lower bound at each marginal update in a way that avoids overshooting a fixed point. Moreover, in its expectation step, we leverage the local structures in the factor graph by using generalized arc consistency to perform a variational mean-field approximation.  The second major contribution is the formulation of a novel two-stage strategy that uses the determinism present in the graphical model's structure to improve the scalability of probabilistic inference. In this strategy, we take into account the fact that if the underlying model involves mandatory constraints as well as preferences then it is potentially wasteful to allocate memory for all constraints in advance when performing inference. To avoid this, we start by relaxing preferences and performing inference with hard constraints only. This helps avoid irrelevant computations involving preferences, and reduces the effective size of the graphical network. Finally, we develop a novel family of message-passing algorithms for inference in an extended factor graph, parameterized by a smoothing parameter. This family allows one to find the ”backbones” of a cluster that involves potentially optimal solutions. The cluster's backbones are not only portions of the optimal solutions, but they also can be exploited for scaling MAP inference by iteratively fixing them to reduce the complex parts until the network is simplified into one that can be solved accurately using any conventional MAP inference method. We then describe lazy variants of this family of algorithms. One limiting case of our approach corresponds to lazy survey propagation, which in itself is novel method which can yield state of the art performance. We provide a thorough empirical evaluation using real-world applications. Our experiments demonstrate improvements to the accuracy, convergence and scalability of all our proposed algorithms and strategies over existing state-of-the-art inference algorithms.


identifier: Berthaut, F. (2015). Étude de l'impact du chevauchement sur les performances de projets complexes d'ingénierie  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le chevauchement d'activités au sein d'un projet est une des techniques les plus répandues pour accélérer l'exécution d'un projet. Le chevauchement d'activités consiste à autoriser des activités qui traditionnellement s'exécutent de façon séquentielle à se chevaucher de sorte que les activités en aval débutent avant la fin des activités en amont en se basant sur des informations partielles. Plusieurs stratégies d'exécution de projets appliquées dans la pratique, telles que l'ingénierie simultanée dans les projets de développement de produits et la construction en « fast-tracking », reposent sur ce principe. Cette technique a montré ses preuves dans sa capacité à réduire la durée de projets, avec cependant plusieurs inconvénients. Le chevauchement peut causer des retouches du travail exécuté à partir d'information préliminaire et mener à des itérations. Ces retouches sont difficilement quantifiables et représentent une charge de travail et des coûts supplémentaires qui peuvent réduire ou annuler les bénéfices du chevauchement. Cela soulève la question de quand et de combien les activités devraient être chevauchées dans les projets industriels. Dans la pratique, les gestionnaires de projets ne possèdent pas d'outils d'aide à la décision pour répondre à cette question. Cette thèse s'intéresse ainsi au problème d'ordonnancement de projet avec chevauchement d'activités dans un contexte déterministe. Ce problème cherche à déterminer conjointement le meilleur calendrier en termes de coût ou de durée de projet et les décisions de chevauchement, c'est-à-dire quelles activités chevaucher et dans quelle mesure. Nous nous intéressons aux projets complexes caractérisés par des contraintes de disponibilité de ressources, des réseaux complexes d'activités, un nombre important d'activités et de couples d'activités qui peuvent se chevaucher. Les objectifs de cette thèse sont de modéliser, quantifier et analyser, dans le cas de projets complexes d'ingénierie, l'impact des décisions de chevauchement activités sur les performances de projet (durée et coût), en considérant un modèle réaliste de chevauchement. Cette thèse vise aussi à apporter une meilleure compréhension de ces choix dans les projets complexes et proposer des stratégies générales applicables en pratique. Les travaux réalisés dans le cadre de cette thèse sont articulés autour de trois articles publiés ou soumis à des revues scientifiques. Le premier article intitulé « Time-cost trade-offs in resource-constrained project scheduling problems with overlapping modes » (publié en 2014 dans International Journal of Project Organisation and Management) introduit un modèle de chevauchement d'activités basé sur des modes de chevauchement reliés aux jalons internes des activités et permet de modéliser de façon réaliste et flexible la relation entre durée de chevauchement et durée de retouche. Ce modèle est inséré dans une modélisation du problème de compromis durée-coût de l'ordonnancement de projets complexes avec contraintes de ressource et chevauchement d'activités sous la forme d'un programme linéaire en nombres entiers. Les durées de communication/coordination et de retouches sont considérées. Le problème est résolu avec une méthode exacte pour un exemple virtuel de projet. Les résultats illustrent les interactions entre le coût de projet, la durée du projet et les contraintes de ressource ainsi que leur influence sur le temps de résolution. Le second article intitulé « A Path Relinking-based Scatter Search for the Resource-Constrained Project Scheduling Problem » (soumis dans European Journal of Operational Research) introduit une métaheuristique dans la famille des recherches dispersées (« scatter search ») pour résoudre le problème standard RCPSP (« Resource-Constrained Project Scheduling Problem ») sans chevauchement. Cet algorithme utilise la méthode FBI (« Forward-Backward Improvement »), inverse la direction d'ordonnancement à chaque itération et est basé sur deux mécanismes novateurs. Premièrement, un PR (« Path Relinking ») bidirectionnel avec un nouveau mouvement opérant sur les distances entre activités est utilisé comme méthode de combinaison des solutions. Deuxièmement, une méthode d'amélioration est utilisée pour améliorer la qualité et la diversité des solutions de l'ensemble de référence. Une méthode avancée de paramétrage de l'algorithme utilisant une méthode de recherche locale a été développée pour déterminer les meilleures valeurs de ses paramètres. L'article montre que cette métaheuristique est capable de fournir des solutions de grande qualité avec des temps de calcul acceptables et appartient aux meilleures méthodes approchées existantes dans la littérature pour la résolution des instances virtuelles de projet de PSPLIB. Enfin, le troisième article intitulé « Influence of the project characteristics on the efficiency of activity overlapping » (soumis dans Computers & Operations Research) a pour principales contributions de quantifier et d'analyser l'influence de huit caractéristiques de projets sur l'efficacité du chevauchement pour diminuer la durée de projet. La réduction de la durée de projet est obtenue en résolvant le problème RCPSP avec et sans chevauchement. Deux méthodes de résolution sont développées pour résoudre le problème avec chevauchement. Une nouvelle méthode exacte basée sur un programme linéaire en nombres entiers avec modes de chevauchement et des techniques de propagation de contraintes est développée. La seconde méthode est une métaheuristique dérivée de la métaheuristique proposée dans le second article. Ces méthodes sont appliquées à un bassin de 3888 instances virtuelles de projets de 30 à 120 activités avec chevauchement. La première observation est que le chevauchement n'apporte aucune réduction dans près de 25% des cas. Une analyse statistique permet de distinguer l'influence de caractéristiques de projets sur l'efficacité du chevauchement et de montrer que la proportion de couples d'activités chevauchables qui sont sur le chemin critique et la sévérité des contraintes de ressources ont le plus d'influence sur la réduction de la durée de projet. Également, les résultats indiquent que certains principes généraux se dégagent pour les décisions de chevauchement. La meilleure stratégie devrait consister à chevaucher peu de couples d'activités chevauchables et de les chevaucher beaucoup. De plus, même si les activités sur le chemin critique sont plus susceptibles d'être chevauchées, les décisions de chevauchement dans un contexte de contraintes de ressource ne doivent pas uniquement être basées sur la criticalité des activités. Enfin, ces observations sont confrontées aux stratégies pratiques de chevauchement proposées dans la littérature. Ces travaux visent à contribuer au développement d'outils pour assister les gestionnaires de projet dans leurs décisions relatives au chevauchement d'activités. Les principales contributions scientifiques de ces travaux sont les suivantes. Premièrement, nous proposons une modélisation plus réaliste du problème d'ordonnancement de projet avec chevauchement d'activités. Deuxièmement, une nouvelle métaheuristique de type recherche dispersée      (« scatter search ») performante pour le problème classique RCPSP est développée. Troisièmement, nous introduisons des méthodes de résolution exacte et approchée performantes pour le problème d'ordonnancement de projet avec chevauchement d'activités. La capacité des méthodes exactes à résoudre des problèmes d'ordonnancement pour des projets de grande taille avec contraintes de ressource étant limitée, cette thèse présente en effet à notre connaissance la première méthode approchée de type métaheuristique pour ce problème. Quatrièmement, ces travaux quantifient et analysent l'effet de huit caractéristiques de projet sur l'efficacité du chevauchement d'activités pour diminuer la durée d'un projet. Enfin, nous proposons des principes généraux pour aide les praticiens à prendre les meilleures décisions de chevauchement d'activités.  ABSTRACT: Activity overlapping is one of the most employed strategies used to accelerate project execution. It consists in relaxing the sequential execution of dependent activities by allowing downstream activities to begin before receiving all the final information required from upstream activities. Several practical strategies, such as concurrent engineering and fast-tracking construction, are based on the concept of overlapping. Overlapping has been demonstrated to be powerful for reducing project makespan, but it has some drawbacks. Overlapping often causes additional reworks in downstream activities, as well as iterations of interdependent activities, that are difficult to quantify and represent additional workloads and costs. Such reworks may outweigh the benefices of overlapping in terms of cost and time. This raises the question of when and to which extent overlapping should be applied. In practice, project teams determine overlapping strategies on an ad hoc basis without always considering rework and interaction between activities. This thesis considers the project scheduling problem with activity overlapping in a deterministic context. This problem aims to jointly determine the best schedule in terms of cost and duration and the best overlapping decisions, namely which activities should be overlapped and to which extent. We focus on the complex projects characterized by constraints on resource availability, a complex network of activities, a large number of activities and a large number of couples of overlappable activities. The main objectives of this thesis are to model, quantify and analyze the impact of overlapping decisions on the project performances (cost and duration) in the case of complex industrial projects, by considering a realistic model of the overlapping process. This thesis also aims at providing a better understanding of these decisions in complex projects and at guiding planners in improving existing practices. The research undertaken in this thesis is divided into three papers published or submitted to international peer-reviewed scientific journals. The first paper titled « Time-cost trade-offs in resource-constrained project scheduling problems with overlapping modes » (published in 2014 in International Journal of Project Organisation and Management) proposes an overlapping process model based on overlapping modes related to activities' internal milestones that is a realistic and flexible model of the relation between the amount of overlap and the amount of rework. This overlapping model is then enclosed in a model for the time-cost trade-offs in resource-constrained project scheduling problem with activity overlapping. The model is formulated as a linear integer programming model. The times and costs for communication/coordination and reworks are considered. The problem is solved with an exact method for an illustrative project instance. The results highlight the interactions between the project total cost, its makespan and the severity of the resource constraints and also show their influence on the computational time. The second paper titled « A Path Relinking-based Scatter Search for the Resource-Constrained Project Scheduling Problem » (submitted to European Journal of Operational Research) introduces a metaheuristic based on scatter search for solving the standard RCPSP (Resource-Constrained Project Scheduling Problem) without overlapping. This algorithm involves FBI (Forward-Backward Improvement), reversing the project network at each iteration and two new mechanisms. First, a bidirectional PR (path relinking method) with a new move is used as method for combining solutions. Second, a new improvement procedure is proposed in the reference set update method for enhancing the quality and the diversity of the reference set. An advanced parameter tuning method based on local search is employed. The paper shows that the proposed scatter search produces high-quality solutions in reasonable computational time and is among the best performing heuristic procedures in the literature for solving the instance of the PSPLIB benchmark.Finally, the main contributions of the third paper titled « Influence of the project characteristics on the efficiency of activity overlapping » (submitted to Computers & Operations Research) are to quantify and analyze the influence of eight project characteristics on the efficiency of activity overlapping for reducing project makespan. The reduction of the project makespan is obtained by solving the project scheduling problem with and without overlapping. Two methods have been developed for solving the problem with overlapping. First, we introduce a 0-1 integer linear programming model with overlapping modes and constraint propagation techniques as preprocessing. Second, we propose a metaheuristic based on the scatter search algorithm described in the second paper. These methods are applied on a set of 3888 project instances with overlapping composed of 30 to 120 activities. The first finding is that no reduction of the makespan is observed in about 25% of the projects of the benchmark. A statistical analysis is conducted to measure the effect of eight project parameters on the makespan gain. It reveals that the proportion of couples of overlappable activities on the critical path and the scarcity of the resource constraints have the highest influence on the makespan gain. In addition, general rules of thumb are derived from the analysis of the results. The best overlapping decisions should consist in overlapping only few couples of overlappable activities and to overlap them with a large degree of overlapping. Even though the activities on the critical path are more likely to be overlapped, overlapping decision should not rely solely on the criticality of the activities. The results are also compared to practical strategies for applying overlapping proposed in the literature. The main scientific contributions of these works with respect to the scientific literature and from the perspective of assisting project managers to choose the most appropriate overlapping decisions can be summarized as follows. First, we propose a more realistic model of the project scheduling problem with activity overlapping. Second, a new competitive metaheuristic based on scatter search has been developed. Third, we propose competitive exact and heuristic methods for solving the project scheduling problem with activity overlapping. Indeed, as the capacity of exact methods for solving project scheduling problem for large scale projects with resource constraints is limited, the metaheuristic developed in this thesis for this kind of problem is the first in the literature to our knowledge. Fourth, this thesis proposes to quantify and analyze the influence of eight project characteristics on the efficiency of activity overlapping for reducing project makespan. Finally, the findings of this work provide a better understanding of the overlapping decisions and should guide planners for the decisions on activity overlapping.


identifier: Tanji, J. (2015). Effets des couverts de glace sur la réponse dynamique des barrages-poids  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Ce travail a pour principal objectif l'étude de la sensibilité du comportement dynamique du système glace-barrage-réservoir vis-à-vis des hypothèses de modélisation du couvert de glace. Plusieurs aspects sont explorés à partir de modèles d'éléments finis 2D et 3D, à savoir: l'effet de la présence du couvert de glace, de l'état de fissuration du couvert de glace et l'influence des interactions glace-structure. Pour ce faire, deux ensembles de modèles d'éléments finis de barrages représentatifs des barrage-poids du Québec, ont été élaborés. Les modèles 2D, inspirés des travaux de Bouaanani (2002), ont permis d'investiguer sur l'influence du choix des hypothèses concernant l'état de fissuration du couvert de glace et des interactions glace-barrage, sur les spectres de planchers et les contraintes internes au niveau de la structure du barrage issus des analyses sismiques dans le domaine du temps.  ABSTRACT: The main goal of this work is to investigate the sensitivity of the dynamical behavior of the system ice-dam-reservoir to modeling assumptions of the ice cover. Several aspects are explored on 2D and 3D finite element models, namely the effect of the cracking state of the ice cover, the influence of the ice-structure interactions. To achieve this, two sets of 2D and 3D finite element models of typical gravity dams in Quebec are developed. The set of 2D models, based on the research works of Bouaanani (2002), permitted to investigate the influence of the assumptions choice about the ice cover cracking state and the ice-dam interactions, on the floor response spectra and the internal stress of the dam structure, extracted from the seismic analysis in the time domain.


identifier: Koupouli, N. J. F. (2015). Comportement mécanique des remblais en pâte cimentés en compression et en cisaillement et étude du frottement aux interfaces remblai-remblai et remblai-roche  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le remblai en pâte cimenté (RPC) une fois acheminé sous terre peut jouer le rôle de support secondaire des terrains encaissants. Grâce à cette fonction de contrôle de terrain, il est possible d'améliorer la récupération des piliers secondaires minéralisés tout en maintenant un bon niveau de sécurité pour les travailleurs et les engins. Le RPC peut également servir de plancher de travail ou de circulation d'engins lourds. Cependant, après sa mise en place dans les chantiers ouverts souterrains, les propriétés mécaniques du RPC évoluent au cours du temps. Cela peut être dû à des facteurs internes liés à la nature et à la quantité des composants du remblai. D'autre part, des facteurs externes comme le massif rocheux encaissant agissent sur le RPC. Toutes ces modifications du comportement mécanique du RPC, si elles ne sont pas connues et mesurées,peuvent causer sa rupture, par exemple lors de l'ouverture d'une face du remblai. Les conséquences pourraient être la dilution du minerai, des dégâts matériels (pertes économiques,des blessures et/ou voire des pertes en vies humaines.  ABSTRACT: The cemented paste backfill once routed underground can act as secondary support of mine stopes. This improves the recovery of secondary mineralized pillars while maintaining a good level of safety for workers and equipment. The cemented paste backfill (CPB) can also serve as working platform or circulation of heavy machines. However, after their incorporation in underground, the mechanical properties of the CPB evolve over time. This may be due to internal factors related to the nature and quantity of the CPB components. Furthermore, external factors also act as the bedrock in which the CPB is placed. All these changes in the mechanical behavior of the cemented paste backfill can create failure inside the CPB or at its interface. This can cause economic and human life loss.


identifier: Goyette, A. (2015). Système d'imagerie optique diffuse hyperspectral intégré à une aiguille de biopsie neurochirurgicale afin d'en améliorer la sécurité  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Lorsqu'un patient a une tumeur au cerveau, la première étape consiste souvent à évaluer le grade de celle-ci grâce à des méthodes d'imagerie conventionnelles, soit l'imagerie par résonance magnétique ou le CT-scan. Un des traitements standards qui suit le diagnostic est la résection de la tumeur par chirurgie à crâne ouvert, suivi de chimiothérapie et/ou radiothérapie. Toutefois, il est parfois nécessaire, avant de se rendre à un tel extrême, de procéder à une biopsie du cerveau. Les principales indications pour une biopsie sont les lésions profondes, les tumeurs traitées seulement par radiothérapie et chimiothérapie, la présence d'une infection ou bien une santé trop fragile du patient. Cette procédure minimalement invasive a pour objectif de récolter un échantillon tumoral afin d'obtenir davantage d'informations pathologiques et d'émettre un diagnostic plus précis que ce qui est possible d'obtenir avec les techniques d'imagerie conventionnelles. Comme toute procédure chirurgicale, les biopsies aux cerveaux ont leurs limitations et leurs risques. Un des plus grands risques liés à la biopsie est l'hémorragie causée par la rupture d'un vaisseau sanguin lors de la prise d'échantillon. Dans le cadre de cette maîtrise, un système d'imagerie optique a été intégré sur une aiguille de biopsie commerciale. Ce système exploite la tomographie par optique diffuse qui est utilisée avec une nouvelle configuration. Cette configuration a été préalablement testée avec une sonde tomographique qui comporte 12 paires de fibres, une d'illumination et une de détection, sur 360°. Au bout de ces fibres se trouvent des prismes permettant l'illumination à 90° par rapport à la longueur de la sonde. Il a été démontré dans un article publié dans Optics Letters que ce design optique était apte à détecter une ou deux inclusions absorbantes de 1mm de diamètre dans un fantôme biologique composé d'Intralipide 1% comme milieu diffus et de tiges de carbone comme absorbeurs. Suite à cela, un protocole de fabrication a été élaboré afin de pouvoir intégrer ce design optique à une aiguille de biopsie commerciale. La fabrication a ensuite été faite à l'École Polytechnique, en collaboration avec Optech. Le prototype intégré comporte 18 fibres, 9 comme sources et 9 comme détecteurs, sur un arc de cercle de 200°, évitant ainsi de bloquer la fenêtre de biopsie. À la place de prismes, il utilise un seul micromiroir unique pour l'illumination et la détection perpendiculaires à l'aiguille. Le prototype a subi des tests de propagation de la lumière afin de valider l'homogénéité de l'illumination et la détection en plus de mettre en évidence certaines failles du design. Finalement, les tests de détection d'inclusions absorbantes ont été réitérés avec le prototype intégré. Il a été démontré que ce dernier, malgré que les fibres ne couvrent pas une circonférence de 360°, est apte à repérer les mêmes configurations d'inclusions que la sonde tomographique. Malgré les nombreuses étapes encore nécessaires avant l'intégration du prototype intégré en salle d'opération, l'étendue des résultats de ce mémoire montre un avenir prometteur pour cette technologie.  ABSTRACT: When a patient has a brain tumor, the first step is assessing its grade through conventional imaging methods such as MRI or CT scan. Standard treatments after diagnosis is tumor resection using open cranium surgery, followed by chemotherapy and/or radiotherapy. However, before going to such extremes, it is sometimes necessary to perform a brain needle biopsy (BNB). The main indications for BNB are deep-seated lesions, tumors treatable only with radiotherapy and chemotherapy, infections and/or patients with poor health. The goal of this minimally invasive procedure is to collect one or more tumor samples in order to obtain further pathological information and a more accurate diagnosis than what is available with conventional imaging techniques. As any surgical procedure, BNB has its risks and limitations. One of the main risks is hemorrhage due to the rupture of a blood vessel during sampling. In the scope of this Master's project, an optical imaging system has been integrated on a commercial biopsy needle. This system utilizes diffuse optical tomography, using a new configuration. This configuration has initially been tested with a tomographic probe which comprises 12 pairs of fibers, an illumination and a detection fiber for each pair, evenly spaced around 360 °. Prisms for side illumination and detection are placed at the end of each pairs. An article published in Optics Letters has shown that the optical design was able to detect one or two absorbing inclusions of 1mm diameter in a biological phantom. This phantom was made of 1% intralipid as a diffuse medium and carbon rods as absorbers. Afterwards, a manufacturing protocol was developed in order to integrate this optical design on a commercial biopsy needle. The prototype was then manufactured at École Polytechnique in collaboration with Optech. The integrated prototype has 18 fibers, 9 as sources and 9 as detectors, on an arc of 200°. This configuration avoids occluding the sampling window of the biopsy needle. Instead of prisms, it has one single micro-mirror for side illumination. The prototype has undergone light propagation tests to validate the homogeneity of the illumination and detection and to highlight potential design limitations. Finally, the tests with the biological phantom and absorbing inclusions were replicated with the integrated prototype. It has been shown that the latter, despite the fact that the fibers do not cover 360°, is able to identify the same configurations of inclusions as the tomographic probe. Although many steps are still needed before the prototype is used in the operating room, the results shown in this thesis shows a promising future for this technology.


identifier: Venne, F. (2015). Towards Near-Infrared Photosensitization of Tungsten Trioxide Nanostructured Films by Upconverting Nanoparticles  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les semiconducteurs à base d'oxydes de métaux nanostructurés sont des matériaux dont l'étude est largement répandue dans le domaine des applications solaires, tel que le démontre l'engouement pour les cellules solaires de type Grätzel. L'oxyde de tungstène (WO3) est un matériau qui a des propriétés électrochromiques et possède une énergie de bande ≈ 2.5 eV,ce qui lui a permis d'être étudié dans des applications reliées à la conversion (photocatalyse ou photoélectrochimie) de l'énergie solaire. Cependant, la valeur de l'énergie de bande du WO3 est telle qu'il est transparent pour une grande partie du spectre solaire, ce qui limite l'efficacité de conversion de puissance des dispositifs à base de WO3. Les matériaux à conversion ascendante de photons sont des matériaux qui peuvent absorber plusieurs photons de faible énergie et émettre un photon de haute énergie. Notamment, les nanoparticules à conversion ascendante de photons sont grandement étudiées pour leur capacité à tranformer deux ou plusieurs photons infrarouge en un photon visible, dans des domaines tels que les applications biomédicales et de l'énergie solaire. En ce qui a trait aux applications en énergie solaire, une partie importante du spectre solaire est composée d'infrarouge, donc de photons qui ont une énergie trop faible pour générer une paire électrontrou dans un semiconducteur à large bande interdite, tel que le WO3. Les nanoparticules à conversion ascendante de photons sont donc d'intéressantes candidates pour transformer la lumière infrarouge en lumière qui puisse être utilisée par des semiconducteur à grande énergie de bande, tels que les oxydes de métaux. Ce projet de maîtrise consiste à ajouter des nanoparticules à conversion ascendante de photons (NaGdF4:Er3+, Yb3+) à un oxyde de métal nanostructuré, à savoir le WO3. De cette façon,l'objectif est d'augmenter l'efficacité de conversion de puissance du WO3 lorsqu'exposé à la lumière solaire. L'intégration des deux nanomatériaux est motivée par le contact intime qui peut s'établir entre eux, dans le but de potentiellement optimiser leur interaction. L'article 1 inclus dans le mémoire concerne des noparticules de NaGdF4:Er3+, Yb3+ mélangées à du WO3 en phase liquide pour le dépôt de couches minces nanocomposites sur un substrat composé d'une paire d'électrodes faite de verre conducteur (ITO). Après avoir optimisé les paramètres de préparation et de dépôt des couches minces, ces dernières ont été systématiquement caractérisées. La morphologie a été étudiée à l'aide de la microscopie à force atomique,la structure à l'aide de la diffraction de rayons-X, les propriétés de photoluminescence à l'aide d'un microscope hyperspectral à fluorescence et les propriétés électriques par des mesures de courant en fonction du temps sous irradiation infrarouge.  ABSTRACT: Nanostructured metal oxides semiconductors are widely used in solar energy related applications, such as in dye-sensitized solar cells. Tungsten trioxide (WO3) is an electrochromic material, extensively investigated in solar energy conversion (e.g. photoelectrochemistry) and conservation (e.g. electrochromism). However, WO3, because of its wide bandgap (≈ 2.5 eV), is transparent to an important portion of the solar spectrum and can effectively absorb light only up to ca. 500 nm, which limits the power conversion efficiency of devices based thereon. Upconverting materials can absorb several low-energy photons to emit one high-energy photon. In particular, upconverting nanoparticles are widely studied in biomedical and solar energy applications, as they can transform two or several infrared photons in a visible photon. As the Sun contains important NIR and IR portion, UCNPs are interesting candidates to transform NIR or IR light into visible light to be absorbed by wide bandgap semiconductor, such as metal oxides. The work presented in this master's thesis consists in embedding NaGdF4:Er3+, Yb3+ UCNPs into a nanostructured WO3 matrix. The objective is to increase the power conversion efficiency of WO3 after solar light harvesting. The integration of two materials with nanostructured nature has the potential to lead to a good synergy between them. We include an article in this master's thesis. In this article, we report on the mixing of NaGdF4:Er3+, Yb3+ UCNPs withWO3 in solution and on the deposition of the two-component solution on ITO-patterned electrodes. After engineering the fabrication and deposition of the thin nanocomposite films, they were systematically studied. Morphology was studied by atomic force microscopy, structure by X-ray diffraction, photoluminescence by fluorescence hyperspectral microscopy, and charge carrier transport under NIR irradiation by currenttime measurements. Notably, we observed an increase in the value of the current with respect to the dark current when UCNP/WO3 thin films were exposed to 980 nm continuous laser irradiation. This increase in the value of the current is tentatively attributed to the absorption of the NIR light by the UCNPs, which is upconverted into visible light to be harvested by the WO3, eventually generating a photocurrent.


identifier: Gauthier, J.-P. (2015). Calcul de l'amortissement ajouté par l'eau sur une aube de turbine hydroélectrique  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Ce mémoire concerne le transfert d'énergie cinétique et potentielle d'une structure immergée vers le fluide qui s'écoule autour, ou encore l'amortissement ajouté par le fluide. L'objectif est de quantifier ce paramètre pour une aube de turbine hydroélectrique dans l'optique d'arriver à mieux estimer la durée de vie en fatigue de telles machines. Pour y arriver, une méthodologie basée sur des analyses modales et des simulations numériques des écoulements de fluide a été développée. Un mouvement oscillatoire de la structure est imposé lors de la simulation de l'écoulement, ce qui évite d'avoir recours à de coûteux calculs où le solide et le fluide sont couplés de manière bidirectionnelle. La méthode a été validée à l'aide d'un cas test fourni par ANDRITZ HYDRO, puis appliquée avec succès sur une aube de turbine à hélice appartenant à Hydro-Québec.  ABSTRACT: This master's thesis considers kinetic and potential energy transfer from a submerged structure to the surrounding fluid flow, here referred as fluid added damping. The goal is to determine the value of this parameter for a hydroelectric turbine blade with the idea of getting better fatigue life estimates for such machines. In order to achieve this, a methodology based on modal analysis and numerical simulations of fluid flows has been developed. Prescribing an oscillatory motion of the structure in the flow simulation avoids the need for computationally intensive two-way fluid-structure coupling. This method has been validated using a test case from ANDRITZ HYDRO, then successfully applied to the blade of a propeller turbine owned by Hydro-Quebec.