Orientador: Jose Roberto Sanches Mantovani / Resumo: Neste trabalho, propõe-se uma nova metodologia para abordar de forma integrada os problemas de restauração automática e sequenciamento de operação de abertura e fechamento de chaves em redes de distribuição de grande porte. Na literatura os problemas de restauração e sequência de chaveamentos são normalmente considerados de forma separada e sequencial, em que o resultado do algoritmo de restauração é o dado de entrada para o algoritmo que gera a sequência de chaveamento. A inconsistência com esta abordagem é que não necessariamente o resultado convencional do algoritmo de restauração (conjunto de chaves que devem ser manobradas), é o melhor dado de entrada para o algoritmo que elabora o sequenciamento ótimo de abertura/fechamento das chaves. Isso porque quando ambos os problemas são resolvidos separadamente, eles possuem funções objetivos diferentes. O problema de restauração tem por objetivo minimizar a quantidade de carga desconectada com o menor número de chaveamentos possíveis, enquanto que o problema de sequenciamento de chaves tem o objetivo de reduzir a energia não suprida no sistema durante um evento de falta permanente. Uma nova abordagem baseada na meta-heurística de Busca Tabu com Vizinhança Variável Reativa é proposta para explorar o espaço de busca do problema em análise, simultaneamente com uma nova heurística para gerar a sequência de chaveamento em sistemas de grande porte com milhares de nós de carga. A existência em operação na rede de controle de equipament... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In this work, a new methodology is proposed to address, in an integrated approach, the automatic restoration problem and the switching sequence problem for large scale distribution networks. In the literature, the restoration and switching sequence problems are usually addressed separately and sequentially. Thus, the result of the distribution restoration algorithm is the initial data for the switching sequence algorithm. The inconsistency with this approach is that, not necessarily the conventional result of the restoration algorithm (a set of switches to be maneuvered) is the best initial data for the switching sequence algorithm. It is explained by the fact that both problems have different objective functions. The distribution restoration problem aims to minimize the amount of disconnected load with the fewest number of possible switching, whereas the switching sequence problem aims to minimize the energy not supplied in the network after a permanent fault. A new approach based on the Tabu Search with Reactive Variable Neighborhood meta-heuristic is proposed to explore the search space of the problem, along with a new heuristic to generate the switching sequence in large size distribution systems with thousands of load buses. The presence of voltage control devices, as switched capacitors and voltage regulators, are considered to improve the quality of solutions. The presence of distributed generation with black start capability is also considered. The cold load pick up c... (Complete abstract click electronic access below) / Doutor

Made available in DSpace on 2015-03-05T13:56:58Z (GMT). No. of bitstreams: 0 Previous issue date: 20 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho tem como objetivo a geração de um modelo de escalonamento aplicado ao Jobshop Scheduling Problem num Sistema de Manufatura Flexível que considera o tempo total de produção (makespan), o tempo total de atraso, o tempo total parado e o tempo total ocioso.O modelo proposto é composto por: (a) uma função objetivo que reflete, através de suas variáveis de decisão e seus pesos respectivos, as estratégias de otimização, e de (b) uma arquitetura que está dividida em cinco fases. O modelo utilizou o algoritmo Busca Tabu que,através de duas estratégias de geração de vizinhanças, busca a otimização da função objetivo. A arquitetura do modelo baseia-se na extração da demanda de produção, na Tecnologia de Grupo, nas Regras de Despacho, no Algoritmo Busca Tabu e na gravação do plano de produção, para tratar os Problemas de Seleção de Partes (Famílias de Partes) e do Escalonamento. Foram realizados, através de um estudo de caso, diversos experimentos que possibilitaram a comparação de estratégias de otimiza / This paper has the aim of generating a scheduling model applied to Job-shop Scheduling Problem in Flexible Manufacturing System, which considers the makespan, total tardiness time, total stop time, total idle time. The model proposed is composed for: (a) an objective function that reflects, through its variables of decision and its weights, the optimization strategies, and (b) arquitecture that is divided in five phases. The model used the Tabu Search algorithm which, through two strategies neighborhoods generation, searching the objective function optimization. The model architecture is based on extraction of production demand, in the Group Technology, in the Dispatching Rules, in the Tabu Search algorithm and save production plan, to deal the Part Selections (Part Families) and Scheduling Problems.Through a study of case, it has been realized several experiments which makes it possible the comparison of optimization strategies and real scheduling, and which proves conflicts in decision variables. For mo

