Este trabalho apresenta o desenvolvimento e a implementação computacional de um algoritmo para a localização de faltas em linhas de transmissão. O algoritmo proposto é baseado em métodos heurísticos, isto é, Algoritmos Genéticos (AG) e Pattern Search (PS), sendo capaz de identificar o ponto de ocorrência da falta utilizando fasores de tensão e corrente de pré e pós-falta, estimados a partir de medições disponíveis apenas no terminal local da linha de tranmsissão. Nesta abordagem, ambas as ferramentas de otimização possuem natureza heurísticas sendo menos propensas a cair em valores mínimos locais, o que implica uma maior eficiência e precisão na determinação da localização da falta. Além disso, o método utiliza potências de curto-circuito monofásicas e trifásicas de ambos os terminais da linha (local e remoto), a fim de obter seus equivalentes de Thévenin, e os parâmetros elétricos da linha de transmissão. Com o objetivo de avaliar o desempenho do algoritmo proposto, consideram-se nas simulações quatro sistemas de transmissão diferentes, que representam sistemas reais de transmissão brasileiros. O primeiro está constituído por uma típica linha de transmissão de 138 [kV] com circuito duplo, e os outros três sistemas são constituídos por linhas de transmissão típicas de 230, 500 e 765 [kV] com circuito simples. A partir dos quatro sistemas de transmissão simulados no software Alterative Transients Program (ATP/EMTP), foram gerados um total de 928 situações de falta. A versão do algoritmo desenvolvido para localização de faltas foram descritas e implementadas, através do software científico MATrix LABoratory (MATLAB), apresentando resultados com altos níveis de precisão. / This paper presents the development and implementation of a computational algorithm for location faults in transmission line. The proposed algorithm is based on heuristic methods, namely AG and PS, being able to identify the occurrence of the fault point using phasor voltage and current pre and post-fault, estimated from measurements available only on the local terminal of the transmission line. In this approach, both optimization tools have heuristic nature being less prone to falling into local minimum values, which implies grater efficiency and accuracy in the determination of fault location. Moreover, the method use singles-phase and three-phase short-circuit powers of both the line terminals (Local and remote), to obtain the Thévenin equivalent and the electrical parameters of the transmission line. In order to evaluate the performance of the proposed algorithm were considered four different transmission systems; these systems represent real systems of Brazilian transmission. The first this made up of a transmission line typical of 138 [kV] with double circuit, the other three systems are made up of transmission line typical of 230, 500 and 765 [kV] of single circuit. Whereas the four simulated transmission systems in the softwareATP/ EMTP, generated a total of 928 situations fault. The version of the algorithm designed to locate faults, have been described and implemented through scientific software MATLAB, presenting results high levels of accuracy.

