Made available in DSpace on 2015-04-14T14:49:25Z (GMT). No. of bitstreams: 1 425006.pdf: 2030732 bytes, checksum: af723abcff811e622f9a8f3c907145a0 (MD5) Previous issue date: 2009-12-17 / A avalia??o de desempenho dos protocolos de roteamento de redes Ad hoc ? realizada, em sua maioria, atrav?s do uso de t?cnicas e ferramentas de simula??o. Atrav?s do uso das Redes de Aut?matos Estoc?sticos, surge uma nova alternativa para realizar esta avalia??o, j? que este formalismo prov? grande quantidade de espa?os de estados, que era um dos grandes problemas de outros formalismos anal?ticos. Os protocolos de roteamento para redes sem fio Ad hoc s?o um fator determinante no sucesso da tarefa de transmiss?o de dados entre os nodos. Sendo assim, foi avaliado neste trabalho o protocolo DSR - Dynamic Source Routing, que tem como caracter?sticas principais as t?cnicas de descoberta e manuten??o de rota, a fim de garantir a menor - ou melhor - rota dentro de uma rede. A primeira contribui??o presente neste trabalho trata diretamente da avalia??o deste processo de descoberta de rota, bem como da possibilidade de falhas de transmiss?o ocorrerem e o processo de manuten??o de rota se fazer necess?rio. Estes resultados est?o diretamente ligados aos resultados obtidos avaliando-se o workload dos nodos da rede, que reflete diretamente na utiliza??o das rotas. A segunda contribui??o ? a an?lise do comportamento de redes quando estas utilizam uma particularidade do protocolo DSR que ? a escuta prom?scua (promiscuous listening). Busca-se avaliar se o uso de tal caracter?stica auxilia no funcionamento da rede. S?o apresentados tamb?m resultados de avalia??o de m?tricas como vaz?o com diferentes tamanhos de pacotes e tempos de pausa dos nodos durante a transmiss?o dentro de uma rede que utiliza o protocolo DSR para o roteamento das informa??es. Adicionalmente busca-se demonstrar a efici?ncia das Redes de Aut?matos Estoc?sticos na obten??o destas m?tricas e assim apresentar este formalismo como uma alternativa para avalia??o deste tipo de ambiente, dada a similaridade dos resultados obtidos, se comparados ?queles apresentados na literatura.

Made available in DSpace on 2015-04-14T14:49:27Z (GMT). No. of bitstreams: 1 426257.pdf: 1755625 bytes, checksum: 752156f9068dd50cc9bde67b5e57153f (MD5) Previous issue date: 2010-04-08 / Redes Tolerantes a Atrasos (Delay Tolerant Network - DTN) s?o redes sujeitas a interrup??es frequentes, altos atrasos e elevadas taxas de erro. Nessas redes os nodos s?o m?veis e fazem o papel de roteadores, armazenando e fazendo o repasse das mensagens que precisam ser entregues. O foco deste trabalho est? nas redes DTN estoc?sticas, nas quais as mudan?as topol?gicas n?o s?o conhecidas e surgem t?cnicas para tentar aumentar a probabilidade de sucesso no roteamento, utilizando conhecimento hist?rico do comportamento da rede na tomada da decis?o. As redes DTN possuem algumas semelhan?as com as redes ad hoc, mas devido ?s constantes disrup??es que ocorrem nas redes DTN, o problema do roteamento ? tratado de forma diferente. Em cen?rios esparsos, devido ? falta de conectividade dos nodos, as redes DTN apresentam maior percentual de mensagens entregues, a custo de maiores atrasos. Um estudo comparando esses dois tipos de redes ? realizado por este trabalho, comprovando esse aspecto. Este trabalho prop?e tr?s varia??es de um protocolo de roteamento para redes DTN estoc?sticas que utiliza uma m?trica chamada de potencial de entrega usada na decis?o do repasse das mensagens. O potencial de entrega ? uma medida hist?rica que indica o n?mero de encontros em que os nodos est?o envolvidos em um per?odo de tempo. No intuito de aumentar a probabilidade de encontrar o destinat?rio, a estrat?gia prioriza o roteamento a nodos que tenham um n?mero alto de encontros. O protocolo inicial ? chamado de APRP (Adaptive Potential Routing Protocol ) e, em compara??o com outros protocolos para o mesmo tipo de rede, apresenta um percentual de mensagens entregues equivalente a esses protocolos, com um overhead bastante reduzido, especialmente para redes esparsas (importantes em DTN). Uma varia??o do APRP utiliza um mecanismo de confirma??o de mensagens j? entregues com o intuito de liberar espa?o em buffer para mensagens novas. Tal varia??o ? chamada de APRP-Ack e apresenta desempenho superior ao APRP, ao custo de um aumento no atraso m?dio na entrega das mensagens. Por fim, ? proposto o APRP-Group, com o objetivo de reduzir o atraso gerado pelo APRP e APRP-Ack. O APRP-Group busca identificar grupos de nodos com potenciais de entrega similares e decidir sobre o repasse das mensagens com base em tais grupos. Este protocolo apresenta uma redu??o significativa no atraso de entrega, se comparado ao APRP e APRP-Ack, mantendo baixos os custos de comunica??o e mantendo ou melhorando n?veis de entrega. Os diferentes protocolos foram simulados em um ambiente espec?fico para DTN e comparados com protocolos da literatura, especialmente com o Spray and Wait devido ao seu alto desempenho reportado na literatura.

