Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2017-02-08T15:41:51Z No. of bitstreams: 1 Wagner Lourenzi Simões_.pdf: 1389162 bytes, checksum: 302aec842d2f4e8b0a7c78ecbae24357 (MD5) / Made available in DSpace on 2017-02-08T15:41:51Z (GMT). No. of bitstreams: 1 Wagner Lourenzi Simões_.pdf: 1389162 bytes, checksum: 302aec842d2f4e8b0a7c78ecbae24357 (MD5) Previous issue date: 2016-12-06 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste estudo, foi desenvolvida uma ferramenta computacional baseada em metaheurísticas para a otimização do sequenciamento de produção em Flow Shop permutacionais aplicados à montagem de placas eletrônicas que operam em ambientes High-Mix, Low-Volume. O ambiente High-Mix, Low-Volume exige a realização de um grande número de setups para atender à flexibilidade exigida. Esse elevado número de sucessivos setups para a produção de pequenos lotes impacta negativamente nos custos operacionais da empresa. Uma das formas de se obter vantagem ao lidar com um grande mix de produção é explorando características similares entre os produtos, de forma que, através de um sequenciamento adequado, seja possível reduzir o tempo total de parada para setup e, por consequência, reduzir também o tempo total de processamento (makespan). A literatura apresenta muitos exemplos de sucesso na aplicação de técnicas de otimização para o sequenciamento da produção como forma de ganho de vantagem competitiva. Porém, a complexidade e o grande esforço computacional exigidos na solução deste problema, por muitas vezes, inviabilizam sua aplicação na rotina das indústrias. Neste contexto, as metaheurísticas emergem como uma opção para a viabilização de ferramentas para otimização do sequenciamento de produção. Dentre as abordagens metaheurísticas existentes, destacam-se as abordagens híbridas que combinam estratégias de busca local com algoritmos evolutivos como opções para a geração, de forma rápida, de boas soluções para o problema de sequenciamento, ainda que estes métodos não possam garantir a otimalidade da solução. A ferramenta desenvolvida, baseada no uso combinado das metaheurísticas Busca Tabu e Algoritmo Genético, busca a melhor sequência possível dentro do tempo computacional disponível de forma a reduzir os tempos gastos com operações de tempo de setup, e consequentemente o makespan. O Algoritmo Hibrido foi avaliado utilizando instâncias da literatura e instâncias advindas de um caso real. Os resultados dos testes indicam a superioridade da abordagem híbrida sobre as abordagens canônicas do algoritmo Genético e Busca Tabu. Os resultados obtidos na avaliação de instâncias reais indicam a aplicabilidade da ferramenta em ambientes reais, obtendo bons resultados na otimização dos tempos de setup, mesmo para o sequenciamento de grandes quantidades de produtos diferentes. / This work proposes the development of a metaheuristics based computation tool, to solve the permutation flow shop scheduling problem (PFSSP) in the electronic manufacturing operating in High-mix, Low-volume enviroment. To operate in HMLV enviroment is demanded a large number of setup changes to comply the flexibility required. This elevated number of successive setup changes to produce little batches have negative impacts on the operation costs. One way for to obtain advantages handling a large product mix is to explore the similar features between this products. Through a proper scheduling we can reduce the total downtime to setup changes, and consequently reduces the process time (makespan). The literature brings many success examples in the production scheduling optimization as a way to obtain competitive advantages. But, the complexity and the computational effort demanded to solve this problems, sometimes, turns the practical application unfeasible in the factories routine. In this contexto emerges the metaheuristics as an option to viability this type of application. Among the mataheuristics approaches, outstands the hybrid approaches that combine local search strategies with evolutionary algorithms as a way to obtain good and fast solutions for the scheduling problems, although the optimality is not been guaranted. The tool proposed combine the metaheuristics Genetic Algorithm and Tabu Search to optimize the flow shop scheduling in the shortest possible time to allow the practical application in industry. The tool was evaluate based on quality metrics like makespan and mean setup time. The Hybrid Algorithm has been evaluated using instances of the literature and instances arising from a real case. The results of the tests indicate a superiority of the hybrid approach over canonical approaches of the Genetic algorithm and Tabu Search. The results obtained in the evaluation of real instances indicate an applicability of the tool in real environments, obtaining good results in the optimization of textit setup times, also for the sequencing of large products. The Hybrid Algorithm has been evaluated using instances of the literature and instances arising from a real case. The tests results indicate a superiority of the hybrid approach over canonical approaches of the Genetic algorithm and Tabu Search. The results obtained in the evaluation of real instances indicate an applicability of the tool in real environments, obtaining good results in the setup time optimization, also for the sequencing of large products.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nas últimas décadas, o problema de escalonamento da produção em oficina de máquinas, na literatura referido como JSSP (do inglês Job Shop Scheduling Problem), tem recebido grande destaque por parte de pesquisadores do mundo inteiro. Uma das razões que justificam tamanho interesse está em sua alta complexidade. O JSSP é um problema de análise combinatória classificado como NP-Difícil e, apesar de existir uma grande variedade de métodos e heurísticas que são capazes de resolvê-lo, ainda não existe hoje nenhum método ou heurística capaz de encontrar soluções ótimas para todos os problemas testes apresentados na literatura. A outra razão basea-se no fato de que esse problema encontra-se presente no diaa- dia das indústrias de transformação de vários segmento e, uma vez que a otimização do escalonamento pode gerar uma redução significativa no tempo de produção e, consequentemente, um melhor aproveitamento dos recursos de produção, ele pode gerar um forte impacto no lucro dessas indústrias, principalmente nos casos em que o setor de produção é responsável por grande parte dos seus custos totais. Entre as heurísticas que podem ser aplicadas à solução deste problema, o Busca Tabu e o Multidão de Partículas apresentam uma boa performance para a maioria dos problemas testes encontrados na literatura. Geralmente, a heurística Busca Tabu apresenta uma boa e rápida convergência para pontos ótimos ou subótimos, contudo esta convergência é frequentemente interrompida por processos cíclicos e a performance do método depende fortemente da solução inicial e do ajuste de seus parâmetros. A heurística Multidão de Partículas tende a convergir para pontos ótimos, ao custo de um grande esforço computacional, sendo que sua performance também apresenta uma grande sensibilidade ao ajuste de seus parâmetros. Como as diferentes heurísticas aplicadas ao problema apresentam pontos positivos e negativos, atualmente alguns pesquisadores começam a concentrar seus esforços na hibridização das heurísticas existentes no intuito de gerar novas heurísticas híbridas que reúnam as qualidades de suas heurísticas de base, buscando desta forma diminuir ou mesmo eliminar seus aspectos negativos. Neste trabalho, em um primeiro momento, são apresentados três modelos de hibridização baseados no esquema geral das Heurísticas de Busca Local, os quais são testados com as heurísticas Busca Tabu e Multidão de Partículas. Posteriormente é apresentada uma adaptação do método Colisão de Partículas, originalmente desenvolvido para problemas contínuos, onde o método Busca Tabu é utilizado como operador de exploração local e operadores de mutação são utilizados para perturbação da solução. Como resultado, este trabalho mostra que, no caso dos modelos híbridos, a natureza complementar e diferente dos métodos Busca Tabu e Multidão de Partículas, na forma como são aqui apresentados, da origem à algoritmos robustos capazes de gerar solução ótimas ou muito boas e muito menos sensíveis ao ajuste dos parâmetros de cada um dos métodos de origem. No caso do método Colisão de Partículas, o novo algorítimo é capaz de atenuar a sensibilidade ao ajuste dos parâmetros e de evitar os processos cíclicos do método Busca Tabu, produzindo assim melhores resultados. / In recent decades, the Job Shop Scheduling Ploblem (JSSP) has received great attention of researchers worldwide. One of the reasons for such interest is its high complexity. The JSSP is a combinatorial optimization problem classified as NP-Hard and, although there is a variety of methods and heuristics that are able to solve it, even today no method or heuristic is able to find optimal solutions for all benchmarcks presented in the literature. The other reason builds on noted fact that this problem is present in day-to-day of industries of various segments and, since the optimal scheduling may cause a significant reduction in production time and thus a better utilization of manufacturing resources, it can generate a strong impact on the gain of these industries, especially in cases where the production sector is responsible for most of their total costs. Among the heuristics that can be applied to the solution of this problem, the Tabu Search and the Particle Swarm Optimization show good performance for most benchmarcks found in the literature. Usually, the Taboo Search heuristic presents a good and fast convergence to the optimal or sub-optimal points, but this convergence is frequently interrupted by cyclical processes, offset, the Particle Swarm Optimization heuristic tends towards a convergence by means of a lot of computational time, and the performance of both heuristics strongly depends on the adjusting of its parameters. This thesis presents four different hybridization models to solve the classical Job Shop Scheduling Problem, three of which based on the general schema of Local Search Heuristics and the fourth based on the method Particle Collision. These models are analyzed with these two heuristics, Taboo Search and Particle Swarm Optimization, and the elements of this heuristics, showing what aspects must be considered in order to achieve a best solution of the one obtained by the original heuristics in a considerable computational time. As results this thesis demonstrates that the four models are able to improve the robustness of the original heuristics and the results found by Taboo Search.

