An integrated scheduling problem of PCB components on sequential pick-and-place machines:mathematical models and heuristic solutions

This paper formulates several mathematical models for determining the optimal sequence of component placements and assignment of component types to feeders simultaneously or the integrated scheduling problem for a type of surface mount technology placement machines, called the sequential pick-andplace (PAP) machine. A PAP machine has multiple stationary feeders storing components, a stationary working table holding a printed circuit board (PCB), and a movable placement head to pick up components from feeders and place them to a board. The objective of integrated problem is to minimize the total distance traveled by the placement head. Two integer nonlinear programming models are formulated first. Then, each of them is equivalently converted into an integer linear type. The models for the integrated problem are verified by two commercial packages. In addition, a hybrid genetic algorithm previously developed by the authors is adopted to solve the models. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total traveling distance.

Integrated component scheduling models for chip shooter machines

This paper focuses on minimizing printed circuit board (PCB) assembly time for a chipshootermachine, which has a movable feeder carrier holding components, a movable X–Y table carrying a PCB, and a rotary turret with multiple assembly heads. The assembly time of the machine depends on two inter-related optimization problems: the component sequencing problem and the feeder arrangement problem. Nevertheless, they were often regarded as two individual problems and solved separately. This paper proposes two complete mathematical models for the integrated problem of the machine. The models are verified by two commercial packages. Finally, a hybrid genetic algorithm previously developed by the authors is presented to solve the model. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total assembly time.

PCB assembly line assignment:a genetic algorithm approach

Purpose – This paper sets out to study a production-planning problem for printed circuit board (PCB) assembly. A PCB assembly company may have a number of assembly lines for production of several product types in large volume. Design/methodology/approach – Pure integer linear programming models are formulated for assigning the product types to assembly lines, which is the line assignment problem, with the objective of minimizing the total production cost. In this approach, unrealistic assignment, which was suffered by previous researchers, is avoided by incorporating several constraints into the model. In this paper, a genetic algorithm is developed to solve the line assignment problem. Findings – The procedure of the genetic algorithm to the problem and a numerical example for illustrating the models are provided. It is also proved that the algorithm is effective and efficient in dealing with the problem. Originality/value – This paper studies the line assignment problem arising in a PCB manufacturing company in which the production volume is high.

Evolutionary neural networks : models and applications

The scaling problems which afflict attempts to optimise neural networks (NNs) with genetic algorithms (GAs) are disclosed. A novel GA-NN hybrid is introduced, based on the bumptree, a little-used connectionist model. As well as being computationally efficient, the bumptree is shown to be more amenable to genetic coding lthan other NN models. A hierarchical genetic coding scheme is developed for the bumptree and shown to have low redundancy, as well as being complete and closed with respect to the search space. When applied to optimising bumptree architectures for classification problems the GA discovers bumptrees which significantly out-perform those constructed using a standard algorithm. The fields of artificial life, control and robotics are identified as likely application areas for the evolutionary optimisation of NNs. An artificial life case-study is presented and discussed. Experiments are reported which show that the GA-bumptree is able to learn simulated pole balancing and car parking tasks using only limited environmental feedback. A simple modification of the fitness function allows the GA-bumptree to learn mappings which are multi-modal, such as robot arm inverse kinematics. The dynamics of the 'geographic speciation' selection model used by the GA-bumptree are investigated empirically and the convergence profile is introduced as an analytical tool. The relationships between the rate of genetic convergence and the phenomena of speciation, genetic drift and punctuated equilibrium arc discussed. The importance of genetic linkage to GA design is discussed and two new recombination operators arc introduced. The first, linkage mapped crossover (LMX) is shown to be a generalisation of existing crossover operators. LMX provides a new framework for incorporating prior knowledge into GAs.Its adaptive form, ALMX, is shown to be able to infer linkage relationships automatically during genetic search.

Genetic and environmentally derived variation in the cell wall composition of miscanthus and implications for thermo-chemical conversion

Fifteen Miscanthus genotypes grown in five locations across Europe were analysed to investigate the influence of genetic and environmental factors on cell wall composition. Chemometric techniques combining near infrared reflectance spectroscopy and conventional chemical analyses were used to construct calibration models for determination of acid detergent lignin, acid detergent fibre, and neutral detergent fibre from sample spectra. The developed equations were shown to predict cell wall components with a good degree of accuracy and significant genetic and environmental variation was identified. The influence of nitrogen and potassium fertiliser on the dry matter yield and cell wall composition of M. x giganteus was investigated. A detrimental affect on feedstock quality was observed to result from application of these inputs which resulted in an overall reduction in concentrations of cell wall components and increased accumulation of ash within the biomass. Pyrolysis-gas chromatography-mass spectrometry and thermo-gravimetric analysis indicates that genotypes other than the commercially cultivated M. x giganteus have potential for use in energy conversion processes and in the bio-refining. The yields and quality parameters of the pyrolysis liquids produced from Miscanthus compared favourably with that produced from SRC willow and produced a more stable pyrolysis liquid with a higher lower heating value. Overall, genotype had a more significant effect on cell wall composition than environment. This indicates good potential for dissection of this trait by QTL analysis and also for plant breeding to produce new genotypes with improved feedstock characteristics for energy conversion.

