Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com o passar do tempo, a demanda elétrica de diversas áreas varia tornando necessária a construção de novos geradores elétricos e a expansão da rede de transmissão de energia elétrica. Nesta dissertação, focamos no problema de expansão da rede de transmissão, assumindo que novos geradores estão construídos para suprir as novas demandas. Essa expansão exige altos investimentos que precisam ser cuidadosamente planejados. O problema pode ser modelado como um problema de otimização não linear inteira mista e pertence à classe dos problemas NP-difíceis. Desta forma, uma abordagem heurística pode ser adequada para a sua solução pois pode vir a fornecer boas soluções em tempo computacional aceitável. Esta dissertação se propõe a apresentar um estudo do problema de planejamento da expansão de redes de transmissão de energia elétrica estático e multiestágio. Mostramos o que já existe na literatura para o que é chamado de problema sem redimensionamento e as inovações feitas por nós para o problema com redimensionamento. Quanto aos métodos de solução, utilizamos a metaheurística GRASP para o problema estático e combinamos o GRASP com o procedimento Backward-Forward quando falamos em problema multiestágio. Nesta dissertação comparamos os resultados computacionais obtidos com resultados encontrados na literatura. / At times, the electrical load in diferent areas varies, claiming the construction of new electric generators and the expansion of the electrical transmission network. In this dissertation we focus on the transmission expansion planning problem, assuming that new generators are built to meet the new demands. This expansion requires large investments, which need to be carefully planned. This problem can be modeled as a mixed nonlinear programming problem, considered to be a NP-hard problem. Therefore a heuristic approach may be appropriate for its solution because it might be able to provide good solutions in satisfactory computational time. This dissertation intends to present a study of both the static and multistage transmission expansion planning problem. We present first a review of the most interesting works found in the technical literature. Then, we present metaheuristics for the static and multistage problems with re-design. These etaheuristics extend known algorithms for the problems without re-design. For the static problem, we extend a GRASP procedure and for the multistage problem, we embed the GRASP (or an exact method) into a backward-forward algorithm. We test our algorithms on real-based power transmission networks and compare them to the results found in the litterature.

Esta dissertação estuda o problema da programação de operações em sistemas job shop de manufatura onde itens com estruturas de materiais são produzidos a partir de componentes fabricados e montados. Tais sistemas são denominados assembly shops. O caso geral do problema de programação de operações em sistemas job shop, no qual não existem restrições quanto ao número de operações a serem programadas nem quanto ao número de máquinas a serem alocadas, é considerado, até o presente momento, intratável do ponto de vista computacional devido à explosão combinatória inerente ao processo de programação, independente da escolha do critério de desempenho. Isto significa dizer que não existe nenhum método eficiente de programação que resolva globalmente instâncias de porte real do problema dentro de um tempo computacional considerado satisfatório. Devido a este fato, nas últimas três décadas, diversos métodos aproximados e heurísticos foram propostos e avaliados para o problema. Nesta pesquisa, é proposto e avaliado um novo método heurístico de programação. Fundamentado na pressuposição de que a melhoria na sincronização de operações de montagem em sistemas assembly shop leva ao melhor atendimento de datas de entrega de pedidos, o método implementa duas abordagens de programação: uma abordagem backward que satisfaz completamente as datas de entrega e outra forward que satisfaz completamente a restrição de capacidade de máquina. Ambas trabalham iterativamente dentro de dois modelos de simulação do sistema de produção um determinístico e outro probabilístico na busca pela melhoria da sincronização das operações e no atendimento das datas de entrega. Os resultados experimentais demonstraram que o desempenho do novo método foi em média melhor que os dos métodos não iterativos (regras) avaliados e tão bom quanto o desempenho do melhor método não iterativo (regra) testado. / This dissertation studies the problem of scheduling operations in manufacturing job shop environments where items with bill of materials are made of many fabricated and assembled components. Such systems are known as assembly shops. The general job shop scheduling problem, which no restrictions exist neither for the number of operations to be scheduled nor for the number of machines to be allocated, is considered at the present date intractable from the computational point of view, whatever the performance criterion used, due to the combinatorial explosion inherent to the scheduling process. It means that there is not an efficient computational method that solves globally real size instances of the problem within a satisfactory period of time. Due to this fact, in the last three decades several approximated and heuristic methods were created and evaluated for the problem. This research proposes and evaluate a new heuristic method which is based on the assumption that the improvement in operations synchronization at the assembly stations brings forth better achievement of due dates. The method implements two scheduling approaches: a backward approach satisfying due date completely and a forward approach satisfying capacity restriction completely. The two approaches work iteratively within two different simulation models of the production system one deterministic e other probabilistic in searching for operations synchronization improvement and due date achievement. The experimental results have shown the new method was better than the single-pass methods (rules) on average and as good as the better single-pass method (rule) tested.