[pt] Esta tese faz um estudo do problema do Conjunto Dominante, um problema NP-difícil de grande relevância em aplicações relacionadas ao projeto de rede sem fio, mineração de dados, teoria de códigos, dentre outras. O conjunto dominante mínimo em um grafo é um conjunto mínimo de vértices de modo que cada vértice do grafo pertence a este conjunto ou é adjacente a um vértice que pertence a ele. Três variantes do problema foram estudadas; primeiro, uma variante na qual considera pesos nos vértices, buscando um conjunto dominante com menor peso total; segundo, uma variante onde o subgrafo induzido pelo conjunto dominante está conectado; e, finalmente, a variante que engloba essas duas características. Para resolver esses três problemas, propõe-se um algoritmo híbrido baseado na meta-heurística busca tabu com componentes adicionais de programação matemática, resultando em um método por vezes chamado de mateurística, (matheuristic, em inglês). Diversas técnicas adicionais e vizinhanças largas foram propostas afim de alcançar regiões promissoras no espaço de busca. Análises experimentais demonstram a contribuição individual de todos esses componentes. Finalmente, o algoritmo é testado no problema do código de cobertura mínima, que pode ser visto como um caso especial do problema do conjunto dominante. Os códigos são estudados na métrica Hamming e na métrica Rosenbloom-Tsfasman. Neste último, diversos códigos menores foram encontrados. / [en] This thesis addresses the Dominating Set Problem, an NP- hard problem with great relevance in applications related to wireless network design, data mining, coding theory, among others. The minimum dominating set in a graph is a minimal set of vertices so that each vertex of the graph belongs to it or is adjacent to a vertex of this set. We study three variants of the problem: first, in the presence of weights on vertices, searching for a dominating set with smallest total weight; second, a variant where the subgraph induced by the dominating set needs to be connected, and,finally, the variant that encompasses these two characteristics. To solve these three problems, we propose a hybrid algorithm based on tabu search with additional mathematical-programming components, leading to a method sometimes called matheuristic. Several additional techniques and large neighborhoods are also employed to reach promising regions in the search space. Our experimental analyses show the good contribution of all these individual components. Finally, the algorithm is tested on the covering code problem, which can be viewed as a special case of the minimum dominating set problem. The codes are studied for the Hamming metric and the Rosenbloom-Tsfasman metric. For this last case, several shorter codes were found.