Genetic risk factors and age-related macular degeneration (AMD)

Age related macular degeneration (AMD) is the leading cause of blindness in individuals older than 65 years of age. It is a multifactorial disorder and identification of risk factors enables individuals to make lifestyle choices that may reduce the risk of disease. Collaboration between geneticists, ophthalmologists, and optometrists suggests that genetic risk factors play a more significant role in AMD than previously thought. The most important genes are associated with immune system modulation and the complement system, e.g., complement factor H (CFH), factor B (CFB), factor C3, and serpin peptidase inhibitor (SERPING1). Genes associated with membrane transport, e.g., ATP-binding cassette protein (ABCR) and voltage-dependent calcium channel gamma 3 (CACNG3), the vascular system, e.g., fibroblast growth factor 2 (FGF2), fibulin-5, lysyl oxidase-like gene (LOXL1) and selectin-P (SELP), and with lipid metabolism, e.g., apolipoprotein E (APOE) and hepatic lipase (LIPC) have also been implicated. In addition, several other genes exhibit some statistical association with AMD, e.g., age-related maculopathy susceptibility protein 2 (ARMS2) and DNA excision repair protein gene (ERCC6) but more research is needed to establish their significance. Modifiable risk factors for AMD should be discussed with patients whose lifestyle and/or family history place them in an increased risk category. Furthermore, calculation of AMD risk using current models should be recommended as a tool for patient education. It is likely that AMD management in future will be increasingly influenced by assessment of genetic risk as such screening methods become more widely available. © 2013 Spanish General Council of Optometry.

Parameter Identification of a Fed-Batch Cultivation of S. Cerevisiae using Genetic Algorithms

Fermentation processes as objects of modelling and high-quality control are characterized with interdependence and time-varying of process variables that lead to non-linear models with a very complex structure. This is why the conventional optimization methods cannot lead to a satisfied solution. As an alternative, genetic algorithms, like the stochastic global optimization method, can be applied to overcome these limitations. The application of genetic algorithms is a precondition for robustness and reaching of a global minimum that makes them eligible and more workable for parameter identification of fermentation models. Different types of genetic algorithms, namely simple, modified and multi-population ones, have been applied and compared for estimation of nonlinear dynamic model parameters of fed-batch cultivation of S. cerevisiae.

Optimization of adaptive traffic signal control with transit signal priority at isolated intersections using parallel genetic algorithms

Optimization of adaptive traffic signal timing is one of the most complex problems in traffic control systems. This dissertation presents a new method that applies the parallel genetic algorithm (PGA) to optimize adaptive traffic signal control in the presence of transit signal priority (TSP). The method can optimize the phase plan, cycle length, and green splits at isolated intersections with consideration for the performance of both the transit and the general vehicles. Unlike the simple genetic algorithm (GA), PGA can provide better and faster solutions needed for real-time optimization of adaptive traffic signal control. ^ An important component in the proposed method involves the development of a microscopic delay estimation model that was designed specifically to optimize adaptive traffic signal with TSP. Macroscopic delay models such as the Highway Capacity Manual (HCM) delay model are unable to accurately consider the effect of phase combination and phase sequence in delay calculations. In addition, because the number of phases and the phase sequence of adaptive traffic signal may vary from cycle to cycle, the phase splits cannot be optimized when the phase sequence is also a decision variable. A "flex-phase" concept was introduced in the proposed microscopic delay estimation model to overcome these limitations. ^ The performance of PGA was first evaluated against the simple GA. The results show that PGA achieved both faster convergence and lower delay for both under- or over-saturated traffic conditions. A VISSIM simulation testbed was then developed to evaluate the performance of the proposed PGA-based adaptive traffic signal control with TSP. The simulation results show that the PGA-based optimizer for adaptive TSP outperformed the fully actuated NEMA control in all test cases. The results also show that the PGA-based optimizer was able to produce TSP timing plans that benefit the transit vehicles while minimizing the impact of TSP on the general vehicles. The VISSIM testbed developed in this research provides a powerful tool to design and evaluate different TSP strategies under both actuated and adaptive signal control. ^

