Navegando por Autor "Carvalho, Marco Antonio Moreira de"
Agora exibindo 1 - 20 de 23
Resultados por página
Opções de Ordenação
Item Uma abordagem evolucionária para o problema escalonamento de tarefas em máquinas idênticas paralelas com limitações de ferramentas.(2018) Soares, Leonardo Cabral da Rocha; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Toffolo, Túlio Ângelo Machado; Arroyo, José Elias ClaudioO Problema de Escalonamento de Tarefas em Máquinas Flexíveis Paralelas Idênticas com Restrições de Ferramentas, consiste em alocar tarefas a um conjunto de máquinas flexíveis paralelas, com o objetivo de minimizar o tempo máximo de processamento das tarefas pelas máquinas. Especificamente, as tarefas possuem tempo de processamento igual em qualquer máquina, porém, possuem tempo de preparo prévio que depende de todas as tarefas anteriores sequenciadas na mesma máquina, devido a configurações de ferramentas nas máquinas flexíveis. Neste trabalho, este problema NP-Difícil é abordado utilizando-se a metaheurística paralela Algoritmo Genético de Chaves Aleatórias Viciadas hibridizada com procedimentos de busca local organizados em uma Descida em Vizinhança Variável. São apresentados resultados inéditos para um conjunto de 2880 instâncias da literatura, incluindo resultados ótimos para 12,31% entre as menores instâncias. O método proposto é comparado ao atual estado da arte e obtém 91,81% das melhores soluções. Novas melhores soluções são apresentadas para 52,75% do total de instâncias. Adicionalmente, o método proposto apresenta tempo de execução 92,69% menor, dominando assim o atual estado da arte.Item Abordagem exata e heurísticas para o problema de planejamento de ordens de manutenção de longo prazo : um estudo de caso industrial de larga escala.(2018) Aquino, Roberto Dias; Souza, Marcone Jamilson Freitas; Chagas, Jonatas Batista Costa das; Souza, Marcone Jamilson Freitas; Chagas, Jonatas Batista Costa das; Carvalho, Marco Antonio Moreira de; Souza, Sérgio Ricardo deEste trabalho propõe uma modelagem de programação linear inteira mista e algoritmos meta-heurísticos para um problema real de planejamento de manutenção de longo prazo para uma planta de beneficiamento de minério de ferro no Brasil. Este é um problema complexo de programação de ordens de manutenção preventiva, para o qual é necessário atribuir ordens de manutenção preventiva para as equipes de trabalho disponíveis em um horizonte de 52 semanas. Foi desenvolvido um modelo de programação inteira mista e os resultados foram utilizados como um benchmark. Como o modelo não foi capaz de resolver a instância real, foram propostos algoritmos meta-heurísticos para resolvê-la. Esses algoritmos foram baseados nos métodos Simulated Annealing, Variable Neighborhood Search, Multi-Start, Biased Random-Key Genetic Algorithm e algoritmos meméticos. Os algoritmos heurísticos desenvolvidos foram capazes de resolver a instância real, assim como melhorar a maioria dos resultados das instâncias de dimensões menores, levando a novos benchmarks.Item Adaptive large neighborhood search applied to the design of electronic circuits.(2018) Santos, Vinícius Gandra Martins; Carvalho, Marco Antonio Moreira deIn this paper, a new algorithm is proposed for solving the Gate Matrix Layout Problem (GMLP). This combinatorial problem is -Hard and aims to determine the physical layout of the components of an electronic circuit in order to minimize the number of tracks required to connect its nets. By reducing the circuit area, it is possible to reduce manufacturing costs and also improve circuit performance. Computer-aided design of such layouts has direct practical applications in engineering and industry, including information technology, industrial processes automation, and consumer goods production. We propose new local search procedures combined in an Adaptive Large Neighborhood Search (ALNS) metaheuristic to generate solutions for the GMLP. To assess the quality of the proposed method, we have considered 1455 real-world and artificial instances from the literature and compared the proposed ALNS with the state-of-the-art method for the GMLP solution. The ALNS performance is robust as it matches 89% of known optimal solutions and also improves the best known results in some instances.Item Algoritmos heurísticos para o problema de roteamento de unidades móveis de mamografia.(2021) Rosa, Otávio Augusto Souza; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Coelho, Igor Machado; Carvalho, Marco Antonio Moreira deEste trabalho introduz o Problema de Roteamento de Unidades Móveis de Mamografia (MMURP). Este problema consiste em roteirizar um conjunto de Unidades Móveis de Mamografia (MMU) para atender a demanda de localidades desprovidas de mamógrafos fixos ou com número insuficiente deles. O objetivo é maximizar a demanda atendida e minimizar a distância total percorrida pelas MMUs. Para tratar o problema, propomos os algoritmos Smart IGS-VND e Smart IGS-RVND, ambos baseados na metaheurística Iterated Greedy Search. Nestes algoritmos, uma solução inicial é gerada por meio de um procedimento de três passos. Para refinar uma solução, usamos os procedimentos Randomized Variable Neighborhood Descent (RVND) e Variable Neighborhood Descent (VND). Para não ficar preso em ótimos locais e explorar diferentes regiões do espaço de soluções do problema, aplicamos um procedimento para destruir a solução atual e outro para construí-la de forma gulosa. Para testar os algoritmos propostos, usamos instâncias com 579 localidades, dois depósitos, até 56 MMUs e 180 km entre dois locais no máximo. Realizamos os testes considerando três cenários diferentes. Esses cenários diferem entre si pelo número de localidades candidatas a serem atendidas, o número de MMUs disponíveis em cada depósito e a capacidade dessas MMUs. Os resultados mostraram que os dois algoritmos encontraram soluções que atendem integralmente a demanda da região estudada. O Smart IGS-VND obteve um melhor desempenho para encontrar um valor alvo de demanda previamente definido. No entanto, quando foram comparadas a distância total percorrida pelas MMUs com a cobertura de exames, o Smart IGS-RVND mostrou ser capaz de encontrar soluções de melhor qualidade, reduzindo a distância total percorrida pelos veículos. No último cenário, apresentamos um plano de serviço mensal para uma MMU, variando de um a doze meses.Item An integer programming approach to the multimode resource-constrained multiproject scheduling problem.(2015) Toffolo, Túlio Ângelo Machado; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Araujo, Janniele Aparecida SoaresThe project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resourceconstrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.Item An integer programming approach to the multimode resource-constrained multiproject scheduling problem.(2016) Toffolo, Túlio Ângelo Machado; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Soares, Janniele AparecidaThe project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resourceconstrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.Item Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints.(2020) Soares, Leonardo Cabral da Rocha; Carvalho, Marco Antonio Moreira deWe address the problem of scheduling a set of n jobs on m parallel machines, with the objective of minimizing the makespan in a flexible manufacturing system. In this context, each job takes the same processing time in any machine. However, jobs have different tooling requirements, implying that setup times depend on all jobs previously scheduled on the same machine, owing to tool configurations. In this study, this N P-hard problem is addressed using a parallel biased random-key genetic algorithm hybridized with local search procedures organized using variable neighborhood descent. The proposed genetic algorithm is compared with the state-of-the-art methods considering 2,880 benchmark instances from the literature reddivided into two sets. For the set of small instances, the proposed method is compared with a mathematical model and better or equal results for 99.86% of instances are presented. For the set of large instances, the proposed method is compared to a metaheuristic and new best solutions are presented for 93.89% of the instances. In addition, the proposed method is 96.50% faster than the compared metaheuristic, thus comprehensively outperforming the current state-of-the-art methods.Item Busca adaptativa em grandes vizinhanças aplicada à minimização da largura de corte em grafos.(2018) Santos, Vinícius Gandra Martins; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Lima, Joubert de CastroO problema de Minimização da Largura de Corte em Grafos (ou CMP, do inglês Cutwidth Minimization Problem) consiste em determinar um leiaute linear para um grafo de forma a minimizar a quantidade máxima de arestas que cruzam cada par de vértices consecutivos. Esse problema pode ser encontrado no projeto de circuitos integrados de larga escala, no desenho de diagramas de grafos e no projeto de compiladores, entre outros. O CMP é um problema NP-Difícil e se apresenta como um desafio para métodos exatos e heurísticas. Neste trabalho, é reportada pela primeira vez na literatura a aplicação do método metaheurístico Busca Adaptativa em Grandes Vizinhanças (Adaptive Large Neighborhood Search) para solução do CMP. Os experimentos computacionais envolvem 11.786 instâncias de quatro conjuntos da literatura e os resultados encontrados são comparados com o atual estado da arte. O método proposto se mostra competitivo, sendo capaz de igualar a maioria dos resultados comprovadamente ótimos e melhores resultados conhecidos, além de melhorar alguns resultados que não foram provados ótimos e encontrar pela primeira vez limitantes superiores para instâncias não resolvidas.Item Descent search approaches applied to the minimization of open stacks.(2017) Lima, Júnior Rhis; Carvalho, Marco Antonio Moreira deIn this paper, new algorithms are proposed for solving the minimization of open stacks, an industrial cutting pattern sequencing problem. In the considered context, the objective is to minimize the use of intermediate storage, as well as the unnecessary handling of manufactured products. We introduce a new local search method, specifically tailored for this NP-hard problem, which has wide practical applications. In order to further explore the solution space, we use this new local search as a component in two descent search methods associated with grouping strategies: variable neighborhood descent and steepest descent. Computational experiments were conducted involving 595 benchmark instances from five different sets through which the contributions of the proposed methods were compared with those of the state-of-the-art methods. The results demonstrate that the proposed algorithms are competitive and robust, as high quality solutions were consistently generated in a reasonable running time.Item Estratégias de otimização contínua Caixa-Cinza para problemas de larga escala.(2021) Costa, Rodolfo Ayala Lopes; Freitas, Alan Robert Resende de; Freitas, Alan Robert Resende de; Carvalho, Marco Antonio Moreira de; Toffolo, Túlio Ângelo Machado; Arroyo, José Elias Claudio; Guimarães, Frederico GadelhaA otimização caixa-cinza tem emergido como uma alternativa promissora aos tradicionais métodos de otimização caixa-preta, uma vez que esses métodos tradicionais deterioram seu desempenho ao lidar com problemas de larga escala. Embora trabalhos relacionados à otimização caixa-cinza tenham sido introduzidos na literatura nos últimos anos, há uma carência de estudos sobre essa abordagem no contexto de otimização contínua. Os problemas de otimização contínua representam uma importante subclasse de problemas práticos de otimização. Em particular, estudos sobre otimização contínua de problemas de larga escala vem recebendo especial atenção na última década. Nesse contexto, este trabalho se propõe a estudar e desenvolver diferentes abordagens caixa-cinza para lidar com essa subclasse de problemas. Para isso, definições matemáticas de separabilidade de problemas de otimização que são a base teórica para implementação das abordagens caixa-cinza são apresentadas e discutidas. Baseados nessas definições, diferentes algoritmos caixa-cinza foram propostos neste estudo. Um estudo experimental utilizando um conjunto de problemas de otimização contínua de larga escala foi proposto para investigar o desempenho das abordagens introduzidas. Os resultados demonstram um desempenho promissor das abordagens caixa-cinza em comparação com as versões caixa-preta. Em resumo, esses resultados demonstram a capacidade das estratégias caixa-cinza de melhorar as soluções encontradas e economizar tempo de processamento, explorando a estrutura do problema e avaliações parciais.Item A general-purpose distributed computing Java middleware.(2019) Almeida, André Luís Barroso de; Cimino, Leonardo de Souza; Resende, José Estevão Eugênio de; Silva, Lucas Henrique Moreira; Rocha, Samuel Queiroz Souza; Gregorio, Guilherme Aparecido; Paiva, Gustavo Silva; Silva, Saul Emanuel Delabrida; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Aquino, André Luiz Lins de; Lima, Joubert de CastroThe middleware solutions for General‐Purpose Distributed Computing (GPDC) have distinct requirements, such as task scheduling, processing/storage fault tolerance, code portability for parallel or distributed environments, simple deployment (including over grid or multi‐cluster environments), collaborative development, low code refactoring, native support for distributed data structures, asynchronous task execution, and support for distributed global variables. These solutions do not integrate these requirements into a single deployment with a unique API exposing most of these requirements to users. The consequence is the utilization of several solutions with their particularities, thus requiring different user skills. Besides that, the users have to solve the integration and all heterogeneity issues. To reduce this integration gap, in this paper, we present Java Cá&Lá (JCL), a distributed‐shared‐memory and task‐oriented lightweight middleware for the Java community that separates business logic from distribution issues during the development process and incorporates several requirements that were presented separately in the GPDC middleware literature over the last few decades. JCL allows building distributed or parallel applications with only a few portable API calls, thus reducing the integration problems. Finally, it also runs on different platforms, including small single‐board computers. This work compares and contrasts JCL with other Java middleware systems and reports experimental evaluations of JCL applications in several distinct scenarios.Item Heuristic methods to consecutive block minimization.(2020) Soares, Leonardo Cabral da Rocha; Reinsma, Jordi Alves; Nascimento, Luis H. L.; Carvalho, Marco Antonio Moreira deMany combinatorial problems addressed in the literature are modeled using binary matrices. It is often of interest to verify whether these matrices hold the consecutive ones property (C1P), which implies that there exists a permutation of the columns of the matrix such that all nonzero elements can be placed contiguously, forming a unique 1-block in every row. The minimization of the number of 1-blocks is approached by a well-known problem in the literature called consecutive block minimization (CBM), an N P-hard problem. In this study, we propose a graph representation, a heuristic based on a classical algorithm in graph theory, the implementation of a metaheuristic for solving the CBM and the application of an exact method based on a reduction of the CBM to a particular version of the well-known traveling salesman problem. Computational experiments demonstrate that the proposed metaheuristic implementation is competitive, as it matches or improves the best known solution values for all benchmark instances available in the literature, except for a single instance. The proposed exact method reports, for the first time, optimal solutions for these benchmark instances. Consequently, the proposed methods outperform previous methods and become the new state-of-the-art for solving the CBM.Item Improved heuristic algorithms for the job sequencing and tool switching problem.(2017) Paiva, Gustavo Silva; Carvalho, Marco Antonio Moreira deIn flexible manufacturing systems, a single machine can be configured with different tools for process- ing different jobs, each requiring a specific set of tools. There is a limit to the maximum number of tools that can be loaded simultaneously in the machine; between the processing of two different jobs, it may be necessary to switch these tools, causing interruptions in the production line. The Job Sequenc- ing and Tool Switching Problem (SSP) aims to determine a job sequence and the tool-loading order for a flexible machine, in order to minimize the number of tool switches. These two tasks can be separated into Sequencing , an N P -hard problem, and Tooling , which is a Pproblem if the job sequence is given. This paper proposes a methodology that uses graph representations, heuristic methods, and local search methods to solve the sequencing problem. These contributions are combined in an Iterated Local Search scheme, which is then combined with a classical tooling method, in order to solve the SSP. Comprehen- sive computational experiments show that the resulting method is competitive and can establish new best solutions for literature instances, while outperforming the current state-of-the-art method.Item Métodos simplificados para o problema de minimização de pilhas abertas.(2011) Carvalho, Marco Antonio Moreira de; Soma, Nei YoshihiroEste trabalho apresenta dois métodos para a solução do Problema de Minimização de Pilhas Abertas (ou MOSP, de Minimization of Open Stacks Problem), um problema de sequenciamento de padrões oriundo do contexto de produção de peças, cuja aplicação industrial é direta. O primeiro é relativo a uma heurística baseada em teoria de grafos e critérios gulosos, enquanto o segundo é relativo a um método de programação dinâmica. Os resultados do experimento realizado comprovam a eficácia das simplificações propostas quando comparadas com os métodos da literatura.Item Um modelo reforçado e heurísticas relax-and-fix e VNS para o Problema da Árvore Geradora Mínima Capacitada em Níveis.(2018) Campos, Jean Carlos Tiburcio; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Souza, Maurício Cardoso deEste trabalho tem seu foco no Problema da Árvore Geradora Mínima Capacitada em Níveis (PAGMCN). Ele consiste em encontrar uma árvore geradora de custo mínimo, tal que o fluxo a ser transferido de um nó central aos demais nós seja limitado pela capacidade das arestas. Para resolvê-lo, propomos neste trabalho uma formulação reforçada de programação matemática e um algoritmo híbrido, combinando as heurísticas relax-and-fix e Variable Neighborhood Search (VNS), juntamente com um modelo matemático. A formulação matemática proposta, chamada \Modelo Baseado na Capacidade das Facilidades 2" (MBC2), consiste em adicionar dois novos conjuntos de restrições à formulação considerada a mais e ciente da literatura. A motivação para a utilização do modelo MBC2 está em ele fornecer um limite inferior de qualidade, esperando assim convergir mais rapidamente à solução ótima. Experimentos computacionais mostraram que a formulação reforçada proposta, quando comparada ao modelo da literatura, melhora a qualidade da relaxação linear, fornecendo um limite inferior melhor e justificando a sua utilização. Para o desenvolvimento do algoritmo híbrido, foi utilizado o modelo MBC2 proposto neste trabalho, em razão de ele ser capaz de proporcionar um limite inferior de qualidade. Essa formulação reforçada é usada com a heurística relax-and-fix para fornecer uma solução inicial para o VNS. Resultados mostram que o VNS melhora a solução inicial e gera soluções com gaps relativamente pequenos nas instâncias usadas para teste.Item New models for the mirrored traveling tournament problem.(2012) Carvalho, Marco Antonio Moreira de; Lorena, Luiz Antonio Nogueira; https://doi.org/10.1016/j.cie.2012.08.002The Mirrored Traveling Tournament Problem (mTTP) is a challenging combinatorial optimization problem which consists in generating a timetable for sports tournaments with two half series, what is equivalent to a double round-robin timetable problem. The distance traveled by the teams should be minimized in the final timetable, and a new objective is to minimize the longest distance traveled, named MinMaxTTP. It is proposed an integer programming formulation to the mTTP and two models with dynamic constraints to its solution. Both models are based on the detection of independent sets on conflict graphs, whose use has not been reported in the literature about the problem. Real data benchmarks from a baseball tournament are used in the experiments carried out.Item Otimização de processos produtivos em sistemas de manufatura flexível.(2023) Soares, Leonardo Cabral da Rocha; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Subramanian, Anand; Chaves, Antônio Augusto; Souza, Marcone Jamilson Freitas; Toffolo, Túlio Ângelo MachadoA complexidade geral do gerenciamento de produção de um sistema de manufatura flexível tem inspirado pesquisadores ao estudo de diversos problemas computacionais advindos de tais sistemas desde a década de 1980. Estudos recentes demonstram que o número de publicações em temas correlatos cresce constantemente desde o ano de 1988, reforçando a relevância e a atualidade do tema. Diante disto, neste trabalho são abordados alguns dos principais problemas advindos deste cenário. Todos os problemas abordados possuem publicações recentes em prestigiados veículos internacionais. Para cada problema abordado apresenta-se definição formal, revisão bibliográfica, método computacional para solução e análise comparativa dos resultados obtidos em relação ao atual estado da arte. Entre os métodos computacionais propostos há predominância da meta-heurística busca local iterada e do algoritmo genético de chaves aleatórias viciadas, entretanto, cada implementação foi cuidadosamente elaborada considerando-se as características individuais dos problemas abordados. Em síntese, inicialmente apresenta-se dois problemas fundamentais relacionados ao escalonamento de tarefas em máquinas flexíveis, o problema de minimização de trocas de ferramentas e o problema do escalonamento de tarefas em máquinas paralelas idênticas com restrições de ferramentas, visando fornecer um referencial teórico para embasar e direcionar o estudo dos demais problemas. Em seguida, são abordados o problema de minimização de blocos de uns consecutivos, o problema de minimização de trocas de ferramentas uniforme, o problema de sequenciamento de tarefas em máquinas paralelas com limitação de recursos e o problema de sequenciamento de tarefas em máquinas paralelas não-idênticas com restrições de ferramentas. Para cada problema abordado realizou-se uma ampla campanha experimental, analisando-se as instâncias disponíveis na literatura e os resultados gerados pelos métodos propostos e pelos métodos que compõem o estado da arte. Análises estatísticas foram realizadas e confirmaram a alta qualidade das soluções reportadas pelos métodos propostos.Item A PageRank-based heuristic for the minimization of open stacks problem.(2018) Frinhani, Rafael de Magalhães Dias; Carvalho, Marco Antonio Moreira de; Soma, Nei YoshihiroThe minimization of open stacks problem (MOSP) aims to determine the ideal production sequence to optimize the occupation of physical space in manufacturing settings. Most of current methods for solving the MOSP were not designed to work with large instances, precluding their use in specific cases of similar modeling problems. We therefore propose a PageRank-based heuristic to solve large instances modeled in graphs. In computational experiments, both data from the literature and new datasets up to 25 times fold larger in input size than current datasets, totaling 1330 instances, were analyzed to compare the proposed heuristic with state-of-the-art methods. The results showed the competitiveness of the proposed heuristic in terms of quality, as it found optimal solutions in several cases, and in terms of shorter run times compared with the fastest available method. Furthermore, based on specific graph densities, we found that the difference in the value of solutions between methods was small, thus justifying the use of the fastest method. The proposed heuristic is scalable and is more affected by graph density than by size.Item Problema de roteamento de mamógrafos móveis : uma abordagem bi-objetiva.(2023) Araujo, Thiago Giachetto de; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Penna, Puca Huachi Vaz; Souza, Marcone Jamilson Freitas; Coelho, Igor Machado; Carvalho, Marco Antonio Moreira deEsta dissertação trabalha com o Problema de Roteamento de Unidades Móveis de Mamografia (MMURP). O problema é uma variante do Problema de Rotea- mento de Veículos Aberto Multi-depósito. Neste problema, existe uma quantidade fixa de depósitos, cada um com uma quantidade limitada de Unidades Móveis de Mamografia (MMUs). Cada MMU tem sua capacidade de realização de exames conhecida e um conjunto de cidades candidatas com uma demanda conhecida por exames de mamografia. O objetivo é definir a ordem de visitação das cidades can- didatas para cada MMU, buscando maximizar a demanda atendida e minimizar a distância total percorrida. Ou seja, o MMURP é tratado como um problema de otimização bi-objetivo. Uma formulação de programação matemátia é pro- posta, o método ε-restrito é implementado e dois algoritmos heurísticos baseados no Non-dominated Sorting Genetic Algorithm II (NSGA-II) são desenvolvidos. Os algoritmos heurísticos se diferenciam pela utilização de busca local como um dos operadores de mutação, um possui e o outro não. O método exato e as duas versões do algoritmo heurístico foram implementados e usados para resolver o MMURP para diversos estados do Brasil. Instâncias baseadas em dados reais foram geradas e usadas para avaliar os métodos implementados. Os resultados computacionais mos- traram que ao considerar o hipervolume, as soluções encontradas pelo método exato são superiores. Porém, ao considerar o min-max da taxa de cobertura, o algoritmo heurístico com a busca local é superior.Item Propostas para solução do problema de movimentação de tripper.(2018) Caldas, Felipe Novaes; Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Carvalho, Marco Antonio Moreira de; Camargo, Ricardo Saraiva deO tripper é um equipamento frequentemente encontrado em uma planta de beneficiamento mineral. Sua função é distribuir o minério proveniente de uma correia transportadora sobre um silo de estocagem. A movimentação de tripper é um problema de sequenciamento definido pela determinação do posicionamento do equipamento sobre um silo ao longo do tempo. A escassez de referências na literatura científica que descrevam detalhadamente o tema em questão releva a importância deste trabalho em propor soluções a um problema que, apesar de receber pouca atenção do meio acadêmico, possui grande importância em muitas instalações de tratamento de minério ao redor do mundo. O primeiro passo é propor a modelagem do sistema silo-tripper na forma de um programa linear inteiro misto, de modo que seja possível determinar uma trajetória ótima de movimentação para o equipamento. Dois paradigmas foram utilizados para obter soluções exatas para este modelo: programação linear inteira mista e programação dinâmica. Embora tenham sido efetivas em solucionar instâncias pequenas, estas duas abordagens se mostraram ineficientes ao lidar com instâncias de dimensões mais elevadas, já que o tempo necessário para se alcançar a solução exata é muito alto, inviabilizando-se aplicações reais em silos com muitos compartimentos. Buscando-se alcançar soluções relativamente boas em relação ao ótimo, mas levando muito menos tempo, as meta-heurísticas GRASP e Simulated Annealing (SA) foram adaptadas como alternativa aos métodos exatos, representando esses algoritmos a segunda contribuição deste trabalho. O desempenho do GRASP se mostrou muito superior aos resultados obtidos pelo SA, tanto em relação ao tempo despendido quanto à assertividade em atingir soluções exatas. Os resultados importantes alcançados pela programação dinâmica e pelo GRASP os tornam fortes candidatos à implantação em aplicações reais, em situações que tanto precisão quanto tempo de resposta sejam pré-requisitos necessários.