Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:36:28Z (GMT). No. of bitstreams: 1 Marini_BrunoConti_M.pdf: 1252984 bytes, checksum: 40439ec279501ea9ca594d950e42a229 (MD5) Previous issue date: 2011 / Resumo: Uma das formas mais econômicas e, em relação ao meio ambiente, mais seguras de se transportar combustíveis é bombeá-los através de redes de dutos. Contudo, as diversas restrições operacionais que precisam ser consideradas fazem com que o planejamento das atividades de bombeamento se transforme em um grande desafio. Dentre os diversos cenários em que o problema se apresenta, investiga-se nessa dissertação o caso de uma rede composta de um único duto onde diversos produtos são bombeados unidirecionalmente. Trata-se de uma situação real enfrentada pela Petrobras no gerenciamento da rede OSBRA. Na literatura existem propostas de vários modelos matemáticos para tratar esta instância particular do problema. Contudo, no melhor do nosso conhecimento, não existem comparações efetivas entre estes modelos e os algoritmos usados para computá-los. Nessa dissertação faz-se uma comparação aprofundada entre três desses modelos, a qual se baseia em uma metodologia sugerida pelos técnicos da Petrobras. Neste trabalho são destacadas não só as dificuldades envolvendo a implementação dos modelos, bem como as deficiências encontradas na aplicação da metodologia de comparação usada pela empresa. Propostas são feitas nessa dissertação no intuito de superar estes obstáculos / Abstract: One of the most economical and, with respect to the environment, safest ways to transport fuel is to pump them through pipeline networks. However, the several operational constraints that have to be considered turn the planning of these activities into a major challenge. Among the several cenarios in which the problem arises, in this dissertation we investigate the case of a network composed of a single pipeline through which several products are pumped unidirectionally. This is a real situation faced by Petrobras in the management of the OSBRA network. In the literature there are proposals of various mathematical models to tackle this particular instance of the problem. However, to the best of our knowledge, there are no effective comparisons of these models and of the algorithms used to compute them. In this dissertation an in-depth comparison is made between three of these models, which is based on a methodology suggested by the technical staff of Petrobras. In this work we highlight not only the difficulties involving the implementation of the models but also the deficiencies encountered in the application of the comparison methodology used by the company. Proposals are made in this dissertation in an attempt to overcome these obstacles / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Raul Vinhas Ribeiro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T00:10:39Z (GMT). No. of bitstreams: 1 Steiner_RenatoMiranda_M.pdf: 2911331 bytes, checksum: f37192c3e00e737a230072ffd04287be (MD5) Previous issue date: 2004 / Resumo: Esta dissertação trata do dimensionamento inicial de tráfego em redes de caminhos ópticos WDM (Wavelength Division Multiplexing) comutadas por comprimento de onda com proteção de caminhos. Fazemos uma introdução das tecnologias chave e dos principais aspectos de planejamento da rede. Apresentamos algumas opções de provisionamento de transporte para diversas arquiteturas de redes clientes. O problema de roteamento e designação de comprimento de onda (RWA ¿ Routing and Wavelength Assignment) é apresentado, e são comparados modelos de programação inteira mista (MILP ¿ Mixed Integer Linear Program) com formulações nó-arco e arco-caminho. A formulação arco-caminho é expandida para incorporar capacidade para proteção compartilhada e dedicada no RWA, em mais dois MILPs. Um algoritmo gerador de rotas alternativas conveniente ao problema foi elaborado. Comparamos diferentes esquemas de restauração de tráfego: pré-configurado 1+1, pré-configurado 1:1, e pré planejado 1:1 e 1:N. A modelagem de proteção/restauração é aplicada a uma rede de 15 nós. Todos os algoritmos foram implementados na linguagem de modelagem AMPL/CPLEX / Abstract: This dissertation is a study about the initial traffic deployment in wavelength-routed WDM (Wavelength Division Multiplexing) optical networks with path protection. We make an introduction of the key technologies and the major network planning aspects. We introduce some architectures for transport provisioning to various client network architectures. The RWA (Routing and Wavelength Assignment) problem is introduced, and node-link and link-path MILP (Mixed Integer Linear Program) formulations are compared. The link-path formulation is expanded to incorporate dedicated and spare capacity in the RWA, in more two MILPs. An algorithm for generation of alternative routes convenient to the problem was elaborated. Different traffic restoration schemes are compared: 1+1, pre-configured 1:1, and pre-planned 1:1 and 1:N. The protection/restoration framework is applied to a 15 nodes network. All the algorithms were implemented on the AMPL/CPLEX modelling language / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Marcius Fabius Henriques de Carvalho / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-08-04T18:10:39Z (GMT). No. of bitstreams: 1 Gibbin_RandalVictor_M.pdf: 340171 bytes, checksum: 8bf48dcb0d44bd8d6f13e705beae8ecc (MD5) Previous issue date: 2005 / Resumo: Neste trabalho procurou-se desenvolver uma ferramenta de suporte à decisão para a seleção de cultivares de Citrus em uma fazenda em fase de implantação localizada em Porto Ferreira/SP. Foram utilizadas as técnicas de Programação Linear para a seleção de cultivares e a Análise de Retorno Esperado para o auxílio na determinação da estimativa de retorno do investimento. Foram determinadas sugestões de ocupação do empreendimento através de três modelos em programação linear, dos quais um foi desenvolvido em programação inteira, os modelos trabalharam com sete cultivares de Citrus desempenhando o papel de variáveis e com restrições de investimento total em insumos, mão-de-obra e área de plantio. Foi realizada uma análise da demanda de laranja de mesa no Estado de São Paulo, determinando-se a equação de regressão descrevendo seu comportamento, a partir desta análise foi construída uma distribuição de probabilidade de demanda de laranja de mesa para o Estado de São Paulo e para o empreendimento, objeto de estudo. A partir destes resultados foi gerada a curva de retorno esperado do empreendimento para a construção de cenários de retorno do investimento. Este trabalho demonstrou a facilidade de aplicação das ferramentas utilizadas em empreendimentos de pequeno porte, fornecendo subsídios para decisões do investidor / Abstract: This investigation describes a set of models to support the decision of a citrus variety selection for an agricultural enterprise located at Porto Ferreira/SP. To achieve this goal were applied the Linear Programming and Expected Return Analysis techniques. By the use of three linear programming models, one of them developed on Integer Programming, were considered seven citrus varieties as decision variables and three constraints: total investment in agro-chemicals, labor and area; the models provided suggestions of land occupation. By the analysis of historical information regarding Citrus production in São Paulo Estate, was developed a Expected Return Analysis for the Citrus production in São Paulo Estate and for the enterprise as well, focused on return on investment. The results obtained from this investigation are important to describe a methodology for supporting the investor decision making process in small agricultural business, due to the easy application of the techniques / Mestrado / Planejamento e Gestão Estrategica da Manufatura / Mestre Profissional em Engenharia Mecanica

