Heuristiques efficaces pour l'optimisation de la performance des systèmes séries-parallèles

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

Parallel metaheuristics for stochastic capacitated multicommodity network design

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

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.

Representación de las homosexualidades en el teatro de Rafael Mendizábal y de Michel Marc Bouchard

À partir d’une étude descriptive et comparative des pièces dramatiques Les Feluettes (1987) et Les Muses orphelines (1988) de Michel Marc Bouchard (Québec) ainsi que Feliz cumpleaños, señor ministro (1992) et Madre amantísima (2003) de Rafael Mendizábal (Espagne), le présent mémoire traite de la représentation des homosexualités à travers les relations amoureuses et familiales, les subversions du genre, l’homophobie, ainsi que la pandémie de sida et son impact au niveau théâtral et littéraire. L’approche méthodologique employée est la perspective des études du genre et des études queer. Comme conclusions, on constate que les relations amoureuses sont marquées par la valorisation paradoxale du cadre de l’amour romantique classique, entre libération et homonormativité, en plus d’une représentation de la sexualité articulée par des rôles polarisés. Les relations familiales, pour leur part, s’organisent autour de la figure paternelle associée avec d’importantes nuances au discours dominant hétérosexiste, et se décline parallèlement en la figure du père absent et désintéressé. De même, les figures maternelles sont majoritairement absentes ou effacées, bien que ce constat soit renversé par une figure maternelle traditionnelle particulièrement forte. Dans tous les cas, la figure maternelle reste idéalisée. Les identités de genres sont étudiées sous l’angle des identités dichotomiques lesbiennes et de l’effémination entant que subversions des normes dominantes du genre et l’articulation sexiste du phénomène de l’homophobie, motivé par le tabou de l’homoérotisme et son poids en scène.

Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.

Global Optimization Algorithms and their Application to Distributed Systems

In this report, we discuss the application of global optimization and Evolutionary Computation to distributed systems. We therefore selected and classified many publications, giving an insight into the wide variety of optimization problems which arise in distributed systems. Some interesting approaches from different areas will be discussed in greater detail with the use of illustrative examples.

Disseny d’un programa que assisteix en la seqüenciació de peces de taller basats en mètodes heurístics

El GREP (grup de recerca de producte, procés i producció) de la UdG actualment disposa d’una eina informàtica desenvolupada en un PFC del 2003 que li permet fer la seqüenciació de la producció d’un taller mecànic amb un màxim de cinc productes, un nombre definit de possibles rutes de fabricació per a cada producte i tres màquines. Aquesta eina és molt resolutiva per a aquests casos, ja que estudia totes les possibilitats i les comprova una per una. No obstant aquest fet presenta una sèrie de limitacions com són el temps d’execució doncs al comprovar totes les seqüències té un elevat cost computacional i la rigidesa del sistema doncs no ens permet seqüenciar més productes ni més màquines. Per tal de donar solució a aquest problema es planteja generar una nova eina informàtica a partir de l’actual però que permeti seqüenciar més peces sense ocupar tanta memòria per així implementar-hi futures millores com el temps de preparació etc... Per a desenvolupar l’eina informàtica s’han utilitzat mètodes heurístics, concretament dos que són: algoritmes genètics i cerca TABU. Aquests mètodes destaquen perquè no busquen totes les combinacions possibles sinó que estudien una sèrie de combinacions i utilitzant mètodes de creuament i generació d’entorns busquen una solució

Os Coveiros enquanto Recursos Humanos

