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.

Estudo e proposta de algoritmo para a minimização do corte de eólica no contexto de uma análise custo-benefício multicritério

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia Electrotécnica Ramo de Energia

Otimização de problemas multimodais usando meta-heurísticas evolutivas

Pós-graduação em Engenharia Elétrica - FEIS

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.

The genome of the leaf-cutting ant Acromyrmex echinatior suggests key adaptations to advanced social life and fungus farming.

We present a high-quality (>100× depth) Illumina genome sequence of the leaf-cutting ant Acromyrmex echinatior, a model species for symbiosis and reproductive conflict studies. We compare this genome with three previously sequenced genomes of ants from different subfamilies and focus our analyses on aspects of the genome likely to be associated with known evolutionary changes. The first is the specialized fungal diet of A. echinatior, where we find gene loss in the ant's arginine synthesis pathway, loss of detoxification genes, and expansion of a group of peptidase proteins. One of these is a unique ant-derived contribution to the fecal fluid, which otherwise consists of "garden manuring" fungal enzymes that are unaffected by ant digestion. The second is multiple mating of queens and ejaculate competition, which may be associated with a greatly expanded nardilysin-like peptidase gene family. The third is sex determination, where we could identify only a single homolog of the feminizer gene. As other ants and the honeybee have duplications of this gene, we hypothesize that this may partly explain the frequent production of diploid male larvae in A. echinatior. The fourth is the evolution of eusociality, where we find a highly conserved ant-specific profile of neuropeptide genes that may be related to caste determination. These first analyses of the A. echinatior genome indicate that considerable genetic changes are likely to have accompanied the transition from hunter-gathering to agricultural food production 50 million years ago, and the transition from single to multiple queen mating 10 million years ago.

An evolutionary algorithm for the one-dimensional cutting stock problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

A genetic algorithm for the one-dimensional cutting stock problem with setups

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method. Journal of the Operational Research Society (2012) 63, 183-200. doi: 10.1057/jors.2011.6 Published online 17 August 2011

A novel algorithm of posture best fit based on key characteristics for large components assembly

Measurement and variation control of geometrical Key Characteristics (KCs), such as flatness and gap of joint faces, coaxiality of cabin sections, is the crucial issue in large components assembly from the aerospace industry. Aiming to control geometrical KCs and to attain the best fit of posture, an optimization algorithm based on KCs for large components assembly is proposed. This approach regards the posture best fit, which is a key activity in Measurement Aided Assembly (MAA), as a two-phase optimal problem. In the first phase, the global measurement coordinate system of digital model and shop floor is unified with minimum error based on singular value decomposition, and the current posture of components being assembly is optimally solved in terms of minimum variation of all reference points. In the second phase, the best posture of the movable component is optimally determined by minimizing multiple KCs' variation with the constraints that every KC respectively conforms to its product specification. The optimal models and the process procedures for these two-phase optimal problems based on Particle Swarm Optimization (PSO) are proposed. In each model, every posture to be calculated is modeled as a 6 dimensional particle (three movement and three rotation parameters). Finally, an example that two cabin sections of satellite mainframe structure are being assembled is selected to verify the effectiveness of the proposed approach, models and algorithms. The experiment result shows the approach is promising and will provide a foundation for further study and application. © 2013 The Authors.

Economic and Environmental Optimization of Ornamental Stone Block Cutting with a 3D Algorithm

This thesis focuses on finding the optimum block cutting dimensions in terms of the environmental and economic factors by using a 3D algorithm for a limestone quarry in Foggia, Italy. The environmental concerns of quarrying operations are mainly: energy consumption, material waste, and pollution. The main economic concerns are the block recovery, the selling prices, and the production costs. Fractures adversely affect the block recovery ratio. With a fracture model, block production can be optimized. In this research, the waste volume produced by quarrying was minimised to increase the recovery ratio and ensure economic benefits. SlabCutOpt is a software developed at DICAM–University of Bologna for block cutting optimization which tests different cutting angles on the x-y-z planes to offer up alternative cutting methods. The program tests several block sizes and outputs the optimal result for each entry. By using SlabCutOpt, ten different block dimensions were analysed, the results indicated the maximum number of non-intersecting blocks for each dimension. After analysing the outputs, the block named number 1 with the dimensions ‘1mx1mx1m’ had the highest recovery ratio as 43% and the total Relative Money Value (RMV) with a value of 22829. Dimension number 1, also had the lowest waste volume, with a value of 3953.25 m3, for the total bench. For cutting the total bench volume of 6932.25m3, the diamond wire cutter had the lowest dust emission values for the block with the dimension ‘2mx2mx2m’, with a value of 24m3. When compared with the Eco-Label standards, block dimensions having surface area values lower than 15m2, were found to fit the natural resource waste criteria of the label, as the threshold required 25% of minimum recovery [1]. Due to the relativity of production costs, together with the Eco-Label threshold, the research recommends the selection of the blocks with a surface area value between 6m2 and 14m2.

Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