Pre-Clinical Models of Diffuse Intrinsic Pontine Glioma.

Diffuse intrinsic pontine glioma (DIPG) is a rare and incurable brain tumor that arises in the brainstem of children predominantly between the ages of 6 and 8. Its intricate morphology and involvement of normal pons tissue precludes surgical resection, and the standard of care today remains fractionated radiation alone. In the past 30 years, there have been no significant advances made in the treatment of DIPG. This is largely because we lack good models of DIPG and therefore have little biological basis for treatment. In recent years, however, due to increased biopsy and acquisition of autopsy specimens, research is beginning to unravel the genetic and epigenetic drivers of DIPG. Insight gleaned from these studies has led to improvements in approaches to both model these tumors in the lab and to potentially treat them in the clinic. This review will detail the initial strides toward modeling DIPG in animals, which included allograft and xenograft rodent models using non-DIPG glioma cells. Important advances in the field came with the development of in vitro cell and in vivo xenograft models derived directly from autopsy material of DIPG patients or from human embryonic stem cells. Finally, we will summarize the progress made in the development of genetically engineered mouse models of DIPG. Cooperation of studies incorporating all of these modeling systems to both investigate the unique mechanisms of gliomagenesis in the brainstem and to test potential novel therapeutic agents in a preclinical setting will result in improvement in treatments for DIPG patients.

Risk Prediction for Epithelial Ovarian Cancer in 11 United States-Based Case-Control Studies: Incorporation of Epidemiologic Risk Factors and 17 Confirmed Genetic Loci.

Previously developed models for predicting absolute risk of invasive epithelial ovarian cancer have included a limited number of risk factors and have had low discriminatory power (area under the receiver operating characteristic curve (AUC) < 0.60). Because of this, we developed and internally validated a relative risk prediction model that incorporates 17 established epidemiologic risk factors and 17 genome-wide significant single nucleotide polymorphisms (SNPs) using data from 11 case-control studies in the United States (5,793 cases; 9,512 controls) from the Ovarian Cancer Association Consortium (data accrued from 1992 to 2010). We developed a hierarchical logistic regression model for predicting case-control status that included imputation of missing data. We randomly divided the data into an 80% training sample and used the remaining 20% for model evaluation. The AUC for the full model was 0.664. A reduced model without SNPs performed similarly (AUC = 0.649). Both models performed better than a baseline model that included age and study site only (AUC = 0.563). The best predictive power was obtained in the full model among women younger than 50 years of age (AUC = 0.714); however, the addition of SNPs increased the AUC the most for women older than 50 years of age (AUC = 0.638 vs. 0.616). Adapting this improved model to estimate absolute risk and evaluating it in prospective data sets is warranted.

Sampling information, length measurements, DNA alignments, models and phylogenetics trees for Oithona similis s.l.

Traditionally, many small-sized copepod species are considered to be widespread, bipolar or cosmopolitan. However, these large-scale distribution patterns need to be re-examined in view of increasing evidence of cryptic and pseudo-cryptic speciation in pelagic copepods. Here, we present a phylogeographic study of Oithona similis s.l. populations from the Arctic Ocean, the Southern Ocean and its northern boundaries, the North Atlantic and the Mediterrranean Sea. O. similis s.l. is considered as one of the most abundant species in temperate to polar oceans and acts as an important link in the trophic network between the microbial loop and higher trophic levels such as fish larvae. Two gene fragments were analysed: the mitochondrial cytochrome oxidase c subunit I (COI), and the nuclear ribosomal 28S genetic marker. Seven distinct, geographically delimitated, mitochondrial lineages could be identified, with divergences among the lineages ranging from 8 to 24 %, thus representing most likely cryptic or pseudocryptic species within O. similis s.l. Four lineages were identified within or close to the borders of the Southern Ocean, one lineage in the Arctic Ocean and two lineages in the temperate Northern hemisphere. Surprisingly the Arctic lineage was more closely related to lineages from the Southern hemisphere than to the other lineages from the Northern hemisphere, suggesting that geographic proximity is a rather poor predictor of how closely related the clades are on a genetic level. Molecular clock application revealed that the evolutionary history of O. similis s.l. is possibly closely associated with the reorganization of the ocean circulation in the mid Miocene and may be an example of allopatric speciation in the pelagic zone.

Evaluating demographic models for goat domestication using mtDNA sequences