A presente dissertação consiste num trabalho de investigação, descritivo e exploratório, cujo objetivo é o estudo da profissão de coveiro no universo dos recursos humanos - a sua profissão, formação, sentimentos e perspetiva inerente ao novo paradigma da cremação. Começou por se abordar as dificuldades surgidas durante a elaboração do trabalho e que, fundamentalmente, se relacionavam com a falta de informação e o tabu e preconceito social que o tema da morte ainda provoca na sociedade atual. Seguidamente, elaborou-se um enquadramento teórico e histórico sobre o nascimento dos cemitérios, baseado em referências bibliográficas, com o intuito de melhor compreender a necessidade da existência da profissão de coveiro. Posteriormente, foi realizada uma análise cuidada e rigorosa aos dados recolhidos durante o trabalho de investigação, abordando os aspetos qualitativos e demográficos para, deste modo, se proceder à caraterização do perfil do coveiro, enquanto profissional. Recolheram-se opiniões junto da hierarquia (chefias) e dos clientes (famílias dos defuntos), de forma a construir uma ideia mais coesa da profissão de coveiro. Para a um melhor entendimento da atividade profissional em estudo, realizou-se ainda uma entrevista aos responsáveis da Servilusa, entidade formadora neste sector, aprofundando deste modo, as boas práticas e se perceber como funciona este setor de atividade terciária. Solicitaram-se esclarecimentos aos responsáveis dos Alcoólicos Anónimos (AA), com o intuito de aprofundar os conhecimentos em torno do problema do alcoolismo nesta profissão, de forma a opinar sobre esta matéria de uma maneira mais rigorosa e responsável. Realizou-se ainda uma abordagem sobre a cremação como um novo paradigma que poderá, de certo modo, pôr em causa o futuro da função do coveiro e respetiva categoria profissional. Como conclusão, sugeriram-se soluções que visam a melhoria da situação profissional dos coveiros, do seu bem-estar e condições de trabalho, tendo o presente trabalho culminado com a criação de um código de ética, na implementação da avaliação de desempenho, atribuição da carreira de coveiro e respetivas categorias, assim como na atualização de conhecimentos e melhoria de competências profissionais e pessoais, com o recurso à formação profissional.

Comportamento de compra face à obsolescência planificada

No século XXI as fábricas produzem mais do que necessário, os fabricantes competem entre eles pelo mercado de consumo e são pressionados para vender. Para não ficarem com produtos em stock, recorrem a diversas técnicas de marketing, entre elas a inserção de obsolescência planificada nos seus produtos no ato da criação. A presente dissertação pretende estudar o comportamento de compra face à obsolescência planificada. O conceito de obsolescência planificada divide-se em três (3) tipologias: tecnológica, por qualidade, e psicológica. Quando um modelo mais recente do mesmo produto é colocado no mercado, este pode ser colocado com base em inovações tecnológicas reais ou melhoramentos superficiais fictícios. Em ambos os casos é considerado obsolescência tecnológica. Se um produto avaria antes do tempo ou é utilizada matéria-prima de qualidade inferior ou defeituosa, o fabricante introduziu obsolescência por qualidade no produto. Por fim, existe a obsolescência psicológica. Neste caso o problema não é do produto, pois continua funcional, mas sim do consumidor. Este está psicologicamente cansado do produto e opta pela sua substituição. O que se pretende estudar é o comportamento humano adotado face ao conceito. Terá a sociedade consumidora conhecimento deste assunto tabu? Este e outros fatores serão questionados e estudados nos capítulos seguintes.

Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints

This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. (C) 2007 Elsevier B.V. All rights reserved.

Task assignment optimization in SAP Extended WarehouseManagement

Nowadays in the world of mass consumption there is big demand for distributioncenters of bigger size. Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual warehouse when we want tominimize the labor costs. Most of the workers’ working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won’t be long traveling timebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and workers.In the scientific literature Generalized Assignment Problem (GAP) is a wellknownproblem which deals with the assignment of m workers to n tasks consideringseveral constraints. The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization) to be implemented into SAPExtended Warehouse Management (SAP EWM) by with task assignment will be moreeffective between tasks and resources.After system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach – instead of the introduced heuristics – which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method.

University Scheduling using Genetic Algorithm

The automated timetabling and scheduling is one of the hardest problem areas. This isbecause of constraints and satisfying those constraints to get the feasible and optimizedschedule, and it is already proved as an NP Complete (1) [1]. The basic idea behind this studyis to investigate the performance of Genetic Algorithm on general scheduling problem underpredefined constraints and check the validity of results, and then having comparative analysiswith other available approaches like Tabu search, simulated annealing, direct and indirectheuristics [2] and expert system. It is observed that Genetic Algorithm is good solutiontechnique for solving such problems and later analysis will prove this argument. The programis written in C++ and analysis is done by using variation in various parameters.

Man kan både sitta bredbent och med benen i kors : En kvalitativ studie om hur genusvetare praktiserar genuskunskap