Reliability concepts applied to cutting tool change time

This paper presents a reliability-based analysis for calculating critical tool life in machining processes. It is possible to determine the running time for each tool involved in the process by obtaining the operations sequence for the machining procedure. Usually, the reliability of an operation depends on three independent factors: operator, machine-tool and cutting tool. The reliability of a part manufacturing process is mainly determined by the cutting time for each job and by the sequence of operations, defined by the series configuration. An algorithm is presented to define when the cutting tool must be changed. The proposed algorithm is used to evaluate the reliability of a manufacturing process composed of turning and drilling operations. The reliability of the turning operation is modeled based on data presented in the literature, and from experimental results, a statistical distribution of drilling tool wear was defined, and the reliability of the drilling process was modeled. (C) 2010 Elsevier Ltd. All rights reserved.

A monolithic smoothing-gap algorithm for contact-impact based on the signed distance function

A new algorithm has been developed for smoothing the surfaces in finite element formulations of contact-impact. A key feature of this method is that the smoothing is done implicitly by constructing smooth signed distance functions for the bodies. These functions are then employed for the computation of the gap and other variables needed for implementation of contact-impact. The smoothed signed distance functions are constructed by a moving least-squares approximation with a polynomial basis. Results show that when nodes are placed on a surface, the surface can be reproduced with an error of about one per cent or less with either a quadratic or a linear basis. With a quadratic basis, the method exactly reproduces a circle or a sphere even for coarse meshes. Results are presented for contact problems involving the contact of circular bodies. Copyright (C) 2002 John Wiley Sons, Ltd.

Automated traffic route identification through the shared nearest neighbour algorithm

Many organisations need to extract useful information from huge amounts of movement data. One example is found in maritime transportation, where the automated identification of a diverse range of traffic routes is a key management issue for improving the maintenance of ports and ocean routes, and accelerating ship traffic. This paper addresses, in a first stage, the research challenge of developing an approach for the automated identification of traffic routes based on clustering motion vectors rather than reconstructed trajectories. The immediate benefit of the proposed approach is to avoid the reconstruction of trajectories in terms of their geometric shape of the path, their position in space, their life span, and changes of speed, direction and other attributes over time. For clustering the moving objects, an adapted version of the Shared Nearest Neighbour algorithm is used. The motion vectors, with a position and a direction, are analysed in order to identify clusters of vectors that are moving towards the same direction. These clusters represent traffic routes and the preliminary results have shown to be promising for the automated identification of traffic routes with different shapes and densities, as well as for handling noise data.

HIV rapid testing as a key strategy for prevention of mother-to-child transmission in Brazil

OBJECTIVE: To assess the feasibility of HIV rapid testing for pregnant women at maternity hospital admission and of subsequent interventions to reduce perinatal HIV transmission. METHODS: Study based on a convenience sample of women unaware of their HIV serostatus when they were admitted to delivery in public maternity hospitals in Rio de Janeiro and Porto Alegre, Brazil, between March 2000 and April 2002. Women were counseled and tested using the Determine HIV1/2 Rapid Test. HIV infection was confirmed using the Brazilian algorithm for HIV infection diagnosis. In utero transmission of HIV was determined using HIV-DNA-PCR. There were performed descriptive analyses of sociodemographic data, number of previous pregnancies and abortions, number of prenatal care visits, timing of HIV testing, HIV rapid test result, neonatal and mother-to-child transmission interventions, by city studied. RESULTS: HIV prevalence in women was 6.5% (N=1,439) in Porto Alegre and 1.3% (N=3.778) in Rio de Janeiro. In Porto Alegre most of women were tested during labor (88.7%), while in Rio de Janeiro most were tested in the postpartum (67.5%). One hundred and forty-four infants were born to 143 HIV-infected women. All newborns but one in each city received at least prophylaxis with oral zidovudine. It was possible to completely avoid newborn exposure to breast milk in 96.8% and 51.1% of the cases in Porto Alegre and Rio de Janeiro, respectively. Injectable intravenous zidovudine was administered during labor to 68.8% and 27.7% newborns in Porto Alegre and Rio de Janeiro, respectively. Among those from whom blood samples were collected within 48 hours of birth, in utero transmission of HIV was confirmed in 4 cases in Rio de Janeiro (4/47) and 6 cases in Porto Alegre (6/79). CONCLUSIONS: The strategy proved feasible in maternity hospitals in Rio de Janeiro and Porto Alegre. Efforts must be taken to maximize HIV testing during labor. There is a need of strong social support to provide this population access to health care services after hospital discharge.