identifier: Fu, S. (2010). Efficient Learning of Markov Blanket and Markov Blanket Classifier  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La sélection de variables est un problème de première importance dans le domaine de l'apprentissage machine et le forage de données. Pour une tâche de classification, un jalon important du développement de stratégies sélection de variables a été atteint par Koller et Shamai [1]. Sur la base des travaux de Pearl dans le domaine des réseaux bayésiens (RB) [2], ils ont démontré que la couverture de Markov (CM) d'une variable nominale représente le sous-ensemble optimal pour prédire sa valeur (classe). Différents algorithmes ont été développés pour d'induire la CM d'une variable cible à partir de données, sans pour autant nécessiter l'induction du RB qui inclue toutes les variables potentielles depuis 1996, mais ils affichent tous des problèmes de performance, soit au plan de la complexité calculatoire, soit au plan de la reconnaissance. La première contribution de cette thèse est le développement d'un nouvel algorithme pour cette tâche. L'algorithme IPC-MB [9-11] permet d'induire la CM d'une variable avec une performance qui combine les meilleures performances en terme de complexité calculatoire et de reconnaissance. IPC-MB effectue une recherche itérative des parents et enfants du noeud cible en minimisant le nombre de variables conditionnnelles des tests d'indépendance. Nous prouvons que l'algorithme est théoriquement correct et comparons sa performance avec les algorithmes les mieux connus, IAMB [12], PCMB [13] et PC [14]. Des expériences de simulations en utilisant des données générées de réseaux bayésiens connus, à savoir un réseau de petite envergure, Asia, contenant huit noeuds; deux réseaus de moyenne envergure, Alarm et PolyAlarm de 37 noeuds, et deux réseaux de plus grande envergure, Hailfinder contenant 56 noeuds et Test152 contenant 152 noeuds. Les résultats démontrent qu'avec un nombre comparable d'observations, (1) IPC-MB obtient une reconnaissance nettement plus élevée que IAMB, jusqu'à 80% de réduction de distance (par rapport à un résultat parfait), (2) IPC-MB a une reconnaissance légèrement supérieure que PCMB et PC, et (3) IPC-MB nécessite jusqu'à 98% moins de tests conditionnels que PC et 95% de moins que PCMB (le nombre de tests conditionnels représente la mesure de complexité calculatoire ici). La seconde contribution de la thèse est un algorithme pour induire la topologie du RB constitué des variables de la CM. Lorsqu'une CM d'une variable cible forme un RB, ce réseau est alors considéré comme un classificateur, nommé une Couverture de Markov de Classification (MBC). L'algorithme a été nommé IPC-MBC sur la base du premier algorithme, IPC-MB. À l'instar de IPC-MB, l'algorithme IPC-MBC effectue une série de recherches locales pour éliminer les faux-négatifs, incluant les noeuds et les arcs. Cependant, sa complexité est supérieure et requiert des ressources calculatoires plus importantes que IPC-MB. Nous prouvons que IPC-MB est théoriquement et effectuons des études empiriques pour comparer sa performance calculatoire et de reconnaissance par rapport à PC seul et PC combiné à IPC-MB (c.-à-d. l'induction de la structure du RB avec l'algorithme PC seul et avec PC appliqué sur le résultat de IPC-MB). Les mêmes données que pour les expériences de simulation de IPC-MB sont utilisées. Les résultats démontrent que IPC-MBC combiné à IPC-MB et que PC combiné à IPC-MB sont tous deux plus efficaces que PC seul en termes de temps de complexité calculatoires, fournissant jusqu'à 95% de réduction du nombre de tests conditionnels, sans pour autant avoir d'impact au plan du taux de reconnaissance.  ABSTRACT: Feature selection is a fundamental topic in data mining and machine learning. It addresses the issue of dimension reduction by removing non-relevant, or less relevant attributes in model building. For the task of classification, a major milestone for feature selection was achieved by Koller and Sahami [1]. Building upon the work of Pearl on Bayesian Networks (BN) [2], they proved that a Markov blanket (MB) of a variable is the optimal feature subset for class prediction. Deriving the MB of a class variable given a BN is a trivial problem. However, learning the structure of a BN from data is known to be NP hard. For large number of variables, learning the BN is impractical, not only because of the computational complexity, but also because of the data size requirement that is one of the curses of high dimensionality feature spaces. Hence, simpler topologies are often assumed, such as the Naive Bayes approach (NB) [5, 6], which is probably the best known one due its computational simplicity, requiring no structure learning, and also its surprising effectiveness in many applications despite its unrealistic assumptions. One of its extension, Tree-Augmented Naïve Bayes (TAN) [7] is shown to have a better performance than NB, by allowing limited additional dependencies among the features. However, because they make strong assumptions, these approaches may be flawed in general. By further relaxing the restriction on the dependencies, a BN is expected to show better performance in term of classification accuracy than NB and TAN [8]. The question is whether we can derive a MB without learning the full BN topology for the classification task. Let us refer to a MB for classification as a Markov Blanket Classifier, MBC. The MBC is expected to perform as well as the whole Bayesian network as a classifier, though it is generally much smaller in size than the whole network. This thesis addresses the problem of deriving the MBC effectively and efficiently from limited data. The goal is to outperform the simpler NB and TAN approaches that rely on potentially invalid assumptions, yet to allow MBC learning with limited data and low computational complexity. Our first contribution is to propose one novel algorithm to filter out non-relevant attributes of a MBC. From our review, it is known that there are at least nine existing published works on the learning of Markov blanket since 1996. However, there is no satisfactory tradeoff between correctness, data requirement and time efficiency. To address this tradeoff, we propose the IPC-MB algorithm [9-11]. IPC-MB performs an iterative search of the parents and children given a node of interest. We prove that the algorithm is sound in theory, and we compare it with the state of the art in MB learning, IAMB [12], PCMB [13] and PC [14]. Experiments are conducted using samples generated from known Bayesian networks, including small one like Asia with eight nodes, medium ones like Alarm and PolyAlarm (one polytree version of Alarm) with 37 nodes, and large ones like Hailfinder (56 nodes) and Test152 (152 nodes). The results demonstrate that, given the same amount of observations, (1) IPC-MB achieves much higher accuracy than IAMB, up to 80% reduction in distance (from the perfect result), (2) IPC-MB has slightly higher accuracy than PCMB and PC, (3) IPC-MB may require up to 98% fewer conditional independence (CI) tests than PC, and 95% fewer than PCMB. Given the output of IPC-MB, conventional structure learning algorithms can be applied to recover MBC without any modification since the feature selection procedure is transparent to them. In fact, the output of IPC-MB can be viewed as the output of general feature selection, and be employed further by all kinds of classifier. This algorithm was implemented by the author while working at SPSS and shipped with the software Clementine 12 in 2007. The second contribution is to extend IPC-MB to induce the MBC directly without having to depend on external structure learning algorithm, and the proposed algorithm is named IPC-MBC (or IPC-BNC in one of our early publication) [15]. Similar to IPC-MB, IPC-MBC conducts a series of local searches to filter out false negatives, including nodes and arcs. However, it is more complex and requires greater computing resource than IPC-MB. IPC-MBC is also proved sound in theory. In our empirical studies, we compare the accuracy and time cost between IPC-MBC, PC and IPC-MB plus PC (i.e. structure learning by PC on the features output by IPC-MB), with the same data as used in the study of IPC-MB. It is observed that both IPC-MBC and IPC-MB plus PC are much more time efficient than PC, with up to 95% saving of CI tests, but with no loss of accuracy. This reflects the advantage of local search and feature selection respectively.


identifier: Abdelali, M. (2010). Résolution du problème inverse en élastographie ultrasonore par une méthode variationnelle  [Thèse de doctorat, École Polytechnique de Montréal].

type:
Mémoire ou thèse
NonPeerReviewed

abstract: RÉSUMÉ: La rupture des plaques d'athérosclérose est associée à la majorité des infarctus du myocarde et des syndromes coronariens aigus. La distribution des contraintes mécaniques dans ces plaques d'athérosclérose peut fournir des indices importants sur leur vulnérabilité d'un point de vue mécanique. La mesure de ces contraintes n'est pas encore possible directement in vivo. Toutefois, les images médicales, telles que les images échographiques, peuvent aider à estimer ces contraintes. Les approches d'inversion des images échographiques permettent d'obtenir des indications sur les contraintes mécaniques en milieu clinique. Les approches utilisées actuellement dans ce domaine vasculaire admettent des limites.  En effet, les approches classiques d'inversion sont souvent basées sur des hypothèses restrictives sur la contrainte elle-même, telles que le fait qu'elle soit constante dans la région d'intérêt. Les autres approches se font généralement dans un processus itératif. Elles sont basées sur le recalage de données mesurables à partir des images à d'autres données calculées par un modèle d'éléments finis simulant la lésion analysée. Ce modèle est la limite de ces méthodes de recalage à leur application en milieu clinique : il nécessite des connaissances a priori sur chaque plaque analysée.  Ce besoin de connaissance a priori complique la transférabilité de ces méthodes de recalage à l'analyse de différents types de plaques. De plus, la formulation des approches d'inversion classiques des images échographiques ne permet généralement pas d'intégrer les effets des caractéristiques mécaniques non linéaires de la lésion artérielle. Dans ce projet, nous démontrons que les effets non linéaires sont importants pour l'analyse de la stabilité mécanique des plaques d'athérosclérose. Ensuite, nous développons une approche d'inversion des images échographiques qui ne nécessite pas d'hypothèses restrictives sur les contraintes, qui est transférable à différents types de plaques artérielles et qui peut s'étendre à des analyses mécaniques non linéaires. Enfin, nous validons  notre approche pour plusieurs types de plaques et pour différents types d'images échographiques synthétisées pour des modalités d'imagerie intravasculaire et extravasculaires.  ABSTRACT: Atherosclerotic plaque rupture is responsible for the majority of myocardial infarctions and acute coronary syndromes. In vivo assessment of the mechanical stress could provide valuable plaque rupture indices for the diagnosis and prognosis of those clinical outcomes. As for now, it is not yet possible to determine the internal distribution of stresses directly in vivo. However, medical imaging modality such as ultrasound imaging could help achieving this goal through processing of image sequences providing the strains of the tissue and its elasticity parameters distribution. The strains and elasticity parameters of an elastic tissue can help to estimate its mechanical stresses. A number of ultrasound images processing methods have been proposed for that purpose. However, often their underlying hypotheses prevent them from being clinically applicable to clinical data. For example, a method may assume a constant stress distribution within a region where therefore the strain map can be interpreted also as an elastic parameter map in this region. Other methods would use an iterative process to best match the measurable data obtained from images to the ones predicted from a finite element model (FEM) of the tissue. But, their implementation generally requires a priori knowledge on each analyzed plaque, as for example its boundary conditions that are not often identifiable from clinical images. This obviously limits the transferability of those methods to the analysis of a broad range of clinical data. Such model-based inversions of ultrasound images do not currently consider non-linear rheological laws of arteries, an important concern for stress analysis. In this project, we first re-examine assessment of plaque vulnerability and demonstrate that non linear mechanical effects are important for the analysis of the stability of the atherosclerotic plaques. We then develop an inversion approach to process ultrasound images, based on the optimization of functionals that minimize the mechanical energy of elastic tissues. Then, we evaluate our approach on several plaque models and several ultrasound imaging modalities: radio-frequency ultrasound data, envelope or B-Mode data, intra-vascular and extra-vascular ones. Due to its generality, this approach can be applied to a broad range of plaque geometry and can be extended to inversions for non linear mechanical cases.