ALVES, Alexsandro de Oliveira. Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos. 2007. 49 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:05:04Z No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:08:40Z (GMT) No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) / Made available in DSpace on 2016-05-20T18:08:40Z (GMT). No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) Previous issue date: 2007 / In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem. / Neste trabalho avaliamos métodos heurísticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurísticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e método de otimização pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiência de nossas heurísticas na obtenção de limites inferiores e superiores de boa qualidade, em tempo computacional razoável, para instâncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instâncias do PPC à otimalidade e para comprovar a qualidade dos resultados alcançados por nossas heurísticas.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nas últimas décadas, o problema de escalonamento da produção em oficina de máquinas, na literatura referido como JSSP (do inglês Job Shop Scheduling Problem), tem recebido grande destaque por parte de pesquisadores do mundo inteiro. Uma das razões que justificam tamanho interesse está em sua alta complexidade. O JSSP é um problema de análise combinatória classificado como NP-Difícil e, apesar de existir uma grande variedade de métodos e heurísticas que são capazes de resolvê-lo, ainda não existe hoje nenhum método ou heurística capaz de encontrar soluções ótimas para todos os problemas testes apresentados na literatura. A outra razão basea-se no fato de que esse problema encontra-se presente no diaa- dia das indústrias de transformação de vários segmento e, uma vez que a otimização do escalonamento pode gerar uma redução significativa no tempo de produção e, consequentemente, um melhor aproveitamento dos recursos de produção, ele pode gerar um forte impacto no lucro dessas indústrias, principalmente nos casos em que o setor de produção é responsável por grande parte dos seus custos totais. Entre as heurísticas que podem ser aplicadas à solução deste problema, o Busca Tabu e o Multidão de Partículas apresentam uma boa performance para a maioria dos problemas testes encontrados na literatura. Geralmente, a heurística Busca Tabu apresenta uma boa e rápida convergência para pontos ótimos ou subótimos, contudo esta convergência é frequentemente interrompida por processos cíclicos e a performance do método depende fortemente da solução inicial e do ajuste de seus parâmetros. A heurística Multidão de Partículas tende a convergir para pontos ótimos, ao custo de um grande esforço computacional, sendo que sua performance também apresenta uma grande sensibilidade ao ajuste de seus parâmetros. Como as diferentes heurísticas aplicadas ao problema apresentam pontos positivos e negativos, atualmente alguns pesquisadores começam a concentrar seus esforços na hibridização das heurísticas existentes no intuito de gerar novas heurísticas híbridas que reúnam as qualidades de suas heurísticas de base, buscando desta forma diminuir ou mesmo eliminar seus aspectos negativos. Neste trabalho, em um primeiro momento, são apresentados três modelos de hibridização baseados no esquema geral das Heurísticas de Busca Local, os quais são testados com as heurísticas Busca Tabu e Multidão de Partículas. Posteriormente é apresentada uma adaptação do método Colisão de Partículas, originalmente desenvolvido para problemas contínuos, onde o método Busca Tabu é utilizado como operador de exploração local e operadores de mutação são utilizados para perturbação da solução. Como resultado, este trabalho mostra que, no caso dos modelos híbridos, a natureza complementar e diferente dos métodos Busca Tabu e Multidão de Partículas, na forma como são aqui apresentados, da origem à algoritmos robustos capazes de gerar solução ótimas ou muito boas e muito menos sensíveis ao ajuste dos parâmetros de cada um dos métodos de origem. No caso do método Colisão de Partículas, o novo algorítimo é capaz de atenuar a sensibilidade ao ajuste dos parâmetros e de evitar os processos cíclicos do método Busca Tabu, produzindo assim melhores resultados. / In recent decades, the Job Shop Scheduling Ploblem (JSSP) has received great attention of researchers worldwide. One of the reasons for such interest is its high complexity. The JSSP is a combinatorial optimization problem classified as NP-Hard and, although there is a variety of methods and heuristics that are able to solve it, even today no method or heuristic is able to find optimal solutions for all benchmarcks presented in the literature. The other reason builds on noted fact that this problem is present in day-to-day of industries of various segments and, since the optimal scheduling may cause a significant reduction in production time and thus a better utilization of manufacturing resources, it can generate a strong impact on the gain of these industries, especially in cases where the production sector is responsible for most of their total costs. Among the heuristics that can be applied to the solution of this problem, the Tabu Search and the Particle Swarm Optimization show good performance for most benchmarcks found in the literature. Usually, the Taboo Search heuristic presents a good and fast convergence to the optimal or sub-optimal points, but this convergence is frequently interrupted by cyclical processes, offset, the Particle Swarm Optimization heuristic tends towards a convergence by means of a lot of computational time, and the performance of both heuristics strongly depends on the adjusting of its parameters. This thesis presents four different hybridization models to solve the classical Job Shop Scheduling Problem, three of which based on the general schema of Local Search Heuristics and the fourth based on the method Particle Collision. These models are analyzed with these two heuristics, Taboo Search and Particle Swarm Optimization, and the elements of this heuristics, showing what aspects must be considered in order to achieve a best solution of the one obtained by the original heuristics in a considerable computational time. As results this thesis demonstrates that the four models are able to improve the robustness of the original heuristics and the results found by Taboo Search.