Made available in DSpace on 2015-04-14T14:49:27Z (GMT). No. of bitstreams: 1 427029.pdf: 2846166 bytes, checksum: e58e7e583a8e59c4cf88f555666e60c4 (MD5) Previous issue date: 2008-03-25 / O trabalho apresenta caracter?sticas, funcionamento e arquitetura das redes wireless mesh assim como sua aplicabilidade em diversos cen?rios. S?o mostrados tamb?m aspectos de hardware, protocolos, algoritmos de roteamento, topologias e grupos de discuss?o criados para esta tecnologia, com destaque para os grupos de padroniza??o IEEE 802.11s, 802.15.5 e 802.16a. Al?m de mostrar o funcionamento destas redes foram investigados tamb?m alguns projetos de pesquisa realizados no MIT (Massachusetts Institute of Technology), e pela Microsoft Research. S?o apresentados resultados de avalia??o de desempenho de protocolos de roteamento de redes mesh em dois cen?rios para a mesma topologia. Os dois cen?rios possuem quantidades diferentes de nodos e fontes de comunica??o. A avalia??o foi realizada por meio de simula??o com a ferramenta Network Simulator (ns2), utilizando UDP como protocolo da camada de transporte. Os resultados de simula??o mostraram resultados interessantes, e tamb?m descobertas n?o esperadas, a partir das an?lises e compara??es entre os protocolos de roteamento selecionados.

As tecnologias de redes sem fio passaram a atender não só às aplicações corporativas mais sofisticadas como também àquelas envolvendo desde o rastreamento de animais, monitoramento de estruturas e automação industrial até o gerenciamento de utilidades urbanas. Este projeto de pesquisa aborda o desenvolvimento de um protocolo de rede mesh multi-hop segundo a especificação IEEE 802.15.4, com o uso de coordenadas geográficas de cada nó para o roteamento de dados em aplicações de iluminação pública. Para o desenvolvimento do protocolo de rede, é considerada a biblioteca de rotinas de interface de rede denominada Simple MAC (SMAC). Tal biblioteca pode ser utilizada para a elaboração do protocolo de roteamento geográfico destinado à rede mesh multi-hop. Paralelamente, propõe-se a descrição de um método a ser adotado para a inserção do protocolo de roteamento geográfico no SMAC. Os códigos, desenvolvidos em linguagem de programação C, são portados para a plataforma de desenvolvimento dos nós de comunicação de um toolkit específico e submetidos a ensaios experimentais. Os resultados englobam a geração de conhecimento teórico e prático a respeito das redes de sensores sem fio, bem como o desenvolvimento de um software aberto para este tipo de rede. As propriedades de auto-organização da rede, robustez e baixa latência são comprovadas nos ensaios experimentais. / The technologies of wireless networks have to serve not only the most sophisticated business applications but also those that involve the tracking of animals, monitoring of structures, industrial automation and the management of urban utilities. This research project addresses the development of a protocol for multi-hop mesh network according to IEEE 802.15.4, with the use of geographical coordinates of each node for routing data in applications such as street lighting. In order to develop the network protocol, the routines library of the network interface, called Simple MAC (SMAC), is considered. This library can be used for establishing the geographic routing protocol destined for the multi-hop mesh network. In parallel it is proposed to describe a method to be adopted for the inclusion of geographic routing protocol in SMAC. The codes, developed in C programming language, are ported to the development platform of communication nodes of a specific toolkit and subjected to experimental tests. The results include the generation of theoretical and practical knowledge regarding the wireless sensor networks, as well as the development of open software for this type of network. The properties of self-organization of the network, robustness and low latency are proven in experimental tests.