identifier: Mbaye, M. M. (2010). Techniques d'exploration architecturale de design à usage spécifique pour l'accélération de boucles  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: De nos jours, les industriels privilégient les architectures flexibles afin de réduire le temps et les coûts de conception d'un système. Les processeurs à usage spécifique (ASIP) fournissent beaucoup de flexibilité, tout en atteignant des performances élevées. Une tendance qui a de plus en plus de succès dans le processus de conception d'un système sur puce consiste à spécifier le comportement du système en langage évolué tel que le C, SystemC, etc. La spécification est ensuite utilisée durant le partitionement pour déterminer les composantes logicielles et matérielles du système. Avec la maturité des générateurs automatiques de ASIP, les concepteurs peuvent rajouter dans leurs boîtes à outils un nouveau type d'architecture, à savoir les ASIP, en sachant que ces derniers sont conçus à partir d'une spécification décrite en langage évolué. D'un autre côté, dans le monde matériel, et cela depuis très longtemps, les chercheurs ont vu l'avantage de baser le processus de conception sur un langage évolué. Cette recherche a abouti à l'avénement de générateurs automatiques de matériel sur le marché qui sont des outils d'aide à la conception comme CapatultC, Forte's Cynthetizer, etc. Ainsi, avec tous ces outils basés sur le langage C, les concepteurs ont un choix de types de design élargi mais, d'un autre côté, les options de designs possibles explosent, ce qui peut allonger au lieu de réduire le temps de conception. C'est dans ce cadre que notre thèse doctorale s'inscrit, puisqu'elle présente des méthodologies d'exploration architecturale de design à usage spécifique pour l'accélération de boucles afin de réduire le temps de conception, entre autres. Cette thèse a débuté par l'exploration de designs de ASIP. Les boucles de traitement sont de bonnes candidates à l'accélération, si elles comportent de bonnes possibilités de parallélisme et si ces dernières sont bien exploitées. Le matériel est très efficace à profiter des possibilités de parallélisme au niveau instruction, donc, une méthode de conception a été proposée. Cette dernière extrait le parallélisme d'une boucle afin d'exécuter plus d'opérations concurrentes dans des instructions spécialisées. Notre méthode se base aussi sur l'optimisation des données dans l'architecture du processeur.  ABSTRACT: Time to market is a very important concern in industry. That is why the industry always looks for new CAD tools that contribute to reducing design time. Application-specific instruction-set processors (ASIPs) provide flexibility and they allow reaching good performance if they are well designed. One trend that gains more and more success is C-based design that uses a high level language such as C, SystemC, etc. The C-based specification is used during the partitionning phase to determine the software and hardware components of the system. Since automatic processor generators are mature now, designers have a new type of tool they can rely on during architecture design. In the hardware world, high level synthesis was and is still a hot research topic. The advances in ESL lead to commercial high-level synthesis tools such as CapatultC, Forte's Cynthetizer, etc. The designers have more tools in their box but they have more solutions to explore, thus their use can have a reverse effect since the design time can increase instead of being reduced. Our doctoral research tackles this issue by proposing new methodologies for design space exploration of application specific architecture for loop acceleration in order to reduce the design time while reaching some targeted performances.  Our thesis starts with the exploration of ASIP design. We propose a method that targets loop acceleration with highly coupled specialized-instructions executing loop operations. Loops are good candidates for acceleration when the parallelism they offer is well exploited (if they have any parallelization opportunities). Hardware components such as specialized-instructions can leverage parallelization opportunities at low level. Thus, we propose to extract loop parallelization opportunities and to execute more concurrent operations in specialized-instructions. The main contribution of this method is a new approach to specialized-instruction (SI) design based on loop acceleration where loop optimization and transformation are done in SIs directly, instead of optimizing the software code. Another contribution is the design of tightly-coupled specialized-instructions associated with loops based on a 5-pattern representation.


identifier: Kaouane, C. (2010). Contribution à l'auscultation des chaussées mixtes par méthodes GPR et électrique  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Dans le contexte des infrastructures urbaines québécoises vieillissantes et dans un souci de planification des travaux, il faut pouvoir diagnostiquer de façon rapide, fiable et à moindre coût les chaussées urbaines. Ce mémoire de maîtrise s'intéresse à investiguer et à développer le potentiel du géoradar et des méthodes électriques pour l'auscultation des chaussées urbaines, soumises aux cycles de gel-degel et de saturation et désaturation. On souhaite détecter les défauts et estimer la teneur en eau dans les chaussées mixtes. Ces dernières consistent en une couche de surface asphaltée, une dalle de béton de ciment et une fondation. Des études antérieures basées en grande partie sur des modélisations et des études terrain, ont montré un potentiel certain de l'application conjointe du GPR et des méthodes électriques pour l'auscultation de ce type de chaussée. Toutefois, une meilleure évaluation du potentiel serait obtenue si on pouvait avoir accès aux propriétés physiques des matériaux de la chaussée et à des données géotechniques.  La mise en contexte permet tout d'abord de souligner le lien entre les variations de propriétés physiques des matériaux routiers, l'apparition des défauts structuraux et la teneur en eau. Après une brève étude par modélisation numérique, des mesures radar sont réalisées sur une chaussée montréalaise (Canada) avant sa réhabilitation complète. Lors de la destruction de la chaussée, on prélève des échantillons de sols dans les tranchées et des blocs de béton et d'asphalte sont récupérés pour étudier ensuite leurs propriétés physiques en laboratoire. La permittivité complexe du béton et de l'asphalte est mesurée avec une sonde à terminaison ouverte qui intègre sur un volume de 30 cm3 dans la plage de fréquence 50 MHz-900 MHz. Les mesures de résistivité électrique sont faites sur des carottes extraites des blocs de béton et d'asphalte avec un montage simple. Les mesures sont faites sur les échantillons secs et humides, ce qui permet d'obtenir une approximation des valeurs prises en fonction des changements climatiques sur une année. En parallèle, on mesure la teneur en eau sur les échantillons de sol. Les teneurs en eau sont élevées et le sol a une composition de silt argileux, ce qui justifie la forte conductivité obtenue avec les mesures électriques réalisées sur la fondation de la chaussée reconstruite. Les données géophysiques et géotechniques disponibles sont ensuite compilées. Des modélisations dites de vérification et de corrélation sont réalisées pour être comparées aux mesures réalisées sur le terrain. Finalement, on observe une bonne concordance. Ce travail fournit une base à des travaux futurs plus spécifiques.  ABSTRACT: Quebec's infrastructures are ageing. A reliable, quick and economical assessment of the state of urban roads would help to plan civil engineering. This M.Sc. thesis aims to investigate and develop the potential of Ground Penetrating Radar (GPR) and electrical methods to assess pavement condition subject to wetting, freezing and drying cycles. The objectives are to display defects and estimate water content in the materials used for the mixed pavement construction; these consist in layers of asphalt (top), concrete (middle) and grade and sub-grade (bottom). Prior studies showed a valuable potential of joint application of GPR and electrical resistivity to assess mixed pavement condition. These studies were mainly based on numerical modeling and some site tests using both methods. It was concluded that a better evaluation of the potential of the coupled methods would come from the assessment of physical properties and validation from geotechnical evidences.   At first, we characterized the context. Structural defects and water content implied modification of physical properties of road materials. After running numerical modeling, we carried out an experiment in one of the streets in Montreal (Canada) where pavement needed complete rehabilitation. GPR surveys were carried out before the pavement was destroyed and removed, and subsequently a resistivity imaging was carried out on the subgrade layer.  We also sampled blocks of asphalt and concrete along the street from the demolition rubble in order to study their physical properties in the lab. Soil samples were taken from trenches to measure water content. The grade and sub-grade were mainly a mix of clayey-silt and gravel, as the embedding ground is grey clay. We measured the complex dielectric constants of asphalt and concrete in the range 50 MHz-900 MHz with a recently developed dielectric probe sampling a volume of 30 cm3. Resistivity measurements were also performed on large cores of asphalt and concrete using an in-house system. Measurements were carried out on dry and wet samples, which provided a range of values encompassing the climatic conditions for the whole year. Finally the physical property and geotechnical data were used as input to numerical modeling and the modeled responses compared to the survey data. The predicted data fit nicely with the observed data. This work aims to provide further information for a better calibration of geophysical devices in pavement condition assessment. Moreover, it gives a wide range of information, which could become a base for further and more specific works.