Made available in DSpace on 2016-06-02T19:52:00Z (GMT). No. of bitstreams: 1 DissRH.pdf: 983555 bytes, checksum: 2f6efc30e82bc4d5f60bb2893dd0bb3f (MD5) Previous issue date: 2004-12-16 / This research consists of the development of algorithms to solve the Periodic Vehicle Routing Problem (PVRP), wich has not received a great deal of attention in the O.R. literature. The objective of the PVRP is to elaborate a set of routes to attend to customers demand along a planning horizon. Each customer roquests that the visits occur in a combination predefined of days. Two heuristics were developed for the PVRP. In the first heuristic, three types of initial solution construction are used to attribute the customers to days. After that, visiting day combinations are changed in order to improvr the solution. The search process is controlled by an adaptative tabu heuristic from the literature which determines intensification and diversification actions, applied for each day in the period. The second heuristic incorporates a similar approach for the period as a whole. Computacional results show that this approach leads to good solution. / Esta pesquisa consiste no desenvolvimento de algoritmos para resolver o Problema de Roteamento de Veículos Periódico (PRPV), o qual tem sido pouco abordado na literatura de Pesquisa Operacional. O objetivo do PRVP é elaborar um conjunto de rotas para atender à demanda de cliente ao longo de um horizonte de planejamento. Cada cliente requer que as visitas aconteçam em uma combinação predefinida de dias. Foram desenvolvidas duas heurísticas para o PRPV, chamadas de VERSÃO 1 e VERSÃO 2. Na VERSÃO 1 são utilizados três tipos de construções iniciais para atribuir os clientes aos dias. Em seguida, são realizadas mudanças de combinações de dias de visitas na tentativa de melhorar a solução. O processo de busca por soluções é controlado por heurísitca tabu adaptativa da literatura que determina as ações de intensificação e diversificação, aplicado a cada dia do período. A VERSÃO 2 incorpora uma abordagem similar para o período como um todo. Resultados computacionais indicam que esta abordagem leva a soluções de boa qualidade.

