Orientador: Rubén Augusto Romero Lázaro / Banca: Sérgio Azevedo de Oliveira / Banca: Carlos Roberto Mendonça da Rocha / Resumo: O aumento consistente e constante do consumo de energia elétrica, o crescimento irregular e desordenado de edificações residenciais, comerciais e industriais, dentro e fora dos centros urbanos, as irregularidades nas características do fator de potência das cargas instaladas, podem colocar em xeque o bom desempenho dos sistemas elétricos de distribuição sendo necessário e urgente, a aplicação de ferramentas computacionais eficientes que atuem na otimização da operação. A investigação, análise e projeto destes sistemas são o foco da automação da distribuição, que visa redução das perdas técnicas que pode ser feita através da reconfiguração e alocação de bancos de capacitores que contribuirão para o melhoramento nos perfis de tensão e a minimização de perda de potência ativa nas linhas. Este trabalho visa propor a melhoria no desempenho econômico da operação de sistemas de distribuição através da minimização de determinados custos da operação, propondo investimentos que garantam lucros em seu retorno, através da solução simultânea dos problemas de reconfiguração de sistemas de distribuição radiais para alguns tipos de carregamento e do problema da alocação dos bancos de capacitores que será feita através de urna metaheurística especializada para avaliar a qualidade de cada proposta de solução fornecida pela meta-heurística sendo implementado um módulo de fluxo de carga em sistemas de distribuição radial com uso de um algoritmo de varredura / Abstract: The consistent and steady increase in electricity consumption, the irregular and uncontrol­ led growth of residential, commercial and industrial buildings, inside and outside urban centers, the irregularities in the characteristics of the power factor of the loads installed, can risk the good performance electrical distribution systems is necessary and urgent, the application of eflicient computational tools that work on optimizing the operation. The research, analysis and design of these systems is the focus of distribution automa­ tion, which aims to reduce technical losses can be clone by reconfiguring and allocation of capacitors which contribute to the improvement in the voltage profile and minimizing loss active power lines. This work aims to propose improvements in the economic perfor­ mance of the distribution system operation by minimizing certain costs of the operation, proposing investments to ensure profits on their return, by the simultaneous solution of the reconfiguration of radial distribution systems problems for some types of loading and allocation problem of capacitor banks to be made by a specialized metaheurist to assess the quality of each proposed solution provided by metarheuristics are implemented a load module radial flow distribution system using an algorithm scan / Mestre

O Serviço de Gerenciamento de Fluxo de Tráfego Aéreo (ATFM) estabelece um controle de fluxo seguro, ordenado e eficiente de acordo com a capacidade da infraestrutura e dos serviços de controle. O Gerenciamento ´e realizado com o auxílio de sistemas automatizados. Tais sistemas implementam programas que ajustam a demanda de voos à capacidade do espaço aéreo. Algoritmos simples podem sugerir medidas ATFM para solucionar a saturação em um conjunto restrito de elementos regulados (aeródromos, regiões do espaço aéreo, fixos ou aerovias). A natureza interconectada dos elementos regulados, que compõem o fluxo de tráfego aéreo, demanda uma abordagem mais abrangente para atingir o uso ótimo desses recursos, uma vez que outros problemas podem surgir quando a otimização local é aplicada a um elemento sem levar em conta seus elementos relacionados. Nem sempre há a necessidade do planejamento estratégico ser um ótimo global, uma vez que cenários viáveis e sub-ótimos encontrados com menor custo computacional podem representar soluções satisfatórias. O aumento da demanda do tráfego aéreo, no entanto, tem fomentado a aplicação de programas de geração de medidas ATFM mais complexos. Esta pesquisa implementou um programa de otimização global para a geração de medidas ATFM em cenários de larga escala do mundo real. O problema ´e modelado como um problema de programa¸c~ao inteira e o modelo adotado ´e abrangente, pois prevê atraso em solo, em voo, alteração de velocidade e rerroteamento. O programa é capaz de balancear o fluxo atendendo restrições de capacidade dos aeródromos e dos setores. Além disso, foi desenvolvida uma interface de visualização e edição de dados para os cenários estudados. Dados de voos no espaço aéreo brasileiro foram processados e utilizados para testar a solução implementada e mostraram a viabilidade do método. A utilização de um programa de otimização que leva em conta mais restrições potencialmente irá contribuir com o aumento de eficiência no uso da infraestrutura e do espaço aéreo de forma segura. / The Air Traffic Flow Management Service (ATFM) establishes a secure, orderly and efficient flow control according to the capacity of the infrastructure and control services. The Management is performed with the aid of automated systems. Such systems implement programs that adjust the flight demand to the airspace capacity. Simple algorithms might suggest ATFM measures to resolve saturation in a restricted set of regulated elements (aerodromes, airspace regions, fixes or airways). The interconnected nature of the regulated elements that make up the air traffic flow requires a more comprehensive approach to achieve optimum use of these resources, since other problems can arise when local optimization is applied to an element without regard to its related elements. There is not always a need for strategic planning to be a global optimum, since feasible and sub-optimal scenarios encountered at lower computational cost might represent satisfactory solutions. The increase in air traffic demand, however, has encouraged the application of programs to generate more complex ATFM measures. This research implemented a global optimization program for the generation of ATFM measures in large-scale real-world scenarios. The problem is modeled as an integer programming problem and the adopted model is comprehensive, since it provides ground and airborne delays, change of speed and re-routing. The program is able to balance the flow by meeting capacity constraints of the aerodromes and sectors. In addition, a visualization and data editing interface was developed for the studied scenarios. Flight data in Brazilian airspace were processed and used to test the implemented solution and the viability of the method was shown. The use of an optimization program that takes into account more constraints will potentially contribute to increase the efficiency in use of infrastructure and airspace in a secure manner.