A seleção de fornecedores é um problema complexo e que vem ganhando importância estratégica nas organizações, principalmente devido à inclusão de diversos atributos que podem ser especificados de acordo com as necessidades da situação, pois o fator custo não é mais o único responsável pela decisão. A relevância da sustentabilidade, em termos econômicos, ambientais e sociais, traz ao tema ainda mais atributos que devem ser mapeados como parte da decisão. Neste trabalho é proposta uma abordagem baseada em otimização combinatória (programação linear inteira) aliada à análise de valor multicriterial que estabelece prioridades e compensações entre os atributos definidos, para seleção de fornecedores de um conjunto de embalagens de cosméticos para uma nova linha de produtos. A solução encontrada é comparada aos métodos de otimização tradicionais (monocriteriais) e à otimização multicriterial sem leilão combinatório. Também são realizadas análises de sensibilidade com o modelo, permitindo que sejam feitas validações de forma a justificar a decisão. / Supplier selection is a complex issue that has gained strategic importance in organizations, mainly due to the consideration of several criteria that can be specified according to the situation, since cost is no longer solely responsible for the decision. The sustainability relevance, in economical, environmental and social terms, brings to the theme even more criteria that should be included as part of the decision. This work proposes an approach based on combinatorial optimization (integer linear programming) combined with multi-criteria value analysis that establishes priorities and trade-offs among the defined criteria, to the supplier selection of a cosmetics packaging set for a new product line. The obtained solution is compared to traditional optimization methods (mono-criteria) and to the multi-criteria optimization without combinatorial auction. Sensitivity analyses are also performed with the model, allowing assessments to be made in order to justify the decision.

