Automatic Inference of Graph Models for Complex Networks with Genetic Programming

Complex networks can arise naturally and spontaneously from all things that act as a part of a larger system. From the patterns of socialization between people to the way biological systems organize themselves, complex networks are ubiquitous, but are currently poorly understood. A number of algorithms, designed by humans, have been proposed to describe the organizational behaviour of real-world networks. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. The algorithms, called graph models, represent significant human effort. Deriving accurate graph models is non-trivial, time-intensive, challenging and may only yield useful results for very specific phenomena. An automated approach can greatly reduce the human effort required and if effective, provide a valuable tool for understanding the large decentralized systems of interrelated things around us. To the best of the author's knowledge this thesis proposes the first method for the automatic inference of graph models for complex networks with varied properties, with and without community structure. Furthermore, to the best of the author's knowledge it is the first application of genetic programming for the automatic inference of graph models. The system and methodology was tested against benchmark data, and was shown to be capable of reproducing close approximations to well-known algorithms designed by humans. Furthermore, when used to infer a model for real biological data the resulting model was more representative than models currently used in the literature.

Canadian National (CN) records, 1974-1989.

Canadian National Railway Company (CN) was incorporated in 1919 as a Crown Corporation. The company was formed during the period after World War I and integrated two of the country’s largest railroads, Canadian Northern and Grand Trunk. CN is the largest rail network in Canada and the only transcontinental network in North America. As the use of railways declined, CN diversified its activities during the 1970s, becoming involved in telecommunications , hotels and oil exploration. The next decade saw a period of financial stability, however, the 1990s were a period of decreased profitability. As part of a restructuring to alleviate the company’s financial difficulties , it was privatized in 1995.

Les politiques commerciales, industrielles, régionales, et d'adaptation dans le Rapport de la Commission MacDonald: un Commentaire

The effect of long discussions between commissioners with divergent views on certain issues is obvious in the report: it is more oriented towards the short term than expected. Undue attention was paid to trade liberalization with the U.S., a region of the world which the report describes as one in relative decline. The report does not deal with a scenario wherein trade liberalization with the U.S.A. is seen as a necessary transitory measure leading towards diversification of Canada's trade relation away from North America. Such an examination would point to a different approach to the U.S.A. in the short term. The report does not deal with services, information and te telecommunication which are fundamental to the economic development of Canada. There is also overemphasis on commercial policy and relative neglect on the use of domestic policies, among them industrial policy, in the pursuit of Canada's objectives. The report notes the interdependence between commercial and domestic policies and rightly recommend that provinces must, as a consequence, be involved in trade liberalization discussions. It is argued that the report underestimates the pressures for extra- territorial application of U.S. policies to Canada and the pressure for harmonization of policies which would follow trade liberalization. The report pays no attention to the implications of offshore investment going primarily to the U.S.A. and does not pay adequate attention to the role of investment to deal with adjustment problems. Available studies would have allowed the commissioners to clarify the determinants of investment decisions by Canadian head offices who have established subsidiaries in the U.S.A. but they were not examined. Little attention was paid to the role of transnationals and intrafirm trade in examining the implications of trade liberalization. The importance given to the reduction of regional disparities in earned incomes is welcome. However, the recommandation to leave regional development to provinces and municipalities denies the importance of national policies in the attainment of regionalization job equilization the impact of new CAD-CAM-telecommunications technologies on location decisions for the production of goods and services was not examined. Nor were the extent of and changes in interregional (i.e. interprovincial and more particularly province-state) trade flows examined. Knowledge of these patterns is essential in the formulation of industrial and adjustment policies in light of trade liberalization. The report recommends passive industrial adjustment policies focussed on the U.S., a reflection of the concern of the commissioners for the short term and the U.S.A. The implementation of the report's recommendations would lead to a centralization of economic power at the nationallevel, hence the need to establish a renewed senate to favour the formulation of regionally sensitive national policies.

Communication and Economic Growth.