O problema de empacotamento em faixas de peças irregulares consiste em cortar um conjunto de peças bidimensionais a partir de um objeto de largura fixa utilizando o menor comprimento possível. Apesar de sua importância econômica para diversos setores industriais, há poucos trabalhos que abordam o problema de forma exata devido a sua dificuldade de resolução. Recentemente, Toledo et al. (2013) propuseram um modelo inteiro misto para este problema, no qual as peças são posicionadas em uma malha de pontos. Este modelo obteve bons resultados, provando a otimalidade para instâncias com até 21 peças. No entanto, o modelo possui um grande número de restrições de não-sobreposição, que cresce rapidamente de acordo com a discretização utilizada e a quantidade de peças distintas que devem ser alocadas. Neste trabalho, são propostas novas formulações matemáticas baseadas neste modelo, com o objetivo de reduzir o número de restrições. Na primeira abordagem, são propostos dois modelos reduzidos que mostraram ser eficientes para instâncias com poucas repetições de peças. Na segunda abordagem, foi proposto um modelo de cobertura por cliques para o problema. Este modelo obteve desempenho igual ou superior ao modelo da literatura para todas as instâncias avaliadas, obtendo uma solução ótima para instâncias com até 28 peças. / The irregular strip packing problem consists of cutting a set of two-dimensional pieces from an object of fixed width using the smallest possible length. Despite its economic importance for many industrial sectors, few exact studies have been made on this problem due to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integer model to this problem in which the pieces are placed on a grid. This model has worked successfully proving the optimality for instances up to 21 pieces. However, the model has a large number of non-overlapping constraints, which grows quickly in accordance with the discretization resolution and number of distinct pieces. In this work, we propose new mathematical formulations based on this model in order to reduce the number of constraints. In the first approach, we present two reduced models that have shown to be effective for instances with few repetitions of pieces. In the second approach, it was proposed a clique covering model for the problem. This model achieved a greater or equal performance than the literature for all instances, getting an optimal solution for instances up to 28 pieces.

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.

