Made available in DSpace on 2014-12-17T15:48:08Z (GMT). No. of bitstreams: 1 HerbertMD.pdf: 1096047 bytes, checksum: 6cf0c7d90914e2c3fd03f494b71cfa3a (MD5) Previous issue date: 2006-11-16 / This work consists on the study of two important problems arising from the operations of petroleum and natural gas industries. The first problem the pipe dimensioning problem on constrained gas distribution networks consists in finding the least cost combination of diameters from a discrete set of commercially available ones for the pipes of a given gas network, such that it respects minimum pressure requirements at each demand node and upstream pipe conditions. On its turn, the second problem the piston pump unit routing problem comes from the need of defining the piston pump unit routes for visiting a number of non-emergent wells in on-shore fields, i.e., wells which don t have enough pressure to make the oil emerge to surface. The periodic version of this problem takes into account the wells re-filling equation to provide a more accurate planning in the long term. Besides the mathematical formulation of both problems, an exact algorithm and a taboo search were developed for the solution of the first problem and a theoretical limit and a ProtoGene transgenetic algorithm were developed for the solution of the second problem. The main concepts of the metaheuristics are presented along with the details of their application to the cited problems. The obtained results for both applications are promising when compared to theoretical limits and alternate solutions, either relative to the quality of the solutions or to associated running time / Este trabalho consiste do estudo de dois importantes problemas oriundos das opera??es das ind?strias de petr?leo e g?s natural. O primeiro problema do dimensionamento de dutos em uma rede urbana de distribui??o de g?s natural consiste em encontrar a combina??o de di?metros de menor custo, a partir de um conjunto de op??es comercialmente dispon?veis, para os dutos de uma dada rede de distribui??o de g?s, de forma a respeitar requisitos de press?o m?nima em cada n? de demanda e condi??es de upstream. Por sua vez, o segundo problema do roteamento da unidade m?vel do pistoneio decorre da necessidade de se definir as rotas de visita??o da dita unidade m?vel do pistoneio aos diversos po?os n?o surgentes do campo de explora??o, ou seja, po?os que n?o possuem press?o suficiente para fazer o ?leo emergir ? superf?cie. A vers?o peri?dica do problema leva em considera??o a equa??o de re-enchimento dos po?os, de forma a possibilitar um planejamento mais acurado num horizonte de tempo maior. Al?m da formula??o matem?tica dos dois problemas, para a solu??o do primeiro foram desenvolvidos um algoritmo exato e uma busca tabu e para o segundo, um limite superior e um algoritmo transgen?tico ProtoGene. Os principais conceitos das metaheur?sticas s?o apresentados, juntamente com os detalhes da aplica??o destas aos problemas citados. Os resultados obtidos para ambas as aplica??es s?o promissores quando comparados com limites te?ricos e solu??es alternativas, tanto relativamente ? qualidade das solu??es como ao tempo computacional envolvido

