Orientador: Prof. Dr. Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2018. / Diversos problemas da area de otimização combinatoria podem ser convertidos, em tempo polinomial, para o problema de Programação Quadratica Binaria Irrestrita (UBQP). Neste problema, desejamos encontrar um vetor solução binario x, de dimensão n, tal que a função objetivo f(x) = x|Qx tenha valor mínimo, onde Q é uma matriz com coeficientes racionais. Em termos de complexidade computacional, o problema UBQP pertence a classe NP-difícil. A importancia deste problema, tanto pratica quanto teorica, tem motivado muitos pesquisadores a dedicarem uma quantidade razoavel de tempo tentando projetar tecnicas de resolução exatas e heuristicas para este problema. Durante o processo de resolução do problema UBQP, estas tecnicas necessitam reavaliar muitas vezes o valor da função objetivo. Dependendo da maneira como esta reavaliação é realizada, pode ser preciso executar um numero relativamente grande de operações elementares (atribuições, adições, subtrações e comparações). Isto pode consumir muito tempo de processamento quando n é grande. Nesta pesquisa, propomos formulas que requerem poucas operações para efetuar a reavaliação. Na literatura do problema UBQP, formulas de reavaliação são aplicadas, normalmente, quando há ate duas alterações nos componentes do vetor solução. As formulas que deduzimos podem ser usadas para efetuar qualquer quantidade de alterações. Analisamos uma das nossas formulas de maneira teorica e deduzimos funções que podem ser adotadas para indicar o melhor momento para aplicar essa formula. Ademais, projetamos algoritmos com estas formulas de reavaliação e verificamos a praticidade destes algoritmos conduzindo experimentos computacionais usando implementações de heurísticas de busca local e Variable Neighborhood Search. Nesses experimentos comparamos o desempenho dessas implementações ao resolver instancias da literatura para o problema UBQP. Os resultados experimentais evidenciaram que as formulas de reavaliação, propostas, podem propiciar reduções relativamente grandes nos tempos de processamento, mesmo quando o numero de diferenças entre soluções é moderadamente grande. / Several combinatorial optimization problems can be reformulated, in polynomial time, to the Unconstrained Binary Quadratic Programming (UBQP) problem. In this problem, we are interested in finding an n-dimensional binary solution vector, x, that minimizes the objective function f(x) = x|Qx, where Q is a matrix with rational coecients. In terms of computational complexity, the UBQP problem belongs to the NP-hard class. The practical and theoretical importance of this problem has motivated many researchers to dedicate a reasonable amount of time developing exact and heuristic solution techniques to solve this problem. During the resolution process of the UBQP problem, these techniques need to evaluate many times the objective function value. Depending on how it is made, it may be necessary to execute a relatively large number of elementary operations, such as assignments, additions, subtractions and comparisons. For n large, this may be time consuming. In this research, we propose formulas to perform the reevaluation requiring lesser operations than the simple evaluation of the objective function. In the literature of the UBQP problem, it is common to use reevaluation formulas only when there are at most two- ip moves that simultaneously change the values of two components. The formulas we have deduced can be used to evaluate any number of ip moves. We analyzed one of our reevaluation formulas and deduced functions that can be used to suggest the best moment to apply this formula. In addition, we designed algorithms with these reevaluation formulas and verified the practicality of these algorithms by conducting computational experiments using implementations of local search and Variable Neighborhood Search heuristics. In these experiments, we compared the performance of these implementations by solving benchmark instances for the UBQP problem. The experimental results showed that the reevaluation formulas we created can provide relatively large reductions in processing times, even when the number of ip moves is moderately large.

