Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The PCE (Cutting Stock Problem) is to cut a set of objects available in stock to produce a quantity of items with specific sizes in order to optimize the raw material. Such problems have numerous industrial applications and has been widely studied in literature. The PCE's are classified as combinatorial optimization problems, because depending on the amount of requested items can be combined in numerous ways within an object forming an arrangement of cut. The number of possible combinations is, in practice, very high, requiring well-developed techniques are developed to determine an optimum arrangement. In defining the arrangements of cut is needed to graph the components of the problem and in this case, the tools used in the implementation must have the ability to manipulate geometric. In this paper, the combinatorial problem was approached from the GRASP heuristic technique and as a tool of manipulation was employed geometric applications deployed in an environment of Computer Aided Design (CAD). Furthermore, we proposed an integration of arrays of cutting systems with computer-aided manufacturing (CAM). The analysis of performance of the developed algorithm considers data provided by a furniture industry in the region of Santa Maria. The results obtained by the algorithm were compared to results generated by specialized software, consisting that the proposed method presents a similar performance, which demonstrates the feasibility of using CAD tools to implement solutions in the industry of PCE small and medium businesses. / O Problema de Corte de Estoque Bidimensional (PCEB) consiste em cortar um conjunto de objetos disponíveis em estoque para produzir uma quantidade de itens com tamanhos específicos, de modo a otimizar a matéria prima. Tais problemas têm inúmeras aplicações industriais e tem sido amplamente estudados na literatura. Os PCEB são classificados como problemas de otimização combinatória, pois, dependendo da quantidade de itens solicitados, podem ser combinados de inúmeras maneiras dentro de um objeto formando um arranjo de corte. O número de combinações possíveis é, na prática, muito elevado, exigindo que técnicas bem elaboradas sejam desenvolvidas para determinar um arranjo ótimo. Na definição dos arranjos de corte é necessário representar graficamente os componentes do problema e neste caso, as ferramentas empregadas na implementação devem apresentar capacidade de manipulação geométrica. Neste trabalho, o problema combinatório foi abordado a partir da técnica heurística GRASP e como ferramenta de manipulação geométrica empregou-se aplicativos implementados em ambiente de Projetos Auxiliado por Computador (CAD). Além disso, foi proposta uma integração dos arranjos de cortes com sistemas de Manufatura Auxiliador por Computador (CAM). A analise de desempenho do algoritmo desenvolvido considera dados fornecidos por uma indústria moveleira da região de Santa Maria. Os resultados obtidos pelo algoritmo foram comparados aos resultados gerados por software especializado, constando-se que a metodologia proposta apresenta um desempenho semelhante, o que demonstra a viabilidade o uso das ferramentas CAD para implementação de soluções PCE em indústria de pequeno e médio porte.

Orientador: José Roberto Sanches Mantovani / Banca: Jozué Vieira Filho / Banca: Arturo Suman Bretas / Resumo: Neste trabalho é proposta uma técnica de otimização para alocar medidores dispersos de tensão em alimentadores radiais aéreos de distribuição baseada na metaheurística Greedy Randomized Adaptive Search Procedure (GRASP), com o objetivo de melhorar o desempenho de algoritmos de localização de faltas que utilizam informações esparsas de tensão e, simultaneamente, fazer o controle em tempo real do nível de tensão do alimentador operando sob diferentes cenários. No modelo de programação proposto para alocar os medidores considera-se a natureza estocástica das variáveis envolvidas no problema relacionado com o estudo de contingências em sistemas de energia elétrica, ou seja: carregamento dos transformadores da rede no instante de ocorrência da falta, impedância de falta, probabilidade de falhas e erros de medição dos medidores dispersos de tensão, probabilidade de ocorrer qualquer um dos tipos de faltas possíveis, entre outros. O modelo da função objetivo contempla a localização de faltas com boa precisão para qualquer algoritmo que utiliza medições esparsas de tensão e os menores valores de magnitudes de tensão no alimentador, operando em condições normais ou sob contingências. Apresentam-se resultados de testes com a metodologia proposta para dois alimentadores reais de distribuição de energia elétrica. O primeiro alimentador é de médio porte, tensão nominal de 13,8 kV e possui 134 barras. O segundo alimentador é de grande porte, tensão nominal de 11,4 kV e possui 3287 barras. / Abstract: This work proposes an optimization technique to allocate voltage measurement devices on radial overhead electric power distribution feeders based on Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, aiming at improving the performance of algorithms for fault location using sparse voltage information, while making the real time control of the feeder's operating voltage under different scenarios. The proposed programming model to allocate the devices considers the nature of the stochastic variables involved in the problem with the study of contingencies in electric power systems: loading of the network transformers at time of occurrence of failure, fault impedance, probability of failures and errors of measurement of dispersed voltage devices, likelihood that any of the possible types of faults occur, among others. The model's objective function includes the faults location procedure with good precision for any algorithm that uses sparse measurements of voltage and the lowest values of the magnitudes of voltage feeder, operating under normal conditions or contingencies. Test results with the proposed methodology applied to simulated data of two real life feeders are presented. The first feeder is medium size, rated voltage of 13.8 kV and has 134 bars. The second feeder is large, rated voltage of 11.4 kV and has 3287 bars. / Mestre