identifier: Ennaouri, I. (2010). Modélisation de la dégradation hydraulique et structurale des réseaux sanitaires et pluviaux  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette recherche a pour but de développer un modèle d'évaluation de l'état global des conduites d'égouts en considérant plusieurs facteurs de dégradation liés au fonctionnement du réseau, à la conduite elle-même ou à l'environnement du réseau. Pour intégrer les deux critères hydraulique et structural de la dégradation, 15 facteurs influençant la dégradation ont été identifiés et considérés dans cette recherche. La méthode AHP a été utilisée pour tenir compte de l'importance relative entre facteurs par le calcul du poids de chaque facteur. Le modèle proposé a été testé pour évaluer l'état actuel des conduites sélectionnées sur le réseau d'égout de la ville de St-Hyacinthe. Une analyse de sensibilité a été réalisée afin de déterminer l'effet de l'importance relative entre le critère hydraulique et le critère structural sur l'évaluation de l'état d'une conduite donnée. Les résultats de cette analyse ont montré que le critère hydraulique doit être considéré dans le même ordre d'importance que le critère structural dans le processus d'évaluation de l'état. Ainsi, le modèle développé constitue un outil simple à utiliser dans les municipalités. Il assistera les gestionnaires des réseaux d'égout dans l'élaboration de leur plan d'intervention et leur permettra par conséquent de garder leurs réseaux en bon état.  ABSTRACT: The aim of this study was to develop a condition assessment model for sewer and storm water pipelines. To integrate both hydraulic and structural aspects of degradation, a set of 15 specific influencing factors was identified and considered in this model. The analytic hierarchy process (AHP) method was used to express the relative importance of these factors. The proposed model was successfully tested to assess the current state of degradation of a representative sample of pipes selected from the sewer network of the city of Saint-Hyacinthe in Canada. A sensitivity analysis was performed to determine the effect of the relative importance between hydraulic and structural criteria on the state assessment of a given pipe. Results from this analysis indicate that the hydraulic criterion should be considered with the same importance as the structural criterion in the degradation assessment process. This model constitutes a useful tool for researchers and municipal engineers to improve their intervention plan by integrating the hydraulic criterion.


identifier: Valiquette, F. (2010). Typologie des chaînes de déplacements et modélisation descriptive des systèmes d'activités des personnes  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: L'étude des déplacements de la population existe depuis plusieurs années, mais il n'en demeure pas moins qu'il n'est pas toujours facile de tracer le réel portrait de la mobilité. En effet, les déplacements ne cessent de se complexifier, phénomène causé par l'étalement urbain, l'éparpillement des activités, l'augmentation de la motorisation des personnes âgées et plusieurs autres. À ceci, s'ajoute la diversification des modes de transport engendrant une flexibilité accrue des individus. Les méthodes d'analyse, ont elles aussi, évolué dans le temps, tentant toujours d'améliorer la compréhension de la mobilité de la population. Les modèles d'activités émergent de ces nouvelles méthodes. Il s'agit de l'analyse des déplacements basée sur les activités des personnes. Ces modèles permettent d'obtenir des résultats désagrégés en utilisant des enquêtes sur les déplacements de la population. La région de Montréal possède, depuis 1970, de nombreuses bases de données sur les déplacements des personnes. En effet, une enquête téléphonique, nommée Enquête Origine-Destination, est effectuée environ tous les cinq ans, permettant de recueillir des informations sur les déplacements de 5% des ménages de la grande région de Montréal. À ce jour, plusieurs études ont porté sur les déplacements à partir de ces bases de données. Toutefois, pour une meilleure compréhension de la mobilité à Montréal, il est important de regarder l'ensemble des déplacements effectués par une personne lors d'une journée. En effet, un déplacement pour une activité a de fortes chances d'avoir une certaine influence sur les déplacements d'une autre activité dans la journée. C'est pourquoi l'analyse des chaînes de déplacements devient plus pertinente pour bien comprendre la mobilité de la population. De nombreuses études dans différentes régions du monde ont déjà traité des chaînes de déplacements. D'ailleurs, plusieurs auteurs, tels que McGuckin et Murakami (1995), Goulias et Kitamura (1989), Primerano et al. (2007), ont contribué à définir les chaînes de déplacements. Bien que les définitions diffèrent quelque peu selon les auteurs, il n'en demeure pas moins que la base est la même, soit la consolidation d'activités lors des déplacements.  ABSTRACT: Individual travel behaviours has been the focus of multiple studies for several years. Nevertheless, it is still not easy to draw the real picture of citizens' mobility. Indeed, trips are constantly becoming more complex due to urban sprawl, fragmentation of activity, increasing motorisation of the population, and specific population segments such as the elderly, or any others category of users. In addition, the diversification of transportation alternatives (new modes) is providing increased travel flexibility for most of the population. The analytical methods have also evolved over time as well, trying to improve the understanding of population mobility. Activity-based models are emerging from these new methods. These models allow to obtain disaggregated results using travel surveys of the population. Since 1976, the Greater Montreal Area has been gathering many databases on citizens' trips. Indeed, a telephone survey, called "Enquête Origine-Destination", is conducted every five years to collect information on the travel behaviours of approximately 5% of the residing population. As of today, several studies have focused on travels from these databases. However, for a better understanding of travel behaviours in Montreal, it is necessary to analyse all trips made by a person during an entire day. In fact, a trip to an activity is likely to influence on a secondary trip to another activity in the same day. Therefore, the analysis of trip chains becomes more significant to understand the behaviour of the population in the end. Many worldwide studies have already addressed trip chains. Moreover, several authors, such as McGuckin and Murakami (1995), Goulias and Kitamura (1989), Primerano et al. (2007), have contributed to define trip chains. Although definitions shortly differ according to authors, the main base remains the same, that is aggregation of activities while traveling. In addition, the authors have overlooked the trip chains based on length, duration, amount of trips, according to some socio-demographic characteristics such as gender and age, households' size, car's access and several other criterias.


identifier: Ait El Cadi, A. (2010). Planification de trajectoires pour une flotte d'UAVs.  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les drones, qu'on appelle aussi UAVs (Unmanned Aerial Vehicles) ou RPV (Remotely Piloted Vehicles), sont des avions sans pilote. Ils sont adoptés par des organisations militaires et civiles pour accomplir des tâches difficiles dans des environnements très hostiles, sans aucun risque pour l'humain. Comme toute nation développée, le Canada a recours à ces avions pour ses missions militaires de maintien de la paix et pour des missions civiles telles que la surveillance du littoral, la surveillance des grands territoires et pour l'aide lors d'opérations de sauvetage. L'utilisation des UAVs est très diverse, que ce soit pour des opérations militaires ou civiles, et l'engouement pour ces engins est de plus en plus grand dans les pays industrialisés. Les progrès réalisés dans les technologies de contrôle, de détection et de calcul ont permis à ces véhicules de réaliser des missions indépendantes du contrôle direct de l'opérateur. L'itinéraire peut être planifié à l'avance de la mission et le drone peut alors l'exécuter automatiquement. La planification de cet itinéraire efficace implique la détermination de solutions permettant d'atteindre un certain but fixé, comme par exemple éviter que le drone soit détecté par les radars au cours de son itinéraire, ou trouver l'itinéraire le plus court en terme de temps de déplacement, ou encore la minimisation du coût de la mission.  ABSTRACT: UAVs (Unmanned Aerial Vehicles) or RPV (Remotely Piloted Vehicles), are planes without pilots. They were adopted by military and civilian organizations to accomplish difficult tasks over hostile environments and without risk for humans. Like any other developed nation, Canada has used the UAVs for its military missions such as peacekeeping and for civilian missions such as coastal monitoring, surveillance of large areas and rescue operations. The applications of UAVs are very diverse, ranging from surveillance operations to combat operations through rescues. Advances in monitoring technologies, detection and computing have allowed these vehicles to perform missions without the direct control of the operator. The itinerary can be planned in advance and the UAVs can then run automatically. Planning efficient routes involves determining a specific solution with a precise objective like avoiding radar detection of the UAVs, finding the shortest path in terms of time, or minimizing the cost of the mission.


identifier: Bouchedda, A. (2010). Inversion conjointe des données électriques et de radar en forage  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Dans le cadre de cette thèse, deux algorithmes d‘inversion conjointe des données électriques et de radar en forage ont été développés. Le premier algorithme combine une approche basée sur l‘échange de l‘information structurale entre deux inversions séparées et une régularisation dans le domaine des ondelettes qui force la solution à avoir une représentation creuse des coefficients en ondelettes. Cette régularisation consiste à appliquer un algorithme de seuillage doux à chaque itération d‘un algorithme de descente. L‘opération de seuillage nécessite le calcul de seuils qui sont déterminés dans notre cas en maximisant un critère de similarité structurale entre les modèles de résistivité et de lenteur. Comme la régularisation dans le domaine des ondelettes permet la reconstruction des discontinuités de contraste fort ainsi que les zones homogène, nous proposons d‘utiliser le détecteur de contours Canny pour extraire l‘information structurale de chaque modèle. Les contours ainsi détectés sont utilisés pour construire des matrices de pondération qui sont appliquées à la matrice de rugosité de chaque inversion séparée. Pour valider cet algorithme trois modèles synthétiques ont été utilisés. Les résultats montrent que celui-ci permet d‘améliorer la résolution spatiale, ainsi qu‘une meilleure estimation des propriétés physiques, en comparaison avec l‘inversion séparée. De plus, il présente l‘avantage d‘être très robuste lorsque le niveau du bruit est élevé. Dans le deuxième algorithme, on propose de combiner une inversion coopérative par zonation et une approche bayésienne hiérarchique. L‘inversion coopérative par zonation consiste à utiliser séquentiellement une approche de classification non-hiérarchique et un algorithme d‘inversion séparée. Dans un processus itératif, l‘algorithme de classification non-hiérarchique est appliqué sur les résultats obtenus par inversion séparée pour générer des modèles composés de plusieurs zones homogènes représentant chacune une certaine lithologie du milieu investigué. Les modèles ainsi construits sont ensuite utilisés comme modèles a priori dans une nouvelle étape d‘inversion séparée. La solution obtenue par une telle approche peut être biaisé vers le modèle a priori qui est fonction du nombre de classes dans l‘algorithme de classification non-hiérarchique.  ABSTRACT: We present two joint structural inversion algorithm for cross-hole electrical resistance tomography (ERT) and cross-hole radar travel time tomography (RTT). The first algorithm proceeds by combining the exchange of structural information and a regularization method that consists of imposing an L1-norm penalty in the wavelet domain. The minimization of the L1-norm penalty is carried out using an iterative soft-thresholding algorithm. The thresholds are estimated by maximizing a structural similarity criterion, which is a function of the two (ERT and RTT) inverted models. Besides, the regularization in the wavelet basis allows for the possibility of sharp discontinuities superimposed on a smoothly varying background. Hence the structural information is extracted from each model using a Canny edge detector. The detected edge serves to construct a weighting matrix that is used to alter the smoothness matrix constraint. To validate our methodology and its implementation, three synthetic models were created. Experiments demonstrate that the proposed approach improves the spatial resolution and quantitative estimation of physical parameters. In addition, it seems to be more robust in high noise level condition. In the second algorithm, we propose to combine a zonal cooperative inversion (ZCI) scheme with a hierarchical Bayesian approach, in order to invert cooperatively cross-hole ERT data and cross-hole radar travel time data. The basic idea of ZCI is to use cooperatively cluster analysis and separate inversion algorithm. For each iteration cluster analysis of separate inversion results is used to construct models that contain the parameter characteristics of dominant subsurface structures. These constructed models are then used as starting model in the next iteration of separate inversion. The resulting models are then biased to starting models which are a function of the number of clusters. To overcome this problem, we formulate the inverse problem within a hierarchical Bayesian framework where the hierarchical prior distribution is based on the a priori models constructed from cluster analysis.


