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

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.

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.

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.