O surgimento de novos serviços de telecomunicações tem provocado um enorme aumento no tráfego de dados nas redes de transmissão. Para atender a essa demanda crescente, novas tecnologias foram desenvolvidas e implementadas ao longo dos anos, sendo que um dos principais avanços está na área de transmissão óptica, devido à grande capacidade de transporte de informação da fibra óptica. A tecnologia que melhor explora a capacidade desse meio de transmissão atualmente é a multiplexação por divisão de comprimento de onda ou Wavelength Division Multiplexing (WDM) que permite a transmissão de diversos sinais utilizando apenas uma fibra óptica. Redes ópticas WDM se tornaram muito complexas, com enorme capacidade de transmissão de informação (terabits por segundo), para atender à explosão de necessidade por largura de banda. Nesse contexto, é de extrema importância que os recursos dessas redes sejam utilizados de forma inteligente e otimizada. Um dos maiores desafios em uma rede óptica é a escolha de uma rota e a seleção de um comprimento de onda disponível na rede para atender uma solicitação de conexão utilizando o menor número de recursos possível. Esse problema é bastante complexo e ficou conhecido como problema de roteamento e alocação de comprimento de onda ou, simplesmente, problema RWA (Routing and Wavelentgh Assignment problem). Muitos estudos foram realizados com o objetivo de encontrar uma solução eficiente para esse problema, mas nem sempre é possível aliar bom desempenho com baixo tempo de execução, requisito fundamental em redes de telecomunicações. A técnica de algoritmo genético (AG) tem sido utilizada para encontrar soluções de problemas de otimização, como é o caso do problema RWA, e tem obtido resultados superiores quando comparada com soluções heurísticas tradicionais encontradas na literatura. Esta dissertação apresenta, resumidamente, os conceitos de redes ópticas e de algoritmos genéticos, e descreve uma formulação do problema RWA adequada à solução por algoritmo genético. / The advent of new telecommunication services resulted in a huge increase of data traffic in the transmission networks. New technologies were developed and implemented over the years to attend to this growing demand, and the optical transmission technology stands. It has advanced greatly, due to the optical fibers large capacity of information transmission. Actually, the best technology to exploits the capacity of the fiber is the wavelength-division multiplexing (WDM), allowing the transmission of multiple signals over a single optical fiber. The WDM optical networks have become very complex, with huge capacity (terabits per second), to attend the ever growing need for bandwidth. In this context, it is extremely important to use the networks resources in an intelligent and optimized way. One of the biggest challenges in an optical network is choosing a route, and selecting a available wavelength on the network to attend a connection request using the least amount of resources. This problem is quite complex, and is known as the routing and wavelength assignment problem or simply RWA problem. Many studies were conducted in order to find an efficient solution to this problem, but it is not always possible to combine good performance with low execution time, a fundamental requirement in telecommunications networks. Genetic Algorithms have been used to solve hard optimization problems, as is the case of the RWA problem, and has produced remarkable results when compared to traditional heuristics found in the literature. This work presents an overview of the concepts of optical networks and genetic algorithms, and describes a formulation of RWA problem that is adequate for solution by genetic algorithm.

O objetivo desta dissertação é avaliar o desempenho de ambientes virtuais de roteamento construídos sobre máquinas x86 e dispositivos de rede existentes na Internet atual. Entre as plataformas de virtualização mais utilizadas, deseja-se identificar quem melhor atende aos requisitos de um ambiente virtual de roteamento para permitir a programação do núcleo de redes de produção. As plataformas de virtualização Xen e KVM foram instaladas em servidores x86 modernos de grande capacidade, e comparadas quanto a eficiência, flexibilidade e capacidade de isolamento entre as redes, que são os requisitos para o bom desempenho de uma rede virtual. Os resultados obtidos nos testes mostram que, apesar de ser uma plataforma de virtualização completa, o KVM possui desempenho melhor que o do Xen no encaminhamento e roteamento de pacotes, quando o VIRTIO é utilizado. Além disso, apenas o Xen apresentou problemas de isolamento entre redes virtuais. Também avaliamos o efeito da arquitetura NUMA, muito comum em servidores x86 modernos, sobre o desempenho das VMs quando muita memória e núcleos de processamento são alocados nelas. A análise dos resultados mostra que o desempenho das operações de Entrada e Saída (E/S) de rede pode ser comprometido, caso as quantidades de memória e CPU virtuais alocadas para a VM não respeitem o tamanho dos nós NUMA existentes no hardware. Por último, estudamos o OpenFlow. Ele permite que redes sejam segmentadas em roteadores, comutadores e em máquinas x86 para que ambientes virtuais de roteamento com lógicas de encaminhamento diferentes possam ser criados. Verificamos que ao ser instalado com o Xen e com o KVM, ele possibilita a migração de redes virtuais entre diferentes nós físicos, sem que ocorram interrupções nos fluxos de dados, além de permitir que o desempenho do encaminhamento de pacotes nas redes virtuais criadas seja aumentado. Assim, foi possível programar o núcleo da rede para implementar alternativas ao protocolo IP. / The aim of this work is to evaluate the performance of routing virtual environments built on x86 machines and network devices existing on the Internet today. Among the most widely used virtualization platforms, we want to identify which best meets the requirements of a virtual routing to allow programming of the core production networks. Virtualization platforms Xen and KVM were installed on modern large capacity x86 machines, and they were compared for efficiency, flexibility and isolation between networks, which are the requirements for good performance of a virtual network. The tests results show that, despite being a full virtualization platform, KVM has better performance than Xen in forwarding and routing packets when the VIRTIO is used. Furthermore, only Xen had isolation problems between networks. We also evaluate the effect of the NUMA architecture, very common in modern x86 servers, on the performance of VMs when lots of memory and processor cores are allocated to them. The results show that Input and Output (I/O) network performance can be compromised whether the amounts of virtual memory and CPU allocated to VM do not respect the size of the existing hardware NUMA nodes. Finally, we study the OpenFlow. It allows slicing networks into routers, switches and x86 machines to create virtual environments with different routing forwarding rules. We found that, when installed with Xen and KVM, it enables the migration of virtual networks among different physical nodes, without interruptions in the data streams, and allows to increase the performance of packet forwarding in the virtual networks created. Thus, it was possible to program the core network to implement alternatives to IP protocol.

