Project scheduling using a competitive genetic algorithm

- The resource constrained project scheduling problem (RCPSP) is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. During the last couple of years many heuristic procedures have been developed for this problem, but still these procedures often fail in finding near-optimal solutions. This paper proposes a genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities and delay times of the activities are defined by the genetic algorithm. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

Combining global tabu search with local search for solving systems of equalities and inequalities

This papers aims at providing a combined strategy for solving systems of equalities and inequalities. The combined strategy uses two types of steps: a global search step and a local search step. The global step relies on a tabu search heuristic and the local step uses a deterministic search known as Hooke and Jeeves. The choice of step, at each iteration, is based on the level of reduction of the l2-norm of the error function observed in the equivalent system of equations, compared with the previous iteration.

Crossing genetic and swarm intelligence algorithms to generate logic circuits

Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetic. The basic concept of GAs is designed to simulate processes in natural system necessary for evolution, specifically those that follow the principles first laid down by Charles Darwin of survival of the fittest. On the other hand, Particle swarm optimization (PSO) is a population based stochastic optimization technique inspired by social behavior of bird flocking or fish schooling. PSO shares many similarities with evolutionary computation techniques such as GAs. The system is initialized with a population of random solutions and searches for optima by updating generations. However, unlike GA, PSO has no evolution operators such as crossover and mutation. In PSO, the potential solutions, called particles, fly through the problem space by following the current optimum particles. PSO is attractive because there are few parameters to adjust. This paper presents hybridization between a GA algorithm and a PSO algorithm (crossing the two algorithms). The resulting algorithm is applied to the synthesis of combinational logic circuits. With this combination is possible to take advantage of the best features of each particular algorithm.

Modified particle swarm optimization for day-ahead distributed energy resources scheduling including vehicle-to-grid

Mestrado em Engenharia Electrotécnica – Sistemas Eléctricos de Energia

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

Melhoria do processo produtivo

A dissertação descreve o levantamento e otimização do processo de fabrico de uma peça plástica para um automóvel. A otimização deste processo produtivo tem em vista a rentabilização de recursos humanos, a redução de custos associados e a redução de atividades ao longo do processo, tais como armazenamento de produto semiacabado, uma vez que este deixa de existir, a eliminação de fluxos logísticos e a eliminação do posto de montagem de componentes desta peça. A metodologia utilizada neste projeto centra-se na aplicação de ferramentas que permitem a análise e melhoria de processos produtivos, tais como o diagrama de processo, o diagrama spaghetti, o PDCA, a cronometragem dos tempos por tarefa e a aplicação de uma heurística para o balanceamento do futuro posto de trabalho da peça em estudo. O diagrama de processo, o diagrama de spaghetti e a cronometragem dos tempos por tarefas mostraram o estado atual do processo produtivo. Da análise do atual estado verifica-se que existe muito desperdício de mão-de-obra nas duas estações de trabalho, injeção e montagem. A eliminação do posto de trabalho exclusivo para montagem e junção dos processos de injeção e montagem no mesmo posto de trabalho, com a aplicação de uma heurística para balanceamento do novo posto de trabalho, demonstra que os ganhos são muito significativos. A aplicação do ciclo PDCA, na base da qual está a elaboração de um plano de ações, tornará esta mudança possível e bem-sucedida. A intenção deste projeto é demonstrar que o estado atual pode sempre ser melhorado se se usarem as ferramentas corretas para análise e proposta de melhorias que trarão ganhos à empresa a curto prazo. Usando esta sugestão, a empresa poderá dar início a um novo ciclo em que o espírito de melhoria esteja presente todos os dias em toda a organização.

An optimization approach for the job shop scheduling problem

This paper presents an optimization approach for the job shop scheduling problem (JSSP). The JSSP is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. The proposed approach is based on a genetic algorithm technique. The scheduling rules such as SPT and MWKR are integrated into the process of genetic evolution. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities and delay times of the operations are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed approach.

Simulação de um Pool Simétrico com validação técnica do despacho provisório e apresentação de medidas corretivas baseadas num despacho ótimo