Made available in DSpace on 2015-03-05T13:58:26Z (GMT). No. of bitstreams: 0 Previous issue date: 1 / Universidade do Vale do Rio dos Sinos / Neste trabalho é abordado o Problema de Escalonamento em um job shop, considerando restrições de datas de entrega, turnos de produção e tempo de setup entre operações. Considera-se um ambiente de Sistema de Manufatura flexível, que dado ao alto nível de automação, permite a previsibilidade dos processos de carregamento dos recursos à área de processamento. O problema foi modelado através de uma Função Objetivo fn composta de três variáveis de decisão. A importância da contribuição de cada variável para o valor de fn é gerida pela atribuição de valores aos pesos associados às variáveis. Na abordagem proposta, são utilizadas técnicas de Tecnologia de Grupo e Busca Tabu. O modelo implementado é uma modificação da técnica i TSAB, proposta por Nowicki e Smutnicki, a qual apresenta bons resultados no tratamento do Problema de Escalonamento em um job shop PEJS clássico. A consideração das restrições adicionais ao PEJS aumenta a complexidade do modelo implementado, porém, deixa o problema mais próximo da realidade. / In this work the Job Shop Scheduling Problem is studied, considering due dates, production turns and tooling constraints. This problem is applied in a Flexible Manufacturing System, which possesses high degree of automation, allowing previsibility in the processes of loading and unloading jobs on the machines. The problem is modeled through a objective function fn composed by three weighted decision variables. The importance of each variable in the fn final value is managed through assignment of values to the weights of these variables. In the proposed approach, it was used Group Technology and Tabu Search techniques. The implemented model is a modification of the i TSAB technique, proposed by Nowicki and Smutniki. The consideration of adicional constraints in the Job Shop Scheduling Problem increases the complexity of the implementation, otherwise, makes the problem closer to the industrial reality. The model was validated using benchmark instances, in which the data from the addional constraints were added.

Made available in DSpace on 2015-03-05T13:59:42Z (GMT). No. of bitstreams: 0 Previous issue date: 27 / Nenhuma / As escalas de tripulações em companhias aéreas é um fator importante na logística de operações dessas empresas e um problema interessante para a aplicação de Pesquisa operacional. Os custos com tripulantes no transporte aéreo são extremamente altos, superiores a 20% dos custos de operações das empresas. Diante desse contexto, este trabalho vem abordar o problema de rotações de tripulações em empresas aéreas. Uma rotação de tripulação – crew pairings – é uma seqüência de etapas ou segmentos de vôo que começam e terminam em uma base domiciliar de tripulantes. O objetivo deste planejamento é encontrar um subconjunto dessas rotações com custo mínimo e que cubra todas as etapas de vôo na programação da empresa atendendo as restrições inerentes ao problema. O trabalho desenvolveu uma solução para o problema com um modelo set covering/set partitioning, primeiramente, promovendo, uma solução inicial viável que foi aplicada, numa segunda etapa, a um processo de otimização utilizando a meta-heurística Busca Tabu e jan / The flight scheduling crews in airliners are an important factor in logistic of operations of a these companies and interesting problem for the application of Operational Research. The costs with crew members in the air transportation are extremely high, superior 20% of the costs of operations of the companies. So, this study presents an approach of the crew pairing problem in airlines. The objective of this planning is to find a subgroup of these pairings with minimum cost and that it covers all the flight legs in the programming of the airliners taking care of the inherent restrictions to the problem. The solution for the problem implemented a set covering/set partitioning model, first, promoting, a viable initial solution that was applied, in one second stage, to optimize process using the meta-heuristic Tabu Search and time windows. The results had disclosed values satisfactory, demonstrating solutions that, compared with the real solution, had promoted minimization indices superior 70%. The validation

Submitted by CARLA MARIA GOULART DE MORAES (carlagm) on 2015-04-01T18:43:13Z No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) / Made available in DSpace on 2015-04-01T18:43:13Z (GMT). No. of bitstreams: 1 CristianoGalafassi.pdf: 2977122 bytes, checksum: 5d851dbaf2aea5f9599c6ce44fa55ba0 (MD5) Previous issue date: 2011 / CNPQ – Conselho Nacional de Desenvolvimento Científico e Tecnológico / Este trabalho aborda o Problema de Roteamento de Veículos Capacitado com Janelas de Tempo, onde devem ser atendidas as restrições de capacidade do veículo e as janelas de tempo de atendimento do cliente. Para resolver tal problema serão utilizadas as metaheurísticas Busca Tabu e Algoritmos Genéticos, além do desenvolvimento de um Algoritmo Híbrido baseado nas duas metaheurísticas. Busca-se contribuir com o desenvolvimento de um Algoritmo Híbrido focado no Problema de Roteamento de Veículos que utilize o poder de intensificação da Busca Tabu e o poder de diversificação do Algoritmo Genético, objetivando a obtenção de soluções de boa qualidade sem comprometer o tempo computacional. Nos experimentos, no que tange a Busca Tabu, analisa-se o processo de busca da através da variação do tamanho da Lista Tabu e do número máximo de iterações sem melhora do valor da função objetivo, como critério de parada, aplicados a uma política de intensificação. Para o Algoritmo Genético, é analisada a influência e o comportamento da busca com base em três operadores de cruzamento aplicados a duas políticas de elitismo. Ainda assim, para o Algoritmo Híbrido, analisa-se o impacto do tamanho da Lista Tabu e das taxas de Mutação e Cruzamento. Por fim, os resultados obtidos são comparados com os melhores métodos heurísticos encontrados na literatura e com métodos exatos, onde o Algoritmo Híbrido mostra-se robusto, obtendo soluções ótimas para diversas instancias de problemas. / This paper approaches the Capacitated Vehicle Routing Problem with Time Windows, which must obey the restrictions on vehicle capacity and time windows for customer service. To solve this problem will be used two metaheuristics, Tabu Search and Genetic Algorithms, and are developed an hybrid algorithm based on this two metaheuristics. The aim is to contribute with the development of a Hybrid Algorithm focused on Vehicle Routing Problem that uses the Tabu Search intensification power and the Genetic Algorithms diversification power, in order to obtain good quality solutions without compromising the computational time. In the experiments, with respect to Tabu Search, we analyze the search process by varying the size of the Tabu List and the maximum number of iterations without improvement in objective function value, such as stopping criterion, applied to an intensification policy. For the genetic algorithm are analyzed the influence and the search behavior on the basis of three crossover operators, applied to two elitism policies. Still, for the hybrid algorithm, we analyze the impact of the Tabu List size and rates of mutation and crossover. Finally, the results are compared with the best heuristics in the literature and with exact methods, where the Hybrid Algorithm shows robust, getting several optimal solutions.

