Orientador: Arnaldo Vieira Moura, Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-12T08:44:27Z (GMT). No. of bitstreams: 1 Cire_AndreAugusto_M.pdf: 961770 bytes, checksum: 5fad1ce7143a7b6505cc4194ac56dc65 (MD5) Previous issue date: 2008 / Resumo: Esta dissertação de Mestrado trata de um problema real de escalonamento, no qual uma complexa rede de dutos é utilizada para distribuição de derivados de petróleo e bio-combustíveis de refinarias a mercados locais. Dutos constituem a alternativa de transporte mais vantajosa em termos econômicos e ambientais, mas trazem consigo um amplo conjunto de restrições operacionais difíceis, envolvendo seqüenciamento de produtos, capacidade de tanques, controle de taxa de vazão, controle de estoque e muitas outras. O objetivo do problema está em escalonar operações de bombeamento nos dutos de forma a satisfazer as demandas locais em cada órgão de distribuição, dentro de um horizonte de planejamento pré-definido. Para resolvê-lo, este trabalho propõe uma nova abordagem híbrida composta por duas fases. Primeiramente, uma fase de planejamento define os volumes de produto que devem ser transmitidos entre órgãos para que as demandas sejam completamente atendidas. Em seguida, uma fase de escalonamento é responsável por criar e escalonar as operações de bombeamento, de forma a garantir que os volumes definidos na fase anterior sejam efetivamente enviados. Esta disserta¸c¿ao foca na fase de escalonamento, e duas formulações em Programação por Restrições (PR) são apresentadas para modelá-la. Conforme foi verificado, a flexibilidade de PR 'e fundamental para representar e satisfazer restrição que, usualmente, são desconsideradas na literatura, mas que são essenciais para a viabilidade operacional das soluções. A estratégia completa foi implementada e produziu resultados adequados e promissoras para 5 instâncias reais fornecidas pela Petrobras. Tais instâncias cont¿em 30 dutos, mais de 30 produtos e 14 órgãos de distribuição que contemplam cerca de 200 tanques. / Abstract: This dissertation deals with a very difficult overly-constrained scheduling challenge: how to operate a large pipeline network in order to adequately transport oil derivatives and biofuels from refineries to local markets. Pipeline network systems are considered the major option for transporting these product types, in view of their many economic and environmental advantages. However, they pose serious operational difficulties related to product sequencing, flow rates and tank capacities. The challenge is how to schedule individual pumping operations, given the daily production and demand of each product, at each location in the network, over a given time horizon. In order to tackle this problem, we propose a novel hybrid approach which comprises two phases. Firstly, a planning phase decides the necessary volume transmission among depots to satisfy the given demands. Finally, a scheduling phase generates and schedules the pumping operations that guarantee the required volume transmission. This dissertation focuses on the scheduling phase, in which two new Constraint Programming (CP) models are proposed. The CP flexibility plays a key role in modeling and satisfying operational constraints that are usually overlooked in literature, but that are essential in rder to guarantee viable solutions. The full strategy was implemented and produced adequate and promising results when tested over 5 large real instances from Petrobras. These instances have a complex topology with around 30 interconnecting pipelines, over 30 different products in circulation, and about 14 distribution depots which harbor more than 200 tanks. / Mestrado / Pesquisa Operacional / Mestre em Ciência da Computação