Orientador: Antônio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-17T07:59:31Z (GMT). No. of bitstreams: 1 Pinto_LuisFrancodeCampos_M.pdf: 11074962 bytes, checksum: 1a81559fbea90f37c92a435180da70b3 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho, foi desenvolvida uma aplicação prática de técnicas da pesquisa operacional para a resolução de um problema real de esquematização ou programação de máquinas. Este problema deriva de um flexible job shop scheduling, porém apresentando diversas características próprias, impossibilitando a aplicação de modelos disponíveis na literatura. O desempenho da utilização da combinação de um modelo de programação linear inteira mista com uma heurística de construção e uma heurística de melhoramento foi avaliado diante de cenários reais obtidos da indústria de produção de frascos plásticos. Estas técnicas provaram ser eficientes para a resolução dos casos propostos / Abstract: In this work, a practical application of operational research techniques was developed to solve a real machine scheduling or programming problem. This problem derives from a flexible job shop scheduling framework, but presents several unique characteristics, which makes it impossible to apply models available in literature. The performance of using a combination of a mixed integer programming model with a construction heuristic and a improvement heuristic was evaluated using real world scenarios obtained from the plastic bottle production industry. Theses techniques were proven efficient in resolving the proposed cases / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-05T20:11:19Z (GMT). No. of bitstreams: 1 Garcia_ViniciusJacques_D.pdf: 1756755 bytes, checksum: e845cc09a5de807da958e9792684e777 (MD5) Previous issue date: 2005 / Resumo: Depois da regulamentação do setor elétrico brasileiro, a qualidade no fornecimento de energia ganhou maior importância por parte das concessionárias. Neste contexto, o problema de restauração do serviço tem particular relevância pela relação com a freqüência e duração das interrupções no fornecimento: através de alterações na configuração original da rede, busca-se reduzir a carga não atendida sem deixar de observar as restrições de capacidade dos alimentadores, de queda de tensão nas barras de carga e de radialidade da rede. Considerando o caráter temporário destas manobras, torna-se desejável reduzir o grau de intervenção de modo a facilitar a restauração da configuração original. Nesta tese é considerado o problema multiobjetivo de restauração do serviço que compreende a minimização da carga sem fornecimento e do número de chaves manipuladas. Depois da definição matemática do problema, da revisão da literatura especializada e da descrição de um "framework" para problemas relacionados, são descritas duas heurísticas, uma construtiva e outra de melhoramento. A seguir, apresentam-se duas metaheurísticas para o problema, uma Busca Tabu e um Algoritmo Evolutivo, ambas baseadas em otimização de Pareto. Por fim, por meio de estudos práticos com sistemas de distribuição brasileiros, avalia-se experimentalmente a aplicabilidade das abordagens propostas / Abstract: After the Brazilian electric power market regulation, quality of service became a crucial concern of utilities. In fact, the service restoration has a particular importance since it is closely related to frequency and duration of service interruption: through network reconfigurations, one aims to reduce the non supplied load while respecting constraints like feeder and voltage limits as well as the maintenance of a radial structure. Considering that this emergency state is transitory existing only until the fault is eliminated, it is convenient to reduce the number of switching operations in order to make the return back to the original configuration easy. This work considers the multiobjective service restoration to minimize both the load not supplied and the number of switching operations. After defining the mathematical formulation proposed and presenting the bibliographical survey with the description of a new framework to related problems, two new heuristics are presented, one for constructive search and another one for neighborhood search. Next, two metaheuristics especially developed for the referred problem are described, both based on Pareto optimization. Finally, the effectiveness of these proposed methods are proved in a set of five systems, three of them referring to actual Brazilian systems / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Carlos Alberto de Castro Junior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T10:50:00Z (GMT). No. of bitstreams: 1 Guimaraes_MarcosAntoniodoNascimento_M.pdf: 908712 bytes, checksum: d5cf1733a05a1a20b87eb0c7abf094fb (MD5) Previous issue date: 2005 / Resumo: A reconfiguração de sistemas de distribuição consiste na alteração da topologia da rede através do fechamento e abertura de chaves instaladas em pontos estratégicos da rede. Normalmente o procedimento é utilizado para fins de isolamento de faltas, minimização de perdas de potência ativa e balanceamento de cargas entre os alimentadores. Esse problema é de difícil resolução devido ao grande número de variáveis envolvidas e das restrições impostas, sendo a restrição de radialidade a de mais difícil representação matemática. O problema pode ser classificado como um problema de programação não linear inteiro misto (PNLIM) e apresenta o fenômeno de explosão combinatorial. Este trabalho tem como principal objetivo o desenvolvimento de um algoritmo de Busca Tabu para a reconfiguração de sistemas de distribuição de energia elétrica tendo como objetivo a maximização da margem de segurança com relação à estabilidade de tensão (ou margem de carregamento). São apresentados resultados para sistemas de 14 barras, 32 barras, 69 barras, 84 barras e os sistemas reais de 135 barras e 202 barras / Abstract: The network reconfiguration consists in modifying the topology of the network through the closing and opening of switches installed in strategical points. The reconfiguration of distribution systems is usually done to isolate faults, minimize real power losses, or to balance the load among feeders. This problem is difficult due to the great number of variables involved and the imposed constraints, being the constraint of radial structure of more difficult mathematical representation. The problem can be classified as nonlinear mixed integer programming problems with combinatorial explosion. The main objective of this work is to develop a Tabu Search algorithm for the reconfiguration of distribution systems for voltage stability margin enhancement. Results for the systems: 14 buses, 32 buses, 69 buses, 84 buses and the real systems 135 bus and 202 bus are presented and discussed. / Mestrado / Sistemas de Energia Eletrica / Mestre em Engenharia Elétrica

