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.

A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium conditions

The container loading problem (CLP) is a combinatorial optimization problem for the spatial arrangement of cargo inside containers so as to maximize the usage of space. The algorithms for this problem are of limited practical applicability if real-world constraints are not considered, one of the most important of which is deemed to be stability. This paper addresses static stability, as opposed to dynamic stability, looking at the stability of the cargo during container loading. This paper proposes two algorithms. The first is a static stability algorithm based on static mechanical equilibrium conditions that can be used as a stability evaluation function embedded in CLP algorithms (e.g. constructive heuristics, metaheuristics). The second proposed algorithm is a physical packing sequence algorithm that, given a container loading arrangement, generates the actual sequence by which each box is placed inside the container, considering static stability and loading operation efficiency constraints.

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%.

Reorganização dos Componentes Neuromotores do Tronco e Membro Superior - Importância da Estabilidade Proximal na Mobilidade Distal durante o Movimento de Alcance, após AVE

Introdução: A função do membro superior (MS), é uma componente fundamental para autonomia dos indivíduos, sendo essencial no movimento de alcance. Após acidente vascular encefálico (AVE), os indivíduos apresentam comprometimento deste movimento. Objetivo(s): O presente estudo teve como objetivo descrever a reorganização do controlo postural do tronco durante o movimento de alcance, em indivíduos com alterações neuromotoras decorrentes de um acidente vascular encefálico, face à aplicação de um programa de intervenção baseado nos princípios do Conceito de Bobath. Metodologia: Estudo de série de casos de indivíduos com alterações neuromotoras decorrentes de AVE, os indivíduos foram sujeitos a dois momentos de avaliação distintos o primeiro (M0) prévio ao plano de intervenção e o segundo (M1), após a implementação do plano de intervenção segundo a abordagem baseada nos princípios do Conceito de Bobath que teve a duração de 12 semanas, através do registo observacional, da utilização do Software de Avaliação Postural (SAPO) para analisar o deslocamento anterior do tronco e simetria entre tronco e cintura escapular do lado ipsilesional e contralesional. Avaliou-se também o comprometimento motor do MS através da Reach Performance Test. Resultados:. A análise do SAPO, na posição de sentado observam-se mudanças quer na vista posterior quer nas laterais, indicando uma diminuição deslocamento anterior do tronco entre M0-M1. Foi ainda possível observar que os indivíduos apresentaram uma melhor extensão linear do tronco na posição inicial em M1 comparativamente a M0. Conclusão: Os indivíduos em estudo evidenciaram um menor deslocamento anterior do tronco no movimento de alcance na posição de sentado, após uma intervenção de fisioterapia baseada nos princípios do conceito de Bobath.

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.

Osteoporotic hip fractures: Bisphosphonates sales and observed turning point in trend. A population-based retrospective study

The aim is to examine the temporal trends of hip fracture incidence in Portugal by sex and age groups, and explore the relation with anti-osteoporotic medication. From the National Hospital Discharge Database, we selected from 1st January 2000 to 31st December 2008, 77,083 hospital admissions (77.4% women) caused by osteoporotic hip fractures (low energy, patients over 49 years-age), with diagnosis codes 820.x of ICD 9-CM. The 2001 Portuguese population was used as standard to calculate direct age-standardized incidence rates (ASIR) (100,000 inhabitants). Generalized additive and linear models were used to evaluate and quantify temporal trends of age specific rates (AR), by sex. We identified 2003 as a turning point in the trend of ASIR of hip fractures in women. After 2003, the ASIR in women decreased on average by 10.3 cases/100,000 inhabitants, 95% CI (− 15.7 to − 4.8), per 100,000 anti-osteoporotic medication packages sold. For women aged 65–69 and 75–79 we identified the same turning point. However, for women aged over 80, the year 2004 marked a change in the trend, from an increase to a decrease. Among the population aged 70–74 a linear decrease of incidence rate (95% CI) was observed in both sexes, higher for women: − 28.0% (− 36.2 to − 19.5) change vs − 18.8%, (− 32.6 to − 2.3). The abrupt turning point in the trend of ASIR of hip fractures in women is compatible with an intervention, such as a medication. The trends were different according to gender and age group, but compatible with the pattern of bisphosphonates sales.