Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future.

Modèle de soutien à l'élaboration et à la réutilisation de scénarios pédagogiques

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

Réutilisation des processus d'affaires pour le développement de systèmes d'information

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Citer la révolte : la reprise québécoise du discours de la décolonisation francophone

Ayant recours aux théories de l’intertextualité et de la citation telles que développées par Genette, Compagnon et Morawski, ce mémoire met en relation deux corpus distincts mais complémentaires : les principaux essais d’Hubert Aquin, de Gaston Miron et des collaborateurs de la revue Parti pris sont analysés comme réécriture des textes (ou réélaboration des idées) d’Aimé Césaire, de Frantz Fanon et d’Albert Memmi, figures dominantes du discours de la décolonisation francophone. L’approche adoptée vise à mettre en lumière les bases sur lesquelles les intellectuels québécois tâchèrent de justifier leur réutilisation du discours de la décolonisation. Elle permet aussi d’observer dans quelle mesure ce discours orienta la réflexion entourant la redéfinition du nationalisme au Québec, en plus de faciliter sa diffusion. Articulé autour de trois grands axes – l’identité culturelle, les conflits linguistiques ainsi que le rôle de la littérature et de l’écrivain dans le combat pour l’émancipation nationale –, ce mémoire démontre que l'établissement d'un tel partenariat symbolique a été d'un grand apport quant à l'appartenance du Québec à la francophonie.

Tarnation, un film sur, avec et par Jonathan Caouette

Document intégré à la collection Archives en mouvement. Cette collection vise à explorer la diffusion par l'utilisation de documents d'archives. Ce document fut préalablement réalisé dans le cadre du cours SCI6113 Description et diffusion des archives, donné à l’EBSI au trimestre d’automne 2009 par François Cartier dans le cadre du programme de maîtrise en sciences de l'infomation.

Timing verification in transaction modeling

Les systèmes Matériels/Logiciels deviennent indispensables dans tous les aspects de la vie quotidienne. La présence croissante de ces systèmes dans les différents produits et services incite à trouver des méthodes pour les développer efficacement. Mais une conception efficace de ces systèmes est limitée par plusieurs facteurs, certains d'entre eux sont: la complexité croissante des applications, une augmentation de la densité d'intégration, la nature hétérogène des produits et services, la diminution de temps d’accès au marché. Une modélisation transactionnelle (TLM) est considérée comme un paradigme prometteur permettant de gérer la complexité de conception et fournissant des moyens d’exploration et de validation d'alternatives de conception à des niveaux d’abstraction élevés. Cette recherche propose une méthodologie d’expression de temps dans TLM basée sur une analyse de contraintes temporelles. Nous proposons d'utiliser une combinaison de deux paradigmes de développement pour accélérer la conception: le TLM d'une part et une méthodologie d’expression de temps entre différentes transactions d’autre part. Cette synergie nous permet de combiner dans un seul environnement des méthodes de simulation performantes et des méthodes analytiques formelles. Nous avons proposé un nouvel algorithme de vérification temporelle basé sur la procédure de linéarisation des contraintes de type min/max et une technique d'optimisation afin d'améliorer l'efficacité de l'algorithme. Nous avons complété la description mathématique de tous les types de contraintes présentées dans la littérature. Nous avons développé des méthodes d'exploration et raffinement de système de communication qui nous a permis d'utiliser les algorithmes de vérification temporelle à différents niveaux TLM. Comme il existe plusieurs définitions du TLM, dans le cadre de notre recherche, nous avons défini une méthodologie de spécification et simulation pour des systèmes Matériel/Logiciel basée sur le paradigme de TLM. Dans cette méthodologie plusieurs concepts de modélisation peuvent être considérés séparément. Basée sur l'utilisation des technologies modernes de génie logiciel telles que XML, XSLT, XSD, la programmation orientée objet et plusieurs autres fournies par l’environnement .Net, la méthodologie proposée présente une approche qui rend possible une réutilisation des modèles intermédiaires afin de faire face à la contrainte de temps d’accès au marché. Elle fournit une approche générale dans la modélisation du système qui sépare les différents aspects de conception tels que des modèles de calculs utilisés pour décrire le système à des niveaux d’abstraction multiples. En conséquence, dans le modèle du système nous pouvons clairement identifier la fonctionnalité du système sans les détails reliés aux plateformes de développement et ceci mènera à améliorer la "portabilité" du modèle d'application.