Orientadores: Christiano Lyra Filho, Celso Cavellucci / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T03:27:30Z (GMT). No. of bitstreams: 1 Reis_PauloAlexandre_M.pdf: 462293 bytes, checksum: 3e3ba986f1d06695ded61d98139be232 (MD5) Previous issue date: 2007 / Resumo: Abordagens tradicionais de manutenção de sistemas de distribuição de energia elétrica se baseiam em ações realizadas periodicamente, ou programadas, de acordo com uma análise de necessidades e prioridades após inspeções. Embora essas abordagens tenham o objetivo de melhorar a confiabilidade dos sistemas, geralmente não há uma avaliação precisa do impacto das ações de manutenção na confiabilidade dos mesmos. O planejamento de manutenções pode ser realizado sob a perspectiva da confiabilidade com abordagens recentes chamadas RCM (reliability centered maintenance - manutenção baseada em confiabilidade). Essas abordagens procuram estabelecer uma ligação rigorosa entre manutenção e confiabilidade. Este trabalho propõe uma abordagem de manutenção baseada em confiabilidade com a perspectiva de encontrar as melhores estratégias para manutenções de redes de distribuição de energia elétrica; apresenta um modelo matemático e metodologia de otimização para encontrar as melhores estratégias de manutenções em um determinado horizonte de estudo. O problema formulado caracteriza-se como um problema de otimização combinatória com o objetivo de encontrar as ações de manutenção que minimizem os recursos utilizados em manutenções preventivas e corretivas, garantindo um nível de confiabilidade desejado para o sistema. O trabalho desenvolve duas alternativas para solução do problema: a primeira abordagem foi construída a partir do método GRASP (greedy randomized adaptive search procedure); a segunda abordagem é um método de computação evolutiva com busca local. Estudos de casos em redes de porte real avaliam as duas alternativas de solução. Os resultados realçam aspectos significativos da abordagem desenvolvida. / Abstract: Traditional approaches to electric power distribution systems maintenance are based on activities performed at regular intervals, or scheduled after analysis of needs end priorities identified after inspections. Although these maintenances activities are carried out to improve reliability, usually such approaches do not explicitly consider the impact of maintenance activities on reliability. Maintenance planning can be guided by reliability with recent approaches known as RCM (reliability centered maintenance). A RCM approach tries to establish a rigorous link between maintenance and reliability. This work proposes a reliability centered maintenance approach to unveil the best maintenance schedule for electric power distribution networks; it presents a mathematical model and optimization methods to find the best maintenance schedule along a given planning horizon. The problem is formulated as a combinatorial optimization problem with the objective of finding the maintenance activities that minimize the resources allocated to preventive and corrective maintenance, making sure the system meets a reliability target. The work proposes two heuristic methods to solve the problem: the first one is a GRASP method (Greedy Randomized Adaptive Search Procedure); the other one is an evolutionary computation method with local search. Realistic case studies are used to evaluate both methods. The results highlight meaningful aspects of the proposed approaches. / Mestrado / Automação / Mestre em Engenharia Elétrica