Orientador: Reginaldo Guirardello / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Quimica / Made available in DSpace on 2018-08-12T13:45:38Z (GMT). No. of bitstreams: 1 Almeida_SheilaSouzade_M.pdf: 1636225 bytes, checksum: 745e0149ac6b7b1271674496404c47e9 (MD5) Previous issue date: 2008 / Resumo: O Layout de uma indústria é de grande preocupação no seu desenvolvimento e, por este motivo, engenheiros e pesquisadores vêm cada vez mais se aprofundando no assunto. A escolha de um bom Layout tem influência nos custos, na segurança, operação e manutenção que são fatores de grande importância para o projeto de planta industrial. Este trabalho tem como objetivo o desenvolvimento da metodologia através de um modelo matemático de otimização para a definição de um Layout industrial através da minimização da função custo, tendo como restrições os critérios de espaço para a segurança, operação e manutenção da planta. Será utilizado como modelo de otimização o problema de atribuição quadrático (QAP), onde se alocam os elementos em uma malha de posições predeterminadas, minimizando a função objetivo. Como este modelo tem uma grande dificuldade em encontrar soluções exatas em tempo viável para a otimização de problemas com grande número de elementos, será utilizado como alternativa métodos heurísticos, que são métodos que encontram soluções rápidas em tempo curto, encontrando uma aproximação para a solução ótima, de fácil implementação e pouco espaço de memória. Dentre as técnicas heurísticas encontra-se o algoritmo Simulated Annealing, um método no qual a solução ótima pode não ser obtida, mas soluções muito próximas a ela são geradas em um tempo de execução muito menor que outras técnicas. Uma característica típica do algoritmo de Simulated Annealing é que além de aceitar soluções que representam melhoramentos no custo, também aceita "deteriorações" (soluções com custo maior) com um certo limite. O mecanismo de geração de soluções escolhido neste trabalho foi a troca de posições entre pares de elementos. A planta escolhida para este estudo foi a de produção de poliéster com 50 equipamentos. Foi necessário estimar com precisão o tamanho e a geometria da rede, para que o tempo computacional fosse o melhor para cada caso. Os resultados indicam que o método escolhido mostrou-se adequado e os Layouts obtidos foram satisfatórios. / Abstract: The layout of an industry is of great concern to its development, and for this particular reason, engineers and researchers are increasingly diving deeper into the subject. Choosing a good layout has a direct influence on costs, security, operations and maintenance, which are all factors of large importance for the project of an industrial plant. This study aims at the development of the methodology through a mathematical optimization model for the definition of an industrial layout by minimizing the cost function, with the restrictions of space criteria for safety, operation and maintenance of the plant. The quadratic assignment problem (QAP), which allocates the elements on to a mesh of preset positions thus minimizing the objective function, will be used as an optimization model. Layout problems usually have great difficulty to encounter exact solutions in viable time for the optimization of problems containing a large numbers of elements; therefore, the alternative heuristic method will be used. This method encounters rapid solutions in short timeframes, finding an approximation for an optimal solution, easy to implement and requires a small amount of storage space. Among the heuristic techniques is the Simulated Annealing algorithm, a method in which an optimal solution may not be obtained, however solutions very close to it are generated in an execution time much smaller than other techniques. A typical characteristic of the Simulated Annealing algorithm is that in addition to accepting solutions that represent improvements in cost, it also accepts deterioration (solutions with greater costs) within a certain limit. The mechanism of generation of new solutions chosen in this study was to change positions between the pairs of elements. In order to demonstrate the proposed approach, a polyester production plant with 50 pieces of equipment was chosen. It was necessary to estimate with precision the size and geometry of the network, so that the computational time was the best for each case. The results indicate that the chosen method proved to be appropriate and the layouts obtained were satisfactory. / Mestrado / Desenvolvimento de Processos Químicos / Mestre em Engenharia Química

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-07T18:24:20Z No. of bitstreams: 1 samuelbelinidefilippo.pdf: 2753590 bytes, checksum: 260a8f328d5b69585883e19fcb94c10f (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-10T12:22:39Z (GMT) No. of bitstreams: 1 samuelbelinidefilippo.pdf: 2753590 bytes, checksum: 260a8f328d5b69585883e19fcb94c10f (MD5) / Made available in DSpace on 2017-03-10T12:22:39Z (GMT). No. of bitstreams: 1 samuelbelinidefilippo.pdf: 2753590 bytes, checksum: 260a8f328d5b69585883e19fcb94c10f (MD5) Previous issue date: 2008-08-29 / A análise de regressão de dados encontra aplicação em diversas áreas e o modelo obtido pode ser em seguida usado intensamente dentro de outro processo de otimização. Escolher o modelo que melhor se ajuste a um determinado banco de dados, contudo, ainda é um processo demorado, e muitas vezes heurístico. Neste trabalho foi desenvolvida uma ferramenta computacional de apoio a este processo de análise (escolha de modelos e a estimação dos parâmetros), baseado em um Algoritmo Genético aplicado aos modelos Least Mean Squares, Multi Layer Perceptron e k- Nearest Neighbors. A ferramenta é testada em diferentes bancos de dados, sendo um deles oriundo da área de desenho racional de fármacos baseado em estrutura, onde estão previstas aplicações futuras. / Regression analysis has application in several areas, and the models obtained can be used afterwards in optimization processes. Choosing the best model for a given databases, however, is still a time-consuming task, which is frequently done in a heuristic way. In this work we develop a computational tool to support the choice of models and the estimation of parameters, based on the application of a Genetic Algorithm to the three groups of models: Least Mean Squares ones, Multi Layer Perceptrons and k-Nearest Neighbors ones. The tool is tested in different databases, one of them originating from the area of structure-based rational drug design, where future applications are foreseen.

Orientadores: Christiano Lyra Filho, Celso Cavellucci / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T04:13:51Z (GMT). No. of bitstreams: 1 Assis_LauraSilvade_D.pdf: 3122445 bytes, checksum: 01644f90a086983b8729f81804874faa (MD5) Previous issue date: 2014 / Resumo: Grande parte das falhas em sistemas elétricos de potência ocorrem por consequência de falhas permanentes nas redes de distribuição. Agências reguladoras definem índices de confiabilidade para quantificar e avaliar a qualidade da distribuição de energia. A violação dos limites estabelecidos podem resultar em multas significativas para a distribuidora de energia. Um dos objetivos ao se realizar a instalação de chaves em redes de distribuição é criar a possibilidade de re-energizar a maior quantidade de clientes no menor tempo possível através da transferência de carga para sistemas que não tiveram seu fornecimento de energia interrompido. Esta tese estuda o problema de alocação de chaves (PAC) em sistemas radiais de distribuição de energia elétrica e propõe a instalação otimizada desses dispositivos em locais apropriados das redes, a fim de melhorar a confiabilidade do sistema pela redução do período que os consumidores ficam sem energia. Uma metodologia baseada nos conceitos de algoritmo memético juntamente com uma população estruturada é proposta neste trabalho para alocar chaves seccionadoras e de manobra, manuais e automáticas, com diferentes capacidades. A função objetivo utilizada busca minimizar o custo de alocação das chaves e o custo da energia não distribuída sob restrições de confiabilidade e fluxo de carga em todos os componentes da rede. É apresentado também um estudo multiobjetivo para o PAC, que procura alocar chaves minimizando simultaneamente os custos de instalação das chaves e da energia não distribuída e maximizando a confiabilidade da rede, sob restrições de fluxos. A abordagem proposta para resolver o PAC mono-objetivo também foi utilizada no PAC multiobjetivo, juntamente com o método do ?-restrito. A metodologia proposta tem o seu bom desempenho confirmado por diferentes estudos de casos com redes reais de grande porte localizadas no estado de São Paulo / Abstract: Most failures in electric power systems occur as a result of permanent faults in distribution networks. Regulatory agencies establish reliability standards indices for quantify and evaluate the quality of power distribution. The infringe of established limits can result in costly fines for the utility suppliers. One of the aim when perform the switches allocation in distribution networks is the possibility of re-energize the largest amount of customers in the shortest possible time by transferring load to other power systems which don¿t had their energy supply interrupted. This thesis studies the switch allocation problem (SAP) in radial systems of electrical power distribution and proposes an optimized installation of these devices in appropriate locations of network, in order to improve the reliability system by the reducing of the period that consumers remains without power. A methodology based on the concepts of memetic algorithm with a structured population is proposed in this thesis to allocate sectionalizing and tie switches of different capacities, with manual or automatic operation schemes. The objective function used seeks to minimize the switches allocation and the energy not supplied costs under constraints of reliability and load flow. A Multi-objective study for SAP is presented, to perform the switches allocation seeks minimize simultaneously the switches installation and energy not supplied costs and maximize the network reliability, under constraints of load flow. The proposed approach to solve the SAP monocriteria was also used in SAP multi-criteria along with the ?-constraint method. The proposed methodology has its good performance confirmed by several case studies with real large networks located in the state of São Paulo / Doutorado / Automação / Doutora em Engenharia Elétrica

Orientadores: Cid Carvalho de Souza, Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T06:06:38Z (GMT). No. of bitstreams: 1 Bogue_EduardoTheodoro_M.pdf: 1929433 bytes, checksum: 1c490811ba46f8482ede0d93da1163f8 (MD5) Previous issue date: 2014 / Resumo: Neste projeto, nós estudamos o Problema da Máxima Interseção de k-Subconjuntos (kMIS). Dado um inteiro k, um conjunto base U e uma coleção S de subconjuntos de U, o problema kMIS consiste em selecior k subconjuntos distintos S1, S2, ... , Sk em S cujo tamanho da interseção de |S1 ? S2 ? ... ? Sk| seja máxima. Trata-se de um problema NP-difícil e difícil de ser aproximado que ocorre em aplicações de áreas como biologia computacional e privacidade de dados. Até o nosso conhecimento, nenhum método exato foi proposto para resolver este problema. Neste trabalho, introduzimos cinco formulações de programação linear inteira para o problema, sendo três baseadas no método de Branch-and-Bound e duas no método de Branch-and-Cut. Além disso, uma heurística gulosa e uma meta-heurística GRASP foram desenvolvidas com o intuito de gerar bons limitantes inferiores. A heurística GRASP desenvolvida foi capaz de encontrar soluções muito próximas da solução ótima. Ademais, introduzimos um método muito eficiente de pré-processamento para reduzir o tamanho da entrada. Experimentos computacionais foram realizados de forma a analisar o desempenho dos modelos de programação linear inteira em questão, demonstrando que os modelos baseados no método de Branch-and-Cut obtiveram melhores resultados / Abstract: In this project, we study the Maximum k-Subset Intersection problem (kMIS). Given an integer k, a ground set U and a collection S of subsets of U, the kMIS problem is to select k distinct subsets S1, S2, ... , Sk in S whose intersection size |S1 ? S2 ? ... ? Sk| is maximum. The kMIS problem is NP-hard and hard to approximate and occurs in areas of applications such as computational biology and data privacy. To the best of our knowledge, no exact method was proposed to solve this problem. In this work, we introduce five integer linear programming formulations for the problem, three using a simple Branch-and-Bound method and two using a Branch-and-Cut method. We also present a greedy heuristic and a metaheuristic GRASP developed in order to generate good lower bounds. The heuristic GRASP developed was able to find solutions very close to the optimal ones. Furthermore, we introduce a very efficient preprocessing procedure to reduce the size of the input. Computational experiments were performed in order to analyze the performance of the integer linear programming models in question, showing that the Branch-and-Cut models performed better / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:59:09Z (GMT). No. of bitstreams: 1 Reis_MarcioFelix_M.pdf: 1988657 bytes, checksum: 6ee5ea6ba406aea3ccb7e3332e679eab (MD5) Previous issue date: 2014 / Resumo: Neste trabalho estudamos o problema da árvore geradora com muitas folhas (PAGMF). Este problema pode ser usado como abstração para diversos problemas práticos e sabe-se que é NP-difícil. Estudamos, implementamos e executamos testes para algoritmos aproximados e exatos para o PAGMF e para um caso particular que considera apenas grafos cúbicos. O principal objetivo do trabalho foi verificar o comportamento prático dos algoritmos estudados. Para as instâncias testadas, em geral, o algoritmo guloso apresentou melhores resultados para o PAGMF e o algoritmo 2-aproximado teve os melhores resultados para os grafos cúbicos / Abstract: In this work we study the maximum leaf spanning tree problem (MLSTP). This problem can be used as an abstraction for many practical problems and is known to be NP-hard. We studied, implemented and executed tests for approximate and exact algorithms for the MLSTP and for a particular case that considers only cubic graphs. The main objective of this study was to investigate the practical behavior of the algorithms studied. For the tested instances, in general, the greedy algorithm showed better results for the MLSTP and the 2-approximate algorithm had the best results for cubic graphs / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Pedro Jussieu de Rezende, Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:56:08Z (GMT). No. of bitstreams: 1 Sasaki_AndersonToshiyuki_M.pdf: 1449279 bytes, checksum: 851c64c64afd4605cbfb4946ed5f97a4 (MD5) Previous issue date: 2014 / Resumo: No problema de cobertura mínima por conjuntos (MSC - Minimum Set Cover), são dados um conjunto L de objetos e uma coleção R de conjuntos e deseja-se encontrar uma sub-coleção S de R que seja uma cobertura de L de custo mínimo, ou seja, L está contido na união de todo os conjuntos R de S com a soma dos custos dos conjuntos R de S sendo mínima. Entre as variantes desse problema, existem aquelas advindas de configurações geométricas, em que tanto os elementos de L quanto os conjuntos contidos em R são objetos geométricos. Como tais problemas são, em geral, NP-difíceis, se P ? NP, não é possível encontrar algoritmos exatos de tempo polinomial para os mesmos. Assim, torna-se interessante a busca por algoritmos aproximados eficientes para obtenção de soluções com garantia de qualidade. Nesta dissertação, estudamos diferentes versões do problema de cobertura mínima por discos (MDC ¿ Minimum Disk Cover), em que o conjunto R é um conjunto de discos, e o objetivo é projetar algoritmos aproximados. Tais versões do problema estão relacionadas com a solução de problemas práticos, como o posicionamento de estações-base em projeto de redes sem fio ou de dispositivos em redes de sensores. Para o caso em que o conjunto de objetos geométricos L é constituído de um único segmento de reta no plano, apresentamos um FPTAS. Para outra versão mais geral, na qual o conjunto de objetos geométricos é dado por um sistema de inequações polinomiais algébricas, propomos um algoritmo aproximado, o qual demonstramos ser um PTAS / Abstract: The Minimum Set Cover problem (MSC) can be described as: given a set L of elements and a collection of sets R, find a subcollection S of R that is a minimum-cost covering for L, i.e., L is contained in the union of the sets R in S, and the sum of the costs of the sets R in S is minimum. Among the variants of this problem, there are those that arise from a geometric configuration in which both the elements of L and the sets contained in R are geometric objects. As such problems are, in general, NP-hard, if P ? NP, it is impossible to find polynomial-time exact algorithms for them. Thus, the use of efficient approximation algorithms to find high quality solutions becomes a good approach. In this dissertation, we study different versions of the Minimum Disk Cover problem (MDC), in which the sets in R are disks, and we seek to develop approximation algorithms. These versions are related to practical problems, such as base station positioning problem for wireless network design and placement of devices in a sensor network. For the case in which the set of geometric objects to be covered is given by a single line segment, we present an FPTAS. For a more general case, where the set of geometric objects is given by a system of algebraic polynomial inequalities, we propose an approximation algorithm which we prove to be a PTAS / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Flávio Keidi Miyazawa, Maxim Sviridenko / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T09:17:37Z (GMT). No. of bitstreams: 1 Pedrosa_LehiltonLelisChaves_D.pdf: 3649302 bytes, checksum: 9f37cca5fca5af1697c2099c8e0f2798 (MD5) Previous issue date: 2014 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic document / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T16:57:43Z (GMT). No. of bitstreams: 1 Tozoni_DaviColli_M.pdf: 4212278 bytes, checksum: afb91e202a72e28729ff14334901884f (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação, apresentamos nossa pesquisa sobre o Problema da Galeria de Arte (AGP), um dos problemas mais estudados em Geometria Computacional. O AGP, que é um problema NP-difícil, consiste em encontrar o número mínimo de guardas suficiente para garantir a cobertura visual de uma galeria de arte representada por um polígono. Na versão do problema tratada neste trabalho, usualmente chamada de Problema da Galeria de Arte com Guardas-Ponto, os guardas podem ser posicionados em qualquer lugar do polígono e o objetivo é cobrir toda a região, que pode ou não conter buracos. Nós estudamos como aplicar conceitos e algoritmos de Geometria Computacional, bem como Técnicas de Programação Inteira, com a finalidade de resolver o AGP de forma exata. Este trabalho culminou na criação de um novo algoritmo para o AGP, cuja ideia é gerar, de forma iterativa, limitantes superiores e inferiores para o problema através da resolução de versões discretizadas do AGP, que são reduzidas a instâncias do Problema de Cobertura de Conjuntos. O algoritmo foi implementado e testado em mais de 2800 instâncias, de diferentes tamanhos e classes. A técnica foi capaz de resolver, em minutos, mais de 90% de todas as instâncias consideradas, incluindo polígonos com milhares de vértices, e ampliou em muito o conjunto de casos para os quais são conhecidas soluções exatas. Até onde sabemos, apesar do extensivo estudo do AGP nas últimas quatro décadas, nenhum outro algoritmo demonstrou a capacidade de resolver o AGP de forma tão eficaz como a técnica aqui descrita / Abstract: In this dissertation, we present our research on the Art Gallery Problem (AGP), one of the most investigated problems in Computational Geometry. The AGP, which is a known NP-hard problem, consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented as a polygon. In the version of the problem treated in this work, usually called Art Gallery Problem with Point Guards, the guards can be placed anywhere in the polygon and the objective is to cover the whole region, which may or not have holes. We studied how to apply Computational Geometry concepts and algorithms as well as Integer Programming techniques in order to solve the AGP to optimality. This work culminated in the creation of a new algorithm for the AGP, whose idea is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. The algorithm was implemented and tested on more than 2800 instances of different sizes and classes of polygons. The technique was able to solve in minutes more than 90% of all instances considered, including polygons with thousands of vertices, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively as the one described here / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T17:56:16Z (GMT). No. of bitstreams: 1 Assis_IgorRibeirode_M.pdf: 5116531 bytes, checksum: 151d5c4293cb869d16ddf4c6f7bb8992 (MD5) Previous issue date: 2013 / Resumo: Aplicações desse problema incluem: máquina de controle numérico, inspeção automática e roteamento. Esta dissertação estuda soluções para o problema do recorte. Propomos um modelo de programação linear inteira e a partir deste desenvolvemos um algoritmo exato. Descrevemos um algoritmo 3.75 aproximado da literatura e propomos algumas melhorias heurísticas para o mesmo. Abandonando as garantias teóricas, projetamos duas heurísticas: a primeira utiliza uma ideia gulosa bastante simples complementada por técnicas da meta-heurística GRASP, especificamente aleatorização e busca local; e a segunda resolve um problema de cobertura mais simples e cuja sua solução pode ser adaptada para o problema original. Por fim propomos uma série de vizinhanças executadas em uma fase de busca local, que dada uma solução, faz mudanças locais que reduzem o custo do tour. As implementações dos algoritmos descritos são analisadas experimentalmente utilizando um benchmark de instâncias que construímos e deixamos público para comparações futuras / Abstract: In the orthogonal milling with turn costs problem is given an orthogonal polygon P that may contain holes. Our goal is to find a closed polygonal curve made of horizontal and vertical segments which when traversed by a unit square, the covered area is exactly P. Turn costs are assigned to direction changes and the objective is to minimize the sum of turn costs. This problem arises in many applications including: numerically controlled (NC) machining, automatic inspection and routing. This dissertation studies solutions for the milling problem. We propose an integer linear programming model and from which an exact algorithm is proposed. A 3.75- approximate algorithm from the literature is described for which heuristic improvements are proposed. Lifting the theoretical guarantees we project two heuristics: the first is based in a simple greedy idea supplemented with techniques of the GRASP meta-heuristic, specifically, randomization and local search; the latter solves a simpler covering problem whose its solution is adapted for the original problem. Finally, we propose a series of neighborhoods run in a local search step where, local changes are made to the solution such that the tour cost is reduced. All described algorithms are implemented and evaluated experimentally using a benchmark of instances that we built and made public for future comparisons / Mestrado / Ciência da Computação / Mestre em Ciência da Computação