O presente estudo trata da configuração de uma rede de distribuição capacitada com restrição de cobertura. O objetivo é determinar quais cidades, dentre um conjunto de candidatas, devem atuar como centrais de desconsolidação de carga, de forma a minimizar o custo total de transporte (transferência e distribuição) para uma determinada demanda, atendendo às restrições operacionais e de distância de cobertura. A partir da pesquisa na literatura sobre o assunto, foi preparado um modelo de programação linear inteira para encontrar a solução ótima para o problema. Esse modelo é baseado nos clássicos problemas de localização, com modificação na função objetivo para retratar melhor a estrutura de custos de transporte, além da inclusão de restrições de cobertura e restrições de atendimento mínimas e máximas em cada central. O modelo foi implementado utilizando o suplemento Solver da planilha eletrônica Excel. Um outro enfoque de solução baseado na metaheurística Busca Tabu (Tabu Search) foi elaborado, com dois objetivos: permitir a análise de problemas quando não se tem disponível uma ferramenta para solução de modelos de programação linear; e analisar o comportamento da metaheurística quando utilizada na solução desse tipo de problema. O procedimento foi implementado a partir da construção de macros em linguagem Visual Basic for Application (VBA), também em Excel. O modelo de programação linear e a metaheurística Busca Tabu foram aplicados a alguns cenários de um problema real. Resultados, comparações e conclusões dessas aplicações são apresentados neste trabalho. / The present study deals with configuring a capacitated distribution network with coverage constraint. The objective consists of determining which cities, among a set of candidates, should act as load deconsolidation centers, aiming to minimize transportation total costs to attend a given demand, and obeying all operational constraints and coverage distances. Based on a literature review, an integer linear programming model was formulated to find the problem optimal solution. The model is based on classical location problems, but includes changes in the objective function to incorporate the transportation costs structure, besides coverage constraints and minimum and maximum central capacity constraints. The model was implemented using Excel’s Solver add-in. Another solution approach based on the Tabu Search metaheuristic was proposed, with two objectives: to permit problem analysis when linear programming tools are not available; and to learn on metaheuristic behavior when used to solve this type of problem. The Tabu Search procedure was implemented using Excel macro language in Visual Basic for Applications (VBA). Both integer linear programming and metaheuristic models were applied to some scenarios of a real-world problem. Applications results, comparisons and conclusions are presented in this work.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Neste trabalho avaliamos mÃtodos heurÃsticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurÃsticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e mÃtodo de otimizaÃÃo pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiÃncia de nossas heurÃsticas na obtenÃÃo de limites inferiores e superiores de boa qualidade, em tempo computacional razoÃvel, para instÃncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instÃncias do PPC ÃÂotimalidade e para comprovar a qualidade dos resultados alcanÃados por nossas heurÃsticas. / In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem.

Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-02-09T12:44:05Z No. of bitstreams: 2 Dissertação - Romário Pereira Marinho - 2017.pdf: 13877023 bytes, checksum: acc279d7703902ca281c2659e82477a2 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-02-09T12:44:48Z (GMT) No. of bitstreams: 2 Dissertação - Romário Pereira Marinho - 2017.pdf: 13877023 bytes, checksum: acc279d7703902ca281c2659e82477a2 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-02-09T12:44:48Z (GMT). No. of bitstreams: 2 Dissertação - Romário Pereira Marinho - 2017.pdf: 13877023 bytes, checksum: acc279d7703902ca281c2659e82477a2 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-08-25 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / The purpose of this work is the solution of the distribution network problem to minimize active power losses using meta-heuristics based on multistart methodology and tabu search. The initialization of both methodologies will be done by solving a power flow for weakly meshed systems whose apparent power will be used by Prim’s algorithm as the weight, which will generate good initial radial topologies. The local searchs implemented are through brach exchanges that aim to improve the solution. The solutions are obtained by programming algorithms implemented in C++ language, which aim to minimize the losses in the distribution feeders. This dissertation is the result of efforts made in the initial stages of the CELG D’s Research and Development (R&D) project, ANEEL’s code PD-6072-0302 / 2015. Therefore, it is one of the project’s by-products entitled: " Sistema de Apoio à Decisão para Restauração de Redes de Distribuição de Energia Elétrica Considerando Curvas de Carga dos Transformadores das Subestações / O objetivo deste trabalho é resolver o Problema de Reconfiguração de Sistemas de Distribuição de Energia Elétrica com foco na minimização das perdas elétricas do sistema através das metodologias metaheurísticas Multipartida e Busca Tabu. A inicialização de ambas metodologias dar-se-á através da resolução de um fluxo de potência para sistemas fracamente malhados cujas potências aparentes resultantes serão utilizadas como pesos ideais no Algoritmo de Prim, o qual gerará topologias iniciais radiais de boa qualidade. As buscas locais adotadas através das trocas ramos visam melhorar a solução inicial obtida. Soluções de reconfiguração de redes elétricas de 14, 33, 84, 136 e 417 nós são obtidas através da programação de algoritmos implementados em linguagem C++, as quais têm como objetivo minimizar as perdas nos alimentadores de distribuição. Esta dissertação é resultado de esforços realizados nas etapas iniciais do projeto de Pesquisa e Desenvolvimento (P&D) da CELG D, código ANEEL PD-6072- 0302/2015. Portanto, constitui-se em um dos subprodutos do projeto intitulado: “Sistema de Apoio à Decisão para Restauração de Redes de Distribuição de Energia Elétrica Considerando Curvas de Carga dos Transformadores das Subestações”.