Neste trabalho é proposta uma nova técnica de solução para resolver o problema de planejamento da expansão de sistemas de transmissão estático através da introdução da tomada de decisão fuzzy. Na técnica apresentada neste trabalho, a tomada de decisão fuzzy é aplicada para o desenvolvimento de um algoritmo heurístico construtivo. O sistema fuzzy é utilizado para contornar alguns problemas críticos das heurísticas que utilizam o índice de sensibilidade como guia para inserção de novas linhas. A heurística apresentada nesse trabalho é baseada na técnica dividir para conquistar. Verificou-se que a deficiência das heurísticas construtivas é decorrente da decisão de inserir novas linhas baseada em valores não seguros encontrados através da solução do modelo utilizado. Para contornar tal deficiência, sempre que surgirem valores não seguros divide-se o problema original em dois subproblemas, um que analisa a qualidade da resposta para o caso em que a linha é inserida e outro para verificar a qualidade da resposta para o caso em que a linha não é inserida. A tomada de decisão fuzzy é utilizada para decidir sobre quando dividir o problema em dois novos subproblemas. Utilizou-se o modelo cc com a estratégia de Villasana-Garver-Salon para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Ao serem realizados testes em sistemas de pequeno, médio e grande portes certificou-se que o método pode encontrar a solução ótima de sistemas de pequeno e médio portes. Porém, a solução ótima dos sistemas de grande porte testados não foi encontrada. Para melhorar a qualidade da solução encontrada utilizou, em uma segunda fase, a metaheurística busca tabu. A busca tabu utiliza o modelo cc. Os resultados se mostraram bastante promissores. Os testes foram realizados em alguns sistemas reais brasileiros e com o sistema real colombiano. / A new solution technique to solve the long-term static transmission expansion planning (TEP) problem based on fuzzy decision making is proposed. The technique applies the concepts of fuzzy decision making in a constructive heuristic algorithm. The fuzzy system is used to circumvent some critical problems of heuristics that use sentivity indices as a guide for insertion and construction of new lines. The heuristic algorithm proposed in this work is based on the divide and conquer technique. It has been verified that the deficiency of the constructive heuristics is due to the decision of inserting new lines based only on information given by the index, which usually is calculated from a relaxed mathematical representation of the problem and can become less accurate during the solution process. In order to be able to deal with such problem, whenever the quality of the index decreases, the original problem is divided into two sub-problems: one examines the quality of the solution when the transmission line indicated by the sensitivity index is inserted and the other subproblem checks the opposite. Fuzzy decision-making is used to decide the moment to divide the problem into two subproblems based on other information. The hybrid linear model is used to model the long-term transmission expansion planning problem and is used in the proposed algorithm. Tests was done with systems of small-term, medium-term and long-term. The optimal solution of small-term and medium-term was foundo using just the construtive heuristic algorithm with fuzzy decision-making. To deal with long-term systems was used the solutions of the construtive heuristic algorithm with fuzzy decision-making to init a tabu search. The tabu search uses the dc model. The results are very promising. The test was done with some real brazilian systems and with the real colombian system.

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.

Abstract This dissertation presents a new algorithm by integrating evolutionary programming (EP), tabu search (TS) and quadratic programming (QP), named the evolutionary-tabu quadratic programming (ETQ) method, to solve the nonconvex economic dispatch problem (NED). This problem involves the economic dispatch with valve-point effects (EDVP), economic dispatch with piecewise quadratic cost function (EDPQ), and economic dispatch with prohibited operating zones (EDPO). EDPV, EDPQ and EDPO are similar problems when ETQ was employed. The problem was solved in two phases, the cost-curve-selection subproblem, and the typical ED solving subproblem. The first phase was resolved by using a hybrid EP and TS, and the second phase by QP. In the solving process, EP with repairing strategy was used to generate feasible solutions, TS was used to prevent prematurity, and QP was used to enhance the performance. Numerical results show that the proposed method is more effective than other previously developed evolutionary computation algorithms.

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.