Made available in DSpace on 2015-04-11T14:02:41Z (GMT). No. of bitstreams: 1 rainer.pdf: 3537323 bytes, checksum: 46bd81628ce774393ea9334f7287a55f (MD5) Previous issue date: 2013-03-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation presents a study on scheduling problems with earliness and tardiness penalties on identical parallel machines, considering independent and weighted jobs with arbitrary processing times. An analysis of the major mathematical formulations in integer programming is given, and presented the main results from the literature. An integer mathematical formulation based on network flow model was also proposed for the problem, which can be applied on single and parallel machines without idle time. Exact methods of implicit enumeration were studied and applied for the problem through the integer linear programming solver CPLEX and the UFFLP library and, mainly, algorithmic strategies of global optimization based on local search heuristic and path-relinking technique were developed. The computational experiments shows that the proposed algorithmic strategies are competitive in relation to existing results from the literature for single-machine scheduling, involving instances based on OR-Library benchmark for 40, 50, 100, 150, 200 and 300 jobs, where all the optimal values were found, and, mainly, being the best algorithmic strategy for multiprocessor environments, involving 2, 4 and 10 identical parallel machines. / Esta dissertação apresenta um estudo sobre problemas de escalonamento com penalidades de antecipação e atraso em máquinas paralelas, considerando tarefas independentes, ponderadas e de tempos de execução arbitrários. Uma análise sobre as principais formulações matemáticas em programação inteira é dada, bem como apresentados os principais resultados da literatura. Uma formulação matemática de programação inteira baseada no modelo de fluxo em redes também foi proposta para o problema, que pode ser aplicada em ambientes mono e multiprocessado sem tempo ocioso. Métodos de enumeração implícita foram estudados e aplicados aos problemas em questão através do resolvedor de programação linear inteira CPLEX e da biblioteca UFFLP, principalmente, estratégias algorítmicas aproximadas de otimização global baseadas em heurísticas de busca local e técnica de reconexão de caminhos foram desenvolvidas. Os experimentos computacionais mostram que as estratégias propostas são competitivas em relação aos resultados existentes na literatura para ambientes de escalonamento monoprocessados, envolvendo instâncias baseadas no benchmark da OR-Library para 40, 50, 100, 150, 200 e 300 tarefas, onde todos os ótimos foram encontrados, e, principalmente, sendo a melhor estratégia apresentada para ambientes multiprocessados, envolvendo 2, 4 e 10 máquinas paralelas idênticas.