Este trabalho apresenta o desenvolvimento e a implementação computacional de um algoritmo para a localização de faltas em linhas de transmissão. O algoritmo proposto é baseado em métodos heurísticos, isto é, Algoritmos Genéticos (AG) e Pattern Search (PS), sendo capaz de identificar o ponto de ocorrência da falta utilizando fasores de tensão e corrente de pré e pós-falta, estimados a partir de medições disponíveis apenas no terminal local da linha de tranmsissão. Nesta abordagem, ambas as ferramentas de otimização possuem natureza heurísticas sendo menos propensas a cair em valores mínimos locais, o que implica uma maior eficiência e precisão na determinação da localização da falta. Além disso, o método utiliza potências de curto-circuito monofásicas e trifásicas de ambos os terminais da linha (local e remoto), a fim de obter seus equivalentes de Thévenin, e os parâmetros elétricos da linha de transmissão. Com o objetivo de avaliar o desempenho do algoritmo proposto, consideram-se nas simulações quatro sistemas de transmissão diferentes, que representam sistemas reais de transmissão brasileiros. O primeiro está constituído por uma típica linha de transmissão de 138 [kV] com circuito duplo, e os outros três sistemas são constituídos por linhas de transmissão típicas de 230, 500 e 765 [kV] com circuito simples. A partir dos quatro sistemas de transmissão simulados no software Alterative Transients Program (ATP/EMTP), foram gerados um total de 928 situações de falta. A versão do algoritmo desenvolvido para localização de faltas foram descritas e implementadas, através do software científico MATrix LABoratory (MATLAB), apresentando resultados com altos níveis de precisão. / This paper presents the development and implementation of a computational algorithm for location faults in transmission line. The proposed algorithm is based on heuristic methods, namely AG and PS, being able to identify the occurrence of the fault point using phasor voltage and current pre and post-fault, estimated from measurements available only on the local terminal of the transmission line. In this approach, both optimization tools have heuristic nature being less prone to falling into local minimum values, which implies grater efficiency and accuracy in the determination of fault location. Moreover, the method use singles-phase and three-phase short-circuit powers of both the line terminals (Local and remote), to obtain the Thévenin equivalent and the electrical parameters of the transmission line. In order to evaluate the performance of the proposed algorithm were considered four different transmission systems; these systems represent real systems of Brazilian transmission. The first this made up of a transmission line typical of 138 [kV] with double circuit, the other three systems are made up of transmission line typical of 230, 500 and 765 [kV] of single circuit. Whereas the four simulated transmission systems in the softwareATP/ EMTP, generated a total of 928 situations fault. The version of the algorithm designed to locate faults, have been described and implemented through scientific software MATLAB, presenting results high levels of accuracy.

O processo de produção, no ambiente da Construção Civil, é abordado segundo certos princípios gerenciais que absorvem conceitos vindo da Engenharia de Produção. Para obter a qualidade na produção, pelo critério competitivo que envolve prazos e confiabilidade de entrega, é fundamental a integração entre o projeto do produto e a produção através do projeto da produção. O processo de planejamento, no contexto do projeto da produção, requer o uso de ferramentas de suporte à tomada de decisão, fazendo da programação uma etapa essencial para o ganho de consistência deste processo decisório. A pesquisa trata da programação de projetos com limitação de recursos, a fim de encontrar uma boa solução para o problema de programação de forma simples e satisfatória. O método utiliza como ferramenta de apoio o software Microsoft Project para manipular os projetos com mais agilidade e flexibilidade, considerando as regras de prioridades que são usadas a depender dos critérios gerenciais adotados pelas empresas. O método é baseado na classe de procedimentos heurísticos: Job Oriented Heuristic Scheduling, já que o grau de prioridade dos projetos orienta o desenvolvimento da programação conjunta, denominada Programação multi-projetos. / The production process in the Civil Construction environment is approached according to some management principles that reinforce concepts from Production Engineering. To obtain Quality in production through the competitive criterion, which comprehends fast delivery time and on-time delivery, it is fundamental the integration between Product Design and production through Production Design. The planning process requires the use of procedures to support the decision-making process concerning global production systems in construction companies. Thus scheduling would be an essential stage for the acquisition of decision consistence. This dissertation deals with the resource-constrained Project Scheduling Problem using a heuristic method based on priority rules. Heuristic procedures are used to obtain a good solution to the problem in a practical and satisfactory way. The method uses Microsoft Project as a supporting tool to deal with the projects with more agility and flexibility. The priority rules are based on management criteria adopted by the companies. The method is based on the category of heuristic procedures known as Job Oriented Heuristic Scheduling, since the project priority degrees orient the steps of the multi-project scheduling.