Overs the past millennium, each of the three centuries of most rapid demographic growth in the West Coincided with the diffusion of a new communications technology. This paper examines the hypothesis of Harold Innis (1894-1952) that there is two-way feeback between such innovations and economic growth.

Optimization of p-cycle protection schemes in optical networks

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème.

Le discours organisationnel et la construction de la responsabilité sociale d’entreprise : une comparaison d’entreprises chiliennes et canadiennes

Cette recherche se propose d’étudier, d’un point de vue ethnométhodologique, la manière dont des entreprises de deux pays (le Chili et le Canada) et trois secteurs productifs (Banque, télécommunications et forestier) construisent leur responsabilité sociale à partir de leur discours, c’est à dire à la manière dont elles s’auto-positionnent par rapport à cette question. Sans vouloir généraliser, la comparaison des entreprises canadiennes et chiliennes a pour objectif de savoir dans quelle mesure des entreprises établies dans des pays représentant différents degrés de développement construisent des discours différents ou similaires par rapport à la question de leur responsabilité sociale. Pour tenter de répondre à cette question, nous étudierons ce sujet à travers l’analyse du message ou de la lettre du Président Directeur Général (PDG) présentées sur leurs rapports de responsabilité sociale, ce qui nous permettra de montrer comment les entreprises construisent et s’auto-positionnent, dans leur discours officiel, par rapport à la question de leur responsabilité sociale. En nous basant sur ces analyses, nous discuterons des similitudes et des différences identifiées et nous montrerons ainsi dans quelle mesure la responsabilité sociale est construite sur des références globales plus larges, ou sur des contingences qui émergent du contexte.

Étude longitudinale du lien entre la satisfaction intrinsèque et la satisfaction extrinsèque au travail et l’intention de quitter chez les travailleurs du secteur des TIC

Le but de ce mémoire est de comprendre l’influence de la satisfaction intrinsèque et de la satisfaction extrinsèque sur l’intention de quitter des travailleurs. Afin d’étudier ce sujet, nous avons formulé trois hypothèses basées sur la théorie des attentes et la théorie des deux facteurs d’Herzberg. La première hypothèse stipule que la satisfaction intrinsèque fait diminuer l’intention de quitter des travailleurs. La seconde hypothèse est formulée à l’effet que la satisfaction extrinsèque fait diminuer l’intention de quitter des travailleurs. La dernière hypothèse stipule que la satisfaction intrinsèque a une influence plus importante sur l’intention de quitter des travailleurs que la satisfaction extrinsèque. Les données utilisées afin de tester nos hypothèses de recherche ont été collectées dans le cadre d’une étude plus vaste portant sur « les liens entre la rémunération, la formation et le développement des compétences et l’attraction et la rétention d’employés clés ». L’entreprise au sein de laquelle les données ont été collectées est dans le domaine des technologies de l’information et des communications (TIC) à Montréal. Les employés interrogés sont les nouveaux employés embauchés par l’entreprise. Les résultats de notre mémoire confirment deux de nos hypothèses. Ainsi, nos résultats ont démontré que la satisfaction intrinsèque fait diminuer l’intention de quitter des travailleurs d’ici six mois, un an et deux ans. De plus, nos résultats ont démontré que la satisfaction intrinsèque a une influence plus importante sur l’intention de quitter que la satisfaction extrinsèque. Par contre, une de nos hypothèses est partiellement confirmée. En effet, nos résultats ont démontré que la satisfaction extrinsèque fait seulement diminuer l’intention de quitter d’ici un an et deux ans et n’a aucune influence significative sur l’intention de quitter d’ici six mois. Le soutien organisationnel perçu est une variable qui a également une forte influence sur l’intention de quitter des travailleurs. Pour terminer, la conclusion de ce mémoire présente en quoi nos résultats peuvent être utiles aux gestionnaires des ressources humaines et des relations industrielles.

Développement d’une grille pour l’analyse de la culture e-learning dans des forums de discussion en ligne