[pt] A otimização em esportes é uma área que reúne diversas aplicações relacionadas ao planejamento e gestão de atividades esportivas. Diversas técnicas de otimização combinatória têm sido aplicadas, por exemplo, à  construção de tabelas de torneios e à  análise do desempenho de equipes em competições. Um problema que surge no contexto da organização de competições esportivas consiste na determinação de quais árbitros atuarão em cada partida de um determinado torneio. Diversas regras devem ser observadas no processo de atribuição de árbitros, que em geral envolve também a consideração de vários objetivos. Esta tese tem como objetivo principal apresentar um estudo sobre um problema de atribuição de árbitros, comum a várias ligas esportivas amadoras. Demonstra-se que a versão de decisão do problema estudado é um problema NP-completo. Considera-se inicialmente duas variantes mono-objetivo do PAA, que diferem uma da outra pela função objetivo adotada. Propõe-se modelos de programação linear inteira que permitem uma abordagem exata para a resolução de instâncias de pequeno e médio portes. Com o intuito de tratar instâncias de tamanho real, propõe-se também abordagens aproximadas de resolução baseadas na metaheurí­stica Iterated Local Search (ILS). Uma vez que o PAA tem origem em aplicações reais, ligadas a processos de tomada de decisões, é natural que envolva a consideração de diversos objetivos, muitas vezes em conflito. Tal fato motivou a investigação do uso de técnicas de otimização multi-critério que possam ser utilizadas na construção de um sistema de suporte a decisão e aplicadas a uma variante bi-objetivo do PAA, que considera simultaneamente as duas funções objetivo utilizadas nas variantes mono-objetivo estudadas. Abordagens de resolução exata e aproximada para esta variante bi-objetivo são propostas e seus resultados discutidos. / [en] Optimization in sports is a field of increasing interest. Combinatorial optimization techniques have been applied e.g. to game scheduling and playoff elimination. A problem that arises in competition management is the assignment of referees to games already scheduled. There are a number of rules and objectives that should be taken into account when referees are assigned to games. We address two mono-objective versions of a Referee Assignment Problem (RAP) common to many amateur leagues of sports such as soccer, baseball, and basketball. The problem is formulated by integer programming and its decision version is proved to be NP-complete. To tackle real-life large instances of the RAP, we propose a three-phase heuristic approach based on a constructive procedure, a repair heuristic to make solutions feasible, and a local search heuristic to improve feasible solutions, based on the metaheuristic iterated local search. Numerical results on realistic instances are presented and discussed. This work also investigates the solution of a bi-objective version of the RAP, which combines both objective functions used in the mono-objective versions. Exact and heuristic approaches are proposed to solve this bi-objective version and its computational results are discussed.