identifier: Laeuffer, P.-A. (2010). Analyse des déterminants de la performance des équipes de projets dispersées: prise en compte de l'influence décisionnelle de trois groupes d'acteurs  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Bon nombre de projets technologiques actuels sont réalisés par des équipes de projets dispersées géographiquement. Des phénomènes, comme la mondialisation de l'économie et le développement fulgurant des technologies de l'information et des communications, sont autant de facteurs qui ont permis l'émergence de ce type de fonctionnement. Responsables de projets et experts techniques se trouvent donc souvent dans un contexte où les rapports intraéquipes se trouvent modifiés; planification du travail, répartition des rôles, mobilisation des membres et résolutions de conflits sont des exemples d'actes de gestion qu'il faut adapter en fonction de ce nouveau contexte. Dans le cadre de ce mémoire, ce sont les processus décisionnels qui sont au coeur de la problématique. Plus spécifiquement, le mémoire s'inscrit dans le courant actuel des facteurs de succès et de la performance des équipes dispersées, et tient compte de l'influence décisionnelle que peuvent avoir certains groupes d'acteurs projets. Nous avons testé des hypothèses quant aux liens pouvant exister entre certaines dimensions et la performance des équipes. Après avoir fait un état des connaissances des concepts liés à la prise de décision et aux équipes dispersées, nous avons exploité une base de données montée à l'aide d'un questionnaire en ligne. Ce questionnaire fut expédié à 1 000 professionnels travaillant en équipes dispersées et basés au Québec, et nous a permis de récupérer un total de 149 questionnaires exploitables.  ABSTRACT: Technology projects today are increasingly handled by distributed teams with members spread around the world. Globalization and the rapid development of information and communication technologies (ICT) are mainly responsible for the rise in distributed teamwork and virtual teams. Project managers and technical experts must cope with a new environment in which team relationships are differently defined. task planning and allocation, team motivation, and conflict solving must be adapted to this new context. In this research, we focused on the decisional process in virtual teams. More specifically, we examined the dynamic interplay between success factors, performance indicators, and the decisional influences of three categories of actors. We tested several hypotheses to evaluate the relationships between various dimensions and virtual team performance. Following a literature review on decision-making concepts and virtual teams, we used a data bank built from an online survey. A questionnaire was sent to a thousand Quebec-based professionals working in virtual teams, resulting in 149 respondents. We first characterized virtual teams by the influential relationships within them, in terms of three actor groups: project managers, team members, and top management. We then performed clustering on the thirty questionnaire items about decisional influences and identified three decisional patterns: small teams with high autonomy (cluster 1), strongly structured organizations (cluster 3), and ad-hoc organizations (cluster 2). To better understand these clusters, we conducted mean comparisons of dimensions.


identifier: Raev, K. P. (2010). Développement d'une méthode respirométrique visant à mesurer l'activité biologique sur du charbon actif en poudre  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le couplage des procédés membranaires basse pression (microfiltration et ultrafiltration) et du charbon actif en poudre (CAP), appelé procédé hybride, est actuellement en plein développement dans le domaine du traitement de l'eau potable. Alors que les membranes permettent la séparation du charbon et la pollution particulaire de l'eau traitée, le CAP est utilisé pour l'élimination de la matière organique dissoute, sous la forme de carbone organique biodégradable et aussi pour l'enlèvement des traces de composés toxiques (pesticides). Pour mieux connaitre les processus de biodégradation du substrat dans le réacteur hybride, une estimation de la croissance et l'abondance bactérienne est nécessaire. À ce jour, il existe plusieurs méthodes pour caractériser la biomasse sur de charbon actif en grains (CAG), mais aucune méthode pour le cas de CAP. Cependant, la respirométrie, une méthode très couramment utilisée dans le domaine des eaux usées, pourrait une alternative intéressante : simple et peu coûteuse. Le présent projet porte sur l'application de la méthode de respirométrie dans le cas de charbon actif en poudre (CAP) utilisé en mode biologique. Les buts principaux étaient de caractériser l'activité bactérienne et quantifier la biomasse hétérotrophe aérobie (ZBH) colonisant la surface du charbon actif en poudre. Du charbon de trois sources différentes a été testé à l'aide de respiromètre Challenge AER-200, soit du CAP de 25 et 200 μm (CAP-laboratoire) et du CAB (CAG-Ste Rose) colonisés au laboratoire à l'extrait de levure, soit du CAP de 25 μm (CAP-Opaline) provenant du pilote biomembrane Opaline-B de l'usine Ste Rose colonisé de façon naturelle avec de l'eau décantée ozonée. Les observations microscopiques au BacLighttm de CAP-laboratoire ont montré que le charbon de 25 μm possédait plus de biomasse par champ microscopique que celui de 200 μm ce qui n'était pas démontré par les résultats expérimentaux de respirométrie. De plus, la comparaison entre les valeurs de ZBH pour 3 et 6 g du même diamètre de CAP a montré que la masse de 3 g possédaitesconcentrations de biomasse supérieures à celles de 6 g ce qui n'était pas en accord avec les attentes.  ABSTRACT: Integration of low pressure membrane processes (microfiltration and ultrafiltration) and powdered activated carbon (PAC), termed as the hybrid process, is currently under development in the field of drinking water treatment. While membranes allow the separation of PAC and particulate matter from treated water, the PAC is used for the removal of dissolved organic matter in the form of biodegradable organic carbon and also to remove traces of organic compounds (pesticides). To learn more about the process of biodegradation of substrate in hybrid membrane reactors, an estimate of bacterial activity and abundance is needed. Up to now, there are several methods to characterize the biomass on activated carbon (GAC), but no method applies to the case of PAC. However, respirometry, a method commonly used in the field of wastewater could be an interesting alternative due to its simplicity and low cost. This project involves the application of respirometry to the case of biological powdered activated carbon (PAC). The main aims were to characterize the biological activity and quantify heterotrophic aerobic biomass (ZBH) colonizing the surface of activated carbon powder. Activated carbons from three different sources were tested using respirometer Challenge AER- 200, PAC 25 and 200 μm (PAC-laboratory) and BAC (GAC-Ste Rose WTP) colonized in the laboratory using yeast extract, or PAC 25 μm (PAC-Opaline) from the biomembrane pilot Opaline-B (located at the Ste Rose treatment plant) colonized naturally with settled-ozonated water. The microscopic observations of BacLighttm PAC-laboratory showed that coal 25 μm had more biomass per microscopic field than 200 μm which was also demonstrated by the experimental results of respirometry. In addition, the comparison between the values of ZBH using 3 or 6 g of the same diameter of PAC have shown that the mass of 6 g had biomass concentrations higher than 3 g, which was consistent with expectations. However, PAC-laboratory of the two diameters were more colonized than the PAC-Opaline.