La formation à distance (FAD) est de plus en plus utilisée dans le cadre de la formation des enseignants aux technologies de l’information et de la communication (TIC). Dans les pays en voie de développement, elle permet non seulement de réduire les coûts par rapport à une formation traditionnelle, mais aussi de modéliser des pratiques pédagogiques exemplaires qui permettent de maximiser le recours aux TIC. En ce sens, la formation continue des enseignants aux TIC par des cours à distance qui intègrent des forums de discussion offre plusieurs avantages pour ces pays. L’évaluation des apprentissages réalisés dans les forums reste cependant un problème complexe. Différents modèles et différentes procédures d’évaluation ont été proposés par la littérature, mais aucun n’a encore abordé spécifiquement la culture e-learning des participants telle qu’elle est définie par le modèle IntersTICES (Viens, 2007 ; Viens et Peraya, 2005). L’objectif de notre recherche est l’élaboration d’une grille opérationnelle pour l’analyse de la culture e-learning à partir des contenus de différents forums de discussion utilisés comme activité de formation dans un cours à distance. Pour développer cette grille, nous utiliserons une combinaison de modèles recensés dans la revue de littérature afin de circonscrire les principaux concepts et indicateurs à prendre en compte pour ensuite suivre les procédures relatives à l’analyse de la valeur, une méthodologie qui appelle la production d’un cahier des charges fonctionnel, la production de l’outil, puis sa mise à l’essai auprès d’experts. Cette procédure nous a permis de mettre sur pied une grille optimale, opérationnelle et appuyée par une base théorique et méthodologique solide.

Construire un système réglementaire : l'état et l'industrie télégraphique au Canada, 1846-1916

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Transfert de connaissances dans les entreprises multinationales : efficacité et influence des facteurs contextuels

Dans la présente recherche, nous nous sommes penchés sur le processus du transfert intra-organisationnel de connaissances au sein d’entreprises multinationales (EM). Partant du triple constat suivant : les connaissances organisationnelles constituent un avantage stratégique (Barney, 1991 ; Bartlett et Ghoshal, 1998), les transferts intra-organisationnels constituent la raison d’être des EM (Gupta et Govindarajan, 2000), lesquelles ont accès à un vaste bassin de connaissances disséminées à travers le monde par le biais de leurs filiales et les mécanismes organisationnels internes sont plus efficaces que ceux du marché (Williamson, 1987 ; Casson, 1976) pour transférer des connaissances entre unités organisationnelles; nous nous sommes intéressés aux facteurs pouvant affecter l’efficacité de ce processus de transfert. Ayant identifié, lors de notre revue des écrits théoriques, une multitude d’approches permettant d’appréhender ce phénomène, nous proposons, dans notre recherche, un modèle théorique intégrant les trois étapes propres au processus de transfert, soit : la détermination des connaissances à transférer, la sélection des mécanismes de transfert appropriés et, finalement, l’évaluation, d’une part, de l’efficacité des transferts et, d’autre part, de l’ensemble des facteurs contextuels ayant un impact sur l’efficacité de ce processus. Sur le plan théorique, cette recherche oppose deux courants dominant ce champ disciplinaire. L’approche stratégique, exprimée par la théorie des ressources, met l’accent sur l’importance prépondérante des facteurs organisationnels internes sur l’efficacité de toute action organisationnelle (Bartlett et Ghoshal, 1998 ; Barney, 1991). Cette approche s’oppose au courant institutionnel, lequel considère plutôt que les choix et les actions organisationnels sont surtout conditionnés par les contraintes de l’environnement externe (Ferner, 1997; Kostova, 1999; Scott, 1991). Les résultats de notre recherche démontrent que, malgré l’existence de contraintes de nature institutionnelle et culturelle, l’efficacité du processus de transfert des connaissances associées à la gestion des ressources humaines relève davantage des conditions organisationnelles internes et, plus particulièrement, de l’implication de la haute direction, du rôle accordé à la fonction RH et de l’alignement entre la stratégie corporative, la stratégie RH et la culture organisationnelle. Sur le plan méthodologique, il s’agit d’une recherche exploratoire qualitative menée auprès de trois EM (2 canadiennes et 1 française) oeuvrant dans les secteurs de la métallurgie et des télécommunications. Les données empiriques proviennent de 17 entrevues approfondies que nous ont accordées, au Canada, en France, en Allemagne et en Suisse des cadres responsables de la gestion des ressources humaines, affectés au siège social des EM en question ou œuvrant au sein de leurs filiales, et de sources documentaires secondaires.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