Neste trabalho, apresentamos um estudo sobre o problema de dimensionamento de lotes com múltiplas plantas, múltiplos itens e múltiplos períodos. As plantas têm capacidade de produção limitada e a fabricação de cada produto incorre em tempo e custo de preparação de máquina. Nosso objetivo é encontrar um plano de produção que satisfaça a demanda de todos os clientes, considerando que a soma dos custos de produção, de estoque, de transporte e de preparação de máquina seja a menor possível. Este trabalho tem duas contribuições centrais. Primeiramente, propomos a modelagem do problema de dimensionamento de lotes com múltiplas plantas utilizando o conceito de localização de facilidades. Para instâncias de pequena dimensão, os testes computacionais mostraram que a resolução do problema remodelado apresenta, como esperado, resultados melhores que o modelo original. No entanto, seu elevado número de restrições e de variáveis faz com que as instâncias de maiores magnitudes não consigam ser resolvidas. Para trabalhar com instâncias maiores, propomos um método híbrido (math-heurística), que combina o método relax-and-fix, com a restrição de local branching. Testes computacionais mostram que o método proposto apresenta soluções factíveis de boa qualidade para estas instâncias / In this work, we present a study about the multi-plant, multi-item, multi-period lot-sizing problem. The plants have limited capacity, and the production of each item implies in setup times and setup costs. Our objective is to find a production plan which satisfies the demand of every client, considering that the sum of the production, stocking, transport and setup costs is the lowest possible. This work has two main contributions. Firstly, we propose the multi-plant lot-sizing problem modeling using the facility location concept. For small dimension problems, computational tests showed that the remodeled problem resolution presents, as expected, better results than the original model. However, the great number of restrictions and variables make bigger instances to be intractable. To work with the bigger dimension instances, we propose a hybrid method (math-heuristic), which combines the relax-and-fix method and the local branching restriction. Computational tests show that the proposed math-heuristic presents good quality feasible solutions for these instances

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

Este trabalho trata de um problema de programação da produção em fundições de pequeno porte, que consiste em programar as ligas que devem ser produzidas em cada período do planejamento e como tais ligas devem ser usadas para a produção de itens sob encomenda, de modo que atrasos e custos operacionais sejam minimizados. Devido à certa incerteza nos dados do problema, a estratégia de horizonte rolante foi empregada. Este problema é representado por um modelo matemático de programação linear inteira mista. Neste trabalho foi desenvolvida uma heurística do tipo residual para obter uma boa solução inteira factível do problema, partindo da solução contínua encontrada pelos métodos relaxe-e-fixe e busca local / This work addresses a planning production problem that arises in small market-driven foundries, which consists of programming a number of alloys that have to be produced in each period of the planning horizon and how these alloys should be used to producing ordered items, in such way that delays and operational costs are minimized. Due to uncertainties in the problem data, the strategy of rolling horizon was used. This problem is modeled as a mixed integer linear programe. In this work we developed a residual typed heuristic in order to obtain a good feasible integer solution of the problem, which are built from the continuous solution found by relax-and-fix and local search methods. Keywords: Lot-sizing problems, mixed integer linear programming, production planning in foundries

O presente trabalho trata do planejamento da movimentação de contêineres vazios ao longo de um conjunto de portos, buscando o balanceamento entre as demandas e ofertas dos mesmos em todos os portos ao menor custo, e considerando as restrições de capacidade de transporte dos modais envolvidos. Para isso será adotado um modelo de fluxo em rede multi-produto para representar o sistema de movimentação de contêineres vazios e que servirá de base para o desenvolvimento de uma formulação matemática, a qual, implementada através de uma ferramenta computacional de otimização, determina os fluxos de vazios no sistema. A verificação do modelo proposto deu-se através de testes em problemas reduzidos de movimentação de vazios, assim como em um problema cujos resultados foram publicados na literatura. Os resultados sugeriram a adequabilidade e confiabilidade do modelo proposto que pode, então, ser aplicado a um problema real da empresa de navegação Hamburg Süd, tendo seus resultados comparados aos resultados fornecidos pela mesma. / This dissertation deals with the empty containers movement planning throughout a set of ports, aiming the balancing between the demands and supplies in all the ports at minimal cost, and considering the capacity constraints of the transport modes considered. A multi-commodity network flow model will be adopted to represent the empty containers movement system. This model supports the development of a mathematical formulation which, through a computational optimization tool, determines the flows of empty containers throughout the system. The verification of the proposed model was given through tests in reduced problems, as well as in a problem which results had already been published in literature. The results had suggested the adequateness and trustworthiness of the proposed model, which could, then, be applied to a real problem of the navigation company Hamburg Süd, and the results could be compared with the ones given by the company.