Routes of migration and exchange are important factors in the debate about how the Neolithic transition spread into Europe. Studying the genetic diversity of livestock can help in tracing back some of these past events. Notably, domestic goat (Capra hircus) did not have any wild progenitors (Capra aegagrus) in Europe before their arrival from the Near East. Studies of mitochondrial DNA have shown that the diversity in European domesticated goats is a subset of that in the wild, underlining the ancestral relationship between both populations. Additionally, an ancient DNA study on Neolithic goat remains has indicated that a high level of genetic diversity was already present early in the Neolithic in northwestern Mediterranean sites. We used coalescent simulations and approximate Bayesian computation, conditioned on patterns of modern and ancient mitochondrial DNA diversity in domesticated and wild goats, to test a series of simplified models of the goat domestication process. Specifically, we ask if domestic goats descend from populations that were distinct prior to domestication. Although the models we present require further analyses, preliminary results indicate that wild and domestic goats are more likely to descend from a single ancestral wild population that was managed 11,500 years before present, and that serial founding events characterise the spread of Capra hircus into Europe.

Forward-in-Time, Spatially Explicit Modeling Software to Simulate Genetic Lineages Under Selection

SELECTOR is a software package for studying the evolution of multiallelic genes under balancing or positive selection while simulating complex evolutionary scenarios that integrate demographic growth and migration in a spatially explicit population framework. Parameters can be varied both in space and time to account for geographical, environmental, and cultural heterogeneity. SELECTOR can be used within an approximate Bayesian computation estimation framework. We first describe the principles of SELECTOR and validate the algorithms by comparing its outputs for simple models with theoretical expectations. Then, we show how it can be used to investigate genetic differentiation of loci under balancing selection in interconnected demes with spatially heterogeneous gene flow. We identify situations in which balancing selection reduces genetic differentiation between population groups compared with neutrality and explain conflicting outcomes observed for human leukocyte antigen loci. These results and three previously published applications demonstrate that SELECTOR is efficient and robust for building insight into human settlement history and evolution.

Directional genetic differentiation and relative migration

Understanding the population structure and patterns of gene flow within species is of fundamental importance to the study of evolution. In the fields of population and evolutionary genetics, measures of genetic differentiation are commonly used to gather this information. One potential caveat is that these measures assume gene flow to be symmetric. However, asymmetric gene flow is common in nature, especially in systems driven by physical processes such as wind or water currents. As information about levels of asymmetric gene flow among populations is essential for the correct interpretation of the distribution of contemporary genetic diversity within species, this should not be overlooked. To obtain information on asymmetric migration patterns from genetic data, complex models based on maximum-likelihood or Bayesian approaches generally need to be employed, often at great computational cost. Here, a new simpler and more efficient approach for understanding gene flow patterns is presented. This approach allows the estimation of directional components of genetic divergence between pairs of populations at low computational effort, using any of the classical or modern measures of genetic differentiation. These directional measures of genetic differentiation can further be used to calculate directional relative migration and to detect asymmetries in gene flow patterns. This can be done in a user-friendly web application called divMigrate-online introduced in this study. Using simulated data sets with known gene flow regimes, we demonstrate that the method is capable of resolving complex migration patterns under a range of study designs.

Nonparametric Evaluation of Quantitative Traits in Population-Based Association Studies when the Genetic Model is Unknown

Statistical association between a single nucleotide polymorphism (SNP) genotype and a quantitative trait in genome-wide association studies is usually assessed using a linear regression model, or, in the case of non-normally distributed trait values, using the Kruskal-Wallis test. While linear regression models assume an additive mode of inheritance via equi-distant genotype scores, Kruskal-Wallis test merely tests global differences in trait values associated with the three genotype groups. Both approaches thus exhibit suboptimal power when the underlying inheritance mode is dominant or recessive. Furthermore, these tests do not perform well in the common situations when only a few trait values are available in a rare genotype category (disbalance), or when the values associated with the three genotype categories exhibit unequal variance (variance heterogeneity). We propose a maximum test based on Marcus-type multiple contrast test for relative effect sizes. This test allows model-specific testing of either dominant, additive or recessive mode of inheritance, and it is robust against variance heterogeneity. We show how to obtain mode-specific simultaneous confidence intervals for the relative effect sizes to aid in interpreting the biological relevance of the results. Further, we discuss the use of a related all-pairwise comparisons contrast test with range preserving confidence intervals as an alternative to Kruskal-Wallis heterogeneity test. We applied the proposed maximum test to the Bogalusa Heart Study dataset, and gained a remarkable increase in the power to detect association, particularly for rare genotypes. Our simulation study also demonstrated that the proposed non-parametric tests control family-wise error rate in the presence of non-normality and variance heterogeneity contrary to the standard parametric approaches. We provide a publicly available R library nparcomp that can be used to estimate simultaneous confidence intervals or compatible multiplicity-adjusted p-values associated with the proposed maximum test.