A reconfiguração de redes de distribuição de energia elétrica consiste em alterar sua topologia por meio de manobras de chaves nos circuitos primários. Trata-se de um problema de otimização combinatória, onde normalmente os objetivos são a minimização de perdas ativas e/ou número de manobras realizadas, atendendo as restrições como isolamento de faltas, balanceamento de cargas entre os alimentadores e melhoria dos níveis de tensão. As dificuldades na modelagem e na resolução exata de problemas envolvendo a reconfiguração de redes de distribuição advém do tamanho dos sistemas reais, representados por um número elevado de chaves e alimentadores e ainda pela natureza combinatorial do problema. Para tratar essas questões, diversas modelagens e técnicas computacionais têm sido desenvolvidas, em particular heurísticas de melhoramento que através de uma solução factível, otimiza os resultados reduzindo o espaço de busca, até encontrar uma nova solução com melhor função objetivo. Neste sentido, são propostas duas formulações matemáticas descrevendo novas restrições a fim de melhorar a descrição do problema. A primeira, uma formulação mais simplificada, considera apenas a parte ativa das instâncias; na segunda um modelo completo é descrito otimizando parte das restrições do primeiro modelo e considerando também a parte reativa das instâncias. Duas heurísticas também são adaptadas pela primeira vez para o problema de reconfiguração de redes, pois a heurística de melhoramento Fix-and-Optmize é configurada de duas formas diferentes, determinando seus principais parâmetros através de uma análise de sensibilidade. Os resultados dos dois modelos propostos e também das heurísticas adaptadas para 13 sistemas de referência são descritos e comparados com outros métodos da literatura. Para verificar a eficiência e robustez dos métodos e heurísticas desenvolvidos, replicações são propostas de dois sistemas de referência, 9 replicações do sistema de 72 barras e 4 replicações do sistema de 10560 barras. Seus resultados bem como o desempenho dos métodos são descritos e avaliados. / A reconfiguration of electricity distribution networks consists in altering a topology of the networks by means of key maneuvers in the primary circuits. It is a problem of combinatorial optimization, where the objectives are a minimization of active losses and/or number of maneuvers performed, taking into account constraints such as fault isolation, load balance between feeders and improvement of voltage levels. As difficulties in modeling and in the exact resolution of problems involving a reconfiguration of distribution networks come from the size of the real systems, represented by a large number of switches and feeders, and also by the combinatorial nature of the problem. To address these issues, several models and computational techniques have been developed, in particular heuristics of improvement that through a feasible solution, improves results by reducing the search space, until finding a new solution with better objective function. In this sense, in this thesis it is proposed of two mathematical formulations describing new constraints in order to improve a description of the problem. A first, simpler formulation considers only a active part of the instances, in the second a complete model is described optimizing some restrictions of the first model and also considering the reactive part of the instances. Two heuristics are also first adapted to the network reconfiguration problem. The Fix-and-Optmize enhancement heuristic is configured in two different ways, determining its key parameters through a sensitivity analysis. The results of the two proposed models and also of the heuristics adapted for 13 reference systems are described and compared with other methods of the literature. To verify the efficiency and robustness of the developed methods and heuristics, replications are proposed for two reference systems, 9 replications of the 72 bus system and 4 replications of the 10560 bus system. Its results as well as the performance of the methods are described and evaluated.

[pt] Este estudo apresenta um modelo de programação inteira mista para a roteirização de navios com controle de estoque nos portos para a movimentação de múltiplos produtos com uma frota heterogênea. O modelo contempla a possibilidade de transformação de produtos dentro de navios, o que representa uma flexibilidade para o modelo optar por qual produto utilizar para atender um cliente com demanda com qualidade flexível. Esta habilidade não foi encontrada em nenhum outro estudo. Ele também combina o atendimento de demandas obrigatórias com opcionais. O modelo então é aplicado em um caso real de movimentação de derivados escuros de petróleo em uma empresa de petróleo brasileira, cujo modelo atual utilizado apresenta problemas que dificultam seu uso. Devido ao longo tempo que leva para obter a solução ótima para estes tipos de modelos, são utilizadas as matheurísticas de relax-and-fix e fix-and-optimize para obter soluções boas em um tempo reduzido. São apresentados experimentos computacionais em uma série de cenários para validar a qualidade das soluções encontradas pelos métodos propostos, testando diferentes configurações e discretizações de tempo. Os resultados apresentados comprovam a superioridade dos métodos em comparação com o modelo matemático puro. O modelo proposto apresentou grande potencial de substituir o modelo atual da empresa e para alcançar a melhoria pretendida na programação dos navios. / [en] This dissertation presents a mixed integer program model to solve a ship routing and scheduling with stock control in ports, also known as maritime inventory routing. This model considers a heterogeneous fleet, carrying multiples products. It also has the ability to transform one product into another inside ships. This aspect allows the model to choose which product it wishes to deliver to a client with a less restrict quality specification in his demand. No model presented in other studies has this capability. Another possibility covered by this model is to combine mandatory demands with optional ones. The model is applied to a real case of maritime transportation of dirty oil products in a Brazilian oil company, whose current model has a series of small problems that hinders its use. Due to the long time it takes to get the optimal solution, the relax-and-fix and fix-andoptimize heuristics are used to get good solutions in a reduced time. With the use of computational experiments in a series of scenarios, it has proved the quality of the solutions found by the proposed methods, testing different configurations and discretizations of time. The results presented prove the superiority of the methods in comparison to the pure mathematical model. The proposed model has shown great potential to replace the current one and to achieve the improvement for the ship routing intended by the company.

