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.

A genetic algorithm for the job shop scheduling with a new local search using Monte Carlo method

This paper presents a methodology for applying scheduling algorithms using Monte Carlo simulation. The methodology is based on a decision support system (DSS). The proposed methodology combines a genetic algorithm with a new local search using Monte Carlo Method. The methodology is applied to 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 methodology is tested on a set of standard instances taken from the literature and compared with others. The computation results validate the effectiveness of the proposed methodology. The DSS developed can be utilized in a common industrial or construction environment.

A two-level genetic algorithm for the multi-mode resource-constrained project scheduling problem

This paper presents a genetic algorithm for the multimode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. The objective function is the minimization of the construction project completion time. To solve the problem, is applied a two-level genetic algorithm, which makes use of two separate levels and extend the parameterized schedule generation scheme by introducing an improvement procedure. It is evaluated the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that this approach is a competitive algorithm.

Implementation of fractional-order electromagnetic potential through a genetic algorithm

Several phenomena present in electrical systems motivated the development of comprehensive models based on the theory of fractional calculus (FC). Bearing these ideas in mind, in this work are applied the FC concepts to define, and to evaluate, the electrical potential of fractional order, based in a genetic algorithm optimization scheme. The feasibility and the convergence of the proposed method are evaluated.

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.

Dynamical modelling of a genetic algorithm

This work addresses the signal propagation and the fractional-order dynamics during the evolution of a genetic algorithm (GA). In order to investigate the phenomena involved in the GA population evolution, the mutation is exposed to excitation perturbations during some generations and the corresponding fitness variations are evaluated. Three distinct fitness functions are used to study their influence in the GA dynamics. The input and output signals are studied revealing a fractional-order dynamic evolution, characteristic of a long-term system memory.

Estudo de uma instalação de climatização adiabática

Esta dissertação teve como objetivo o estudo de uma central de climatização adiabática, que tem como finalidade controlar a temperatura e a humidade de um salão com equipamentos de torcedura e de bobinagem, pertencente à Continental - ITA. Foi realizado um levantamento de dados relativamente à temperatura e humidade interior e exterior do referido salão. Verificou-se que estes parâmetros não estavam dentro dos valores ótimos desejados, 26 ± 1˚C e 50 ± 5%, e por isso foi necessário estimar as necessidades nominais de arrefecimento. Este valor foi determinado a partir do Regulamento das Características de Comportamento Térmico dos Edifícios (RCCTE), obtendo-se o valor de 79 kWh/m2.˚C. No sentido de avaliar se as centrais de climatização instaladas no salão em estudo satisfaziam estas necessidades, calcularam-se as suas capacidades de arrefecimento obtendo-se um valor máximo de 64 kWh/m2.˚C. Paralelamente a este estudo, foi calculada a eficiência de humidificação para cada central nos meses de março e setembro. Os valores obtidos foram oscilantes obtendo-se um valor máximo de 100% em setembro. Este fato deve-se à temperatura exterior neste mês ser mais alta e, por consequência, a eficiência de humidificação da central é maior, pois a quantidade de água que o ar pode conter na sua composição é também mais elevada. Com o objetivo de colmatar a diferença entre as necessidades nominais de arrefecimento e a capacidade de arrefecimento das centrais, foram analisadas algumas soluções que, a serem implementadas, poderiam ajudar na poupança energética. Uma dessas soluções era a substituição do sistema atual de humidificação por um sistema mais eficiente de alta pressão. Com o estudo económico deste investimento obteve-se um período de retorno de dois anos. Foram ainda apresentados mais dois investimentos onde foi alterado o sistema de controlo automático existente, obtendo-se para um, dois anos de período de retorno e para o outro três anos e meio.

Project, modelling and simulation of air stripping columns for the treatment of groundwater contaminated with volatile organic compounds

Volatile organic compounds are a common source of groundwater contamination that can be easily removed by air stripping in columns with random packing and using a counter-current flow between the phases. This work proposes a new methodology for the column design for any particular type of packing and contaminant avoiding the necessity of a pre-defined diameter used in the classical approach. It also renders unnecessary the employment of the graphical Eckert generalized correlation for pressure drop estimates. The hydraulic features are previously chosen as a project criterion and only afterwards the mass transfer phenomena are incorporated, in opposition to conventional approach. The design procedure was translated into a convenient algorithm using C++ as programming language. A column was built in order to test the models used either in the design or in the simulation of the column performance. The experiments were fulfilled using a solution of chloroform in distilled water. Another model was built to simulate the operational performance of the column, both in steady state and in transient conditions. It consists in a system of two partial non linear differential equations (distributed parameters). Nevertheless, when flows are steady, the system became linear, although there is not an evident solution in analytical terms. In steady state the resulting system of ODE can be solved, allowing for the calculation of the concentration profile in both phases inside the column. In transient state the system of PDE was numerically solved by finite differences, after a previous linearization.

NoC contention analysis using a branch-and-prune algorithm