L’assainissement écologique des eaux usées domestiques : scénario d’aménagement type pour les résidences isolées de pays développés nordiques

L’aménagement des systèmes d’assainissement conventionnel des eaux usées domestiques entraine actuellement la déplétion de ressources naturelles et la pollution des milieux récepteurs. L’utilisation d’une approche écosystémique plus globale telle que l’Assainissement Écologique, visant la fermeture du cycle de l’eau et des éléments nutritifs (phosphore et azote), contenus dans les excréments, par leur réutilisation à travers l’agriculture, permettrait d’améliorer de façon écologique cette situation. Toutefois, ce paradigme émergent est peu enseigné aux professionnels de l’aménagement responsables de sa planification, surtout au niveau de son application dans les pays développés nordiques. C’est pourquoi, afin d’améliorer la planification de ce type de système, il faut informer ces derniers des pratiques les plus adéquates à adopter. Pour y arriver, un scénario d’aménagement type a été développé à partir d’une revue exhaustive de la littérature et de l’analyse des données en se basant sur les recommandations de l’approche en fonction du contexte étudié. Ce scénario aidera les professionnels à mieux comprendre l’Assainissement Écologique et son aménagement. Il représente alors un point de départ pour les discussions interdisciplinaires et participatives que celui-ci requiert. En conclusion, il y a encore de nombreux manques d’informations concernant l’utilisation de traitements alternatifs dans les climats nordiques et l’acceptation de ceux-ci par les usagers. De plus, les cadres législatifs demeurent un obstacle considérable à l’aménagement d’un tel système. Cette recherche permet cependant de démystifier l’approche auprès des professionnels et pourrait aider à modifier certains cadres législatifs afin d’y intégrer sa philosophie.

L’éthique de la valorisation des bases de données et des banques de matériel créées à des fins de recherche : une étude empirique et normative

La recherche du premier chapitre de ce mémoire a été menée en collaboration avec les co-chercheurs suivants: Catherine Olivier et Michel Bergeron.

Autour de Pierre Falardeau : found footage et réemploi d'images dans le cinéma politique

Ce mémoire portera sur le réemploi d’images dans le cinéma politique d’une manière générale dans un premier temps, puis plus spécifiquement dans l’oeuvre du cinéaste québécois Pierre Falardeau. Il s’agit donc d’abord de regarder comment, d’un point de vue historique, l’image fut réemployée dans le cinéma documentaire classique. Il sera ensuite question de la réutilisation de l’image à des fins politiques dans le cinéma expérimental à travers une analyse du found footage film. Dans un deuxième temps, nous verrons le réemploi d’images dans le cinéma militant, engagé politiquement (voire révolutionnaire) dans le cinéma d’Amérique latine (Santiago Alvarez, Fernando Solanas et Octavio Getino) et en France (Guy Debord, Chris Marker et Jean-Luc Godard). Par la suite, nous verrons comment Pierre Falardeau recyclera des images principalement dans trois de ses documentaires : Pea Soup, Speak White et Le temps des bouffons. Nous allons voir où il se situe dans les différentes traditions de réemploi d’images que nous avons vu précédemment et comment il se rapprochait et se distinguait de ses prédécesseurs.

Identification et localisation des préoccupations fonctionnelles dans un code légataire Java