La tesis de investigación estuvo orientada a la optimización de las rutas que operan en el transporte de la distribución de mercancía de equipos celulares que se encuentra a cargo del Operador Logístico, a través de la aplicación de la metodología de programación lineal con el uso del solver de Excel. Para lo cual el primer trabajo realizado fue la búsqueda de información asociada al tema de tesis para la confección del marco teórico y la definición de los conceptos básicos utilizados en el tema como son por ejemplo los términos de Investigación de operaciones, programación lineal, distribución física, transporte, ruta óptima y simulación; para posteriormente continuar con el diagnóstico de la situación actual y el análisis de la problemática existente en la distribución física de los productos, relacionado al diseño y desempeño actual de las rutas en la empresa. Luego con la identificación y selección de las rutas a optimizar, se procedió a encontrar la ruta óptima en distancias para cada una de ellas, a través del uso de la programación lineal y uso del software Excel en donde se ingresaron los datos correspondientes de cada ruta. Finalmente se presentaron los resultados obtenidos de cada simulación realizada en el software informático, en donde luego del análisis y comparación entre las distancias de las rutas reales y las rutas ideales simuladas, se pudo comprobar la disminución de distancias a través del uso de la ruta óptima. La disminución de distancias en las rutas disminuyó también el costo de combustible utilizado en la unidad de transporte. The thesis research was oriented to the optimization of routes operating in the transport of distribution of cellular equipment that is in charge of the Logistics Operator, through the application of linear programming methodology. For which the first work was the search for information associated with the thesis topic to prepare the framework and the definition of the basic concepts used in the subject as such terms are operations research, linear programming, physical distribution , transportation, simulation and optimal route; and then continue with the diagnosis of the current situation and identify the problems in the physical distribution of products related to the design and performance of current routes in the company. Then with the identification and selection of routes to optimize, we proceeded to find the optimal route distances for each of them, through the use of linear programming and using the software Excel where the data of each route is entered. Finally the results of simulation performed on each computer software, where after analysis and comparison of the distances of the actual paths and routes ideal simulated showed it was found decreasing distances through the use of the optimum route. Decreasing distances on routes also reduced the cost of fuel used in the transport unit.

[pt] Esta dissertação tem como objetivo propor modelos matemáticos e ferramentas computacionais de assessoria na tomada de decisão para o dimensionamento da frota ótima de veículos. O trabalho apresenta modelos que visam reduzir os custos de transporte para uma frota heterogênea de veículos composta por veículos próprios e terceirizados. Os modelos são baseados em problemas de Bin Packing, Roteirização de veículos e dimensionamento de frotas heterogêneas e foram moldados para atender as necessidades da empresa em estudo. Os resultados obtidos na aplicação de cada modelo foram comparados e as ferramentas computacionais utilizadas foram analisadas para identificar os pontos positivos e negativos. Este trabalho também propõe um modelo que compara a compra de novos veículos com a terceirização das entregas quando a frota própria não é suficiente para atender a demanda. / [en] This dissertation aims to propose mathematical models and computational tools to optimize the dimension of a heterogeneous vehicle fleet in his size and composition. This work shows models that intend to reduce transportation cost for a heterogeneous fleet compose by own and third vehicles. The models are based in problems such as BPP- Bin packing problem, VRP – Vehicle routing problem and linear programming. The problems have been molded to attend the necessities of the company in the study of case. The results achieved in the application of each model were compared and the computational tools had been analyzed to identify positive and negative points. This work also proposes a model that compares the purchase of new vehicles with the delivery by third company when the own fleet is not enough to attend the demand.