Made available in DSpace on 2016-06-02T19:06:10Z (GMT). No. of bitstreams: 1 5631.pdf: 1787133 bytes, checksum: c363525148fa6a5fe71608e7a8ffcf4c (MD5) Previous issue date: 2012-09-28 / Universidade Federal de Sao Carlos / The Wireless Sensor Networks (WSNs) and Mobile Wireless Sensor Networks (MWSNs) are being increasingly used by different applications, such as monitoring of animals, monitoring of vital signs, environmental monitoring, surveillance and protection of critical infrastructure, leaking gas, among many others. Some of these applications are already making use of mobile sensor nodes, such as underwater monitoring, precision agriculture, among many others. Due to restricted resources of sensor nodes, especially in relation to energy consumption, the development for solutions based on WSN and MWSN becomes limited. The use of mobile sensor nodes, which typically has more computational resources, power and communication, can help to reduce the energy consumption of fixed nodes, increasing the lifetime of the network. Networks that use mobile sensor nodes (fixed and mobile) with different types of hardware are called Wireless Sensor Networks Heterogeneous Mobile. This paper presents the RAHMoN (Routing Algorithm for Heterogeneous Mobile Networks), which makes use of data aggregation technique to reduce the traffic transmissions on the network, hierarchy of nodes (clustering), and use of sensor nodes (fixed and mobile) that collaborate to deliver data to a sink node at high speed. In RAHMoN, the network is configured using the techniques of inundation (flooding) and inundation reverse (reverse flooding) to collect the fixed position of sensor nodes and form an adjacency matrix. This matrix helps to build routes for data delivery to the sink and is stored in the mobile sensor nodes. Results show that our solution can guarantee a high packages delivery rate, low latency and reduce the delay of packet delivery. The solution was compared with the WHISPER, present in the literature and also focused on the delivery of data to sink node at high speed. / As Redes de sensores sem Fio (RSSFs) e Redes de Sensores Sem Fio Móveis (RSSFMs) estão sendo cada vez mais utilizadas por diferentes aplicações, tais como: monitoramento de animais, monitoramento de sinais vitais, monitoramento ambiental, vigilância e proteção de infraestruturas críticas, vazamento de gás, dentre inúmeras outras. Algumas dessas aplicações já fazem uso de nós sensores móveis. Devido aos recursos restritos dos nós sensores, principalmente em relação ao consumo energético, o desenvolvimento de soluções baseadas em RSSF e RSSFM torna-se limitado. O uso de nós sensores móveis, que tipicamente têm mais recursos computacionais, de energia e de comunicação, pode ajudar a reduzir o consumo de energia dos nós fixos, aumentando o tempo de vida da rede. Redes que utilizam nós sensores (fixos e móveis) com diferentes tipos de hardware são denominadas Redes de Sensores Sem Fio Móvel Heterogênea. Neste trabalho é apresentado o RAHMoN (Routing Algorithm for Heterogeneous Mobile Networks), que faz uso da técnica de agregação de dados para reduzir o tráfego de transmissões na rede, da hierarquização de nós (clustering), da utilização de nós sensores (fixos e móveis) e de um sink em alta velocidade. No RAHMoN, a rede é configurada utilizando flooding e flooding reverse para coletar a posição dos nós sensores fixos e formar uma matriz de adjacência. Essa matriz auxilia na construção de rotas durante a entrega dos dados para o sink e será armazenada nos nós sensores móveis. Resultados de avaliação mostram que a nossa solução consegue garantir uma alta taxa de entrega de pacotes, diminuir a latência e reduzir o atraso de entrega dos pacotes. A solução foi comparada com o WHISPER, presente na literatura e também voltado à entrega de dados para o nó sink em alta velocidade.