Traditionnellement, les applications orientées objets légataires intègrent différents aspects fonctionnels. Ces aspects peuvent être dispersés partout dans le code. Il existe différents types d’aspects : • des aspects qui représentent des fonctionnalités métiers ; • des aspects qui répondent à des exigences non fonctionnelles ou à d’autres considérations de conception comme la robustesse, la distribution, la sécurité, etc. Généralement, le code qui représente ces aspects chevauche plusieurs hiérarchies de classes. Plusieurs chercheurs se sont intéressés à la problématique de la modularisation de ces aspects dans le code : programmation orientée sujets, programmation orientée aspects et programmation orientée vues. Toutes ces méthodes proposent des techniques et des outils pour concevoir des applications orientées objets sous forme de composition de fragments de code qui répondent à différents aspects. La séparation des aspects dans le code a des avantages au niveau de la réutilisation et de la maintenance. Ainsi, il est important d’identifier et de localiser ces aspects dans du code légataire orienté objets. Nous nous intéressons particulièrement aux aspects fonctionnels. En supposant que le code qui répond à un aspect fonctionnel ou fonctionnalité exhibe une certaine cohésion fonctionnelle (dépendances entre les éléments), nous proposons d’identifier de telles fonctionnalités à partir du code. L’idée est d’identifier, en l’absence des paradigmes de la programmation par aspects, les techniques qui permettent l’implémentation des différents aspects fonctionnels dans un code objet. Notre approche consiste à : • identifier les techniques utilisées par les développeurs pour intégrer une fonctionnalité en l’absence des techniques orientées aspects • caractériser l’empreinte de ces techniques sur le code • et développer des outils pour identifier ces empreintes. Ainsi, nous présentons deux approches pour l’identification des fonctionnalités existantes dans du code orienté objets. La première identifie différents patrons de conception qui permettent l’intégration de ces fonctionnalités dans le code. La deuxième utilise l’analyse formelle de concepts pour identifier les fonctionnalités récurrentes dans le code. Nous expérimentons nos deux approches sur des systèmes libres orientés objets pour identifier les différentes fonctionnalités dans le code. Les résultats obtenus montrent l’efficacité de nos approches pour identifier les différentes fonctionnalités dans du code légataire orienté objets et permettent de suggérer des cas de refactorisation.

A Categorical Framework for the Specification and the Verification of Aspect Oriented Systems

Un objectif principal du génie logiciel est de pouvoir produire des logiciels complexes, de grande taille et fiables en un temps raisonnable. La technologie orientée objet (OO) a fourni de bons concepts et des techniques de modélisation et de programmation qui ont permis de développer des applications complexes tant dans le monde académique que dans le monde industriel. Cette expérience a cependant permis de découvrir les faiblesses du paradigme objet (par exemples, la dispersion de code et le problème de traçabilité). La programmation orientée aspect (OA) apporte une solution simple aux limitations de la programmation OO, telle que le problème des préoccupations transversales. Ces préoccupations transversales se traduisent par la dispersion du même code dans plusieurs modules du système ou l’emmêlement de plusieurs morceaux de code dans un même module. Cette nouvelle méthode de programmer permet d’implémenter chaque problématique indépendamment des autres, puis de les assembler selon des règles bien définies. La programmation OA promet donc une meilleure productivité, une meilleure réutilisation du code et une meilleure adaptation du code aux changements. Très vite, cette nouvelle façon de faire s’est vue s’étendre sur tout le processus de développement de logiciel en ayant pour but de préserver la modularité et la traçabilité, qui sont deux propriétés importantes des logiciels de bonne qualité. Cependant, la technologie OA présente de nombreux défis. Le raisonnement, la spécification, et la vérification des programmes OA présentent des difficultés d’autant plus que ces programmes évoluent dans le temps. Par conséquent, le raisonnement modulaire de ces programmes est requis sinon ils nécessiteraient d’être réexaminés au complet chaque fois qu’un composant est changé ou ajouté. Il est cependant bien connu dans la littérature que le raisonnement modulaire sur les programmes OA est difficile vu que les aspects appliqués changent souvent le comportement de leurs composantes de base [47]. Ces mêmes difficultés sont présentes au niveau des phases de spécification et de vérification du processus de développement des logiciels. Au meilleur de nos connaissances, la spécification modulaire et la vérification modulaire sont faiblement couvertes et constituent un champ de recherche très intéressant. De même, les interactions entre aspects est un sérieux problème dans la communauté des aspects. Pour faire face à ces problèmes, nous avons choisi d’utiliser la théorie des catégories et les techniques des spécifications algébriques. Pour apporter une solution aux problèmes ci-dessus cités, nous avons utilisé les travaux de Wiels [110] et d’autres contributions telles que celles décrites dans le livre [25]. Nous supposons que le système en développement est déjà décomposé en aspects et classes. La première contribution de notre thèse est l’extension des techniques des spécifications algébriques à la notion d’aspect. Deuxièmement, nous avons défini une logique, LA , qui est utilisée dans le corps des spécifications pour décrire le comportement de ces composantes. La troisième contribution consiste en la définition de l’opérateur de tissage qui correspond à la relation d’interconnexion entre les modules d’aspect et les modules de classe. La quatrième contribution concerne le développement d’un mécanisme de prévention qui permet de prévenir les interactions indésirables dans les systèmes orientés aspect.