WiMAX ou l’évolution des réseaux sans-fil ?

L'adoption des technologies de réseaux sans-fil de type WiFi a connu une croissance impressionnante ces dernières années. Cette vague de popularité ne semble pas vouloir s'estomper, il est estimé que 84 millions d’appareils seront vendus en 2007 totalisant des revenus de 3.7 milliards de dollars. Devant cette forte demande, les fabricants d’appareils de télécommunications ont songés à développer des produits encore plus performants. Appuyé par la norme IEEE 802.16, un consortium du nom de WiMAX Forum a regroupé 350 membres dans le but de promouvoir des produits standardisés portant la marque WiMAX. À l'inverse des premières versions du WiFi, le WiMAX sera doté de mécanismes de sécurité beaucoup plus fiables. L'avantage du WiMAX, comme pour plusieurs de ses concurrents, repose sur sa capacité d'opérer sur une large bande de fréquences, réglementées ou non. Sa portée théorique de 50 Km et son débit escompté de 75 Mbit/s a capté l'attention des fournisseurs de services qui cherchent à réduire leurs coûts d'exploitations mais également de divers organismes gouvernementaux qui espèrent améliorer les services de communications dans les communautés des régions éloignées. Grâce à l'appui du ministre des Affaires indiennes et du nord canadien, le territoire du Nunavut a mis sur pied un réseau à large bande qui dessert actuellement l’ensemble de ses 29 communautés sur tout son territoire. La possibilité de couvrir une superficie de plusieurs kilomètres ramène à la surface le concept d’omniprésence ou de « Pervasive computing ». Cette notion représente l’intégration des technologies dans notre entourage afin de rendre nos interactions avec celle-ci plus naturelles. Nos déplacements dans cet environnement pourraient être facilités puisque les ordinateurs seraient en mesure de détecter et réagir à notre présence pour nous offrir des solutions personnalisées. Les déploiements de réseaux de type WiMAX sont déjà en cours dans plusieurs pays, d'après la situation actuelle du marché, il est envisageable de voir une forte adoption de cette forme de diffusion d’informations dans les prochaines années. Le présent document trace un résumé des applications liées au WiMAX et discute de certaines problématiques engendrées par ce type de réseau.

Étude longitudinale du lien entre la justice organisationnelle et le niveau d’engagement organisationnel chez les travailleurs du secteur des technologies de l’information et des communications

L’objectif de ce mémoire est de comprendre l’impact de la justice organisationnelle sur l’engagement organisationnel des travailleurs du secteur des technologies de l’information et des communications (TIC). Afin d’étudier ce sujet, trois hypothèses de recherche ont été formulés à partir des théories suivantes : 1- la théorie des attentes d’Adams (1965), 2- la théorie de l’échange social de Blau (1964) et 3- la théorie de Leventhal (1980). La première hypothèse stipule que, toutes choses étant égales par ailleurs, la justice distributive fait augmenter l’engagement affectif des travailleurs du secteur des TIC. La seconde hypothèse indique que toutes choses étant égales par ailleurs, la justice procédurale fait augmenter l’engagement affectif des travailleurs du secteur des TIC. La dernière hypothèse énonce que toutes choses étant égales par ailleurs, la justice procédurale a un impact plus important sur l’engagement affectif des travailleurs du secteur des TIC que la justice distributive. Les données utilisées proviennent d’une enquête par questionnaires électroniques auprès de l’ensemble des nouveaux employés d’une entreprise d’envergure internationale du secteur des TIC ayant un établissement à Montréal. Les employés ont été sondés à trois reprises. Les résultats indiquent que la justice distributive fait augmenter l’engagement affectif auprès des travailleurs, ce qui appuie la première hypothèse. Ils démontrent également qu’il n’existe aucune relation statistiquement significative entre la justice procédurale et l’engagement affectif. Seule la justice distributive a un effet sur l’engagement affectif du travailleur. Les résultats montrent l’existence de relations significatives et positives entre trois des variables de contrôle et l’engagement affectif. Il s’agit de : 1- travail sous supervision, 2- soutien organisationnel perçu et 3- satisfaction intrinsèque.

Méthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacité

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.

Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

Le problème de tournées de véhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problèmes les plus étudiés en recherche opérationnelle, et ce, en raison de son intérêt méthodologique et de ses retombées pratiques dans de nombreux domaines tels que le transport, la logistique, les télécommunications et la production. L'objectif général du VRP est d'optimiser l'utilisation des ressources de transport afin de répondre aux besoins des clients tout en respectant les contraintes découlant des exigences du contexte d’application. Les applications réelles du VRP doivent tenir compte d’une grande variété de contraintes et plus ces contraintes sont nombreuse, plus le problème est difficile à résoudre. Les VRPs qui tiennent compte de l’ensemble de ces contraintes rencontrées en pratique et qui se rapprochent des applications réelles forment la classe des problèmes ‘riches’ de tournées de véhicules. Résoudre ces problèmes de manière efficiente pose des défis considérables pour la communauté de chercheurs qui se penchent sur les VRPs. Cette thèse, composée de deux parties, explore certaines extensions du VRP vers ces problèmes. La première partie de cette thèse porte sur le VRP périodique avec des contraintes de fenêtres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fenêtres de temps (VRPTW) puisqu’il considère un horizon de planification de plusieurs jours pendant lesquels les clients n'ont généralement pas besoin d’être desservi à tous les jours, mais plutôt peuvent être visités selon un certain nombre de combinaisons possibles de jours de livraison. Cette généralisation étend l'éventail d'applications de ce problème à diverses activités de distributions commerciales, telle la collecte des déchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la première partie de cette thèse est le développement d'une méta-heuristique hybride dans la quelle un ensemble de procédures de recherche locales et de méta-heuristiques basées sur les principes de voisinages coopèrent avec un algorithme génétique afin d’améliorer la qualité des solutions et de promouvoir la diversité de la population. Les résultats obtenus montrent que la méthode proposée est très performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problème. La deuxième partie de cette étude a pour but de présenter, modéliser et résoudre deux problèmes riches de tournées de véhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dépendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problèmes sont connus respectivement sous le nom de Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW) et de Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS). Ces deux problèmes proviennent de la planification des opérations de systèmes logistiques urbains à deux niveaux. La difficulté de ces problèmes réside dans la manipulation de deux ensembles entrelacés de décisions: la composante des tournées de véhicules qui vise à déterminer les séquences de clients visités par chaque véhicule, et la composante de planification qui vise à faciliter l'arrivée des véhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont été abordées séparément. La combinaison de ces types de décisions dans une seule formulation mathématique et dans une même méthode de résolution devrait donc donner de meilleurs résultats que de considérer ces décisions séparément. Dans cette étude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de décisions simultanément, et ce, d'une manière complète et efficace. Les résultats de tests expérimentaux confirment la performance de la méthode proposée lorsqu’on la compare aux autres méthodes présentées dans la littérature. En effet, la méthode développée propose des solutions nécessitant moins de véhicules et engendrant de moindres frais de déplacement pour effectuer efficacement la même quantité de travail. Dans le contexte des systèmes logistiques urbains, nos résultats impliquent une réduction de la présence de véhicules dans les rues de la ville et, par conséquent, de leur impact négatif sur la congestion et sur l’environnement.