Submitted by Caroline Periotto (carol@ufscar.br) on 2016-09-19T18:29:26Z No. of bitstreams: 1 DissRBL.pdf: 2233937 bytes, checksum: 7a73fb1e4ba8f340cb8d4bdf4e8153d4 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-20T18:01:34Z (GMT) No. of bitstreams: 1 DissRBL.pdf: 2233937 bytes, checksum: 7a73fb1e4ba8f340cb8d4bdf4e8153d4 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-20T18:05:15Z (GMT) No. of bitstreams: 1 DissRBL.pdf: 2233937 bytes, checksum: 7a73fb1e4ba8f340cb8d4bdf4e8153d4 (MD5) / Made available in DSpace on 2016-09-20T18:05:28Z (GMT). No. of bitstreams: 1 DissRBL.pdf: 2233937 bytes, checksum: 7a73fb1e4ba8f340cb8d4bdf4e8153d4 (MD5) Previous issue date: 2015-12-14 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / The Brazilian market for dairy products is highly competitive and is still dominated by multinationals. Thus, it's essential that the national companies to invest in operational efficiency in order to compete successfully. Therefore, this research focuses in a small dairy company of the state of Pará, whose distribution system requires periodic stops for battery recharging. Moreover, the system is characterized by multiple periods and multiple time windows. To our knowledge, so far the literature hasn't presented a directly applicable methodology for the treatmeant of the application with similar characteristics. Therefore, aiming to provide more effective solutions than the ones in practice, a mixed integer linear model was developed to describe (and solve) the problem as a vehicle routing problem with time window constraints, multi-period and periodic stops for recharging. The results showed that the model adequately describes the distribution of the company, and the obtained solutions are better than those currently practiced. Furthermore, the model shows good performance within 3600 seconds of computational time for instances of 40 customers, 1 vehicle and 1 and 2 recharging stations. Aiming to tackle with larger examples, we developed a mathematical programming heuristic Relax-and-Fix to solve the model. It was also tested adapting a similar model present in the literature in order to analyze if the relaxation of some restrictions have a positive impact on the quality of the solutions. Finally, we propose a location-distribution model for recharging stations in order to examine whether the addition of new stations produce significant improvements in the solutions. / O mercado brasileiro de laticínios é altamente competitivo, sendo ainda dominado por multinacionais. Desta forma, é indispensável que as empresas nacionais invistam na eficiência operacional de forma a concorrer satisfatoriamente neste mercado. À vista disso, o foco desta pesquisa é uma pequena empresa de laticínios do Estado do Pará, cujo o sistema de distribuição a pontos de venda possui a particularidade de necessitar de paradas periódicas para recarga da bateria. Ainda, esse sistema tem como característica múltiplos períodos e múltiplas janelas de tempo. Nota-se que o levantamento bibliográfico realizado não apontou nenhuma metodologia diretamente aplicável para solução da aplicação real tratada. Portanto, objetivando provar soluções mais efetivas que as correntemente aplicadas na prática, foi desenvolvido um modelo linear inteiro misto para descrever (e resolver) o problema como um problema de roteamento de veículos com restrições janela de tempo, multi-períodos e paradas periódicas para recarga. Os resultados mostraram que o modelo proposto descreve adequadamente o processo distribuição da empresa, e as soluções obtidas são melhores que as praticadas atualmente. Além disso, verificou-se que o modelo tem um desempenho satisfatório em até 3600 segundos de processamento para instâncias de até 40 clientes, 1 veículo e até 2 postos de recarga. Com vistas ao tratamento de problemas de maior porte, foi desenvolvida uma heurística de programação matemática do tipo Relax-and-Fix para resolução do modelo. Também foi testada a adaptação de um modelo similar presente na literatura, visando analisar se a relaxação de algumas restrições impacta positivamente na qualidade das soluções. Finalmente, é proposto um modelo de localização-distribuição de postos de recarga, de forma a se examinar se a inclusão de novos postos produz melhorias significativas nas soluções atuais. / FAPESP: 14/10330-0

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-06T17:59:08Z No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:08Z (GMT) No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T13:51:14Z (GMT) No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) / Made available in DSpace on 2016-10-20T13:51:20Z (GMT). No. of bitstreams: 1 DissJFSN.pdf: 5729965 bytes, checksum: 946688f479f7780db197fa49b4b4c853 (MD5) Previous issue date: 2016-03-21 / Não recebi financiamento / Vehicle routing problems occur in many practical situations where the pickup and/or delivery of goods is required. In this context, the present research aims to contribute to the study of logistic operations that arise in companies that deliver products on a regular basis to customers in densely populated urban areas. The problem consists in designing minimal cost daily routes serving the maximal number of customers. To this end, the crew of each vehicle comprise multiple deliverymen as means to reduce service times. Based on a case study in a drinks producer and distributor in the state of São Paulo, it is proposed a mixed integer linear programming model that comprise costs with own and chartered vehicles and the number of deliverymen, and various operational constraints such as time windows in customers, multiple daily trips, time limitations for the circulation of some vehicle types in specific areas, compatibility between vehicles and customers, maximum load in each vehicle, maximum route time and minimum load for the realization of a second trip. Results obtained by solving the model with real instances through exact (branch&cut), heuristic (constructive, local search, GRASP and Simulated Annealing) and hybrid (GRASP and branch&cut) approaches demonstrate the good quality of the generated solutions, and indicate the potential of application of some of these methods in practice. / Problemas de roteamento de veículos ocorrem em diversas situações práticas onde se faz necessária a distribuição e/ou coleta de produtos. Nesse contexto, a presente pesquisa visa o estudo das operações logísticas presentes em empresas que entregam produtos em base regular a clientes localizados em áreas urbanas de alta densidade demográfica. O problema consiste na obtenção de rotas de mínimo custo visando o atendimento do maior número de clientes da carteira diária. Para tal, a tripulação de cada veículo pode contemplar múltiplos entregadores para redução dos tempos de serviço. Com base em um estudo de caso em uma distribuidora de bebidas do interior do Estado de São Paulo, é proposto um modelo de programação linear inteira mista que considera custos com frota própria e fretada e com o número de entregadores, e diversas restrições operacionais, tais como janelas de tempo em clientes, múltiplas viagens diárias, limitações de horários de circulação de tipos de veículos, compatibilidade entre veículos e clientes, capacidade máxima de carga a ser transportada em cada veículo, tempo máximo de rota e carga mínima para realização da segunda viagem. Resultados da resolução do modelo para instâncias reais por meio de abordagens exatas (branch&cut), heurísticas (construtiva, busca local, GRASP e Simulated Annealing) e híbrida (GRASP e branch&cut), demonstram a boa qualidade das soluções geradas, e evidenciam o potencial de uso dessas metodologias na prática.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-24T10:38:55Z No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:50:29Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:51:23Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Made available in DSpace on 2017-02-08T10:51:33Z (GMT). No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) Previous issue date: 2016-04-01 / Outra / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / The object of this study is the routing and scheduling problem of vessels with pickup and delivery and time windows in the oil industry. A case study was performed in a Brazilian oil industry that produces crude oil in o shore platforms, that is, located in the ocean, and transports to the terminals located in the Brazilian coast. Then, it was proposed a mixed integer model to represent the problem adequately and for this, a detailed analysis of the real problem in order to know all its characteristics and consider some simplifying assumptions. Therefore, to the pickup and delivery problem with time windows present in the literature were aggregated other speci c restrictions of the case study, for example, multiple depots, ship mooring restrictions, exible draft and dynamic positioning. Besides that, the eet is heterogeneous related to capacity, LOA (length overall), dynamic positioning and velocity. In practice, in general there are no identical vessels. This problem can be represented as a combinatorial optimization model, which belongs to the NP-hard class and its solution is a challenging in practice depending on the size of the real problems. Then, were proposed several exact branch-and-cut methods based on models with 2 and 3-index variables for routing problems with pickup and delivery and time windows to solve speci cally the Brazilian oil industry problem. Finally, we proposed a branch-and-price method, which includes all characteristics of the problem in oil industry. In summary, the main contributions of this thesis are related to the study and modeling of this problem in practice, and the proposal and development of exact solution methods to solve it, based on branch-and-cut and branch-and-price. The performance of the mathematical model in optimization software and the exact methods were veri ed using a real data set provided by the company. Results show that these approaches may be e ective to solve problems of moderate size in real situations. / O objeto de estudo deste trabalho é o problema de roteamento e programação de navios com coleta e entrega e janelas de tempo na indústria petrolífera. Foi realizado um estudo de caso com uma empresa petrolífera brasileira que produz óleo cru em plataformas o shore, isto é, localizadas no oceano e os transporta até os terminais localizados na costa brasileira. Então, foi proposto um modelo de programação inteira mista para representar o problema adequadamente e para isso, foi necessária uma análise detalhada do problema real, com o intuito de conhecer todas as suas características e considerar hipóteses simpli cadoras. Desta maneira, ao problema de coleta e entrega e janelas de tempo da literatura foram agregadas outras restrições especí cas do problema do estudo de caso como, por exemplo, múltiplos depósitos, restrições de atracação dos navios, calado exível e posicionamento dinâmico. Além disso, a frota de navios é heterogênea em relação à capacidade, LOA (length overall ), posicionamento dinâmico e velocidade. Na prática, em geral não existem navios iguais. Este problema pode ser representado como um modelo de otimização combinatória que pertence à classe NP-difícil e sua solução é bastante desa adora na prática em função do tamanho dos problemas reais. Depois, foram propostos vários métodos do tipo branch-and-cut baseados em modelos com variáveis de 2 e 3-índices para problemas de roteamento com coleta e entrega e janelas de tempo para resolver especi camente o problema da empresa brasileira. E por m, foi proposto um método do tipo branch-and-price, o qual abrange todas as características do problema da indústria petrolífera. Em síntese, as principais contribuições desta tese referem-se ao estudo e modelagem deste problema na prática, e a proposta e desenvolvimento de métodos de solução exatos para resolvê-lo, baseados em branch-and-cut e branch-and-price. O desempenho do modelo matemático em softwares de otimização e também dos métodos exatos propostos foi veri cado usando-se exemplares reais fornecidos pela empresa. Os resultados mostram que essas abordagens podem ser efetivas para resolver problemas de tamanho moderado em situações reais.