There is an awareness of the importance of gender equality in most western societies, both at the political level and in everyday life. In academia, for instance, gender is nowadays a scientific field which indicates that there is a lot of knowledge about the subject. What we do not have much knowledge about is whether gender knowledge leads to changes in gender relations in practice. The aim of this study is to explore how gender scholars relate to using – practicing – gender knowledge. Key issues in this study are how gender scholars construct gender, how they practice gender theoretical knowledge, and their reflections of gender boundaries.             Theoretically, this study is mainly based on Sara Ahmed’s perspective on gender. The main finding of the study is that despite gender knowledge gender scholars tend to reproduce traditional gender orders. By identifying concepts such as reflected and unreflected masculinity/femininity, different ideals of masculinity/femininity are made visible. There seems to be an ideal among gender scholars to practice their gender knowledge. This ideal is practiced among “gender scholar women” by doing reflected masculinity and reflected femininity. Among “gender scholar men”, however, the ideal to practice gender knowledge by doing unreflected masculinity and reflected femininity seems to be a taboo at the same time. For men, it seems important to mark a distance to a certain type of femininity and to maintain the heterosexual – straight – line. For women, it seems desirable both to distance themselves from a certain type of masculinity and femininity and thereby follow alternative – queer – lines.

Eutanásia e dignidade da pessoa humana: desafios jurídicos

Esta monografia busca apresentar uma visão panorâmica da eutanásia, tema este que se reveste de grande polemicidade, ensejando implicações de ordem médico jurídica. Neste pesquisa, buscou-se resgatar conceitos técnicos e também uma abordagem histórica do tema. Em que pese este trabalho haver se atido apenas a uma classificação da eutanásia, são várias as classificações encontradas nos compêndios científicos. Procurou-se também abordar a posição do Direito Brasileiro e a do Direito Estrangeiro, apresentando-se o posicionamento jurídico de algumas nações, no que tange ao assunto, encontrando-se posições divergenes e variadas. Notou-se que, face ao grande avanço biotecnológico, a questão vem sendo discutida mais amplamente nas áreas médicas e jurídicas, porém, a eutanásia ainda é considerada um grande tabu na prática médica. A atualidade e a complexidade do tema "morrer com dignidade" justificam este estudo, por suscitar questões ético-jurídicas intrincadas, diante do avanço da tecnologia médica, nas últimas décadas do século XX e início deste, provocando uma verdadeira mutação cultural e impregnando de valores morais e sociais as questões sobre o início e o fim da vida. Vislumbram-se situações verdadeiramente paradoxais no que concerne a este tema, a ponto de muitos pensadores considerarem a eutanásia o grande desafio do século XXI.

A trama da violência na escola

Nesse trabalho se analisa o tratamento dado à violência no espaço escolar, bem como a relação entre a violência que se expressa dentro e fora daquele ambiente. Parte-se de um estudo realizado numa escola pública da rede estadual de Duque de caxias - RJ, município onde elevados índices de criminalidade e violência são revelados pelos indicadores das pesquisas. Tem como pressuposto uma compreensão da violência como uma rede na qual se entrelaçam diversos fatores que abrangem os campos da vida individual e social. Dentro dessa concepção, a manifestação de violência na escola é vista como articulada às outras formas de violência existentes na sociedade, o que representa também colocar a escola ao mesmo tempo como agente e vítima da violência. Se por um lado, a violência aparece como uma preocupação no cotidiano do trabalho pedagógico, por outro lado, a enorme complexidade desse problema e a assustadora realidade, em princípio, levam a uma negação da mesma, limitando as possibilidades de enfrentamento. Verificou-se que , além do grau de subjetividade que envolve o próprio tcono, do tabu que se cria a seu redor, da redução da sua compreensão ao seu aspecto fisico e da concepção ideológica que se tem da instituição escolar, a naturalidade que vem se processando frente à violência é um dos principais elementos que contribuem para essa negação. Perante um contexto tão grave, qualquer prática de violência por parte da escola passa a ser considerada normal, natural, o que vai concorrer conseqüentemente para a sua legitimação. Diante dessa dura realidade que ameaça e faz com que se evite a sua constatação, tem-se como desafio a definição de uma proposta pedagógica que inclua o reconhecimento desse conteúdo, buscando entender a criança construída / destruída nesse espaço. Contrapondo-se a essa convivência com a dor e com a morte, há resistências e expressões de luta pela vida, que deverão sustentar toda uma pedagogia a ser inventada, num processo coletivo, constituindo-se num agenciamento do desejo de prazer e de viver.