identifier: Velut, B. (2010). Application de la méthode IPS au problème de localisation d'entrepôt sans capacité  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le problème de localisation d'entrepôts sans capacité (LESC) est un problème qui a été très étudié dans le domaine de la recherche opérationnelle depuis une cinquantaine d'années pour ses caractéristiques et ses applications dans le monde industriel. Il consiste à installer un certain nombre d'entrepôts sur un ensemble de sites et à affecter un et un seul entrepôt à chaque client d'un ensemble de clients. Sur chaque site, il coûte un certain montant pour y installer un entrepôt et pour chaque client, il coûte un autre montant pour l'affecter à un site sur lequel un entrepôt est installé. L'objectif est de minimiser le coût total. Ce problème NP-difficile est très compliqué à résoudre de manière exacte surtout pour des instances de grande taille. Nous proposons dans ce mémoire une méthode permettant de le résoudre à l'optimalité. La méthode proposée est basée sur la combinaison d'une métaheuristique de type recherche tabou et d'un algorithme de résolution de programmes linéaires nommé IPS (Improved Primal Simplex) qui implémente une version améliorée du très connu algorithme du simplexe primal. Le tout fonctionne en faisant créer par la métaheuristique une solution proche de la solution optimale. Celle-ci sert de point de départ pour l'algorithme IPS qui termine la résolution jusqu'à l'optimalité. Cet algorithme IPS corrige une faiblesse de l'algorithme du simplexe primal en profitant de la dégénérescence quand celle-ci apparaît lors de la résolution d'un problème. Le problème LESC fait partie des problèmes à dégénérescence forte.  Dans ce mémoire, nous développons d'abord une métaheuristique de recherche tabou qui produit des résultats qui sont, dans certains cas, supérieurs à ceux obtenus dans la littérature. Par la suite, nous montrons que la méthode proposée est plus efficace pour résoudre la relaxation linéaire du problème LESC que le traditionnel algorithme du simplexe primal sur les instances dont la matrice des coûts d'affectation a une densité comprise entre 0,1 et 0,6. Nous montrons également que cette efficacité augmente avec la taille des instances. Nos résultats mettent en évidence des temps de calcul réduits d'un facteur pouvant aller jusqu'à 3,5 pour certaines relaxations linéaires par rapport à l'algorithme du simplexe primal.  Enfin, pour la résolution en nombres entiers, nous testons l'intégration de cette méthode dans un algorithme d'évaluation et séparation utilisant deux stratégies différentes : la stratégie profondeur d'abord et la stratégie meilleur d'abord. Nos tests sur cette intégration dans l'algorithme d'évaluation et séparation font ressortir des faiblesses sur l'implémentation, ce qui empêche la méthode proposée de conserver sa supériorité sur un algorithme d'évaluation et séparation identique utilisant l'algorithme du simplexe primal.  Nous terminons ce mémoire en donnant des pistes d'amélioration pour la méthode proposée, ainsi que pour son application à la résolution du problème LESC.  ABSTRACT: In the last five decades, the uncapacitated facility location problem (UFLP) has been widely studied in operations research because of its features and its many applications in industrial contexts. Given a set of customers to service and a set of potential sites on which a warehouse can be built, the UFLP consists of selecting on which sites to install a warehouse and assigning one and only one warehouse to each customer. A fixed cost for building a warehouse is associated with each site and customer/warehouse assignment costs are also considered. The aim of the problem is to minimize the total cost. This NP-hard problem is very hard to solve to optimality, especially when the instance size is large. In this master's thesis, we propose a method to solve it to optimality. The proposed method is based on a combination of a tabu search heuristic and a linear programming solution algorithm called Improved Primal Simplex (IPS). It starts by computing a solution close to optimality using tabu search. This solution is then used to initialize IPS that solves the problem to optimality. The IPS algorithm overcomes a weakness of the simplex primal algorithm by taking advantage of degeneracy when it appears during the solution process. Typically, the UFLP yields high degeneracy. In this thesis, we first develop an efficient tabu search method that produces better results in some cases than the algorithms from the literature. Second, we show that the proposed method solves the linear relaxation of UFLP more efficiently than the classic primal simplex algorithm for instances where the assignment cost matrix has a density between 0.1 and 0.6. This efficiency increases with the instance size. We report a reduction of the computational time of up to a factor of 3.5 when the IPS algorithm is compared with the primal simplex algorithm. Then, for the integer solution process, we test an integration of the IPS method into a branch-and-bound algorithm using two search strategies: depth-first and best-first. Our tests highlight a weakness of this approach that forbids our method to keep its superiority over the same branch-and-bound algorithm based on the primal simplex algorithm. We conclude this thesis by briefly discussing future research directions for the proposed method and also for its application to solve the UFLP.


identifier: Côté, P. (2010). Gestion d'un ensemble d'installations hydroélectriques soumis à une contrainte de demande  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse présente une nouvelle approche pour solutionner un problème de gestion d'un ensemble d'installations hydroélectriques dont l'objectif est de maximiser la différence entre les revenus des ventes et les coûts des achats d'électricité et ceci tout en satisfaisant à la demande. La technique de solution proposée est basée sur la méthode des trajectoires optimales développée par Turgeon [1]. Le but de cette méthode est de déterminer un ensemble de niveaux de références à chaque période et ce pour chaque réservoir. Ces niveaux sont dit optimaux si l'espérance de la production est maximisée lorsque les réservoirs se situent sur ces niveaux. Bien que cette méthode soit applicable quelque soit le nombre de réservoirs, elle ne permet pas de solutionner un problème avec demande. La quantité d'énergie produite maximisant l'espérance de la production ne maximisera pas nécessairement la différence entre les revenus et les coûts. Ceci est particulièrement vrai durant l'hiver où les apports naturels sont faibles et la demande est forte.  Afin de modifier cette méthode, nous avons donc estimé la quantité optimale d'énergie à produire pour chaque période à l'aide de la programmation dynamique stochastique.  Le problème à résoudre est un problème à un réservoir qui est obtenu par l'agrégation des contenus énergétiques de l'ensemble des réservoirs du système. La règle de gestion « agrégée » donne la quantité d'énergie cible devant être produite en fonction de l'énergie potentielle stockée et des apports énergétiques prévus.  Pour déterminer de quel réservoir l'eau doit être soutirée (ou emmagasinée) pour atteindre la cible, les valeurs marginales de l'eau stockée dans les réservoirs ont été estimées avec la méthode des trajectoires. La méthode a été appliquée et comparée à la programmation dynamique pour des problèmes de 2 et 3 réservoirs. La méthode a aussi été appliquée à des problèmes de grande dimension afin de montrer que la modification apportée n'affecte pas les deux principales qualités de la méthode qui sont son efficacité et sa rapidité.  ABSTRACT: This thesis presents a method for determining a weekly operating policy of a hydropower system subject to a demand. The objective function is to maximize the difference between the revenues due to the surplus of energy and the cost of the energy bought to meet the demand. The method is based on the Optimal Reservoir Trajectory (ORT) approach developed by Turgeon [1].  The task of the ORT is to find a set of trajectories that maximize the expected production of energy. The aim of the operating policy of the ORT is to follow these trajectories as close as possible. Consequently, this operating policy does not necessarily maximize the objective function in each period. It can be advantageous to reduce the production and buy energy to prevent future shortage or increase the production to sell the surplus of energy. We tackle the problem of calculating the optimal amount of energy that should be produced in each period by solving a small-scale stochastic dynamic problem. In this problem, the objective is to maximize the objective function for the whole system represented by an aggregated model. The feedback policy of this dynamic problem gives the energy target that the system should reach in each period. We identify afterwards the reservoirs for which the release should be increased (or reduced) to reach this target by means of an estimation of marginal values of the water stored in the reservoirs. These values indicate the impact of operating the reservoirs below or above the optimal trajectories. The method is compared to Stochastic Dynamic Programming for systems of two and three reservoirs. We also show, for a seven reservoirs system, that the CPU time is not affected by this modification when compared to the original ORT method. Thus, a large-scale problem can be solved even when there is a demand to satisfy.


identifier: Mortazy, E. (2010). Innovative Traveling-Wave Optoelectronic Devices for Radio over Fiber and Terahertz Applications  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La structure des composants conventionnels pour les applications optoélectroniques à haute fréquence ainsi que son intégration avec d'autres composants peuvent être modifiées en utilisant les guides d'ondes à faible perte. Par ailleurs le concept des circuits intégrés au substrat (Substrate Integrated Circuits: SICs), largement utilisé dans les structures des applications micro-ondes, peut être employé pour l'intégration de ces composantes dans les applications à ondes millimétriques (millimetre Wave: mmW) et sous-millimétriques. Dans les systèmes de communication optique et systèmes optoélectroniques,  photodétecteurs et modulateurs sont les éléments clés pour la conception des récepteurs et des émetteurs. Les photodétecteurs à ondes progressives (Traveling-Wave: TW) et les modulateurs conventionnels, dans leurs structures, utilisent les lignes microrubans (Microstrip: MS) et les guides coplanaires (Coplanar Waveguide: CPW).  Les substrats majoritairement utilisés pour la fabrication des composantes optoélectroniques et électro-optiques, citées ci-dessus, sont en arséniure de gallium (GaAs) et  niobate de lithium (LiNbO3). Il faut bien noter que les pertes de micro-ondes/mmW dans les lignes microrubans et les guides coplanaires augmentent avec la fréquence. Ces pertes incluent les pertes ohmique, diélectrique et de rayonnement. Le guide d'ondes rectangulaire ayant  une  faible perte après la fréquence de coupure sans grand changement, est un guide d'ondes de remplacement pour les composants mmW. Son inconvénient est qu'il n'est pas planaire et difficilement intégrable. Le guide d'ondes intégré au substrat (Substrate Integrated Waveguide: SIW) est une forme planaire du guide d'ondes rectangulaire. Dans ces guides d'ondes les trous métallisés remplacent les parois métalliques du guide rectangulaire. De nouveaux composants optoélectroniques peuvent être proposées avec l'intégration de la structure SIW pour les fréquences mmW. Les photodétecteurs et les modulateurs sont les candidats potentiels pour les nouveaux composants optoélectroniques.  ABSTRACT: The structure of conventional optoelectronic devices for new high frequency applications as well as the integration with other devices may be modified by using low-loss microwave waveguides. Also the concept of substrate integrated circuits (SICs), which has widely been used in the microwave domain, can be utilized for the integration of optoelectronic devices at millimetre wave (mmW) and sub-mmW frequency ranges. Photodetectors and modulators, as optoelectronic devices, are two key components of receivers and transmitters in optical communication systems. Conventional traveling-wave (TW) photodetectors and modulators make use of microstrip (MS) and coplanar waveguide (CPW) in their structures as transmission line electrodes. These electrode structures with high losses cannot be utilized in mmW devices. Microwave/mmW losses of MS and CPW, including ohmic, dielectric and radiative losses, in optoelectronic and electro-optical materials such as gallium arsenide (GaAs) and lithium niobate (LiNbO3) are increased with frequency. Rectangular waveguide (RWG) with constant low loss in specific frequency range after its cut-off frequency is an alternative waveguide for mmW devices, although it is non planar and non integrable. Substrate integrated waveguide (SIW) derived from the general SICs concept is a planar form of RWG with some metalized via holes instead of metallic side walls of RWG. New optoelectronic devices and in particular TW photodetector and modulator can be proposed based on SIW structure for mmW frequency, terahertz (THz) photonics and electro-optical applications. In the design of waveguide photodetectors, the microwave/mmW loss as an important factor for bandwidth limitation is related to two sections, namely, active MS multilayer detection and non-active MS single layer transmission.  It is expected that the long section of lossy microstrip line after the detection would significantly limit the bandwidth of the photodetector and may be replaced by low-loss SIW structure. A transition of MS in the photodetector to the multilayer SIW, to separate the photodetector DC bias and SIW metallic plates, is designed and realised in this work.