“Many-core” systems based on a Network-on-Chip (NoC) architecture offer various opportunities in terms of performance and computing capabilities, but at the same time they pose many challenges for the deployment of real-time systems, which must fulfill specific timing requirements at runtime. It is therefore essential to identify, at design time, the parameters that have an impact on the execution time of the tasks deployed on these systems and the upper bounds on the other key parameters. The focus of this work is to determine an upper bound on the traversal time of a packet when it is transmitted over the NoC infrastructure. Towards this aim, we first identify and explore some limitations in the existing recursive-calculus-based approaches to compute the Worst-Case Traversal Time (WCTT) of a packet. Then, we extend the existing model by integrating the characteristics of the tasks that generate the packets. For this extended model, we propose an algorithm called “Branch and Prune” (BP). Our proposed method provides tighter and safe estimates than the existing recursive-calculus-based approaches. Finally, we introduce a more general approach, namely “Branch, Prune and Collapse” (BPC) which offers a configurable parameter that provides a flexible trade-off between the computational complexity and the tightness of the computed estimate. The recursive-calculus methods and BP present two special cases of BPC when a trade-off parameter is 1 or ∞, respectively. Through simulations, we analyze this trade-off, reason about the implications of certain choices, and also provide some case studies to observe the impact of task parameters on the WCTT estimates.

Step count algorithm adapted to indoor localization

This paper presents a step count algorithm designed to work in real-time using low computational power. This proposal is our first step for the development of an indoor navigation system, based on Pedestrian Dead Reckoning (PDR). We present two approaches to solve this problem and compare them based in their error on step counting, as well as, the capability of their use in a real time system.

Traveled Distance Estimation Algorithm for Indoor Localization

This paper presents an ankle mounted Inertial Navigation System (INS) used to estimate the distance traveled by a pedestrian. This distance is estimated by the number of steps given by the user. The proposed method is based on force sensors to enhance the results obtained from an INS. Experimental results have shown that, depending on the step frequency, the traveled distance error varies between 2.7% and 5.6%.

Domestic Consumption Simulation and Management Using a Continuous Consumption Management and Optimization Algorithm

The recent changes concerning the consumers’ active participation in the efficient management of load devices for one’s own interest and for the interest of the network operator, namely in the context of demand response, leads to the need for improved algorithms and tools. A continuous consumption optimization algorithm has been improved in order to better manage the shifted demand. It has been done in a simulation and user-interaction tool capable of being integrated in a multi-agent smart grid simulator already developed, and also capable of integrating several optimization algorithms to manage real and simulated loads. The case study of this paper enhances the advantages of the proposed algorithm and the benefits of using the developed simulation and user interaction tool.

A Learning Algorithm and System Approach to Address Exceptional Events in Domestic Consumption Management

The integration of the Smart Grid concept into the electric grid brings to the need for an active participation of small and medium players. This active participation can be achieved using decentralized decisions, in which the end consumer can manage loads regarding the Smart Grid needs. The management of loads must handle the users’ preferences, wills and needs. However, the users’ preferences, wills and needs can suffer changes when faced with exceptional events. This paper proposes the integration of exceptional events into the SCADA House Intelligent Management (SHIM) system developed by the authors, to handle machine learning issues in the domestic consumption context. An illustrative application and learning case study is provided in this paper.

Video-­‐monitorization system for a realistic driving simulator

Nos últimos anos, o ISEP em colaboração com a FEUP e outras Universidades, criou um simulador realista de condução chamado DRIS, que tem como objectivo ajudar em trabalhos de investigação de diferentes áreas, como engenharia civil, computação gráfica, psicologia, educação, etc. O resultado deste trabalho pretende ajudar os profissionais a analisarem os dados recolhidos em cada experiência de condução, a fim de permitir o estudo das reações do motorista em diferentes obstáculos durante um percurso. O simulador DRIS é constituído por uma tela branca, onde os ambientes de simulação são projetados; um carro real, onde é feita a experiência de condução e quatro câmaras colocadas no carro. Destas quatro câmaras, três estão dentro do carro e uma fora do carro. Cada câmara está focada estrategicamente, em partes críticas da condução: a estrada, o motorista, os pedais e os controles (mudança de marcha, volante, os comandos do limpador, etc). Cada uma das câmaras grava um vídeo, que é guardado em um computador colocado em uma das salas de controlo, dentro do Laboratório de Análise de Tráfego na FEUP. Além disso, um arquivo de texto é guardado no mesmo computador. Este arquivo de texto contém algumas informações sobre a experiência do motorista, como as coordenadas do carro, a velocidade do carro, o tempo, etc O trabalho desta Tese surge com a finalidade de melhorar a forma de os profissionais analisar e interpretar os dados recolhidos a partir de uma experiência de condução no DRIS. Para o efeito, foi criado um sistema de vídeo-­‐monitorização, que consiste em uma aplicação de vídeo, que permite a visualização de quatro vídeos simultaneamente, e ler um arquivo de texto, que contém todos os dados recolhidos na experiência. Ambos (vídeo e texto) têm de estar sincronizados com o mesmo tempo de forma a permitir ao utilizador, navegar backward e forward com a ajuda de um cursor. Além disso, como qualquer reprodutor de vídeo básico, contém alguns botões para controlar o status do vídeo (Play, Stop, Pause) e permiti que os profissionais analisem com detalhe os dados dos quatro vídeos. Aproveitando os avanços no desenvolvimento de software, a aplicação foi feita em C++ usando a biblioteca Qt, em ambiente de desenvolvimento integrado do Qt Creator, o que tornou mais fácil a implementação. No fim deste relatório (capítulo 4) é anexado um manual do usuário, a fim de explicar e ajudar os profissionais a usar a aplicação.