Made available in DSpace on 2016-06-02T19:50:25Z (GMT). No. of bitstreams: 1 6346.pdf: 5901404 bytes, checksum: 2d78b0f5f68ac25a089acd315f55b157 (MD5) Previous issue date: 2014-06-09 / The production of sugar, ethanol and electricity from sugar cane necessarily involves harvesting and transportation of raw materials, which are expensive and complex operations and have significant influence on the quality of the industrial raw material. The literature reports several optimization approaches related to the planning of planting, harvesting and transporting of sugarcane, however the scheduling of harvesting fronts is underexplored. This thesis intends to contribute to the state-of-art of this important issue in the context of the Brazilian agribusiness. Optimization approaches to support scheduling decisions of harvesting fronts considering the balance of harvesting and transportation capacities, as well as good agronomic management are proposed. The approaches are inspired by the representation of the problem as a lot sizing and scheduling model with parallel machines and sequence-dependent setup costs and times, a modelling technique well studied in the production planning and control literature. Three variants of this formulation, based on mathematical programming models, were developed and tested in two real case studies of medium size sugar mills. Heuristic methods based on aggregation procedures and mathematical programming have also been studied and developed to solve large scaled problems found in practice. Among the three variants studied, one presented the best solution quality within the expected execution time. Important scenario analysis were done indicating that the schedule s fulfilment provides reduction of harvesting and transporting complexity to the following season, which can generate significant saves in the cases studied. Besides that, comparing the proposed scheduling method with one of the sector s practice, it can be generated also significant cost reduction in the cases studied. The results were analyzed according to a validation methodology (descriptive facet of tetraedrum) well known in the literature. / A produção de açúcar, álcool e energia elétrica a partir de cana-de-açúcar passa necessariamente pela colheita e transporte da matéria-prima, que são operações custosas, complexas e que interferem significativamente na qualidade da matéria-prima industrial. A literatura reporta várias abordagens de otimização relacionadas ao planejamento do plantio, da colheita e do transporte de cana-de-açúcar, todavia a programação das frentes de colheita é pouco explorada. Nesta tese pretende-se contribuir para o estado da arte deste importante tema no contexto do agronegócio brasileiro. Propõe-se abordagens de otimização para apoiar decisões de programação das frentes de colheita, considerando-se o equilíbrio das capacidades de colheita e transporte, bem como um bom manejo agronômico. As abordagens são inspiradas na representação do problema por meio de um modelo de dimensionamento de lotes e sequenciamento da produção em máquinas paralelas com custos e tempos de setup dependentes da sequência, bem estudado na literatura em contextos de planejamento e controle da produção. Para isso foram desenvolvidas três variantes desta formulação baseadas em programação matemática, voltadas para a programação das frentes de colheita, que foram testadas em dois estudos de caso reais de usinas de cana-de-açúcar de médio porte do setor. Métodos heurísticos baseados em procedimentos de agregação e programação matemática também foram estudados e desenvolvidos para a resolução dos problemas de grande porte encontrados na prática. Das três variantes estudadas, uma delas apresentou melhor qualidade da solução dentro de tempos computacionais aceitáveis para o problema. Análises de cenário importantes foram feitas indicando que o cumprimento da programação proporciona redução de complexidade da colheita e transporte na safra seguinte, podendo gerar economias significativas nos casos estudados. Além disso, a comparação dos resultados das abordagens aqui exploradas com o que é praticado no setor indica um potencial de redução de custos também significativo para os casos estudados. Os resultados foram analisados de acordo com uma metodologia de validação (faceta descritiva do tetraedro) conhecida na literatura.