O crescimento do tráfego de serviços de telecomunicações tem aumentado o consumo de energia e, em consequência, aumentado as emissões de CO2 que tem efeitos nocivos sobre o meio ambiente. É assim que a economia de energia torna-se um fator chave no planejamento de redes de telecomunicações. Para garantir a disponibilidade e confiabilidade, as redes possuem arquitetura redundante e são projetadas para suportar a demanda de pico de tráfego. Redes com mecanismos de proteção como proteção dedicada de caminhos (DPP), proveem caminhos alternativos para cada demanda de conexão. Os elementos da rede que suportam esses caminhos estão em estado ativo (consumindo energia), apesar de, na maior parte do tempo, não transportarem tráfego efetivo. Um método para diminuir o gasto de energia é utilizar roteamento adaptado à carga real de tráfego baseado em modo suspenso (estado de baixo consumo de energia que pode passar a estado ativo rapidamente). Assim, o tráfego é roteado com vistas à maximizar a quantidade de componentes que são parte de caminhos de proteção, que podem ser postos em modo suspenso. Neste trabalho, as redes usadas para os testes são a rede europeia Cost239, a rede estadunidense UsNet e a rede brasileira Ipê. Abordamos o problema de economia de energia em redes WDM com DPP através de quatro estratégias de roteamento. Cada uma tem objetivos diferentes, a Shortest Path-DPP (SP-DPP) faz o roteamento por caminho mais curto, a Energy Aware-DPP (EA-DPP) aloca as demandas por enlaces que estejam ativos, a Energy Aware-DPP with Mixing (EA-DPP-MixS) evita que caminhos principais sejam roteados por enlaces que já são parte de caminhos de proteção e a Energy Aware-DPP with Differentation (EA-DPP-Dif) evita a mistura de caminhos por um mesmo enlace. Em nossas simulações computacionais observamos que a EA-DPP-Dif economiza energia de maneira eficiente, mas a probabilidade de bloqueio aumenta. A EA-DPP-MixS diminui o bloqueio em detrimento da energia economizada. Já a SP-DPP e a EA-DPP são menos eficientes na diminuição da energia consumida. É assim que propomos um roteamento com busca de recursos mais ampla, usando cada uma das estratégias. A proposta será chamada de roteamento intensivo. A EA-DPP-Dif-Intensivo diminui a probabilidade de bloqueio e economiza energia mediante modo suspenso. Neste trabalho, analisamos o desempenho das estratégias para cada uma das redes e avaliamos o impacto da energia economizada sobre a probabilidade de bloqueio. A proposta de roteamento i>intensivo diminui a energia consumida em até 50%, diminuindo a probabilidade de bloqueio. Porém, os resultados estão diretamente relacionados com a carga de rede e as características particulares da topologia de cada rede. / The growth of data traffic in telecommunication networks has increased energy consumption and hence increased CO2 emissions, with harmful effects on the environment. Thus, energy saving becomes a key and a differential factor when planning telecommunication networks. In order to guarantee availability and reliability, core networks have redundant architecture and are designed to support peak-hour traffic demand. Networks with dedicated path protection (DPP) mechanisms provide alternative paths for each connection request. Network elements supporting these paths are in active state (consuming energy), although most of the time they dont carry traffic. One technique to decrease energy waste is by adaptive real traffic routing using sleep mode (a low energy consumption state which is able to rapidly change to an active state). Thus, traffic is routed in order to maximize the amount of network components used by protection paths, which can be set in sleep mode. In this work, European Cost239, American UsNet and Brazilian Ipê networks were used in computational simulations. We addressed the energy saving problem in WDM networks with DPP through four routing strategies, each with different goals. The Shorthest Path-Dedicated Path Protection (SP-DPP) technique uses shortest path for routing, Energy Aware-Dedicated Path Protection (EA-DPP) allocates demands in active links, Energy Aware-Dedicated Path Protection with Mixing (EA-DPP-MixS) prevents primary paths to be formed by links that are already part of the protection paths and Energy Aware-Dedicated Path Protection with Differentation (EA-DPP-Dif) prevents mixing primary and protection paths through the same link. We observe that EA-DPP-Dif efficiently saved energy, however blocking probability has increased. EA-DPP-MixS reduced blocking rather than saved energy. At least, SP-DPP and EA-DPP are less efficient in reducing energy consumption. Hence, we propose a wider resource search routing, the in-depth routing, using each of these strategies. Thus, EA-DPP-Dif-In-depth decreased blocking probability while maintaining energy saving through sleep mode. In this work, we analyze the strategies performance for each network and evaluate the impact of energy saved on the blocking probability. Our in-depth routing strategy reduced the energy consumption up to 50%, decreasing blocking probability. However, the results are directly related with the network load and the specific properties of each network topology.