O problema de dimensionamento de lotes, objeto desse estudo, considera um ambiente composto por múltiplas plantas independentes, múltiplos itens e múltiplos períodos. O ambiente de produção tem capacidade limitada e as plantas podem produzir os mesmos itens. Cada planta tem uma demanda própria e é permitida a transferência de lotes entre as plantas, o que envolve um certo custo. Este problema tem como caso particular o de dimensionamento de lotes com máquinas paralelas. O objetivo desta dissertação é propor uma heurística baseada na meta-heurística GRASP (Greedy Randomized Adaptive Search Procedures). Além disso, uma estratégia path relinking foi incorporada ao GRASP como uma fase de melhoria do algoritmo. Para verificar a eficiência da heurística proposta, os seus resultados são comparados aos da literatura tanto no caso de máquinas paralelas quanto no de múltiplas plantas. Como resultado, o problema de múltiplas plantas obteve melhores resultados quando comparado aos da heurística da literatura. Com relação ao problema de máquinas paralelas, a heurística proposta se mostrou competitiva / The lot sizing problem, which is the aim of this study, considers an environment consisting of multiple independent plants, multiple items and multiple periods. The production environment has limited capacity and the plants can produce the same items. Each plant has its own demand and the lot transfers between the plants are permitted, which involves a certain cost. This problem has as a particular case the parallel machines lot sizing problem. The objective of this dissertation is to propose a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedures). Furthermore, a path relinking phase is embedded in the GRASP to obtain better performance. To verify the efficiency of the proposed heuristic, its results were compared with the literature as for the multi-plant as for parallel machines problem. Computational tests showed that the proposed heuristic performed better than other literature heuristic concerning the multiplant problem. Concerning the parallel machines, the heuristic is competitive

Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto, são interessantes de serem atacadas dos pontos de vista teórico e prático. Nosso foco nesse trabalho é considerar algoritmos de aproximação e algoritmos de programação inteira mista para os problemas mencionados, apresentando novos resultados superiores àqueles conhecidos previamente na literatura, bem como determinar a complexidade computacional destes problemas ou de alguns de seus casos particulares de interesse. / In this thesis we consider allocation and pricing problems, where we have a set of items and a set of consumers interested in such items. Our objective is to choose an allocation of items to consumers, considering the maximum value a consumer is willing to pay in a specific item. In particular, we focus in three problems: the Max-Buying Problem, the Envy-Free Pricing Problem and the Second-Price Ad Auction. The Max-Buying Problem and the Envy-Free Pricing Problem model a problem faced in reality by companies that sell products or services, where it is necessary to correctly choose the price of the products or services available to clients in order to obtain an interesting profit. The Second-Price Ad Auction models the problem faced by companies that own search engines and desire to sell space for advertisers in the search results of the users. Both questions, the pricing of items and services and the allocation of advertisers in search results are of great economical relevance and, for this, are interesting to be attacked from a theoretical and a practical perspective. Our focus in this work is to consider approximation algorithms and mixed integer programming algorithms for the aforementioned problems, presenting new results superior than the previously known in the literature, as well as to determine the computational complexity of such problems or some of their interesting particular cases.

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática / Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Zanoni Dias / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T03:52:46Z (GMT). No. of bitstreams: 1 Dias_UlissesMartins_D.pdf: 19168517 bytes, checksum: 463a6e15e1414ce37a0fe80f92de6b07 (MD5) Previous issue date: 2012 / Resumo: Esta tese aborda três aspectos da comparação entre genomas: primeiro, eventos de transposição; segundo, eventos de reversão e de reversão quase-simétrica; terceiro, estudo da distância entre genomas sem ligação com algum tipo específico de rearranjo. O estudo do primeiro aspecto, eventos de transposição, permitiu a criação de um novo algoritmo de aproximação na razão 1.375 e de modelos exatos usando programação em lógica com restrições para o problema da distância de transposição. Ambas as abordagens foram comparadas com outras semelhantes encontradas na literatura e, em ambos os casos, foi mostrado que o produto aqui apresentado é superior 'aqueles previamente conhecidos. Sob o segundo aspecto, eventos de reversões e de reversões quase-simétricas, houve avanços relacionados ao entendimento do processo de diferenciação das espécies na família Pseudomonadaceae e nos gêneros Mycobacterium, Shewanella e Xanthomonas com a criação de uma ferramenta de simulação capaz de gerar um histórico evolutivo com características semelhantes 'as observadas nos referidos grupos. Além disso, foram obtidos avanços em abordagens algorítmicas para o problema de construção de scaffolds usando um genoma de referência. De modo particular, foi obtida uma ferramenta superior 'as demais existentes na literatura para construção de scaffolds de genomas bacteriais. Ainda neste segundo aspecto, tratou-se do problema da distância de reversões quase-simétricas com a geração de um algoritmo guloso que fornece uma sequência de reversões quase-simétricas para ordenar qualquer permutação, além de algoritmos exatos para várias famílias específicas de permutações. No que diz respeito ao terceiro aspecto, foram desenvolvidas duas medidas que podem ser calculadas de forma eficiente (poucos segundos). Uma das medidas é adequada para genomas próximos e a outra é adequada para genomas distantes. Ambas foram avaliadas com genomas bacteriais reais, o que mostrou as vantagens e limitações de cada medida. Com esta tese, espera-se ter contribuído para a área de comparação de genomas em geral e, em particular, para a área de rearranjo de genomas / Abstract: In this PhD thesis, we work on three aspects of genome comparison: first, transposition events; second, inversion and almost-symmetric inversion events; third, whole-genome distance measures that are not connected to any specific kind of rearrangement event. The study of transposition events (first aspect) allowed us to create a new 1.375-approximation algorithm and some exact models using constraint logic programming. These approaches were compared to other published methods and in all cases our methods perform best. The second aspect of this thesis concerns inversion and almost-symmetric inversion events. In this regard, we developed a simulation tool for the study of symmetric inversions in bacterial genomes. Through this work we were able to contribute to the understanding of the evolutionary differentiation process in species of the following groups: the Pseudomonadaceae family, the Xanthomonas genus, the Shewanella genus, and the Mycobacterium genus. We used the knowledge acquired in building our simulation tool to establish a method that uses inversion signatures to generate draft genome sequence scaffolds using a complete genome as a reference. Apart from the practical applications of this research, we contribute to the computer science field by providing a theoretical framework for the almost-symmetric distance problem that can be improved in the future and can serve as a basis for approximation and heuristic algorithms. This framework is comprised of a greedy algorithm for any permutation, exact algorithms for specific families of permutation, and several lemmas and conjectures related to these problems. The third and last aspect of this thesis addresses the need for methods that can quickly and effectively compare large sets of genome sequences. We propose two new methods for efficiently determining whole genome sequence distance measures. One of them is aimed at comparing closely related genomes, and the other is meant to compare more distant genomes. Both measures were evaluated in order to find their limitations and their efficacy. It is our hope that thiswork represents a contribution to knowledge of the genome comparison field in general, and the genome rearrangement field, in particular / Doutorado / Ciência da Computação / Doutor em Ciência da Computação