Irregular cutting and packing problems, with convex and non-convex polygons, are found in many industries such as metal mechanics, textiles, of shoe making, the furniture making and others. In this thesis we study the two-dimensional version of these problems, where we want to allocate a set of items, without overlap, inside one or more containers, limited or unlimited, so as to optimize an objective function. In this document we study the knapsack problem, placement problem, strip packing problem, cutting stock problem and bin packing problem. For these problems, the heuristic methods and mathematical programming models are proposed and presented very promising results, surpassing in many cases the best results in the specialized literature. This thesis is organized as follows. In Chapter 1, we present a review of the studied problems, the value proposition for this thesis with the main contributions and ideas. In Chapter 2, we propose a metaheursitic for the strip packing problem with irregular items and circles. Then, in Chapter 3, we present a generic heuristic for the allocation of irregular items that may be weakly or strongly heterogeneous and will be allocated in a container (output maximization problems) or multiple containers (input minimization problems). In Chapter 4, we propose a solution method for the cutting stock problem with deterministic demand and stochastic demand. In Chapters 5 and 6, we present mathematical programming models for the strip packing problem. Finally, in Chapter 7, we present a conclusion and a concise direction for future works. / Os problemas de corte e empacotamento de itens irregulares, polígonos convexos e não convexos, são encontrado em diversas indústrias, tais como a metal-mecânica, a têxtil, a de calçados, a moveleira e outras. Nesta tese estudamos a versão bidimensional destes problemas, na qual desejamos alocar um conjunto de itens, sem sobreposição, no interior de um ou mais recipientes, limitados ou ilimitados, de modo a otimizar uma função objetivo. Neste trabalho estudamos o problema da mochila, o problema do assentamento, o problema empacotamento em faixa, o problema de corte de estoque e o problema de empacotamento de contêineres. Para estes problemas, os métodos heurísticos e modelos de programação matemática propostos e apresentam resultados muito promissores, ultrapassando em muitos casos os melhores resultados da literatura especializada. Esta tese esta organizada da seguinte maneira. No Capítulo 1, apresentamos uma revisão dos problemas estudados, a proposta de valor deste doutorado com as principais contribuições e ideias. No Capítulo 2, propomos uma meta-heurística para o problema de empacotamento em faixa para itens irregulares e círculos. Em seguida, no Capítulo 3 apresentamos uma heurística genérica para a alocação de itens irregulares que podem ser fracamente ou fortemente heterogêneos e serão alocados em um recipiente (problema de maximização de saída) ou de múltiplos recipientes (problemas de minimização de entrada). O Capítulo 4 propõem um método de solução para o problema de corte de estoque com demanda conhecida e demanda estocástica. Nos Capítulos 5 e 6 apresentamos modelos de programação matemática para o problema de corte de itens irregulares em faixa. Finalmente, no Capítulo 7, apresentamos a conclusão e uma sucinta direção para os trabalhos futuros.

Organizações eficientes são aquelas que conseguem manter equilibradas as vertentes de qualidade, custo e tempo. Em relação ao último, existem várias etapas da cadeia produtiva nas quais o tempo deve ser monitorado. Quando a programação da produção nas indústrias não é priorizado, pode-se incorrer vários efeitos negativos. Um deles, é o atraso em relação à data de entrega, no qual a corporação pode sofrer penalidades financeiras, além de uma exposição negativa para a marca, a qual pode ter sua credibilidade contestada. Dessa forma, essa pesquisa tem por objetivo propor métodos construtivos, que minimize a medida de desempenho total tardiness (atraso total). Para aproximar o método à realidade vivenciada pelas indústrias, será considerada a restrição de manutenção preventiva. Além disso, o ambiente de estudo será o contexto de no-wait flowshop, no qual as tarefas são processados continuamente e sem que haja interrupções entre uma operação e outra de uma mesma tarefa. Além da proposição de métodos construtivos para a resolução do problema, apresenta-se uma metaheurística como forma de demostrar como pode-se aprimorar os resultados gerado pelos métodos construtivos. Experimentações computacionais foram elaboradas e realizadas para comparação dos algoritmos. Dentre as heurísticas construtivas a que apresentou melhor desempenho foi a \"EDD + NEH + LS1 + LS2\'\', na qual utiliza uma lógica de inserção. A metaheurística proposta é baseada no procedimento IG (iterated greedy), sendo que há melhora de resultado em relação as heurísticas construtivas. Assim, espera-se que essa pesquisa possa ser utilizada e aplicada pela indústria de manufatura para aumentar a efetividade da programação da produção. / Efficient organizations are those that manage to keep the quality, cost and time strands balanced. With respect to the variable time, there are several stages of the production chain in which it must be monitored. When scheduling in companies is not prioritized, several negative effects incur. One of them is the delay in relation to the due date, for which the corporation can suffer financial penalties, in addition to a negative exposure to the brand, which may have its credibility challenged. Therefore, this research aims to propose constructive methods, which minimizes the performance criterion of total tardiness. In order to approximate the method to the reality of the industries, preventive maintenance constraints will be considered. And the environment of the study will be the no-wait flowshop, in which jobs are processed continuously and without interruptions between one operation and another of the same job. In addition to proposing constructive methods to solve the problem, a metaheuristic is presented as a way of demonstrating how to improve the results generated by the constructive methods. Computational experiments were elaborated and performed for comparison of the algorithms. Among the constructive heuristics that presented the best performance was \"EDD + NEH + LS1 + LS2\", in which it uses an insertion logic. The proposed metaheuristic is based on the IG (iterated greedy) procedure, and there is an improvement of the result in relation to the constructive heuristics. Thus, it is expected that this research can be used and applied by the manufacturing industry to increase the effectiveness of scheduling.