As redes de telecomunicações são responsáveis pelo envio de informação entre pontos de origem e destino. Dentre os diversos dispositivos que participam deste processo, destaca-se o sistema de roteamento, que realiza a seleção das rotas a serem percorridas pelas mensagens ao longo da rede e sua condução ao destino desejado. O avanço das tecnologias utilizadas pelas redes de telecomunicações provocou a necessidade de novos sistemas de roteamento, que sejam capazes de lidar corretamente com as diversas situações enfrentadas atualmente. Dentro deste contexto, este projeto de pesquisa desenvolveu um algoritmo de roteamento adaptativo e distribuído, resultado da integração de três estratégias de aprendizagem e da adição de alguns mecanismos extras, com o objetivo de obter um algoritmo eficiente e robusto às diversas variações das condições de operação da rede. As abordagens utilizadas foram a aprendizagem-Q, aprendizagem por reforço dual e aprendizagem baseada no comportamento coletivo de formigas. O algoritmo desenvolvido foi aplicado a duas redes de comutação de circuitos e seu desempenho foi comparado ao de dois algoritmos baseados no comportamento coletivo de formigas, que foram aplicados com sucesso ao problema de roteamento. Os experimentos conduzidos envolveram situações reais enfrentadas pelas redes, como variações dos seus padrões de tráfego, nível de carga e topologia. Além disto, foram realizados testes envolvendo a presença de ruído nas informações utilizadas para a seleção das rotas a serem percorridas pelas chamadas. O algoritmo proposto obteve melhores resultados que os demais, apresentando maior capacidade de adaptação às diversas situações consideradas. Os experimentos demonstraram que novos mecanismos de otimização devem ser anexados ao algoritmo proposto, para melhorar seu comportamento exploratório sob variações permanentes do nível de carga da rede e presença de ruído nos dados utilizados em suas tarefas. / The telecommunications networks are responsible for transmiting information between source and destination points in a fast, secure and reliable way, providing low cost and high quality services. Among the several devices that takes place on this process, there is thre routing system, which selects the routes to be traversed by the messages through the network and their forwarding to the destination desired. The advances in tecnologies used by telecommunications networks caused the necessity of new routing systems, that can work correctly with the situations faced by current telecommunications networks. Hence, this research project developed an adaptive and distributed routing algorithm, resulting of the integration of three leaming strategies and addition of some extra mechanisms, with the goal of having a robust and adaptive algorithm to the several variations on operation network conditions. The approaches chosen were Q-learning, dual reinforcement learning and learning based on collective behavior of ants. The developed algorithm was applied to two circuit-switching telecommunications networks and its performance was compared to two algorithms based on ant colony behavior, which were used with success to solve the routing problem. The experiments run comprised real situations faced by telecommunications networks, like variations on the network traffic patterns, load level and topology. Moreover, we did some tests with the presence of noise in information used to select the routes to be traversed by calls. The algorithm proposed produced better results than the others, showing higher capacity of adaptation to the several situations considered. The experiments showed that new optimization mechanisms must be added to the routing algorithm developed, to improve its exploratory behavior under permanent variations on network load level and presence of noise in data used in its tasks.