O planejamento de rotações de culturas é um tema de interesse em ascensão por permitir uma redução significativa no uso de adubos industriais, agrotóxicos e outros produtos químicos no cultivo, permitindo a auto-sustentação e qualidade das terras cultivadas. Este trabalho centraliza em utilizar rotações para atender uma demanda periódica prédeterminada, respeitando as restrições relativas a aspectos ecológicos que auxiliam na estabilidade geral do solo para definir uma rotação de culturas factível. Modelos matemáticos que consideram um tamanho mínimo de lote a ser usado por uma rotação e métodos heurísticos, baseados em geração de colunas, são apresentados. Uma análise detalhada do comportamento dos métodos perante variações em diferentes parâmetros e critérios é realizada. A primeira heurística, denominada Algoritmo GC-BC, obteve resultados de melhor qualidade e de forma mais rápida que a segunda heurística, denominada Heurística Lote Fixo. Entretanto, combinando ambas heurísticas foi possível obter os resultados mais satisfatórios, ou seja, soluções que respeitam a condição de lote mínimo em um tempo computacional aceitável para um planejamento anual, cujos valores são próximos a um limitante superior. A ideia subjacente de gerar colunas adicionais para um problema mestre restrito produz soluções de qualidade, o que pode vir a ser aplicado em outras áreas de pesquisa que necessitam da geração de colunas para uma resolução em tempo computacional viável / The crop rotation planning is a rising topic for providing a significative reduction on the usage of industrial fertilizers, pesticides and other chemical, allowing the soil to selfsustain. This study focus on using rotations to meet a periodic and pre-defined demand while ecologic restrictions, that help sustain the soils stability, define a valid crop rotation. Mathematical models that consider a minimum size of a used lot associated with a given rotation and heuristic resolution methods, based on column generation, are presented. A detailed analysis of the methods behaviour before changes on parameters and criteria is performed. The first heuristic, called GC-BC Algorithm, achieved better and faster results compared to the second heuristic, called Fixed Lot Heuristic. However, combining both heuristics produced even better results, that is, solutions that respect the minimum lot sizing restrictions in good execution time for an annual planning. The idea behind of generating additional columns to the restricted master problem produces good quality solutions, which may be applicable in other research areas that require column generation for their resolution with a reasonable execution time

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T05:20:45Z (GMT). No. of bitstreams: 1 SanFelice_MarioCesar_M.pdf: 1592906 bytes, checksum: 7d6d43104cbdeb2ad46a93e6ef11ae23 (MD5) Previous issue date: 2010 / Resumo: Nesta dissertação consideramos o problema do k-Servidor. Neste problema temos k servidores em um espaço métrico e nosso objetivo e atender a uma seqüência de requisições, de modo a minimizar a distancia total percorrida pelos servidores. Dedicamos especial atenção a conjectura do k-Servidor: qualquer espaço métrico admite um algoritmo k-competitivo para o problema do k-Servidor. Este e um dos problemas mais importantes em aberto da area de computação online. O algoritmo da função trabalho, proposto por Chrobak e Larmore, e especialmente relevante para a conjectura. Isto porque foi provado que este algoritmo e k-competitivo para diversos casos particulares do problema do k-Servidor. Alem disso, acredita-se que este algoritmo e de fato k-competitivo para todo espaço métrico. Por isto, o entendimento deste algoritmo e central neste trabalho. Para analisar o algoritmo da função trabalho são utilizados diversos resultados auxiliares desenvolvidos por vários autores. Neste trabalho tentamos apresentar de forma coesa uma coletânea destes resultados. A partir desta mostramos uma prova do teorema de Koutsoupias e Papadimitriou: o algoritmo da função trabalho e (2k - 1)-competitivo para todo espaço métrico. Este e o resultado mais importante relacionado ao problema do k-Servidor. Alem disso, mostramos que a conjectura do k-Servidor vale para alguns casos particulares do problema / Abstract: In this work we study the k-server problem. In this problem, we have k servers on a metric space that must attend a sequence of requests with the goal of minimizing the total distance moved by the servers. We dedicate special attention to the k-server conjecture: any metric space allows for a k-competitive k-server algorithm. This is one of the most important open problems in online computing. The work function algorithm, proposed by Chrobak and Larmore, is very relevant to the conjecture. It has been proved that this algorithm is k-competitive for several special cases of the k-server problem. Furthermore, most researchers believe that the algorithm is indeed k-competitive for any metric space. Thus, a deeper understanding of this algorithm plays a special role in this work. To analyze the work function algorithm, we use many auxiliary results developed by several authors. In this work we tried to present a collection of these results in a concise way. From this, we present a proof of Koutsoupias and Papadimitriou's theorem: the work function algorithm is (2k - 1)-competitive for any metric space. This is the most important result related to the k-server problem. Moreover, we show that the k-server conjecture holds in some special cases / Mestrado / Otimização Combinatoria / Mestre em Ciência da Computação