Este trabalho trata do problema de programação de operações no ambiente flow shop com máquinas múltiplas, com seus tempos de preparação (setup) assimétricos e dependentes da seqüência de processamento das tarefas. Este ambiente de produção é comum em indústrias gráficas, químicas, têxteis, de papel e de tinta, caracterizadas por sistemas com amplo mix de produtos. Qualquer processo produtivo requer um gerenciamento eficaz por meio do Planejamento e Controle da Produção (PCP). Esta atividade inclui a programação da produção, ou seja, a alocação de recursos para a execução de tarefas em uma base de tempo. A atividade de programação é uma das tarefas mais complexas no gerenciamento de produção, pois há a necessidade de lidar com diversos tipos diferentes de recursos e atividades simultaneamente. Além disso, o número de soluções possíveis cresce exponencialmente em várias dimensões, de acordo com a quantidade de tarefas, operações ou máquinas, conferindo uma natureza combinatorial ao problema. No ambiente estudado neste trabalho as operações de cada tarefa são executadas em múltiplos estágios de produção, podendo variar a quantidade de máquinas em cada um deles. Cada operação é processada por apenas uma máquina em cada estágio. Os tempos de preparação das máquinas possuem uma variabilidade relevante em função da ordem de execução das tarefas nas máquinas. A função-objetivo considerada é a minimização da duração total da programação (makespan). Foram desenvolvidos quatro métodos heurísticos construtivos com base em algoritmos reportados na literatura para solução de problemas flow shop permutacional e máquinas paralelas no ambiente cujo tempo de setup é dependente da seqüência. Como não foram encontrados na literatura métodos para programação no ambiente tratado neste trabalho, os algoritmos construídos foram comparados entre si. O foco da pesquisa foi o estudo da influência da relação entre as ordens de grandeza dos tempos de processamento e de setup em cada método de solução. Os resultados obtidos na experimentação computacional foram analisados e discutidos com base na porcentagem de sucesso, desvio relativo (%), desvio-padrão do desvio relativo e tempo médio de computação / This work adressess the hybrid flow shop scheduling problem with asymmetric sequence dependent setup times. This environment of production system is common in graphical, chemical, fabric, paper and ink industries. It’s characterized by systems with large mix of products. Any productive process requires an efficient management by means of Production Planning and Control. This activity includes scheduling, i.e., the resources allocation for the execution of jobs in a time base. Scheduling is one of the tasks most complex in production management, since it deals simultaneously with different types of resources and activities. Moreover, the number of possible solutions grows exponentially in some dimensions, in accordance with the number of jobs, operations or machines, conferring a combinatorial nature to the problem. In the environment studied in this work, the operations of each job are processed in multiple production stages. The number of machines in each stage can be different. Each operation is processed by only one machine in each stage. The setup times have a significant variability in function of the sequence of job processing on the machines. The objective is minimizing the total time to complete the schedule (makespan). Four constructive heuristic methods were developed on the basis of algorithms reported in the literature for solving permutation flow shop and parallel machine problems with sequence dependent setup times. The proposed heuristic methods have been compared between themselves, since no constructive heuristics have been found in the literature for the scheduling problem considered in this work. The focus of the research was the study of the influence of the relations among the range of the times processing and setup times in each method. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation, standard deviation of relative deviation and average computation time. Results from computational experience are discussed