Made available in DSpace on 2016-08-17T14:52:50Z (GMT). No. of bitstreams: 1 AgneloCoelho.pdf: 1955217 bytes, checksum: bdaabbadfbcefa2a1d4e8f8926759c45 (MD5) Previous issue date: 2006-03-10 / The distribution utilities must satisfy two concurrent objectives during planning process of the electric network: minimization of the investment cost and the satisfaction of reliability targets. An alternative to satisfy these objectives is to include low cost alternatives in the planning process. One of these alternatives is the reconfiguration of the distribution network. The reconfiguration of the distribution network can reduce the loss and balance the loads in the system only with opening and closing of switches without additional investment cost. In addition to reconfiguration, another alternative of low cost is the Distributed Generation (DG) allocation. This alternative became feasible due to the recent technological advances in the building of turbines that reduced significantly the costs of energy generation. In this way, the DG is a attractive option to satisfy the demand growth and minimize the costs associated with: building of new substations, feeder reconductoring and transformer upgrading. Consequently, is opportune to develop methodologies that include the reconfiguration and the DG in the planning of the distribution network. This dissertation presents the development of two methodologies for the planning of distribution networks: reconfiguration and optimal allocation of DG. The first part of the dissertation presents the development of the methodology for the network reconfiguration. Usually, the reconfiguration is carried out with the following objectives: minimization of the electric losses, voltage profile correction and load balancing between feeders. In this dissertation, in addition to these objectives, reliability constraints have been included in the reconfiguration methodology. This methodology is based on the combination of the following techniques: power flow algorithm, based on the Power Summation Method, to estimate the state of the network; analytic techniques to estimate the reliability indices and Tabu Search to identify the optimal topology. The second part of the research work presents the development of the methodology for the allocation of DG. This methodology has as objective to attend a forecasted demand level without violating operational constraints of the network (feeders loading and voltage drops) and minimizing the interruption costs through the DG allocation. These objectives are satisfied minimizing the cost/worth ratio between the installation/operation costs of DG and the costs associated with: interruptions, noncommercialized, energy purchases and electric losses. The minimization of the cost/worth ratio described above has been carried out by combining the following techniques: analytic approaches to estimate the impact of DG in the reliability indices, load flow algorithm to estimate the losses and violations in the operational constraints and genetic algorithms to maximize the cost worth ratio. The impact of the DG in the reliability indices has been considered including network constraints (voltage drop and feeder loading) in the predictive reliability model. The models and techniques proposed in this dissertation for the reconfiguration and DG allocation have been validated and applied in two large scale substations belonging to distribution network of the Electricity Utility of Maranhão - CEMAR. The results obtained with the algorithm of reconfiguration demonstrated that the proposed methodology was capable of reducing the losses in the feeders without deteriorating the reliability. Furthermore, the application of the methodology of DG allocation in the test system resulted in a cost/worth ratio lower than one. / As empresas de distribuição de energia elétrica devem satisfazer dois objetivos concorrentes durante o processo de planejamento da rede elétrica: minimizar os custos de investimento e satisfazer as metas de continuidade. Uma alternativa para satisfazer estes objetivos é incluir alternativas de projeto com baixo custo de investimento no processo de planejamento. Uma destas alternativas é a reconfiguração da rede de distribuição. A reconfiguração da rede de distribuição pode reduzir as perdas e balancear a carga do sistema apenas com a abertura e o fechamento de chaves sem nenhum custo de investimento adicional. Além da reconfiguração, uma outra alternativa de baixo custo de investimento é a alocação de Geração Distribuída (GD). Esta alternativa tornou-se factível devido aos recentes avanços tecnológicos na construção de turbinas que reduziram significativamente os custos de geração de energia. Desta forma, a GD é uma opção atrativa para atender o crescimento da demanda e minimizar os custos associados com: construção de novas subestações, recondutoramento de alimentadores e repotencialização de transformadores. Consequentemente, é oportuno desenvolver metodologias que incorporem a reconfiguração e a GD no processo de planejamento da rede de distribuição. Este trabalho apresenta o desenvolvimento de duas metodologias para planejamento de redes de distribuição: reconfiguração e alocação ótima de geração distribuída. A primeira parte do trabalho apresenta o desenvolvimento da metodologia para reconfiguração de redes. Geralmente, a reconfiguração é realizada com o objetivo de minimizar as perdas elétricas, melhorar perfil de tensão e para balancear cargas entre alimentadores. Neste trabalho, além destes objetivos, restrições de confiabilidade são incluídas na metodologia de reconfiguração. Esta metodologia se baseia na combinação das seguintes técnicas: algoritmo de fluxo de carga, baseado no método de Soma de Potências, para estimar o estado da rede, métodos analíticos para estimar os índices de confiabilidade e no algoritmo de Busca Tabu para identificar a topologia ótima. A segunda parte do trabalho apresenta o desenvolvimento da metodologia para a alocação ótima de geração distribuída. Esta metodologia tem como objetivo atender um nível de demanda previsto sem violar restrições operacionais da rede (carregamento dos alimentadores e queda de tensão) e minimizar os custos de interrupção através da alocação de GD. Estes objetivos são satisfeitos minimizando-se a relação custo/benefício entre os custos de instalação/operação da GD e os custos associados com: interrupções, energia não-faturada, compra de energia e perdas elétricas. A minimização da relação custo/benefício descrita acima foi realizada combinando-se as seguintes técnicas: métodos analíticos para estimar o impacto do GD nos índices de confiabilidade, algoritmo de fluxo de carga para estimar as perdas e violações nas restrições operacionais e algoritmos genéticos para minimizar a relação custo/benefício. O impacto da GD nos índices de confiabilidade foi considerado incluindo-se restrições de rede (queda de tensão e carregamento dos alimentadores) no modelo de confiabilidade preditivo. Os modelos e técnicas propostos nesta dissertação para reconfiguração e alocação de GD foram validados e aplicados em duas subestações de grande porte da rede de distribuição da Companhia Energética do Maranhão - CEMAR. Os resultados obtidos com o algoritmo de reconfiguração demonstraram que a metodologia proposta foi capaz de reduzir as perdas nos alimentadores sem deteriorar a confiabilidade. Além disso, a aplicação da metodologia de alocação de GD no sistema teste resultou em uma relação custo/benefício menor que 1.0.