O sistema produtivo de fabricação de cilindros de laminação de aço plano é caracterizado por uma produção complexa e sob encomenda. A concorrência entre os fabricantes deste produto é de nível global. Devido a isto, o atendimento de entrega dos cilindros ao cliente é fundamental, pois qualquer atraso paralisa a linha de produção das principais siderúrgicas mundiais (Arcelor, CSN, Usiminas, Posco, Hylsa, Ussteel, Dofasco, Corus, Mittal, etc) ocasionando grandes prejuízos. A Aços Villares S.A. é o terceiro maior fabricante mundial deste produto, exportando cerca de 80% de sua produção para as principais siderúrgicas. Para que o processo de exportação ocorra normalmente é importante que a assertividade do processo produtivo tenha um excelente desempenho, para que o cliente final receba o produto no prazo acordado. Portanto o objetivo principal deste trabalho foi apresentar a aplicação dos conceitos da Teoria das Restrições, Programação Linear Inteira (PLI) e Simulação em um modelo integrado com a finalidade de melhorar o atendimento de prazo junto aos clientes. Como resultado, obteve-se a otimização do processo produtivo, com o foco no gerenciamento da restrição, que ocasiona a redução das filas de espera e do lead time, melhorando o atendimento ao cliente em uma empresa de produção não seriada.

Esta pesquisa aborda o problema de alocação de jatos executivos compartilhados para casos em que a demanda diária é variável. É proposta uma ferramenta auxiliar de planejamento de uma empresa de operação de jatos compartilhados. São apresentadas as características principais do tipo de negócio que formam o problema estudado neste trabalho. Consideram-se os aspectos de uma empresa que administra jatos de propriedade compartilhada. O cliente adquire uma cota de uma aeronave e quando solicita uma viagem, com poucas horas de antecedência, a empresa deve garantir a realização do voo em uma aeronave da categoria adquirida. Também é de responsabilidade da empresa a gestão da tripulação, o reposicionamento da frota e a manutenção das aeronaves Este trabalho apresenta o desenvolvimento de uma ferramenta para auxiliar na tomada de decisões estratégicas que envolvem a escolha dos locais de base de operação e o dimensionamento da frota. A metodologia de solução é composta de um modelo de simulação e um de otimização. O modelo de simulação utiliza o método de Monte Carlo para obtenção da demanda de voos dia a dia que gera uma programação de clientes a atender. Os dados da simulação são então estruturados como um problema de fluxo em rede de mínimo custo e é realizada a alocação ótima das aeronaves. A ferramenta foi construída em ambiente de planilha eletrônica Microsoft Excel e aplicada em um caso prático de jatos executivos compartilhados com múltiplas bases. Foram testadas diversas configurações de bases e políticas operacionais como frota homogênea, frota heterogênea e frota alugada. Os resultados da ferramenta permitem determinar o impacto que a escolha das bases de operação tem no tamanho da frota e no reposicionamento de aeronaves. A metodologia mostrou-se robusta e, em tempo adequado, a ferramenta encontrou a solução ótima para cada configuração testada. / This research deals with the problem of scheduling jets with fractional ownership in cases where the demand varies daily. It has been devised a tool to support the planning phase of a company that operates shared jets. The main characteristics of the fractional shared market are presented in this manuscript and the research was developed under the point of view of a provider of fractional ownership. A client becomes a partial owner of an aircraft of a specific model and is entitled to a certain amount of flight hours. When the client requests a flight, usually only a few hours ahead, the fractional provider must guarantee that an aircraft of the requested model is available to the owner at the requested time and place. The provider is responsible for all the operational considerations, including managing the crew and having a well-maintained fleet. This work presents the development of a tool to help making decisions involving the choice of the operational bases and the size of the fleet. The solution methodology is composed of a simulation and a optimization model. Monte Carlo simulation is the method used to obtain the daily flight demand. The results of the simulation are structured as a minimum cost network flow problem to solve optimally the fleet allocation. This tool has been built in a Microsoft Excel spreadsheet environment and applied to a case of fractional jets with multiple bases. Several configurations and operational policies have been tested, such as operations with homogenous fleet, with heterogeneous fleet and with rented fleet. The results provided by the tool allow the user to evaluate the impact that the choice of the operational bases has on the size of the fleet and on the redeployment of the aircrafts. The methodology presented itself as adequate and the developed tool was able to solve optimally, in acceptable time, the problem for each case.