abstract: In this thesis, a single-level, multi-item capacitated lot sizing problem with setup carryover, setup splitting and backlogging is investigated. This problem is typically used in the tactical and operational planning stage, determining the optimal production quantities and sequencing for all the products in the planning horizon. Although the capacitated lot sizing problems have been investigated with many different features from researchers, the simultaneous consideration of setup carryover and setup splitting is relatively new. This consideration is beneficial to reduce costs and produce feasible production schedule. Setup carryover allows the production setup to be continued between two adjacent periods without incurring extra setup costs and setup times. Setup splitting permits the setup to be partially finished in one period and continued in the next period, utilizing the capacity more efficiently and remove infeasibility of production schedule. The main approaches are that first the simple plant location formulation is adopted to reformulate the original model. Furthermore, an extended formulation by redefining the idle period constraints is developed to make the formulation tighter. Then for the purpose of evaluating the solution quality from heuristic, three types of valid inequalities are added to the model. A fix-and-optimize heuristic with two-stage product decomposition and period decomposition strategies is proposed to solve the formulation. This generic heuristic solves a small portion of binary variables and all the continuous variables rapidly in each subproblem. In addition, the case with demand backlogging is also incorporated to demonstrate that making additional assumptions to the basic formulation does not require to completely altering the heuristic. The contribution of this thesis includes several aspects: the computational results show the capability, flexibility and effectiveness of the approaches. The average optimality gap is 6% for data without backlogging and 8% for data with backlogging, respectively. In addition, when backlogging is not allowed, the performance of fix-and-optimize heuristic is stable regardless of period length. This gives advantage of using such approach to plan longer production schedule. Furthermore, the performance of the proposed solution approaches is analyzed so that later research on similar topics could compare the result with different solution strategies. / Dissertation/Thesis / Masters Thesis Industrial Engineering 2015

Submitted by JACKELINE DEL CARMEN HUACCHA NEYRA null (jacky_157_93@hotmail.com) on 2017-03-24T15:38:11Z No. of bitstreams: 1 dissertação jackeline.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-03-24T18:02:08Z (GMT) No. of bitstreams: 1 huacchaneyra_jc_me_sjrp.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) / Made available in DSpace on 2017-03-24T18:02:08Z (GMT). No. of bitstreams: 1 huacchaneyra_jc_me_sjrp.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) Previous issue date: 2017-03-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Os problemas de dimensionamento de lotes consistem em determinar a quantidade de itens que devem ser produzidos em todos os períodos de um horizonte de planejamento. Em geral, são considerados custos de produção, preparação de máquina e de manutenção de estoque. Neste trabalho estuda-se uma extensão do problema de dimensionamento de lotes com restrição de capacidade que considera tempos de preparação, preparação carryover e crossover, em que se tem uma única máquina, único estágio, multi-itens e big-bucket (CLSP-SCC). Novas formulações para o CLSP-SCC são apresentadas e evitam a necessidade de definir novas variáveis binárias para modelar a preparação crossover. Também são propostas restrições de quebra de simetria para formulações propostas na literatura. São provadas as relações teóricas que existem entre cada uma destas formulações estudadas. Além disso, é proposta uma heurística híbrida que combina as heurísticas Relax-and-Fix e Fix-and-Optimize (RF-FO), em que a heurística Relax-and-Fix é usada para obter uma solução inicial e a heurística Fix-and-Optimize melhora essa solução. Por fim, apresentam-se os resultados computacionais e conclui-se que os resultados obtidos melhoram significativamente quando comparam-se a formulação clássica com as formulações sem preparação carryover. Compara-se também os resultados da heurística com os do pacote computacional CPLEX e, quando ambos são limitados ao mesmo tempo computacional, a heurística RF-FO obtém melhores resultados. / Lot-Sizing Problems consist of determining the quantity of items to be produced in each period of a planning horizon. In general, production, setup and inventory costs are considered. In this work an extension of the Capacitated Lot-Sizing Problem is studied, which considers setup times, Setup Carryover and Setup Crossover, single machine, single level, multi items, multi periods and big-bucket (CLSP-SCC). New formulations to the CLSP-SCC are presented and avoid the necessity of defining new extra binary variables to model the setup crossover. Furthermore, symmetry breaking constraints are proposed for formulations from the literature. The theoretical relations between the studied formulations are proved. A Relax-and-Fix and Fixand-Optimize (RF-FO) hybrid heuristic is proposed, in which the Relax-and-Fix helps to find an initial solution and the Fix-and-Optimize improves it. Computational results are presented and the obtained results improve significantly when comparing the classical formulation with the formulation without setup carryover. Finally, the results obtained by the RF-FO heuristic and the computational package CPLEX are compared and, when they both are limited to the same computational time, the RF-FO heuristic obtains better results.