identifier: Rodrigue, H. (2010). Méthodologie de conception et d'optimisation de mécanismes fabriqués par fabrication rapide  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La fabrication rapide est un procédé de fabrication dont le marché est en expansion rapide. Ce procédé de fabrication présente de nouvelles possibilités de fabrication révolutionnaires, telle la possibilité de créer des formes plus complexes et la possibilité de fabriquer des pièces composées de plusieurs matériaux. De plus, avec les procédés de fabrication traditionnels, dits par enlèvement de matière, le facteur le plus important du coût de fabrication est la complexité de la pièce. En utilisant la fabrication rapide comme moyen de fabrication, le coût de fabrication est influencé principalement par le volume de la pièce, ce qui fait qu'ajouter de la complexité n'est pas un problème. Les méthodologies de conception utilisées auparavant aident le concepteur à créer des pièces simples à fabriquer avec des procédés par enlèvement de matière et donc de diminuer les coûts. Toutefois, aucune de ces méthodologies ne sont applicables à la fabrication rapide. Avec la fabrication rapide, il est préférable de guider le concepteur à ajouter de la complexité afin d'améliorer le produit. Ce mémoire vise à développer une méthodologie qui a pour objectif d'aider le concepteur à apporter des améliorations au produit et de l'aider à incorporer les avantages de la fabrication rapide dans son produit, ce qui n'existe pas dans la littérature actuelle. Pour ce faire, une analyse est faite des différentes méthodologies d'aide à la conception ainsi que de méthodologies reliées à la fabrication rapide afin de déterminer si certaines des approches utilisées par d'autres méthodologies sont applicables à la fabrication rapide. À la suite de ces observations, une méthodologie adaptée spécifiquement à la fabrication rapide est présentée. La méthodologie développée guide le concepteur à concevoir en termes de solutions optimales, non en termes de limitation, et à implémenter parallèlement des solutions pour consolider l'assemblage, prévenir les défaillances de l'assemblage et l'optimiser vers un but défini par le concepteur.  ABSTRACT: Rapid manufacturing is a manufacturing processes of which the market is in rapid growth. This process presents revolutionary fabrication possibilities, such as the possibility to create complex shapes and multi-material parts. Furthermore, with traditional manufacturing process which function by materiel removal, the most important factor influencing the cost of a part is the complexity. With rapid manufacturing the manufacturing cost is influenced primarily by the volume of the piece, adding complexity is therefore not a problem. Older methodologies help the designer to create pieces that are easy to manufacture using traditional manufacturing processes and thus to diminish the manufacturing cost, although none of these methodologies are applicable to rapid manufacturing. With rapid manufacturing it is preferable to guide the designer into adding complexity in order to improve the product. This thesis has for goal to develop a methodology which aims at helping the designer to bring ameliorations to his product and also to incorporate the advantages of rapid manufacturing in the product, which doesn't exist in the actual literature. To do so, an analysis of the different design methodologies and of methodologies related to rapid manufacturing is done in order to determine if some of the approaches used by these methodologies are also applicable to rapid manufacturing. Further on, from these observations a methodology adapted specifically for rapid manufacturing is presented. The proposed methodology guides the designer to conceive in terms of optimal solutions instead of in terms of limitation and to implement in parallel solutions to consolidate the assembly, prevent failures in the assembly and to optimize the assembly towards a user-defined goal. In order to verify that the methodology works