Os processos industriais de produção exigem uma programação da produção efetiva. Essa atividade consiste da alocação dos recursos produtivos, a fim de executar tarefas determinadas por um período de tempo definido. Programar a produção é uma das atividades mais complexas do Planejamento da Produção, pois existem diferentes tipos de recursos a serem administrados simultaneamente. E também a quantidade de possíveis soluções aumenta exponencialmente com o aumento da quantidade de tarefas e máquinas presentes no sistema. A proposta deste trabalho é apresentar um método heurístico construtivo para a solução de problemas flow shop permutacional. A função-objetivo utilizada é a minimização do tempo total da programação (makespan). O algoritmo foi desenvolvido com base no melhor algoritmo construtivo presente na literatura, e os resultados obtidos são discutidos e analisados com base na porcentagem de sucesso, desvio relativo médio e tempo médio de computação. / Industrial productive processes demand an effective production scheduling. These activities consist in allocating the productive resources in order to execute determined jobs for a established period of time. Scheduling the production is one of the most complex activities involved in Planning the Production because there are different kinds of resources to be managed simultaneously. Furthermore, the amounts of feasible solutions increase exponentially as the number of jobs and machines in large systems. This dissertation presents a constructive heuristic method to solve the permutational flow shop problem. The evaluation criterion is the total production elapsed time (makespan). The developed algorithm was based on the best algorithm found in the literature, the results are analysed based on the success rate, mean relative deviation and computing time.

A teoria de programação da produção preocupa-se em fornecer diretrizes e métodos eficientes para a utilização dos recursos nas atividades produtivas. Este trabalho investiga o problema de programação da produção em ambientes flow shop com máquinas múltiplas e tempos de preparação das máquinas assimétricos e dependentes da seqüência de execução das tarefas. A atividade de programação da produção constitui uma das várias funções executadas pelo planejamento e controle da produção, que tem como objetivo comandar e gerenciar o processo produtivo, e caracteriza uma das atividades mais complexas no gerenciamento dos sistemas produtivos. A programação da produção preocupa-se com a alocação de recursos sobre o tempo para executar um conjunto de tarefas. No ambiente estudado neste trabalho as operações de cada tarefa são executadas em múltiplos estágios de produção, podendo variar a quantidade de máquinas em cada um deles. Cada operação é processada por apenas uma máquina em cada estágio. Os tempos de preparação das máquinas possuem uma variabilidade relevante em função da ordem de execução das tarefas nas mesmas. A função-objetivo considerada é a minimização do tempo médio de fluxo. Foram desenvolvidos quatro métodos heurísticos construtivos com base em algoritmos reportados na literatura para solução do problema flow shop permutacional e máquinas paralelas cujo tempo de setup é dependente da seqüência de execução das tarefas. Como não foram encontrados na literatura métodos de solução para o problema investigado neste trabalho, os algoritmos propostos foram comparados entre si. Foi efetuado um estudo da influência da relação entre as ordens de grandeza dos tempos de processamento das tarefas e do setup das máquinas em cada método de solução. Os resultados obtidos na experimentação computacional foram analisados e discutidos com base na porcentagem de sucesso, desvio relativo, desvio-padrão do desvio relativo e tempo médio de computação. / Scheduling theory attempts to provide guidelines and efficient methods to the use of the resources in the productive activities. This study investigates the hybrid flow shop problem with asymmetric sequence dependent setup times. The activity of production scheduling constitute is one of the several functions carried by production planning and control, which has as the objective command and management the production system, and characterize is one of the tasks most complex in production management. This activity of the scheduling aims within the allocation of the resources for the execution of jobs in a time base. In the environment studied in this work, the operations of each job are processed in multiple production stages. The number of machines in each stage can be different. Each operation is processed by only one machine in each stage. The setup times have a significant variability in function of the sequence of job processing on the machines. The objective is minimizing the mean flow time. Four constructive heuristic methods were proposed on the basis of algorithms reported in the literature for solving permutation flow shop and parallel machine problems with sequence dependent setup times. The proposed heuristic methods will have compared between themselves, since no constructive heuristics have been found in the literature for the scheduling problem considered in this work. It was carried out the study of the influence of the relations among the range of the times processing and setup times in each method. The statistics used in order to evaluate the heuristic performances were the percentage of success (in finding the best solution), relative deviation, standard deviation of relative deviation and average computation time. Results from computational experience are discussed.