[pt] O problema de roteamento de navios com gestão de estoques (conhecido pelo termo em inglês Maritime inventory routing ou MIR) representa um problema prático de logística onde o transportador da carga também é responsável pela manutenção dos estoques do produto transportado nos portos de carga e descarga. Esta tese estuda um caso real do problema MIR. Um conjunto de testes é apresentado de modo a comparar diferentes formulações matemáticas da literatura, a fim de encontrar aquela mais aderente ao problema real. Em função da complexidade computacional do problema, é apresentada uma abordagem heurística que consegue encontrar soluções similares e reduz consideravelmente o tempo computacional quando comparadas com as formulações baseadas em PLIM. No entanto, problemas reais são muito influenciados por aspectos incertos. Sendo assim, é apresentada uma abordagem robusta para a otimização do problema MIR, que considera incerteza no tempo de estadia do navio nos portos. A abordagem apresentada produz soluções para diferentes níveis de robustez. Em outras palavras, considera o risco de variação no tempo de estadia do navio em um porto durante uma operação de carga ou descarga. Assim, é capaz de determinar a probabilidade de inviabilidade da solução encontrada para cada nível de robustez oferecido, além do impacto no custo de transporte à medida que soluções mais robustas são apresentadas. Esta abordagem oferece ao tomador de decisão a medida do trade-off entre robustez e custo de transporte. Desta forma, o mesmo pode determinar qual o nível de conservadorismo irá adotar em sua programação de navios e quanto isto irá impactar o custo de transporte. Os experimentos apresentados identificaram que, aumentos sutís no nível de robustez (com pequeno impacto no custo de transporte) podem reduzir consideravelmente a probabilidade de inviabilidade de uma solução. / [en] Maritime inventory routing (MIR) problem is an academic name for a practical logistic problem that represents the routing or scheduling of vessels to carry product(s) between ports. Meanwhile, the product(s) inventory levels in these ports must remain between operational bounds during the entire planning horizon. This thesis focus on how to support decision on a real-life MIR problem faced by a Brazilian petroleum company. To do so, we structure a set of tests to compare different formulation from literature and identify which is more adherent to real problem. Due to computational complexity of the problem, we present an heuristic approach that provides reasonably good solutions when compared to deterministic mixed integer linear programming (MILP) formulations and reduces considerably the computational time of solving real-life instances. However, uncertainty events have great impact in the ship scheduling planning. Therefore, we propose a robust optimization approach that considers uncertainty in the time spent at ports in each ship visit. Our approach is able to determine the probability of infeasibility and the impact in the objective function for each level of robustness, helping to measure the uncertain aversion of the decision maker. Our experiments identified that, for a certain instance, varying the level of robustness one may reduce the probability of infeasibility from 87 per cent (of deterministic solution) to 2 per cent and it represents an increase in the transportation costs of about 13 per cent.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