Le secteur des semi-conducteurs a connu un développement considérable ces dernières décennies, du fait des nouvelles applications de la microélectronique dans l'industrie. Le processus de fabrication est réputé pour sa complexité. L'un des ateliers les plus critiques de la production, l'atelier de photolithographie, est régi par un ensemble conséquent de contraintes de production. La multiplicité des ressources utilisées, le nombre important de produits traités, en font une zone importante à optimiser. Les objectifs de la thèse ont été de modéliser cet atelier sous la forme d'un problème d'ordonnancement sur machines parallèles et d'optimiser plusieurs critères jugés pertinents pour évaluer la qualité des solutions. Des résultats en termes de complexité, et d'algorithmes de résolution, ont permis une application industrielle, dans la mesure où un logiciel d'optimisation destiné à l'ordonnancement des lots en photolithographie a été développé. / Semiconductor manufacturing has grown considerably in recent decades, due to new industrial applications of microelectronic devices. The related manufacturing process is known to be complex. A bottleneck process step, the photolithography workshop, gathers various types of constraints, related to the number of auxiliary resources and the tools characteristics. The aims of the thesis were to model this workstation as a parallel machine scheduling problem and to optimize various criteria, determined by industrial needs. Some complexity results are provided and optimization algorithms led to an industrial application, i.e. a software providing optimized schedules in a specific fab.

In this dissertation, we examine specific network connectivity problems, and achieve improved approximation algorithm and integrality gap results for them. We introduce an important new, highly useful and applicable, network connectivity problem - the Vital Core Connectivity Problem (VCC). Despite its many practical uses, this problem has not been previously studied. We present the first constant factor approximation algorithm for VCC, and provide an upper bound on the integrality gap of its linear programming relaxation. We also introduce a new, useful, extension of the minimum spanning tree problem, called the Extended Minimum Spanning Tree Problem (EMST), that is based on a special case of VCC; and provide both a polynomial-time algorithm and a complete linear description for it. Furthermore, we show how to generalize this new problem to handle numerous disjoint vital cores, providing the first complete linear description of, and polynomial-time algorithm for, the generalized problem. We examine the Survivable Network Design Problem (SNDP) with multiple copies of edges allowed in the solution (multi-SNDP), and present a new approximation algorithm for which the approximation guarantee is better than that of the current best known for certain cases of multi-SNDP. With our method, we also obtain improved bounds on the integrality gap of the linear programming relaxation of the problem. Furthermore, we show the application of these results to variations of SNDP. We investigate cases where the optimal values of multi-SNDP and SNDP are equal; and we present an improvement on the previously best known integrality gap bound and approximation guarantee for the special case of SNDP with metric costs and low vertex connectivity requirements, as well as for the similar special case of the Vertex Connected Survivable Network Design Problem (VC-SNDP). The quality of the results that one can obtain for a given network design problem often depends on its integer linear programming formulation, and, in particular, on its linear programming relaxation. In this connection, we investigate formulations for the Steiner Tree Problem (ST). We propose two new formulations for ST, and investigate their strength in terms of their associated integrality gaps.

The thesis describes a way of searching a better financial opportunities. The first part is about the multiple criteria decision making. I focus on application methods of multicriterial evaluation of alternatives on different possibilities of solving retirement. The target is to compare different possibilities and then suggest a solution. The second part is about the linear programming. The main objective of the diploma thesis is to suggest a create mathematical model, which I will use in my profession. This mathematical model will display results, which tell us how we can solve the question of money and finance.

The presented thesis is focused on a set of problems related to managerial decision-making concerning networks (particularly transportation networks), respectively - if we put it more precisely - the thesis focuses on the support of this decision-making by means of quantitative methods. A set of problems related to nets and decision-making concerning their individual parts or elements represents a very complex sphere which has been a subject of research for a number of decades. Out of this sphere, the thesis formulates and elaborates in great detail two problems, which - from the point of view of their practical significance - are important for the decision-making of managers of carriers, or the public sphere, and which have not been published in this form yet. The main point is the problem of how to find a subnet with a limited prolongation of routes between important pairs of vertices. Another problem is a design of a bus route in an area with a low demand. For each of these problems, the thesis offers an exact combinatorial solution method, furthermore a method based on integer linear programming, and - last but not least - also, of course, heuristic methods of solution. All these methods have been tested on a set of networks, which has been created for this purpose in a pseudo-random way in the frame of this thesis. The testing has been focused primarily on the comparison of the results provided by heuristic methods, which are of great importance - with regard to a great computational difficulty of exact methods - for feasible tasks on a larger scale. The tests have proved that the proposed heuristic methods are practically applicable and show results whicheven represent the optimal solution in a number of cases, or are only slightly distant from the optimal solution.