Étude exploratoire de la phase d’usage des produits électroniques en vue de minimiser les impacts environnementaux : le cas du téléviseur

À cause de leur impact environnemental élevé, les déchets d’équipements électriques et électroniques (DEEE) sont un problème majeur pour les pays développés. La consommation importante de produits électroniques, dont la durée d’utilisation est de plus en plus courte, a entrainé une production croissante de DEEE. C’est dans ce contexte que l’Union européenne a instauré en 2003 la responsabilité élargie des producteurs (REP). Cet outil de politique environnementale a rendu légalement responsables les fabricants de la mise en oeuvre et du financement d’un programme d’intendance des DEEE. Alors que la REP vise principalement le traitement écologique des DEEE, cet instrument ne permet pas de réduire les quantités considérables qui sont produites par les consommateurs. Cette situation est d’autant plus inquiétante que les gains environnementaux obtenus, grâce à l’implantation de la REP, ont été annulés au regard de l’augmentation continue de la consommation de biens électroniques à l’échelle mondiale. En réponse à cette problématique, la présente thèse porte sur les pratiques de l’usager au cours de la phase de consommation des appareils électroniques (aussi appelée phase d’usage). Cette étape du cycle de vie regroupe l’achat, l’utilisation, la réparation et la mise au rebut des biens. Une approche qualitative de type exploratoire faisant appel à l’étude de cas a été utilisée. Le téléviseur, retenu comme cas d’étude, illustre des enjeux partagés par plusieurs équipements électroniques, tels que : la fréquente mise sur le marché de nouveaux modèles, le bas prix d’acquisition comparé au coût de la réparation et l’influence de la mode sur les choix effectués par le consommateur. Ces facteurs facilitent le remplacement des biens et, par conséquent, pourraient entrainer leur fin de vie prématurée qui se matérialise à travers différentes formes d’obsolescence. Dans le cadre de cette étude de cas, une trentaine d’entrevues semi-dirigées a été réalisée avec des usagers et réparateurs de produits électroniques en vue de documenter les différentes sous-étapes de la phase d’usage d’un téléviseur. Sur la base des informations recueillies, l’objectif de cette thèse est de formuler des recommandations, à destination des autorités politiques, qui pourront permettre une minimisation des impacts environnementaux liés à la phase d’usage des appareils électroniques. Les résultats ont permis de mettre en évidence, via le rôle et le statut singulier occupé par le téléviseur dans les foyers, les comportements de l’usager contribuant à augmenter l’empreinte écologique associée à la phase d’usage. L’acquisition de nombreux biens électroniques et non électroniques suite à l’achat du téléviseur, ses multiples fonctionnalités le rapprochant de celles de l’ordinateur et des tablettes, ainsi que la fin de vie prématurée de produits fonctionnels, mais obsolètes d’un point de vue technologique, font partie des résultats de cette recherche. En lien avec ces constats, cette étude propose des instruments de politique environnementale, dont l’affichage de la durée de vie des équipements électroniques, destinés à aider le consommateur à réaliser des choix plus éclairés au moment de l’achat. D’autres orientations, telles que la possibilité d’évoluer vers une réglementation horizontale, c’est-à-dire un cadre législatif qui ne se basera plus sur le produit individuel, mais sur l’ensemble des appareils ayant des fonctionnalités similaires, sont exposées. Par ailleurs, cette recherche explore certains leviers pouvant minimiser le phénomène de fin de vie prématurée des appareils électroniques, tels que l’envoi de biens obsolètes et fonctionnels des pays développés vers ceux en développement pour permettre leur réutilisation et la tendance du Do-It- Yourself dans la réparation des produits électroniques.