A geração de quadros de horários escolares é um problema clássico de otimização que tem sido largamente estudado devido a sua importâncias prática e teórica. O problema consiste em alocar um conjunto de aulas entre professor-turma em períodos de tempo pré-determinados, satisfazendo diferentes tipos de requisitos. Devido a natureza combinatória do problema, a resolução de instâncias médias e grandes torna-se uma tarefa desafiadora. Quando recursos são escassos, mesmo uma solução factível pode ser difícil de ser encontrada. Várias técnicas tem sido propostas na literatura científica para resolver o problema de geração de quadros de horários escolares, no entanto, métodos robustos ainda não existem. Visto que o uso de métodos exatos, como por exemplo, técnicas de programação matemática, não podem ser utilizados na prática, para resolver instâncias grandes da realidade, meta-heurísticas e meta-heurísticas híbridas são usadas com frequência como abordagens de resolução. Nesta pequisa, são desenvolvidas técnicas que combinam programação matemática e heurísticas, denominadas mateheurísticas, para resolver de maneira eficiente e robusta algumas variações de problemas de geração de quadros de horários escolares. Embora neste trabalho sejam abordados problemas encontrados no contexto de instituições brasileiras, os métodos propostos também podem ser aplicados em problemas similares oriundo de outros países. / The school timetabling is a classic optimization problem that has been extensively studied due to its practical and theoretical importance. It consists in scheduling a set of class-teacher meetings in a prefixed period of time, satisfying requirements of different types. Given the combinatorial nature of this problem, solving medium and large instances of timetabling to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Several techniques have been developed in the scientific literature to tackle the high school timetabling problem, however, robust solvers do not exist yet. Since the use of exact methods, such as mathematical programming techniques, is considered impracticable to solve large real world instances, metaheuristics and hybrid metaheuristics are the most used solution approaches. In this research we develop techniques that combine mathematical programming and heuristics, so-called matheuristics, to solve efficiently and in a robust way some variants of the high school timetabling problem. Although we pay special attention to problems arising in Brazilian institutions, the proposed methods can also be applied to problems from different countries.

A reconfiguração de redes de distribuição de energia elétrica consiste em alterar sua topologia por meio de manobras de chaves nos circuitos primários. Trata-se de um problema de otimização combinatória, onde normalmente os objetivos são a minimização de perdas ativas e/ou número de manobras realizadas, atendendo as restrições como isolamento de faltas, balanceamento de cargas entre os alimentadores e melhoria dos níveis de tensão. As dificuldades na modelagem e na resolução exata de problemas envolvendo a reconfiguração de redes de distribuição advém do tamanho dos sistemas reais, representados por um número elevado de chaves e alimentadores e ainda pela natureza combinatorial do problema. Para tratar essas questões, diversas modelagens e técnicas computacionais têm sido desenvolvidas, em particular heurísticas de melhoramento que através de uma solução factível, otimiza os resultados reduzindo o espaço de busca, até encontrar uma nova solução com melhor função objetivo. Neste sentido, são propostas duas formulações matemáticas descrevendo novas restrições a fim de melhorar a descrição do problema. A primeira, uma formulação mais simplificada, considera apenas a parte ativa das instâncias; na segunda um modelo completo é descrito otimizando parte das restrições do primeiro modelo e considerando também a parte reativa das instâncias. Duas heurísticas também são adaptadas pela primeira vez para o problema de reconfiguração de redes, pois a heurística de melhoramento Fix-and-Optmize é configurada de duas formas diferentes, determinando seus principais parâmetros através de uma análise de sensibilidade. Os resultados dos dois modelos propostos e também das heurísticas adaptadas para 13 sistemas de referência são descritos e comparados com outros métodos da literatura. Para verificar a eficiência e robustez dos métodos e heurísticas desenvolvidos, replicações são propostas de dois sistemas de referência, 9 replicações do sistema de 72 barras e 4 replicações do sistema de 10560 barras. Seus resultados bem como o desempenho dos métodos são descritos e avaliados. / A reconfiguration of electricity distribution networks consists in altering a topology of the networks by means of key maneuvers in the primary circuits. It is a problem of combinatorial optimization, where the objectives are a minimization of active losses and/or number of maneuvers performed, taking into account constraints such as fault isolation, load balance between feeders and improvement of voltage levels. As difficulties in modeling and in the exact resolution of problems involving a reconfiguration of distribution networks come from the size of the real systems, represented by a large number of switches and feeders, and also by the combinatorial nature of the problem. To address these issues, several models and computational techniques have been developed, in particular heuristics of improvement that through a feasible solution, improves results by reducing the search space, until finding a new solution with better objective function. In this sense, in this thesis it is proposed of two mathematical formulations describing new constraints in order to improve a description of the problem. A first, simpler formulation considers only a active part of the instances, in the second a complete model is described optimizing some restrictions of the first model and also considering the reactive part of the instances. Two heuristics are also first adapted to the network reconfiguration problem. The Fix-and-Optmize enhancement heuristic is configured in two different ways, determining its key parameters through a sensitivity analysis. The results of the two proposed models and also of the heuristics adapted for 13 reference systems are described and compared with other methods of the literature. To verify the efficiency and robustness of the developed methods and heuristics, replications are proposed for two reference systems, 9 replications of the 72 bus system and 4 replications of the 10560 bus system. Its results as well as the performance of the methods are described and evaluated.