Os mercados de energia elétrica são atualmente uma realidade um pouco por todo o mundo. Contudo, não é consensual o modelo regulatório a utilizar, o que origina a utilização de diferentes modelos nos diversos países que deram início ao processo de liberalização e de reestruturação do sector elétrico. A esses países, dado que a energia elétrica não é um bem armazenável, pelo menos em grandes quantidades, colocam-se questões importantes relacionadas com a gestão propriamente dita do seu sistema elétrico. Essas questões implicam a adoção de regras impostas pelo regulador que permitam ultrapassar essas questões. Este trabalho apresenta um estudo feito aos mercados de energia elétrica existentes um pouco por todo o mundo e que o autor considerou serem os mais importantes. Foi também feito um estudo de ferramentas de otimização essencialmente baseado em meta-heurísticas aplicadas a problemas relacionados com a operação dos mercados e com os sistemas elétricos de energia, como é o exemplo da resolução do problema do Despacho Económico. Foi desenvolvida uma aplicação que simula o funcionamento de um mercado que atua com o modelo Pool Simétrico, em que são transmitidas as ofertas de venda e compra de energia elétrica por parte dos produtores, por um lado, e dos comercializadores, consumidores elegíveis ou intermediários financeiros, por outro, analisando a viabilidade técnica do Despacho Provisório. A análise da viabilidade técnica do Despacho Provisório é verificada através do modelo DC de trânsito de potências. No caso da inviabilidade do Despacho Provisório, por violação de restrições afetas ao problema, são determinadas medidas corretivas a esse despacho, com base nas ofertas realizadas e recorrendo a um Despacho Ótimo. Para a determinação do Despacho Ótimo recorreu-se à meta-heurística Algoritmos Genéticos. A aplicação foi desenvolvida no software MATLAB utilizando a ferramenta Graphical User Interfaces. A rede de teste utilizada foi a rede de 14 barramentos do Institute of Electrical and Electronics Engineers (IEEE). A aplicação mostra-se competente no que concerne à simulação de um mercado com tipo de funcionamento Pool Simétrico onde são efetuadas ofertas simples e onde as transações ocorrem no mercado diário, porém, não reflete o problema real relacionado a este tipo de mercados. Trata-se, portanto, de um simulador básico de um mercado de energia cujo modelo de funcionamento se baseia no tipo Pool Simétrico.

Optimal fuzzy PID control tuned with genetic algorithms

Fuzzy logic controllers (FLC) are intelligent systems, based on heuristic knowledge, that have been largely applied in numerous areas of everyday life. They can be used to describe a linear or nonlinear system and are suitable when a real system is not known or too difficult to find their model. FLC provide a formal methodology for representing, manipulating and implementing a human heuristic knowledge on how to control a system. These controllers can be seen as artificial decision makers that operate in a closed-loop system, in real time. The main aim of this work was to develop a single optimal fuzzy controller, easily adaptable to a wide range of systems – simple to complex, linear to nonlinear – and able to control all these systems. Due to their efficiency in searching and finding optimal solution for high complexity problems, GAs were used to perform the FLC tuning by finding the best parameters to obtain the best responses. The work was performed using the MATLAB/SIMULINK software. This is a very useful tool that provides an easy way to test and analyse the FLC, the PID and the GAs in the same environment. Therefore, it was proposed a Fuzzy PID controller (FL-PID) type namely, the Fuzzy PD+I. For that, the controller was compared with the classical PID controller tuned with, the heuristic Ziegler-Nichols tuning method, the optimal Zhuang-Atherton tuning method and the GA method itself. The IAE, ISE, ITAE and ITSE criteria, used as the GA fitness functions, were applied to compare the controllers performance used in this work. Overall, and for most systems, the FL-PID results tuned with GAs were very satisfactory. Moreover, in some cases the results were substantially better than for the other PID controllers. The best system responses were obtained with the IAE and ITAE criteria used to tune the FL-PID and PID controllers.

Afetação de recursos em sistemas de produção

O problema do escalonamento, por ser um dos factores fundamentais na tomada de decisão para uma boa gestão das operações, tem sido alvo de um amplo estudo, tanto na sua componente teórica como na sua componente prática. A importância de um escalonamento correto das operações é preponderante, quando as pequenas diferenças, em termos de tempos de produção, podem ter um grande impacto na competitividade da organização. Em muitas unidades produtivas, existem máquinas capazes de realizar as mesmas operações com diferentes desempenhos. Isto pode dever-se à necessidade de flexibilizar os recursos ou mesmo a uma atualização da capacidade produtiva. Embora os problemas de máquinas diferentes em paralelo tenham sido alvo de um vasto estudo, muitos deles não são passíveis de ser resolvidos através de métodos exatos. O problema de minimização do makespan (Rm||Cmax), é NP-hard, sendo habitualmente abordado através de heurísticas. Entre as heurísticas utilizadas em problemas de minimização do makespan em máquinas diferentes em paralelo, é possível identificar duas filosofias de afectação: a que utiliza os tempos de processamento para alocar as tarefas e a que utiliza as datas de conclusão. Nesta dissertação, pretende-se dar uma contribuição para a resolução do problema de afectação de recursos em sistemas de produção. Para tal, foram propostas as heurísticas OMTC 3 e Suffrage One. A contribuição consiste na proposta de versões híbridas e modificadas das heurística MCT e Suffrage, uma vez identificadas várias características que podem limitar o seu desempenho, como o facto da heurística MCT alocar as tarefas numa ordem aleatória ou a heurística Suffrage alocar mais que uma tarefa por iteração. Finalmente, procedeu-se à realização de testes computacionais, para avaliar o desempenho das heurísticas propostas. Os testes realizados permitiram concluir que a heurística OMTC 3 apresentou um melhor desempenho que a heurística MCT.