Submitted by Edisangela Bastos (edisangela@ufpa.br) on 2014-01-13T19:54:13Z No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_RoteamentoMulticamadaBaseado.pdf: 3768147 bytes, checksum: 94a2ae401264e821c6a84e2a9779dedc (MD5) / Approved for entry into archive by Ana Rosa Silva(arosa@ufpa.br) on 2014-01-16T15:01:46Z (GMT) No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_RoteamentoMulticamadaBaseado.pdf: 3768147 bytes, checksum: 94a2ae401264e821c6a84e2a9779dedc (MD5) / Made available in DSpace on 2014-01-16T15:01:46Z (GMT). No. of bitstreams: 2 license_rdf: 23898 bytes, checksum: e363e809996cf46ada20da1accfcd9c7 (MD5) Dissertacao_RoteamentoMulticamadaBaseado.pdf: 3768147 bytes, checksum: 94a2ae401264e821c6a84e2a9779dedc (MD5) Previous issue date: 2012-02 / A pesquisa apresentada nesta dissertação descreve a elaboração de um protocolo de roteamento para aplicações de Redes de Sensores Sem Fio (RSSF) em cidade inteligentes com forte restrição de energia e alta densidade de nodos. Através do estudo dos principais objetivos da comunicação de dados e do levantamento do estado-da-arte sobre os protocolos de roteamento e tecnologias para RSSF, a proposta contempla requisitos como: vazão de dados, confiabilidade de entrega e eficiência energética. A pesquisa apresenta em detalhes o protocolo AODV (Ad hoc On Demand Distance Vector), bem como sua relevância no contexto de RSSF devido a sua popularidade entre as plataformas de dispositivos comercializados. Além disso, são apresentados protocolos derivados do AODV, e a ausência de uma proposta robusta capaz de contemplar os requisitos levantados. O protocolo REL (Routing by Energy and Link Quality) é o resultado da pesquisa levantada e a proposta de solução para roteamento plano sob demanda baseado em eficiência energética e qualidade de enlace para prover um roteamento escalável, capaz de realizar balanceamento de carga e prolongar o tempo de vida da rede. O protocolo REL foi avaliado através de simulação e tesbed, a fim de garantir validação da proposta em ambiente real de escala reduzida e simulado de alta densidade. Os resultados mostraram que o protocolo REL apresenta considerável melhoria de entrega de dados através da escolha de enlaces confiáveis de transmissão e menos suscetíveis a erro, além de moderado consumo de energia capaz de prolongar o tempo de vida da rede, evitando a saturação prematura de nodos. / Multilayer routing based on energy efficiency and link quality for wireless sensor networks This Thesis describes the development of a new routing protocol for Wireless Sensor Networks (WSN) for energy restriction and scenarios with high density of nodes. Through the study of the main goals of data communication and the state of the art on the routing protocols and technologies for WSN, this proposal has the following requirements throughput, reliability on data delivery and energy-efficiency. The study presents in detail the AODV (Ad hoc On Demand Distance Vector) protocol and its relevance in the context of WSN, due to the fact of its popularity among the devices. Additionally, it is presented the proposed extensions for AODV and their main drawbacks to provide the required goals. The REL (Routing by Link Energy and Quality) protocol is the result of this research and the proposed solution for on-demand routing protocol for plan architecture based on energy-efficiency and link quality, in order to provide scalability, load balancing and prolong the network lifetime. The REL protocol was evaluated by using simulation and tesbed experiments in order to show its impact and benefits in real and simulated scenarios. The results presents that REL increases the data delivery rate due to the use of reliable links with less probability of error. Additionally, it uses energy issues to select routes, which avoid the fast saturation of nodes and increase the network lifetime.