On Space-Time Trade-Off for Montgomery Multipliers over Finite Fields

La multiplication dans le corps de Galois à 2^m éléments (i.e. GF(2^m)) est une opérations très importante pour les applications de la théorie des correcteurs et de la cryptographie. Dans ce mémoire, nous nous intéressons aux réalisations parallèles de multiplicateurs dans GF(2^m) lorsque ce dernier est généré par des trinômes irréductibles. Notre point de départ est le multiplicateur de Montgomery qui calcule A(x)B(x)x^(-u) efficacement, étant donné A(x), B(x) in GF(2^m) pour u choisi judicieusement. Nous étudions ensuite l'algorithme diviser pour régner PCHS qui permet de partitionner les multiplicandes d'un produit dans GF(2^m) lorsque m est impair. Nous l'appliquons pour la partitionnement de A(x) et de B(x) dans la multiplication de Montgomery A(x)B(x)x^(-u) pour GF(2^m) même si m est pair. Basé sur cette nouvelle approche, nous construisons un multiplicateur dans GF(2^m) généré par des trinôme irréductibles. Une nouvelle astuce de réutilisation des résultats intermédiaires nous permet d'éliminer plusieurs portes XOR redondantes. Les complexités de temps (i.e. le délais) et d'espace (i.e. le nombre de portes logiques) du nouveau multiplicateur sont ensuite analysées: 1. Le nouveau multiplicateur demande environ 25% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito lorsque GF(2^m) est généré par des trinômes irréductible et m est suffisamment grand. Le nombre de portes du nouveau multiplicateur est presque identique à celui du multiplicateur de Karatsuba proposé par Elia. 2. Le délai de calcul du nouveau multiplicateur excède celui des meilleurs multiplicateurs d'au plus deux évaluations de portes XOR. 3. Nous determinons le délai et le nombre de portes logiques du nouveau multiplicateur sur les deux corps de Galois recommandés par le National Institute of Standards and Technology (NIST). Nous montrons que notre multiplicateurs contient 15% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito au coût d'un délai d'au plus une porte XOR supplémentaire. De plus, notre multiplicateur a un délai d'une porte XOR moindre que celui du multiplicateur d'Elia au coût d'une augmentation de moins de 1% du nombre total de portes logiques.

Europeana comme modèle de portail de diffusion des archives et du patrimoine

Travail réalisé à l'EBSI, Université de Montréal, sous la direction de M. Yvon Lemay dans le cadre du cours SCI6850 – Recherche individuelle, à l'hiver 2015

Peter Pan contre le héros victorien : la poétique du recyclage dans le Cycle de Kraven de Xavier Mauméjean

Le Cycle de Kraven de Xavier Mauméjean met en place un réseau référentiel qui repose sur le recyclage systématique d’éléments historiques et littéraires. Afin de bien saisir le fonctionnement de ce cycle narratif, il importe de se pencher sur cette dynamique référentielle exacerbée relevant d’une poétique du recyclage (au sens de réutilisation) qui se manifeste par l’emprunt de nombreux référents historiques et littéraires, que le récit modifie à divers degrés. Au moyen de la notion de recyclage, des travaux sur la récupération de l’Histoire par l’uchronie et d’études sur le steampunk, esthétique dont relève le Cycle de Kraven, ce mémoire examine les effets de ce recyclage sur le fonctionnement du récit, mais aussi sur le lecteur. En effet, par un imposant mélange de références authentiques et fictives, le Cycle de Kraven cherche à mystifier le lecteur qui se trouve au centre d’un fourmillement intertextuel brouillant les frontières entre Histoire et fiction. Une réflexion sur le paratexte vient compléter l’analyse du Cycle de Kraven, puisque préface, notes en bas de page, liste de livres et bon de commande contribuent grandement à la création d’un effet de mystification.