Orientador: Vinícius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T07:40:14Z (GMT). No. of bitstreams: 1 Sacchi_LuisHenrique_D.pdf: 1448719 bytes, checksum: f89915d271683e250283d8ec86b25839 (MD5) Previous issue date: 2010 / Resumo: Este trabalho apresenta um estudo computacional da busca tabu paramétrica para resolver problemas de programação inteira mista (PIM) com variáveis binárias. Trata-se de uma heurística genérica para problemas PIM gerais que resolve uma série de problemas de programação linear ao incorporar inequações de ramificação de variáveis inteiras como termos ponderados na função objetivo. O procedimento central do método é baseado em memória de curto prazo da busca tabu, enquanto fases de intensificação e diversificação são induzidas pela memória de longo prazo baseada em freqüência e idéias derivadas de scatter search. Novas estratégias são propostas para encontrar soluções de alta qualidade e extensivos testes computacionais são realizados em instâncias da literatura / Abstract: We present a computational study of parametric tabu search for solving 0-1 mixed integer programming (MIP) problems, a generic heuristic for general MIP problems that solves a series of linear programming problems by incorporating branching inequalities as weighted terms in the objective function. The core procedure is founded on short term memory, whereas both intensification and diversification phases are induced by long term memory based on frequency and ideas derived from scatter search. New strategies are proposed for uncovering feasible and high-quality solutions and extensive computational tests are performed on instances from the literature / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:58:08Z (GMT). No. of bitstreams: 1 Porto_ClaudiaAkemiFurushima_M.pdf: 1805902 bytes, checksum: 15341772d15a37d8642fa403d27fbd6a (MD5) Previous issue date: 2010 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic digital document / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T20:59:25Z (GMT). No. of bitstreams: 1 Azuma_ReginaMitsue_M.pdf: 2321816 bytes, checksum: 44c4417bf2a4fad2a8241c7189e4d04a (MD5) Previous issue date: 2011 / Resumo: A classe de problemas de estoque e roteamento está presente em várias áreas, incluindo indústria automobilística e gerência de numerário no reabastecimento de caixas eletrônicos. Supondo que o fornecedor é responsável pela estocagem e distribuição dos produtos, sujeito a um conjunto de restrições, o desafio que se apresenta é a determinação de uma política ótima, mais especificamente quais clientes atender, qual quantidade a ser fornecida a cada cliente e qual rota empregar visando a minimização dos custos. Este trabalho apresenta uma proposta de solução para uma das mais comuns formulações do problema: um produto é distribuído a partir de um fornecedor para vários clientes em um horizonte de tempo definido. O transporte é realizado por um veículo de capacidade limitada. Para produzir a otimização simultânea de ambos os objetivos, minimização dos custos de transporte e estoque, a proposta segue uma abordagem multiobjetivo e se baseia no uso do algoritmo SPEA2 (do inglês, Strength Pareto Evolutionary Algorithm 2), incluindo inovações na representação de soluções-candidatas, nos operadores genéticos e de busca local. A fronteira de Pareto estimada é então composta de múltiplas soluções não-dominadas, representando compromissos distintos entre custos de transporte e estoque. Como casos de estudo, são tomadas instâncias de médio porte extraídas da literatura e são geradas instâncias de grande porte. Para as instâncias de médio porte, as fronteiras de Pareto estimadas em cada caso são comparadas com as respectivas soluções ótimas da versão mono-objetivo de cada problema, pois já existe um algoritmo exato de solução para a formulação mono-objetivo de instâncias de médio porte / Abstract: The class of inventory routing problems (IRP) is present in several areas, including automotive industry and cash management for ATM networks. Given that the supplier is responsible for managing the product inventory and replenishment, subject to a set of restrictions, the challenge here is to determine an optimal policy, more specifically which retailers to serve, the quantity to deliver to each retailer and which routes to employ in order to minimize the cost. This work presents a proposal to solve one version of the IRP usually found in the scientific literature: a product is distributed from a supplier to several retailers in a defined time horizon. Shipment is performed by a vehicle with limited capacity. To perform the simultaneous optimization of both objectives, minimization of transportation and inventory costs, the proposal follows a multi-objective approach based on SPEA2 (Strength Pareto Evolutionary Algorithm 2), including innovative aspects mainly associated with the representation of candidate solutions, genetic operators and local search. The Pareto front is then composed of multiple non-dominated solutions with distinct trade-offs between transportation and inventory costs. As case studies, medium size instances extracted from the literature are considered and large size instances are generated. For the medium size instances, the estimated Pareto fronts are compared, in each case, with the corresponding optimal solutions associated with the single-objective version of each problem, given that there is already an exact algorithm to solve such medium size single-objective instances / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientadores: Christiano Lyra Filho, Celso Cavellucci / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T02:44:14Z (GMT). No. of bitstreams: 1 VizcainoGonzalez_JoseFederico_D.pdf: 9526841 bytes, checksum: 9fc3b73df592526f56693f9b329fc70c (MD5) Previous issue date: 2011 / Resumo: O trabalho desenvolve alternativas de otimização combinatória para a redução de perdas técnicas e melhoria das condições de operação de sistemas de distribuição de energia elétrica. Sua principal contribuição é na área de redução dos fluxos de reativos através da instalação e controle de bancos de capacitores. Duas alternativas de otimização são desenvolvidas. A primeira, propõe um algoritmo genético híbrido com buscas locais nas representações fenotípicas e genotípicas das soluções. A segunda alternativa utiliza conceitos de programação dinâmica no projeto de algoritmos que encontram soluções ótimas globais para o problema de localização, dimensionamento e controle de capacitores. Outro algoritmo genético híbrido, para a instalação de reguladores de tensão, complementa a possibilidade de melhoria nos perfis de tensão proporcionada pelos capacitores. Os algoritmos baseados em programação dinâmica são de complexidade polinomial; adicionalmente, suas complexidades são lineares para instâncias reais. As características desses algoritmos estabelecem novas referências para a área de localização e controle de capacitores em sistemas de distribuição de energia elétrica, hoje povoada por métodos heurísticos / Abstract: This work develops combinatorial optimization alternatives for technical loss reduction and improvements on operational conditions of power distribution networks. Its main contribution is in the area of loss reduction by decreasing reactive flows, through allocation and control of shunt capacitors banks. Two optimization strategies are proposed. The first one develops a hybrid genetic algorithm with local searches in both genotypical and fenotypical representations of solutions. The second alternative uses dynamic programming concepts in the design of algorithms that unveil global optimal solutions for capacitor location, sizing and control. Another hybrid genetic algorithm for allocation of voltage regulators complements the improvement in voltage profiles obtained with the allocation of capacitors. The algorithms based on dynamic programming concepts have polynomial-time complexity; further, they have linear-time complexity for practical applications. Therefore, these algorithms establish a new reference for the area of shunt capacitors allocation and control on power distribution systems, which is today populated by heuristic methods / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Orientadores: Carlos Alberto Favarin Murari, Ruben Augusto Romero Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-05T08:51:38Z (GMT). No. of bitstreams: 1 SilvaJunior_IreniodeJesus_D.pdf: 556445 bytes, checksum: 5c960cb84852b3168eabbeed28c1a28a (MD5) Previous issue date: 2005 / Resumo: Este trabalho apresenta algumas propostas para solucionar o problema de planejamento da expansão de sistemas de transmissão, estático e multiestágio, considerando restrições de segurança - critério de segurança (n_1), assim como para o planejamento da expansão de um sistema elétrico que satisfaça simultaneamente vários planos de programação da geração pré-especificados. Visando superar deficiências na determinação de soluções ótimas para sistemas de grande porte quando se usa métodos exatos, como decomposição de Benders e algoritmos Branch and Bound, implementouse um algoritmo genético (AG) especializado, o AG de Chu-Beasley. Utilizou-se o modelo DC para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Para a geração da população inicial e melhora de um descendente do AG de Chu-Beasley utilizou-se o algoritmo heurístico construtivo de Villasana-Garver-Salon / Abstract: This Ph.D. thesis presents some proposals to solve the transmission network expansion planning problem, static and multistage, taking into account security constraints - (n _ 1) security criterium, and the transmission expansion planning to satisfy some generation programming plans. Trying to find optimal solutions to large scale power systems, the specialized genetic algorithm of Chu-Beasley was implemented. The DC model was used to model the electrical network, and the constructive heuristic algorithm of Villasana-Garver-Salon was implemented to create the initial population and to improve the offsprings of the Chu-Beasley Genetic Algorithm / Doutorado / Energia / Doutor em Engenharia Elétrica