Este trabalho analisou o desempenho obtido pelos arranjos físicos distribuídos levando em consideração a flexibilidade de seqüenciamento das operações das peças. Foram comparados os arranjos físicos funcional, parcialmente distribuído, aleatoriamente distribuído e maximamente distribuído em três tamanhos (20, 40 e 80 máquinas), em duas configurações (equilibrado e desequilibrado) e usando dois métodos de roteamento (rígido e flexível). Para obtenção do arranjo físico maximamente distribuído foi desenvolvido um algoritmo genético e uma metodologia heurística de baixo impacto computacional denominada ALVO. A flexibilidade de seqüenciamento das operações foi baseada em relações de precedência e um procedimento automático para criação de peças com essas características foi desenvolvido. Os métodos e procedimentos propostos foram computacionalmente implementados em Visual Basic 6. Foram elaborados 152 arranjos físicos para cada tamanho e configuração sendo 50 funcionais, 50 parcialmente distribuídos, 50 aleatoriamente distribuídos e 2 maximamente distribuídos (um pelo algoritmo ALVO e outro pelo algoritmo genético). As simulações rotearam, para cada tipo de arranjo físico, 30 conjuntos com 150 peças cada um para obter o tempo total de programação (makespan) e a distância total percorrida. Os resultados mostraram que o desempenho do arranjo físico maximamente distribuído é sensivelmente superior ao parcialmente distribuído, mostrando que a desagregação completa dos departamentos é altamente vantajosa. As análises também mostraram que os arranjos físicos equilibrados, quando maximamente distribuídos, formam células fractais. / This work analyzes the performance obtained for the distributed layouts when the task routing environment takes in consideration the operations sequence flexibility of the parts. The functional, partially distributed, random distributed and maximally distributed layouts were compared in three sizes (20, 40 and 80 machines), in two configurations (balanced and unbalanced) and using two routing methods (rigid and flexible). For obtainment of the maximally distributed layout a genetic algorithm and a heuristically methodology of low computational impact was developed (ALVO algorithm). The sequence flexibility of the operations is based on precedence diagram and an automatic procedure for creation of parts with these characteristics was developed. The proposed methods and procedures had been implemented in Visual Basic 6. Have been builds 152 layouts for each size and configuration being 50 functional, 50 partially distributed, 50 random distributed and 2 maximally distributed (one by ALVO algorithm and another by genetic algorithm). The simulations routing, for each layout type, 30 groups with 150 parts each to obtain the makespan and the traveled total distance. The results showed that performance of the maximally distributed layout has a performance slightly superior to the partially layout, showing that the complete disaggregation of the departments is highly advantageous. The analysis also showed that balanced layouts, when maximally distributed, forms fractal cells.

Este trabalho analisou o desempenho obtido pelos arranjos físicos distribuídos levando em consideração a flexibilidade de seqüenciamento das operações das peças. Foram comparados os arranjos físicos funcional, parcialmente distribuído, aleatoriamente distribuído e maximamente distribuído em três tamanhos (20, 40 e 80 máquinas), em duas configurações (equilibrado e desequilibrado) e usando dois métodos de roteamento (rígido e flexível). Para obtenção do arranjo físico maximamente distribuído foi desenvolvido um algoritmo genético e uma metodologia heurística de baixo impacto computacional denominada ALVO. A flexibilidade de seqüenciamento das operações foi baseada em relações de precedência e um procedimento automático para criação de peças com essas características foi desenvolvido. Os métodos e procedimentos propostos foram computacionalmente implementados em Visual Basic 6. Foram elaborados 152 arranjos físicos para cada tamanho e configuração sendo 50 funcionais, 50 parcialmente distribuídos, 50 aleatoriamente distribuídos e 2 maximamente distribuídos (um pelo algoritmo ALVO e outro pelo algoritmo genético). As simulações rotearam, para cada tipo de arranjo físico, 30 conjuntos com 150 peças cada um para obter o tempo total de programação (makespan) e a distância total percorrida. Os resultados mostraram que o desempenho do arranjo físico maximamente distribuído é sensivelmente superior ao parcialmente distribuído, mostrando que a desagregação completa dos departamentos é altamente vantajosa. As análises também mostraram que os arranjos físicos equilibrados, quando maximamente distribuídos, formam células fractais. / This work analyzes the performance obtained for the distributed layouts when the task routing environment takes in consideration the operations sequence flexibility of the parts. The functional, partially distributed, random distributed and maximally distributed layouts were compared in three sizes (20, 40 and 80 machines), in two configurations (balanced and unbalanced) and using two routing methods (rigid and flexible). For obtainment of the maximally distributed layout a genetic algorithm and a heuristically methodology of low computational impact was developed (ALVO algorithm). The sequence flexibility of the operations is based on precedence diagram and an automatic procedure for creation of parts with these characteristics was developed. The proposed methods and procedures had been implemented in Visual Basic 6. Have been builds 152 layouts for each size and configuration being 50 functional, 50 partially distributed, 50 random distributed and 2 maximally distributed (one by ALVO algorithm and another by genetic algorithm). The simulations routing, for each layout type, 30 groups with 150 parts each to obtain the makespan and the traveled total distance. The results showed that performance of the maximally distributed layout has a performance slightly superior to the partially layout, showing that the complete disaggregation of the departments is highly advantageous. The analysis also showed that balanced layouts, when maximally distributed, forms fractal cells.

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.