Híper-heurísticas com aprendizagem

A otimização nos sistemas de suporte à decisão atuais assume um carácter fortemente interdisciplinar relacionando-se com a necessidade de integração de diferentes técnicas e paradigmas na resolução de problemas reais complexos, sendo que a computação de soluções ótimas em muitos destes problemas é intratável. Os métodos de pesquisa heurística são conhecidos por permitir obter bons resultados num intervalo temporal aceitável. Muitas vezes, necessitam que a parametrização seja ajustada de forma a permitir obter bons resultados. Neste sentido, as estratégias de aprendizagem podem incrementar o desempenho de um sistema, dotando-o com a capacidade de aprendizagem, por exemplo, qual a técnica de otimização mais adequada para a resolução de uma classe particular de problemas, ou qual a parametrização mais adequada de um dado algoritmo num determinado cenário. Alguns dos métodos de otimização mais usados para a resolução de problemas do mundo real resultaram da adaptação de ideias de várias áreas de investigação, principalmente com inspiração na natureza - Meta-heurísticas. O processo de seleção de uma Meta-heurística para a resolução de um dado problema é em si um problema de otimização. As Híper-heurísticas surgem neste contexto como metodologias eficientes para selecionar ou gerar heurísticas (ou Meta-heurísticas) na resolução de problemas de otimização NP-difícil. Nesta dissertação pretende-se dar uma contribuição para o problema de seleção de Metaheurísticas respetiva parametrização. Neste sentido é descrita a especificação de uma Híperheurística para a seleção de técnicas baseadas na natureza, na resolução do problema de escalonamento de tarefas em sistemas de fabrico, com base em experiência anterior. O módulo de Híper-heurística desenvolvido utiliza um algoritmo de aprendizagem por reforço (QLearning), que permite dotar o sistema da capacidade de seleção automática da Metaheurística a usar no processo de otimização, assim como a respetiva parametrização. Finalmente, procede-se à realização de testes computacionais para avaliar a influência da Híper- Heurística no desempenho do sistema de escalonamento AutoDynAgents. Como conclusão genérica, é possível afirmar que, dos resultados obtidos é possível concluir existir vantagem significativa no desempenho do sistema quando introduzida a Híper-heurística baseada em QLearning.

Multilayer Perceptron Neural Networks Training Through Charged System Search and its Application for Non-Technical Losses Detection

The non-technical loss is not a problem with trivial solution or regional character and its minimization represents the guarantee of investments in product quality and maintenance of power systems, introduced by a competitive environment after the period of privatization in the national scene. In this paper, we show how to improve the training phase of a neural network-based classifier using a recently proposed meta-heuristic technique called Charged System Search, which is based on the interactions between electrically charged particles. The experiments were carried out in the context of non-technical loss in power distribution systems in a dataset obtained from a Brazilian electrical power company, and have demonstrated the robustness of the proposed technique against with several others natureinspired optimization techniques for training neural networks. Thus, it is possible to improve some applications on Smart Grids.

Environmental/Regatta Buoy: Telemetry and Configuration