Made available in DSpace on 2014-06-11T19:22:32Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-05-20Bitstream added on 2014-06-13T18:08:28Z : No. of bitstreams: 1 oliveira_mbc_me_ilha.pdf: 670316 bytes, checksum: 7becc0c6eda68736bd3c8cea58146dea (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Neste trabalho a metaheurística GRASP é utilizada para resolver o problema de reconfiguração de sistemas de distribuição de energia elétrica modelado como um problema de programação não linear binário misto. O objetivo é minimizar as perdas de potência ativa do sistema sujeito a restrições físicas e operacionais do sistema de distribuição. As variáveis binárias do problema representam a abertura e/ou fechamento de chaves de interconexão existentes nos ramos do sistema e as variáveis contínuas representam as tensões nodais e ângulos das tensões nodais. Na metodologia utilizada todas as chaves de interconexão do sistema de distribuição estão fechadas no início do processo e a cada passo da fase construtiva do GRASP um ramo é desconectado do sistema e um fluxo de carga é resolvido. Na fase de melhoria, tendo em vista que a solução da fase construtiva é um sistema radial, foi utilizado a cada iteração um fluxo de carga especializado para sistemas radiais. Para garantir que o sistema de distribuição opere de forma radial, foi introduzido na metodologia de solução uma rotina na qual é verificada a formação de laços e a conectividade do sistema em cada iteração das fases de construção e de melhoria local. São apresentados testes realizados utilizando os sistemas de 14, 33, 84,119 e 136 barras para avaliar a eficiência e robustez da metodologia proposta. Os resultados obtidos foram comparados aos resultados encontrados na literatura com o objetivo de validar a proposta deste trabalho / In this work the GRASP is used to solve the problem of reconfiguring systems for electricity distribution modeled as a nonlinear programming problem of binary mixture. The goal is to minimize the power losses of the system subject to physical constraints and operating the distribution system. The problem of binary variables represents the opening and/or closing braces interconnecting branches existing in the system and the continuous variables represent the nodal voltages and angles of nodal voltages. In the methodology used to interconnect all the keys of the distribution system are closed at the beginning of the process and every step of the constructive phase of GRASP a branch is disconnected from the system and a load flow is solved. In the improvement phase, given that the solution of the constructive phase is a radial system was used at each iteration a load flow for radial systems specialist. To ensure that the distribution system operates in a radial manner, was introduced into the solution methodology is a routine in which verified the formation of linkages and connectivity of the system in each iteration of the phases of construction and local improvement. Tests are presented using the systems 14, 33, 84, 119 and 136 bus to evaluate the efficiency and robustness of the proposed methodology. The results were compared to results from the literature in order to validate the proposal of this work

Made available in DSpace on 2015-05-14T12:36:55Z (GMT). No. of bitstreams: 1 parte1.pdf: 1169586 bytes, checksum: 685986454ee5e2cc58d709e7d646732f (MD5) Previous issue date: 2009-08-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents a new heuristic, called Heurística 1, and the implementations of the GRASP, Simulated Annealing and Genetic Algorithms metaheuristics for the rectilinear Steiner minimum tree problem (RSMTP), talking about its theoretical aspects, like computational complexity, and practical ones, like pseudo-codes and implementation strategies. The new techniques for RSMTP presented, especially the Genetic Algorithms, have computational results of superior quality in comparison to the best heuristics in present litera / Este trabalho apresenta uma nova heurística, denominada Heurística 1, e a implementação das metaheurísticas GRASP, Simulated Annealing e Algoritmos Genéticos para o problema da árvore retilínea mínima de Steiner (RSMTP), discorrendo sobre seus aspectos teóricos, como a complexidade computacional; e práticos, como pseudocódigos e estratégias de implementação. As novas abordagens para o RSMTP apresentadas, em especial os Algoritmos Genéticos, ostentam resultados computacionais de qualidade superior às apresentadas pelas melhores heurísticas da literatura atual.

Made available in DSpace on 2014-12-17T14:53:05Z (GMT). No. of bitstreams: 1 EvertonS_DISSERT.pdf: 1215528 bytes, checksum: 9fd0b2ab4c831dc0b107eb1bed7bb87b (MD5) Previous issue date: 2012-01-27 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / This work presents a hybrid approach for the supplier selection problem in Supply Chain Management. We joined decision-making philosophy by researchers from business school and researchers from engineering in order to deal with the problem more extensively. We utilized traditional multicriteria decision-making methods, like AHP and TOPSIS, in order to evaluate alternatives according decision maker s preferences. The both techiniques were modeled by using definitions from the Fuzzy Sets Theory to deal with imprecise data. Additionally, we proposed a multiobjetive GRASP algorithm to perform an order allocation procedure between all pre-selected alternatives. These alternatives must to be pre-qualified on the basis of the AHP and TOPSIS methods before entering the LCR. Our allocation procedure has presented low CPU times for five pseudorandom instances, containing up to 1000 alternatives, as well as good values for all considered objectives. This way, we consider the proposed model as appropriate to solve the supplier selection problem in the SCM context. It can be used to help decision makers in reducing lead times, cost and risks in their supply chain. The proposed model can also improve firm s efficiency in relation to business strategies, according decision makers, even when a large number of alternatives must be considered, differently from classical models in purchasing literature / Este trabalho apresenta uma abordagem h?brida para o problema de sele??o de fornecedores em cadeias de suprimentos geridas com base na metodologia SCM (do ingl?s, Supply Chain Management). Busca-se combinar as filosofias de avalia??o tradicionalmente adotadas pelos pesquisadores oriundos da escola de neg?cios e pelos pesquisadores oriundos da ?rea de engenharia, esta ?ltima baseada em otimiza??o, para o trato do problema. Para tal, utilizam-se t?cnicas multicrit?rios tradicionais, como os m?todos AHP e TOPSIS para avaliar as alternativas segundo a prefer?ncia dos decisores. Ambas as t?cnicas s?o modeladas de maneira a suportar defini??es da Teoria dos Conjuntos Fuzzy, tratando-se assim informa??es imprecisas. Adicionalmente, apresenta-se um algoritmo GRASP, com base em m?ltiplos objetivos, para a aloca??o de pedidos entre as alternativas pr?-selecionadas por meio dos m?todos supracitados. Este algoritmo, por sua vez, apresenta tempos de CPU relativamente baixos para cinco inst?ncias pseudo-aleat?rias, contendo entre 20 e 1000 alternativas, bem como valores pr?ximos aos valores m?nimos para cada um dos objetivos considerados. Destaca-se que o modelo proposto se mostrou apropriado para a avalia??o de fornecedores no contexto apresentado, podendo-se auxiliar os decisores na redu??o de lead times, custos e riscos de sua cadeia de suprimentos, bem como na melhoria da efici?ncia desta estrutura em rela??o ? sua vis?o de neg?cios, mesmo quando um n?mero elevado de alternativas ? considerado, diferentemente dos modelos cl?ssicos apresentados na literatura

Made available in DSpace on 2014-12-17T14:55:11Z (GMT). No. of bitstreams: 1 JoaoPQS.pdf: 1464588 bytes, checksum: ad1e7b6af306b0ce9b1ccb1fb510c4ab (MD5) Previous issue date: 2009-03-06 / The metaheuristics techiniques are known to solve optimization problems classified as NP-complete and are successful in obtaining good quality solutions. They use non-deterministic approaches to generate solutions that are close to the optimal, without the guarantee of finding the global optimum. Motivated by the difficulties in the resolution of these problems, this work proposes the development of parallel hybrid methods using the reinforcement learning, the metaheuristics GRASP and Genetic Algorithms. With the use of these techniques, we aim to contribute to improved efficiency in obtaining efficient solutions. In this case, instead of using the Q-learning algorithm by reinforcement learning, just as a technique for generating the initial solutions of metaheuristics, we use it in a cooperative and competitive approach with the Genetic Algorithm and GRASP, in an parallel implementation. In this context, was possible to verify that the implementations in this study showed satisfactory results, in both strategies, that is, in cooperation and competition between them and the cooperation and competition between groups. In some instances were found the global optimum, in others theses implementations reach close to it. In this sense was an analyze of the performance for this proposed approach was done and it shows a good performance on the requeriments that prove the efficiency and speedup (gain in speed with the parallel processing) of the implementations performed / As metaheur?sticas s?o t?cnicas conhecidas para a resolu??o de problemas de otimiza??o, classificados como NP-Completos e v?m obtendo sucesso em solu??es aproximadas de boa qualidade. Elas fazem uso de abordagens n?o determin?sticas que geram solu??es que se aproximam do ?timo, mas no entanto, sem a garantia de que se encontre o ?timo global. Motivado pelas dificuldades em torno da resolu??o destes problemas, este trabalho prop?s o desenvolvimento de m?todos paralelos h?bridos utilizando a aprendizagem por refor?o e as metaheur?sticas GRASP e Algoritmos Gen?ticos. Com a utiliza??o dessas t?cnicas em conjunto, objetivou-se ent?o, contribuir na obten??o de solu??es mais eficientes. Neste caso, ao inv?s de utilizar o algoritmo Q-learning da aprendizagem por refor?o, apenas como t?cnica de gera??o das solu??es iniciais das metaheur?sticas, este tamb?m aplicado de forma cooperativa e competitiva com o Algoritmo Gen?tico e o GRASP, em uma implementa??o paralela. Neste contexto, foi poss?vel verificar que as implementa??es realizadas neste trabalho apresentaram resultados satisfat?rios, tanto na parte de coopera??o e competi??o entre os algoritmos Q-learning, GRASP a Algoritmos Gen?ticos, quanto na parte de coopera??o e competi??o entre grupos destes tr?s algoritmos. Em algumas inst?ncias foi encontrado o ?timo global; quando n?o encontrado, conseguiu-se chegar bem pr?ximo de seu valor. Neste sentido foi realizada uma an?lise do desempenho da abordagem proposta e verificou-se um bom comportamento em rela??o aos quesitos que comprovam a efici?ncia e o speedup (ganho de velocidade com o processamento paralelo) das implementa??es realizadas

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-09T20:48:39Z (GMT). No. of bitstreams: 1 Ferber_DanielFelix_M.pdf: 2571168 bytes, checksum: 373e2b3bb3f1ca3735beb4c4303dc5d9 (MD5) Previous issue date: 2007 / Resumo: O principal objetivo deste trabalho é a elaboração de heurísticas para auxiliar no projeto de cabeamento de redes telefônicas. O cabeamento será tratado desde os armários de distribuição até as caixas terminais. O auxílio de uma ferramenta computacional especializada no projeto de novas redes telefônicas abre caminhos para a minimização de custos e também reduz sensivelmente o tempo de planejamento. Inicialmente, estuda-se o problema para se obter uma especificação minuciosa, acompanhada de um modelo matemático. Com estas informações, desenvolve-se diferentes estratégias para algoritmos baseados na heurística GRASP, e compara-se os resultados experimentais obtidos / Abstract: The main goal of these studies is the design of heuristics to support the planning of wire cabling on a phone network. The cabling will be handled from the central distribution point to terminal boxes. The assistance of a computational tool specialized in the design of phone networks raises new opportunities for cost reduction and decreases considerably the time spent designing the network. The problem is first studied in order to achieve a detailed specification with a mathematical model. Based on this information, several different strategies are laid out based on a heuristic called GRASP and the experimental results are compared. / Mestrado / Otimização Combinatoria / Mestre em Computação

Made available in DSpace on 2016-12-23T14:33:39Z (GMT). No. of bitstreams: 1 Dissertacao_CRAVO_G_L_2009.pdf: 1278828 bytes, checksum: ebab7f313edc64bb51241b5c7d587d33 (MD5) Previous issue date: 2009-06-25 / This master s thesis presents an implementation of the GRASP meta-heuristic for solving the Multi-mode Resource constrained Problem of Scheduling Project (MRCPSP). The MRCPSP belongs to the class NP-Hard and therefore has received attention of many researchers. In this thesis, a case study problem of Scheduling Industrial Maintenance is viewed as a MRCPSP. The GRASP was tested with a set of benchmark tests obtained from PSPLIB (Project Scheduling Library). The results showed that the GRASP is a good strategy for solving MRCPSP instances. / Esse trabalho apresenta uma implementação da meta-heurística GRASP para a resolução do Problema de Escalonamento de Projetos com Restrições de Recursos e Múltiplos Modos de Processamento (MRCPSP). O MRCPSP é um problema da classe NP Difícil e por isso vem recebendo atenção dos pesquisadores. Nessa dissertação, também é apresentado um estudo de caso cujo problema de Programação de Manutenção Industrial é visto como um problema de escalonamento de projeto. O GRASP foi testado com o conjunto de instâncias do MRCPSP disponíveis na PSPLIB (Project Scheduling Problem Library). Os resultados obtidos mostraram que o GRASP proposto se configura como uma boa estratégia de solução para o MRCPSP.

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

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