Este trabalho aborda o problema de programação de tarefas, a partir de um caso específico, conhecido como Flow Shop com buffer zero. O problema consiste em programar n tarefas em m máquinas no ambiente Flow Shop permutacional. Com o aumento do nível de exigência dos clientes, pesquisas que buscam o atendimento das datas de entrega têm se tornado de extrema importância em ambientes de manufatura. Este trabalho analisa o problema de minimização do atraso total no ambiente Flow Shop onde não existe a possibilidade de armazenagem das tarefas entre estágios de produção sucessivos (buffer zero), tendo como consequência o bloqueio de máquinas. A Heurística Evolutiva Clustering Search foi proposta e analisada para a obtenção de soluções de altíssima qualidade para o problema. Finalmente, uma extensa experimentação computacional foi realizada. Quando comparado com o melhor método reportado na literatura, o método proposto apresentou qualidade superior. / This work deals with the Flow Shop scheduling problem. The objective is scheduling n jobs on m machines in the Permutation Flow Shop environment. With the increasing customer demand level, researches that aims the attendance of due dates have become extremely important in manufacturing process. This work studies the total tardiness minimization problem in the flow shop environment where there is no buffer storage between machines, resulting in the machine block. The Heuristic Evolutionary Clustering Search was proposed and analyzed to obtain high quality solutions to the problem. Finally, an extensive computational experiment was performed. When compared to the best method reported in the literature, the proposed method showed high quality.

Inicialmente este problema é enquadrado no contexto mais amplo de Corte e Empacotamento e uma forma exata de resolver o problema é apresentada. O problema é NP-'Arduo no sentido forte e extremamente difícil de ser resolvido na prática, por isso uma atenção especial aos algoritmos aproximativos e seus desempenhos, não poderia ser omitida. Como resultado, uma classe de algoritmos aproximativos (heurísticas e meta-heurísticas) foi desenvolvida e seus desempenhos avaliados com relação às heurísticas famosas. O procedimento para o preenchimento dos itens dentro dos bins utiliza o bem conhecido princípio da alocação em pontos de cantos. Os critérios para a estabilidade estática dos itens dentro dos bins são apresentados com detalhes. Uma abordagem distribuída também foi usada como forma de resolver o problema, com o intuito de diminuir o tempo de execução computacional dos algoritmos aproximativos que levam em conta a estabilidade estática dos itens dentro dos bins. Grande quantidade de experimentos computacionais são apresentados para problemas com até 90 itens (com e sem estabilidade estática) e os resultados são comparados com aqueles obtidos da literatura. Por último, foi sugerida algumas idéias para o direcionamento das futuras pesquisas sobre o problema.