identifier: Boucher, V. (2010). Modélisation des propriétés électromagnétiques de métamatériaux à base de réseaux de fils ferromagnétiques  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les métamatériaux électromagnétiques consistent en des matériaux composites artificiels, structurés à l'échelle sous-longueur d'onde et caractérisés par des propriétés souvent inaccessibles aux matériaux naturels. Depuis la dernière décennie, leur étude suscite un vif engouement au sein de la communauté scientifique, motivé en grande partie par leur potentiel pour des applications novatrices dans les technologies de l'information et des télécommunications. Les métamatériaux s'appuient typiquement sur des arrangements astucieux d'inclusions métalliques ou de permittivité élevée à l'intérieur d'une matrice hôte. Leur structuration souslongueur d'onde permet de les assimiler à des milieux homogènes et de décrire leur réponse électromagnétique par l'intermédiaire de tenseurs de permittivité et de perméabilité effectives, qui dépendent à la fois des propriétés intrinsèques des inclusions, de leurs paramètres géométriques et de leurs interactions mutuelles. En particulier, des propositions basées sur l'utilisation d'inclusions ferromagnétiques ont ouvert la voie à une nouvelle classe de métamatériaux caractérisés par des paramètres constitutifs ajustables à l'aide d'un champ magnétique statique et par un spectre d'excitations magnétiques en hyperfréquences plus riche que celui des métamatériaux usuels, lesquels sont fond´es sur un effet de magnétisme artificiel à l'intérieur d'inclusions conductrices ou diélectriques. Parmi ces matériaux composites, les réseaux de fils ferromagnétiques apparaissent comme des candidats prometteurs pour des dispositifs en hyperfréquences, des applications magnéto-optiques et des métamatériaux à indice de réfraction négatif. Or, l'exploitation technologique de ces réseaux requiert des modèles théoriques capables de d´ecrire leur réponse à des ondes électromagnétiques. Dans ce contexte, l'objectif principal de ce travail consiste à établir des expressions analytiques pour la permittivité et la perméabilité effectives de métamatériaux à base de réseaux de fils ferromagnétiques conducteurs. En particulier, nous considérons le cas de fils de rayon allant de 10 nm à 100 μm, aimantés axialement et excités dans les hyperfréquences (1–100 GHz) par des champs électrique et magnétique respectivement parallèle et perpendiculaire à l'axe des fils. De même, nous portons une attention particulière à l'évaluation du potentiel de ces réseaux à présenter, sur une même plage de fréquences, des réponses électrique et magnétique simultanément ajustables par un champ magnétique statique. Pour ce faire, nous développons une procédure d'homogénéisation de type Maxwell Garnett, qui incorpore l'influence du retard électromagnétique (notamment de l'effet de peau) sur la réponse gyromagnétique tensorielle des fils individuels, de même que l'effet des interactions dipolaires interfils sur le comportement macroscopique de réseaux de taille finie. Il convient  ABSTRACT: Electromagnetic metamaterials consist of artificially designed subwavelength composite materials exhibiting properties not readily available in natural materials. Over the last decade, the study of their electromagnetic response has sparked considerable interest in the scientific community, owing largely to their potential for novel applications in information and telecommunication technologies. Metamaterials typically rely on clever arrangements of metallic or high-permittivity inclusions in a host matrix. Their subwavelength structure allows us to treat them as homogeneous media and to describe their macroscopic electromagnetic response in terms of effective permittivity and permeability tensors which depend upon the intrinsic properties of the inclusions, their geometrical parameters, and their mutual interactions. In particular, recent proposals for the use of ferromagnetic inclusions have opened the way to a new class of microwave metamaterials, characterized by magnetic-field-tuneable constitutive parameters and by a spectrum of magnetic excitations richer than that of most present-day metamaterials, which are based on the artificial magnetism exhibited by nonmagnetic conducting or dielectric inclusions. Among these magnetic composite materials, arrays of ferromagnetic wires emerge as interesting candidates for microwave devices, magnetooptical applications, and negative-refractive-index metamaterials. However, exploiting the full technological potential of such arrays requires theoretical models able to describe their response to electromagnetic waves. In this context, the main objective of this work is to establish analytical expressions for the effective permittivity and permeability of metamaterials based on arrays of ferromagnetic conducting wires. Specifically, we consider the case of axially magnetized wires of radius ranging from 10 nm to 100 μm, which are excited in the microwave frequency range (1– 100 GHz) by electric and magnetic fields parallel and perpendicular to the axis of the wires, respectively. We place special emphasis on evaluating the potential of these ferromagnetic wire arrays to produce, over the same frequency range, simultaneous magnetic-field-tuneable electric and magnetic responses. Our theoretical approach consists of developing a Maxwell-Garnett-type homogenization procedure, which incorporates the influence of electromagnetic retardation (e.g., skin effect) on the tensorial gyromagnetic response of the individual wires, as well as the effect of interwire dipolar interactions on the macroscopic behaviour of finite-size arrays. It must be noted that the treatment in the literature of these aspects is generally lacking or incomplete.


identifier: Labbé, P. (2010). Méthodologie de vérification d'un processus adaptatif utilisant la mesure de non-conformité  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Dans le contexte où l'on veut obtenir des résultats fiables d'analyses CFD pour des problèmes d'écoulements internes incompressibles à haut nombre de Reynolds, on s'intéresse à la mise en oeuvre rigoureuse et méthodique d'un processus adaptatif qui contrôle l'erreur d'interpolation pour un problème à un seul scalaire. Deux contributions originales ont été faites lors de la mise en oeuvre de ce processus. La première est une mesure universelle permettant de mesurer la conformité d'un élément du maillage par rapport aux spécifications du maillage données sous forme d'espace métrique. Cette mesure permet d'évaluer la qualité d'un maillage en regard de l'estimateur d'erreur utilisé. La mesure peut donc servir pour optimiser le maillage ou pour comparer des algorithmes d'optimisation en mesurant la conformité des maillages produits par ces algorithmes. La mesure s'applique à tous les types d'éléments et est insensible aux dimensions du domaine. La seconde contribution est une méthodologie de vérification du processus adaptatif qui utilise des solutions manufacturées afin de vérifier chaque étape du processus. Cette méthodologie mesure l'équirépartition de l'erreur d'approximation en calculant l'écart type de l'erreur maximum sur chaque élément afin de vérifier que le processus contrôle bel et bien l'erreur d'approximation. Un second article présentant cette méthodologie compare un raffinement uniforme, un processus d'adaptation isotrope et un processus d'adaptation anisotrope appliqués à des solutions manufacturées. On montre, pour une solution fortement anisotrope, qu'un maillage de 7000 tétraèdres étirés est aussi précis qu'un maillage de 4 millions de tétraèdres uniformes. De plus, on présente deux autres contributions originales réalisées durant cette thèse, mais qui n'ont pas fait l'objet de publication dans des revues scientifiques. Il s'agit, dans un premier temps, d'un algorithme récursif de basculement par division bipariétale permettant de trouver la façon optimale de basculer une arête lors de l'optimisation du maillage. Dans un deuxième temps, on présente une façon de visualiser les actions principales que l'estimateur d'erreur veut effectuer sur le maillage.  ABSTRACT: A method is presented that measures the non-conformity of a mesh with respect to a size specification map given in the form of a Riemannian metric. The measure evaluates the difference between the metric tensor of a simplex of the mesh and the metric tensor specified on the size specification map. This measure is universal because it is a unique, dimensionless number which characterizes either a single simplex of a mesh or a whole mesh, both in size and in shape, be it isotropic or anisotropic, coarse or fine, in a small or a big domain, in two or three dimensions. This measure is important because it can compare any two meshes in order to determine unequivocally which of them is better. Analytical and numerical examples illustrate the behavior of this measure. Also, a verification methodology that can assess the precision and convergence of an anisotropic adaptive process as it applies to control the interpolation error of sample 2D and 3D reaction-diffusion problems is presented. The technique of Manufactured Solution is used to devise problems for which the analytical solution is known. The convergence rate of the Hessian-based error estimator used in this unstructured mesh adaptation method is first evaluated through mesh convergence studies. Two distinct mesh quality measures are then used to illustrate mesh improvement in the course of adaptation. Finally, the overall adaptive process is verified by measuring the convergence rate of the interpolation error as well as measuring how evenly the interpolation error is distributed over all the elements of the adapted meshes. This verification process first demonstrates that each component of the adaptation process converges at a rate predicted by theory, and second how effective anisotropic adaptation is to reduce the number of nodes needed to achieve a prescribed error level. The proposed verification methodology constitutes a quantitative approach to compare mesh adaptation algorithms among them, both in terms of efficiency and quality of the resulting mesh. Two other contributions are presented that complement the work done in this thesis. The first contribution is a tridimentionnal edge swapping procedure that recursively subdivides the edge swapping problem by finding two parietal pairs of tetraedra of optimal quality. The second contribution is the visualisation of the principal actions that an error estimator wants to perform on a mesh.


identifier: Michel, L. (2010). Étude et caractérisation des phénomènes d'éclatement et d'explosion des pneus de camion.  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Ce mémoire présente les résultats des activités de recherche sur les phénomènes d'éclatement et d'explosion de pneus de véhicules lourds. Réalisé conjointement par l'Institut de Recherche en Santé et en Sécurité du Travail (IRSST) de Montréal et l'École Polytechnique de Montréal, il permet une mise à jour des connaissances sur ces deux types d'évènements, explique leurs causes et leurs conséquences et présente des résultats pertinents pour l'évaluation du risque. Les résultats qui sont présentés ici reposent à la fois sur des essais expérimentaux et des analyses numériques utilisant la méthode des éléments finis. Un essai d'explosion a été mené au Laboratoire Canadien de Recherche sur les Explosifs (LCRE) à Ottawa, Canada pour caractériser le phénomène d'explosion. Le phénomène d'éclatement par surpression, qui est un cas particulier d'éclatement, a été étudié à l'aide d'un test d'éclatement hydrostatique et d'analyses microscopiques. Les analyses numériques ont été réalisées avec le logiciel Altair Radioss pour compléter et/ou valider les résultats de ces essais. Les éclatements et explosions de pneus, bien que relativement rares, sont très dangereux du fait de leur imprévisibilité. Ils interviennent la plupart du temps lors de la réparation, de l'entretien ou encore du remplacement des roues du véhicule. La cause la plus commune des phénomènes d'éclatement ou d'explosion de pneu est un apport de chaleur au système pneu-jante. Cet apport de chaleur déclenche des réactions chimiques qui dégradent le caoutchouc des pneus produisant alors des gaz et des matières inflammables. Il s'agit principalement des réactions de pyrolyse, thermo-oxydation et de combustion. En s'ajoutant au phénomène d'expansion thermique et à la diminution des propriétés mécaniques du pneu par divers facteurs, les gaz produits contribuent à l'augmentation de la pression dans le pneu et augmentent ainsi le risque d'éclatement ou d'explosion. A l'aide des données retrouvées dans la littérature et celles de l'analyse numérique, le scénario menant à l'explosion d'un pneu a pu être établi. Une telle explosion survient lorsque les trois conditions critiques de concentration et de température des matières inflammables et de concentration en oxygène sont simultanément réunies. L'onde de pression résultant du mélange  ABSTRACT: This thesis presents the results of research activities on heavy vehicles tire blowout and explosion phenomena. Produced jointly by the Institut de Recherche en Santé et en Sécurité du Travail (IRSST) in Montreal, Canada and École Polytechnique de Montréal, it allows an update of knowledge on these two kinds of events, explains their causes and their consequences and presents relevant results to risk assessment. The results presented in this thesis are based on both experimental tests and numerical analyses using the finite element method. An explosion test was performed in the Laboratoire Canadien de Recherche sur les Explosifs (LCRE) in Ottawa, Canada to provide relevant scientific data for a better understanding of the tire failure mechanism in the case of explosion. Tire blowouts include the tire burst due to over-pressurization. The latter has been studied using a hydrostatic burst test and microscopic analyses. A numerical analysis was conducted using the Altair Radioss software to complete and/or validate the results of these tests. Even though relatively rare, tire blowouts and explosions are very dangerous because of their unpredictability. They usually occur during the repair, maintenance or replacement of wheels of the vehicle. A heat input to the tire-rim assembly is the main contributor to the final blowout or explosion event. The heat input generates chemical reactions which degrade tire rubber and produce flammable gases. Three types of thermo-chemical reactions have been identified as potential sources. They are pyrolysis, thermo-oxidation and combustion. The gases these reactions produce add to the increase in pressure inside the tire due to thermal expansion of the air and, consequently, the risk of blowout or explosion. Information gathered in the literature and numerical simulation results allowed to propose a scenario for an explosion. Such an explosion occurs if the three critical conditions of concentration, temperature of flammable gas and oxygen concentration occur simultaneously.


identifier: Trillon, A. (2010). Reconstruction de défauts à partir de données issues de capteurs à courants de Foucault avec modèle direct différentiel  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La tomographie par courants de Foucault peut être utilisée pour évaluer la forme et le volume de défauts dans des plaques métalliques de générateur de vapeur de centrale nucléaire. L'objectif du travail présenté est de cartographier la distribution d'une grandeur représentative du défaut, ici la conductivité relative. Ce problème est difficile à résoudre car mal-posé et non-linéaire. Afin de le résoudre un modèle numérique est nécessaire. Nos travaux ont tout d'abord consisté à étudier les modèles directs existants pour choisir le plus adapté à notre cas. Il s'est avéré que les méthodes différentielles, différences finies ou éléments finis, étaient les plus adaptées à notre cas. Une fois que le modèle direct a été choisi, nous avons adapté les méthodes de type contrast source inversion (CSI) à ce modèle, puis proposé un nouveau critère à minimiser. Les méthodes de type CSI sont basées sur la minimisation de l'erreur quadratique pondérée des équations du modèle, observation et couplage. Par construction, elles autorisent une erreur sur ces équations. Il apparaît que les résultats de reconstruction s'améliorent lorsque l'erreur sur l'équation de couplage diminue. Afin de contraindre cette équation en évitant des problèmes de conditionnement, on a eu recours à une technique de Lagrangien augmenté. Enfin, le caractère mal-posé de ce problème peut être contourné en introduisant des informations a priori adéquates notamment sur la forme générale des défauts à reconstruire ainsi que sur les valeurs possibles de la conductivité relative. L'efficacité des méthodes développées est illustrée avec des cas simulés en 2D.  ABSTRACT: Eddy current tomography can be employed to caracterize flaws in metal plates in steam generators of nuclear power plants. Our goal is to evaluate a map of the relative conductivity that represents the flaw. This nonlinear ill-posed problem is difficult to solve and a forward model is needed. First, we studied existing forward models to chose the one that is the most adapted to our case. Finite difference and finite element methods matched very good to our application. We adapted contrast source inversion (CSI) type methods to the chosen model and a new criterion was proposed. These methods are based on the minimization of the weighted errors of the model equations, coupling and observation. They allow an error on the equations. It appeared that reconstruction quality grows with the decay of the error on the coupling equation. We resorted to augmented Lagrangiantechniques to constrain coupling equation and to avoid conditioning problems. In order to overcome the ill-posed character of the problem, prior information was introduced about the shape of the flaw and the values of the relative conductivity. Efficiency of the methods are illustrated with simulated flaws in 2D case.


identifier: Côté, M.-C. (2010). Utilisation de langages formels pour la modélisation et la résolution de problèmes de planification de quarts de travail  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La planification d'horaires de personnel représente un défi pour plusieurs organisations. Dans cette thèse, nous étudions différentes variantes du problème de planification des quarts de travail. La planification des quarts de travail représente la sélection d'un ensemble de quarts couvrant une période de temps, typiquement une journée à une semaine, divisée en périodes de durées égales pour lesquelles un nombre d'employés requis est donné. Un quart est défini par son heure de début, sa durée et par sa composition en termes d'affectation de pauses et d'activités de travail.  Nous divisons les problèmes de planification de quarts en quatre classes. Premièrement, les problèmes où les employés sont considérés comme identiques et les problèmes où les employés ont des caractéristiques individuelles qui les distinguent et qui doivent être prises en compte dans la sélection des quarts. Nous référons à la première classe de problèmes comme étant des problèmes anonymes et à la seconde, comme étant des problèmes personnalisés. Ensuite, nous différencions les problèmes de planification de quarts mono-activité et multi-activités. La première classe de problèmes est en fait un cas particulier de la deuxième. Elle détermine quelles périodes du quart sont affectées à des activités de travail et quelles périodes sont affectées à des activités de repos (repos, pause, repas), alors que les problèmes de planification de quarts multi-activités définissent pour chaque période de travail du quart quelle activité de travail, parmi un ensemble d'activités de travail pouvant être effectuées, lui est affectée. Dans ce cas, pour chaque activité de travail et pour chaque période de temps sur lequel s'étend l'horaire, le nombre d'employés requis est donné.  Dans cette thèse, nous abordons chacune des classes de problèmes de planification de quarts à l'aide de différentes approches, toutes basées sur la formulation des contraintes restreignant la formation des quarts par des outils issus de la théorie des langages formels. En effet, à l'aide d'automates et de grammaires, nous pouvons définir des langages qui sont composés d'un ensemble de mots représentant des quarts respectant les contraintes de notre problème. Les automates et les grammaires sont des outils très expressifs qui permettent de formuler plusieurs concepts relatifs à notre contexte de manière relativement naturelle. Plus précisément, notre première contribution présente comment, à partir d'un automate ou d'une grammaire définissant les règles régissant la composition des quarts pour un problème, nous pouvons générer automatiquement un modèle linéaire en nombres entiers basé sur des variables d'affectation binaires dans une structure de graphe qui encode tous les quarts permis par ce problème. La transformation d'un automate ou d'une grammaire en modèle de programmation mathématique est inspirée de structures de la programmation par contraintes. Un exemple experimental de problème de planification de quarts multi-activités montre la puissance de la modélisation utilisant les langages formels. En effet, cette nouvelle approche de modélisation permet d'aborder des règles très complexes en ce qui concerne la composition des quarts multi-activités. Malgré que l'intérêt de ce type de modèles dans le contexte de problèmes de planification de quarts soit indéniable, les résultats expérimentaux soulèvent les limites de la formulation décomposée par employés et définie avec des variables d'affectation binaires. En effet, avec le nombre d'employés et le nombre d'activités de travail qui augmentent, le modèle devient difficile à résoudre directement.  ABSTRACT: Personnel scheduling is a challenging problem for many organizations. In this thesis, we address different versions of the shift scheduling problem. The shift scheduling problem is to select a set of shifts to cover a planning horizon, typically from 1 to 7 days, divided into periods of equal length for which the required numbers of employees are given. A shift is defined by its starting time, its duration and its composition. Its composition is defined by the position of the breaks and work activities within the shift.  We divide the shift scheduling problems into four main classes. First, we distinguish the problems where the employees are considered to be identical from the problems where each employee has individual characteristics that must be taken into account when assigning them to shifts. We call the first class the anonymous problems and the second one, the personalized problems. Then, we differenciate two other classes of problems, the mono-activity  and the multi-activity shift scheduling problems. The former is a particular case of the latter and consists in specifying the work and rest periods to assign to the shifts. In the multi-activity case, we are also interested in a set of distinct work-activities to be performed. So, not only should we specify if the shift is assigned to a work-activity or not at a given period, but we must specify to which work-activity it is assigned. In this case, for each work-activity and each period, the required number of employees is given. In this thesis, we study each of these classes of shift scheduling problems with different approaches where constraints on shift construction are formulated with tools based on formal languages. In fact, using automata and grammars, we define languages composed of words that represent allowed shifts for our problem. More precisely, our first contribution presents how, from a finite automata or a context-free grammar defining the rules constraining the construction of shifts for a given problem, one can automatically generate an integer programming model based on binary assignment variables in a graph structure embedding every allowed shift for this problem. The transformation of an automaton or a grammar into a mathematical programming model is inspired by structures from constraint programming. Experiments on a multi-activity shift scheduling problem show that formal language based modeling is very powerful and allows us to address complex rules in the construction of multi-activity shifts. However, while the relevance of our modeling approach is clear, the experimental results reveal some limitations on the scalability of the formulation based on binary assignment variables and decomposed on employees. In fact, when the number of employees and the number of work-activities grow, the model is hard to solve directly.


identifier: Figueroa, M. Y. (2010). Interopérabilité des systèmes de planification réactive de la logistique des interventions d'urgence  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le type d'urgences qu'un réseau de transport en commun peut subir est varié. De même, les conséquences sur la compagnie qui rend le service et sur la clientèle qui en fait usage. Bien que les urgences ne puissent pas se planifier, la minimisation des effets négatifs sur le réseau et sur la clientèle doit toujours être une priorité. Dans ce contexte, les systèmes d'information de la société qui gère le service de transport en commun peuvent jouer un rôle très important. Ces systèmes aident à obtenir une connaissance approfondie du fonctionnement du réseau et ils peuvent aussi participer à la résolution des situations inattendues en temps réel.  Cependant, la communication entre les systèmes d'information d'une entreprise, et même avec les systèmes informationnels de compagnies partenaires, ne se produit toujours pas d'une manière fluide et efficiente. Le but de ce mémoire est donc d'évaluer l'interopérabilité des systèmes informationnels d'une société de transport en commun. Cette évaluation se fait en regardant spécialement le rôle de ces systèmes dans un contexte de situations d'urgences. Le Réseau de Transport de Longueuil a d'ailleurs collaboré pour la réalisation de ce mémoire. La méthodologie choisie pour faire cette évaluation est la structure d'interopérabilité d'entreprise ATHENA. Cette structure comporte huit étapes dont nous en avons retenu les deux premières. Les deux étapes choisies couvrent en effet la portée de cette recherche en analysant l'interopérabilité interne et l'interopérabilité externe de la société étudiée. Pour mesurer l'interopérabilité interne du RTL, la structure d'interopérabilité ATHENA propose le modèle de maturité d'interopérabilité d'entreprise – EIMM. Ce modèle évalue l'état de l'interopérabilité en cinq domaines d'inquiétude : la stratégie d'affaires, l'organisation et les compétences, les systèmes et la technologie, l'environnement légal, de sécurité et de confiance et, finalement, la modélisation d'entreprise. De plus, ce modèle propose cinq niveaux de maturité d'interopérabilité possibles (du plus bas au plus haut) : effectué, modelé, intégré, interopérable et optimisé.  ABSTRACT: The type of emergencies that affects a public transit network is broad. It is broad as well the type of consequences for the company and for its clients. Even though these emergencies cannot be planned, the minimization of the negatives effects should always be a priority. In this context, the public transit company's information systems play an important role. These systems help to gather a deep knowledge about the running of the network and they can also participate in the real time solution of unexpected situations. However, the communication between the company's different information systems, and even more, the communication with others partners' information systems, is not always performed in a seamless fashion. Thus, the objective of this dissertation is to evaluate the interoperability of a public transit company's information system. This evaluation is done by observing the roles of these systems under an emergency context. The Réseau de Transport de Longueuil, RTL, has collaborated in the execution of this research. The methodology that was chosen to do this evaluation is the enterprise interoperability framework ATHENA. This framework includes eight steps of which we have developed the first two. These two steps cover the scope of this research by analyzing both the internal and the external interoperability of the studied company. In order to measure the RTL's internal interoperability, the ATHENA framework proposes the Enterprise Interoperability Maturity Model, EIMM. This model evaluates the state of the interoperability in five areas of concern: business strategy and processes; organization and competences; systems and technology; legal environment, security and trust; and finally, enterprise modelling. Moreover, this model proposes five possible interoperability maturity levels (from the lowest to the highest): performed, modelled, integrated, interoperable and optimising.


identifier: Al-Terkawi Hasib, O. (2010). Design and Implementation of Integrated High Efficiency Low-voltage CMOS DC-DC Converters  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: De nos jours, les appareils portatifs sont utilisés dans plusieurs applications. Ils utilisent en général une batterie qui doit être remplacée ou rechargée régulièrement. Dans le cas d'applications biomédicales, la durée de vie de la batterie est un paramètre critique. Pour un appareil implantable, une longue durée de vie est un objectif primordial. Cet objectif est généralement atteint en réduisant la consommation de puissance des circuits constituant l'implant. Parmi les diverses techniques existantes qui permettent la réduction de la consommation en puissance des circuits CMOS, on retrouve la technique d'ajustement dynamique de la tension (dynamic voltage scaling - DVS). En réduisant la tension d'alimentation, la consommation totale des circuits peut être diminuée. Cependant cette technique ne peut être implémentée sans faire appel à des circuits dédiés à une gestion intelligente de l'énergie. Dans ce contexte, l'utilisation de convertisseurs de tension DC-DC devient nécessaire pour économiser la charge de la batterie. Mais pour garantir une réduction effective de la consommation globale, des convertisseurs DC-DC de haute efficacité doivent être utilisés. A cette contrainte se rajoute la miniaturisation en utilisant des circuits hautement intégrés pour les applications telles que les implants biomédicaux. Le défi réside dans la conception d'un convertisseur DC-DC totalement intégré tout en assurant une haute efficacité sur une grande plage de tension de sortie. De plus, les appareils tels que les implants électroniques fonctionnent souvent en mode de veille pour réduire la consommation, entrainant ainsi des variations conséquentes de la charge du convertisseur DC-DC. Ceci rajoute un défi supplémentaire pour le maintient d'une haute efficacité de la conversion DC-DC à faible charge.   Dans ce mémoire, nous présentons la conception détaillée d'un convertisseur DC-DC hautement efficace et totalement intégré dans une technologie CMOS à faible tension. Nous proposons une implémentation originale et totalement intégrée d'un convertisseur DC-DC à capacités commutés (switched capacitor - SC) opérant avec un contrôle asynchrone. L'efficacité du convertisseur est maintenue élevée en ajustant sa topologie et sa fréquence d'opération selon la charge.  ABSTRACT: Today, battery-powered portable devices are used in many applications. In applications like biomedical implants, the battery life is a major concern. Since replacing the battery of an implant needs a surgical procedure, a long battery life is a goal that all implants try to achieve. This is normally done by reducing the power dissipation in the implant's circuitry. One of the various techniques that exist for reducing the power consumption in CMOS circuitry is the dynamic voltage scaling (DVS) technique. By reducing the supply voltage, the overall power consumption of the circuits can be decreased. This technique cannot be implemented without power management blocks. The use of DC-DC converters  becomes a must to save battery power. The overall power reduction can be improved by introducing high efficiency DC-DC converters. Moreover, to provide patients with the most comfort, small integrated circuits should be used in applications such as biomedical implants.  The challenging aspect of designing integrated DC-DC converters is keeping the efficiency high while providing an adjustable output voltage. Additionally, devices such as electronic implants go in and out of stand-by mode to reduce power consumption. From the perspective of the DC-DC converter, the output load power is varying according to the mode of operation of the implant. This adds another challenge of sustaining the DC-DC conversion efficiency high under various loading conditions. At very light loads, preserving a high conversion efficiency is a challenge. In this master thesis, a detailed design of a high-efficiency low-voltage fully integrated DC-DC converter is presented. A unique structure of a fully integrated switched-capacitor (SC) DC-DC converter with asynchronous control is proposed. The efficiency of the converter is maintained high by adjusting the converter topology and operating frequency according to the loading conditions. The proposed SC DC-DC converter uses three different topologies to achieve three different conversion ratios. By doing so, the converter maintains high conversion efficiency at various output voltage levels. Also, an adaptive operating frequency is used by the asynchronous control to reduce efficiency losses at various loading conditions.