Spelling suggestions: "subject:"busca tau"" "subject:"musca tau""
41 |
Abordagem metaheurística híbrida para a otimização de sequenciamento de produção em Flow Shop Permutacional com tempos de setup dependentes da sequênciaSimões, Wagner Lourenzi 06 December 2016 (has links)
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.
|
42 |
Proposição e análise de modelos híbridos para o problema de escalonamento de produção em oficina de máquinas / Presentation and analysis of hybridization models for the jobshop scheduling problemTatiana Balbi Fraga 26 March 2010 (has links)
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.
|
43 |
[en] MATHEURISTICS FOR VARIANTS OF THE DOMINATING SET PROBLEM / [pt] MATEURÍSTICAS PARA VARIANTES DO PROBLEMA DO CONJUNTO DOMINANTEMAYRA CARVALHO ALBUQUERQUE 14 June 2018 (has links)
[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.
|
44 |
Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos / Integration of Lagrangean heuristics with exact algorithms to otimization of the set partitioning problemAlves, Alexsandro de Oliveira January 2007 (has links)
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.
|
45 |
Proposição e análise de modelos híbridos para o problema de escalonamento de produção em oficina de máquinas / Presentation and analysis of hybridization models for the jobshop scheduling problemTatiana Balbi Fraga 26 March 2010 (has links)
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.
|
46 |
Desenvolvimento e aplicação de algoritmos adaptativos de busca tabu para a resolução de Problemas de Roteamento de Veículos Periódicos (PRVP).Hallal, Renato 16 December 2004 (has links)
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.
|
47 |
Configuração de uma rede de distribuição capacitada com restrição de cobertura. / Configuring a capacitated distribution network with coverage constraint.Thiago Pires 05 May 2006 (has links)
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 Excels 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.
|
48 |
IntegraÃÃo de heurÃsticas lagrangeanas com algoritmos exatos para a otimizaÃÃo de particionamento de conjuntos / Integration of Lagrangean heuristics with exact algorithms to otimization of the set partitioning problemAlexsandro de Oliveira Alves 31 August 2007 (has links)
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.
|
49 |
Reconfiguração de sistemas de distribuição de energia elétrica utilizando metodologias multipartida e busca tabu / Reconfiguration of electrical distribution systems using multistart method and tabu searchMarinho, Romário Pereira 25 August 2017 (has links)
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”.
|
50 |
Análise da Confiabilidade em Redes de Distribuição Radiais: Reconfiguração e Alocação de Geração Distribuída / ANALYSIS OF THE TRUSTWORTHINESS IN NETS OF DISTRIBUTION RADIAL: RECONFIGURATION AND ALOCATION OF DISTRIBUTED GENERATIONCoelho Neto, Agnelo 10 March 2006 (has links)
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.
|
Page generated in 0.038 seconds