Orientador: Cid Carvalho de SouzaDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: 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 futurasAbstract: 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 comparisonsMestradoCiência da ComputaçãoMestre em Ciência da Computação