A monitorização ambiental é essencial para a tomada de decisões tanto na ciência como na indústria. Em particular, uma vez que a água é essencial à vida e a superfície da Terra é composta principalmente por água, a monitorização do clima e dos parâmetros relacionados com a água em ecossistemas sensíveis, tais como oceanos, lagoas, rios e lagos, é de extrema importância. Um dos métodos mais comuns para monitorar a água é implantar bóias. O presente trabalho está integrado num projeto mais amplo, com o objetivo de projectar e desenvolver uma bóia autónoma para a investigação científica com dois modos de funcionamento: (i) monitorização ambiental ; e (ii) baliza ativa de regata. Assim, a bóia tem duas aplicações principais: a coleta e armazenamento de dados e a assistência a regatas de veleiros autónomos. O projeto arrancou há dois anos com um grupo de quatro estudantes internacionais. Eles projetaram e construíram a estrutura física, compraram e montaram o sistema de ancoragem da bóia e escolherem a maioria dos componentes electrónicos para o sistema geral de controlo e medição. Este ano, durante o primeiro semestre, dois estudantes belgas - Jeroen Vervenne e Hendrick Verschelde – trabalharam nos subsistemas de recolha e armazenamento de dados (unidade de controlo escrava) e de telemetria e configuração (unidade de controlo mestre) assim como definiram o protocolo de comunicação da aplicação. O trabalho desta tese continua o desenvolvimento do subsistema de telemetria e configuração. Este subsistema _e responsável pela configuração do modo de funcionamento e dos sensores assim como pela comunicação com a estacão de base (controlo ambiental), barcos (baliza ativa de regata) e com o subsistema de recolha e armazenamento de dados. O desenvolvimento do subsistema de recolha e armazenamento de dados, que coleta e armazena num cartão SD os dados dos sensores selecionados, prossegue com outro estudante belga - Mathias van Flieberge. O objetivo desta tese é, por um lado, implementar o subsistema de telemetria e de configuração na unidade de controle mestre e, por outro lado, refinar e implementar, conjuntamente com Mathias van Flieberge, o protocolo de nível de aplicação projetado. Em particular, a unidade de controlo mestre deve processar e atribuir prioridades às mensagens recebidas da estacão base, solicitar dados à unidade de controlo escrava e difundir mensagens com informação de posição e condições de vento e água no modo de regata. Enquanto que a comunicação entre a unidade de controlo mestre e a estacão base e a unidade de controlo mestre e os barcos é sem fios, a unidade de controlo mestre e a unidade de controlo escrava comunicam através de uma ligação série. A bóia tem atualmente duas limitações: (i) a carga máxima é de 40 kg; e (ii) apenas pode ser utilizada em rios ou próximo da costa dada à limitação de distância imposta pela técnica de comunicação sem fios escolhida.

Análise de desempenho de algoritmos de otimização para extração de parâmetros em modelos semicondutores de potência

Apresenta-se nesta tese uma revisão da literatura sobre a modelação de semicondutores de potência baseada na física e posterior análise de desempenho de dois métodos estocásticos, Particle Swarm Optimizaton (PSO) e Simulated Annealing (SA), quando utilizado para identificação eficiente de parâmetros de modelos de dispositivos semicondutores de potência, baseado na física. O conhecimento dos valores destes parâmetros, para cada dispositivo, é fundamental para uma simulação precisa do comportamento dinâmico do semicondutor. Os parâmetros são extraídos passo-a-passo durante simulação transiente e desempenham um papel relevante. Uma outra abordagem interessante nesta tese relaciona-se com o facto de que nos últimos anos, os métodos de modelação para dispositivos de potência têm emergido, com alta precisão e baixo tempo de execução baseado na Equação de Difusão Ambipolar (EDA) para díodos de potência e implementação no MATLAB numa estratégia de optimização formal. A equação da EDA é resolvida numericamente sob várias condições de injeções e o modelo é desenvolvido e implementado como um subcircuito no simulador IsSpice. Larguras de camada de depleção, área total do dispositivo, nível de dopagem, entre outras, são alguns dos parâmetros extraídos do modelo. Extração de parâmetros é uma parte importante de desenvolvimento de modelo. O objectivo de extração de parâmetros e otimização é determinar tais valores de parâmetros de modelo de dispositivo que minimiza as diferenças entre um conjunto de características medidas e resultados obtidos pela simulação de modelo de dispositivo. Este processo de minimização é frequentemente chamado de ajuste de características de modelos para dados de medição. O algoritmo implementado, PSO é uma técnica de heurística de otimização promissora, eficiente e recentemente proposta por Kennedy e Eberhart, baseado no comportamento social. As técnicas propostas são encontradas para serem robustas e capazes de alcançar uma solução que é caracterizada para ser precisa e global. Comparada com algoritmo SA já realizada, o desempenho da técnica proposta tem sido testado utilizando dados experimentais para extrair parâmetros de dispositivos reais das características I-V medidas. Para validar o modelo, comparação entre resultados de modelo desenvolvido com um outro modelo já desenvolvido são apresentados.