Made available in DSpace on 2016-12-12T17:38:37Z (GMT). No. of bitstreams: 1 ALEXANDRE ITTNER.pdf: 1538757 bytes, checksum: f2722c8cdafb578a75d3a153751fa3a1 (MD5) Previous issue date: 2010-08-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation presents a research work on the Cable Routing Problem in Electrical Panels and its resolution by computational means. Strictly, this work shows a formal definition for the problem, elaborates on the available computational approaches, and suggests several algorithms for its resolution. At last, an application developed using the proposed algorithms is described, yielding good results for the problem instances typically found in the industry. / Esta dissertação apresenta um estudo sobre as características do Problema do Roteamento de Cabos em Painéis Elétricos e sua solução por meios computacionais. Especificamente, este trabalho apresenta uma definição formal para o problema, descreve as abordagens computacionais disponíveis e propõe uma série de algoritmos para sua solução. Por fim, descreve-se um aplicativo desenvolvido empregando os algoritmos propostos que permite a obtenção de bons resultados para as instâncias deste problema tipicamente encontradas na indústria.

O objetivo desta dissertação é avaliar o desempenho de ambientes virtuais de roteamento construídos sobre máquinas x86 e dispositivos de rede existentes na Internet atual. Entre as plataformas de virtualização mais utilizadas, deseja-se identificar quem melhor atende aos requisitos de um ambiente virtual de roteamento para permitir a programação do núcleo de redes de produção. As plataformas de virtualização Xen e KVM foram instaladas em servidores x86 modernos de grande capacidade, e comparadas quanto a eficiência, flexibilidade e capacidade de isolamento entre as redes, que são os requisitos para o bom desempenho de uma rede virtual. Os resultados obtidos nos testes mostram que, apesar de ser uma plataforma de virtualização completa, o KVM possui desempenho melhor que o do Xen no encaminhamento e roteamento de pacotes, quando o VIRTIO é utilizado. Além disso, apenas o Xen apresentou problemas de isolamento entre redes virtuais. Também avaliamos o efeito da arquitetura NUMA, muito comum em servidores x86 modernos, sobre o desempenho das VMs quando muita memória e núcleos de processamento são alocados nelas. A análise dos resultados mostra que o desempenho das operações de Entrada e Saída (E/S) de rede pode ser comprometido, caso as quantidades de memória e CPU virtuais alocadas para a VM não respeitem o tamanho dos nós NUMA existentes no hardware. Por último, estudamos o OpenFlow. Ele permite que redes sejam segmentadas em roteadores, comutadores e em máquinas x86 para que ambientes virtuais de roteamento com lógicas de encaminhamento diferentes possam ser criados. Verificamos que ao ser instalado com o Xen e com o KVM, ele possibilita a migração de redes virtuais entre diferentes nós físicos, sem que ocorram interrupções nos fluxos de dados, além de permitir que o desempenho do encaminhamento de pacotes nas redes virtuais criadas seja aumentado. Assim, foi possível programar o núcleo da rede para implementar alternativas ao protocolo IP. / The aim of this work is to evaluate the performance of routing virtual environments built on x86 machines and network devices existing on the Internet today. Among the most widely used virtualization platforms, we want to identify which best meets the requirements of a virtual routing to allow programming of the core production networks. Virtualization platforms Xen and KVM were installed on modern large capacity x86 machines, and they were compared for efficiency, flexibility and isolation between networks, which are the requirements for good performance of a virtual network. The tests results show that, despite being a full virtualization platform, KVM has better performance than Xen in forwarding and routing packets when the VIRTIO is used. Furthermore, only Xen had isolation problems between networks. We also evaluate the effect of the NUMA architecture, very common in modern x86 servers, on the performance of VMs when lots of memory and processor cores are allocated to them. The results show that Input and Output (I/O) network performance can be compromised whether the amounts of virtual memory and CPU allocated to VM do not respect the size of the existing hardware NUMA nodes. Finally, we study the OpenFlow. It allows slicing networks into routers, switches and x86 machines to create virtual environments with different routing forwarding rules. We found that, when installed with Xen and KVM, it enables the migration of virtual networks among different physical nodes, without interruptions in the data streams, and allows to increase the performance of packet forwarding in the virtual networks created. Thus, it was possible to program the core network to implement alternatives to IP protocol.