Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Probability Distribution of the Eigenvalues of the Random String Equation

The probability distribution of the eigenvalues of a second-order stochastic boundary value problem is considered. The solution is characterized in terms of the zeros of an associated initial value problem. It is further shown that the probability distribution is related to the solution of a first-order nonlinear stochastic differential equation. Solutions of this equation based on the theory of Markov processes and also on the closure approximation are presented. A string with stochastic mass distribution is considered as an example for numerical work. The theoretical probability distribution functions are compared with digital simulation results. The comparison is found to be reasonably good.

Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems

In this paper, a novel genetic algorithm is developed by generating artificial chromosomes with probability control to solve the machine scheduling problems. Generating artificial chromosomes for Genetic Algorithm (ACGA) is closely related to Evolutionary Algorithms Based on Probabilistic Models (EAPM). The artificial chromosomes are generated by a probability model that extracts the gene information from current population. ACGA is considered as a hybrid algorithm because both the conventional genetic operators and a probability model are integrated. The ACGA proposed in this paper, further employs the ``evaporation concept'' applied in Ant Colony Optimization (ACO) to solve the permutation flowshop problem. The ``evaporation concept'' is used to reduce the effect of past experience and to explore new alternative solutions. In this paper, we propose three different methods for the probability of evaporation. This probability of evaporation is applied as soon as a job is assigned to a position in the permutation flowshop problem. Experimental results show that our ACGA with the evaporation concept gives better performance than some algorithms in the literature.

Rocking response of rectangular rigid blocks under random noise base excitations

The response of a rigid rectangular block resting on a rigid foundation and acted upon simultaneously by a horizontal and a vertical random white-noise excitation is considered. In the equation of motion, the energy dissipation is modeled through a viscous damping term. Under the assumption that the body does not topple, the steady-state joint probability density function of the rotation and the rotational velocity is obtained using the Fokker-Planck equation approach. Closed form solution is obtained for a specific combination of system parameters. A more general but approximate solution to the joint probability density function based on the method of equivalent non-linearization is also presented. Further, the problem of overturning of the block is approached in the framework of the diffusion methods for first passage failure studies. The overturning of the block is deemed incipient when the response trajectories in the phase plane cross the separatrix of the conservative unforced system. Expressions for the moments of first passage time are obtained via a series solution to the governing generalized Pontriagin-Vitt equations. Numerical results illustra- tive of the theoretical solutions are presented and their validity is examined through limited amount of digital simulations.

Nature inspired optimization techniques for the design optimization of laminated composite structures using failure criteria

The design optimization of laminated composites using naturally inspired optimization techniques such as vector evaluated particle swarm optimization (VEPSO) and genetic algorithms (GA) are used in this paper. The design optimization of minimum weight of the laminated composite is evaluated using different failure criteria. The failure criteria considered are maximum stress (MS), Tsai-Wu (TW) and failure mechanism based (FMB) failure criteria. Minimum weight of the laminates are obtained for different failure criteria using VEPSO and GA for different combinations of loading. From the study it is evident that VEPSO and GA predict almost the same minimum weight of the laminate for the given loading. Comparison of minimum weight of the laminates by different failure criteria differ for some loading combinations. The comparison shows that FMBFC provide better results for all combinations of loading. (C) 2010 Elsevier Ltd. All rights reserved.

A finite element analysis of dynamic fracture initiation by ductile failure mechanisms in a 4340 steel

In some recent dropweight impact experiments [5] with pre-notched bend specimens of 4340 steel, it was observed that considerable crack tunneling occurred in the interior of the specimen prior to gross fracture initiation on the free surfaces. The final failure of the side ligaments happened because of shear lip formation. The tunneled region is characterized by a flat, fibrous fracture surface. In this paper, the experiments of [5] (corresponding to 5 m/s impact speed) are analyzed using a plane strain, dynamic finite element procedure. The Gurson constitutive model that accounts for the ductile failure mechanisms of micro-void nucleation, growth and coalescence is employed. The time at which incipient failure was observed near the notch tip in this computation, and the value of the dynamic J-integral, J d, at this time, compare reasonably well with experiments. This investigation shows that J-controlled stress and deformation fields are established near the notch tip whenever J d , increases with time. Also, it is found that the evolution of micro-mechanical quantities near the notch root can be correlated with the time variation of J d .The strain rate and the adiabatic temperature rise experienced at the notch root are examined. Finally, spatial variations of stresses and deformations are analyzed in detail.

Minimum weight design of fiber-reinforced laminated composite structures with maximum stress and Tsai-Wu failure criteria

In this article, a minimum weight design of carbon/epoxy laminates is carried out using genetic algorithms. New failure envelopes have been developed by the combination of two commonly used phenomenological failure criteria, namely Maximum Stress (MS) and Tsai-Wu (TW) are used to obtain the minimum weight of the laminate. These failure envelopes are the most conservative failure envelope (MCFE) and the least conservative failure envelope (LCFE). Uniaxial and biaxial loading conditions are considered for the study and the differences in the optimal weight of the laminate are compared for the MCFE and LCFE. The MCFE can be used for design of critical load-carrying composites, while the LCFE could be used for the design of composite structures where weight reduction is much more important than safety such as unmanned air vehicles.

Performability of automated manufacturing systems with centralized material handling

We present a framework for performance evaluation of manufacturing systems subject to failure and repair. In particular, we determine the mean and variance of accumulated production over a specified time frame and show the usefulness of these results in system design and in evaluating operational policies for manufacturing systems. We extend this analysis for lead time as well. A detailed performability study is carried out for the generic model of a manufacturing system with centralized material handling. Several numerical results are presented, and the relevance of performability analysis in resolving system design issues is highlighted. Specific problems addressed include computing the distribution of total production over a shift period, determining the shift length necessary to deliver a given production target with a desired probability, and obtaining the distribution of Manufacturing Lead Time, all in the face of potential subsystem failures.

Degradation and Failure of Field Emitting Carbon Nanotube Arrays

It has been observed experimentally that the collective field emission from an array of Carbon Nanotubes (CNTs) exhibits fluctuation and degradation, and produces thermal spikes, resulting in electro-mechanical fatigue and failure of CNTs. Based on a new coupled multiphysics model incorporating the electron-phonon transport and thermo-electrically activated breakdown, a novel method for estimating accurately the lifetime of CNT arrays has been developed in this paper. The main results are discussed for CNT arrays during the field emission process. It is shown that the time-to-failure of CNT arrays increases with the decrease in the angle of tip orientation. This observation has important ramifications for such areas as biomedical X-ray devices using patterned films of CNTs.

Passive pressure coefficients, critical failure surface and its kinematic admissibility

Using a combination of a logarithmic spiral and a straight line as a failure surface, comprehensive charts have been developed to determine the passive earth pressure coefficients and the positions of the critical failure surface for positive as well as negative wall friction angles. Translational movement of the wall has been examined in detail, considering the soil as either an associated flow dilatant material or a non-dilatant material, to determine the kinematic admissibility of the limit equilibrium solutions.

Influence of foam/glass-epoxy interface on the macroscopic compressive failure features

The effect on the macroscopic compressive failure features of introduction of two flexible foam layers, either together at mid-region or separately at two locations that are away from the midregion, into a glass-epoxy (G-E) system is studied in this work. In this experimental approach an attempt to look at the possible influence the foam/G-E interface region has on the way the materials respond to compressive loading is made by involving an analyses of macrofractographic features. While foam-free samples fail by extensive ear formation and separation nearer to the mid-region, the foam bearing ones display pronounced interface separation. The positioning of the foam sheet(s) has a bearing on the failure features.

Regarding the effect of aging heat treatment on the failure behaviour of a SiC reinforced Al based metal matrix composite

In the present study, 6061 Al metallic matrix was reinforced by 12.2 wt% df SiC particulates using liquid metallurgy route. The composite material thus obtained was extruded and characterized in the as-solutionized and peak aged conditions in order to delineate the effect of aging associated precipitation of secondary phases on the tensile fracture behavior of the composite samples. The results' of microstructural characterization studies carried out using scanning electron microscope revealed the increased presence of precipitated secondary phases in the metallic matrix and a more pronounced interfacial segregation of alloying elements in case of peak aged samples when compared to the as-solutionized samples. The results of the fractographic studies conducted on the as-solutionized samples revealed that the failure was dominated by the SiC particulates cracking while for the peak aged samples the fracture surface revealed a comparatively more pronounced SiC/6061 Al debonding and reduced SiC particulates cracking. This change in the failure behavior was rationalized in terms of embrittlement of the interfacial region brought about by the aging heat treatment and is correlated, in addition, with the mechanical properties of the composite samples in as-solutionized and peak aged conditions.

Studies on compressive failure features in syntactic foam material

Syntactic foam made by mechanical mixing of glass hollow spheres in epoxy resin matrix is characterized for compressive properties in the present study. Volume fraction of hollow spheres in the syntactic foam under investigation is kept at 67.8%. Effect of specimen aspect ratio on failure behavior and stress-strain curve of the material is highlighted. Considerable differences are noted in the macroscopic fracture features of the specimen and the stress-strain curve with the variation in specimen aspect ratio, although compressive yield strength values were within a narrow range. Post compression test scanning electron microscopic observations coupled with the macroscopic observations taken during the test helped in explaining the deviation in specimen behavior and in gathering support for the proposed arguments.

Reliability Based Design Optimization for Internal Stability of Reinforced Soil Structures Using Pseudo‐Static Method

Seismic design of reinforced soil structures involves many uncertainties that arise from the backfill soil properties and tensile strength of the reinforcement which is not addressed in current design guidelines. This paper highlights the significance of variability in the internal stability assessment of reinforced soil structures. Reliability analysis is applied to estimate probability of failure and pseudo‐static approach has been used for the calculation of the tensile strength and length of the reinforcement needed to maintain the internal stability against tension and pullout failures. Logarithmic spiral failure surface has been considered in conjunction with the limit equilibrium method. Two modes of failure namely, tension failure and pullout failure have been considered. The influence of variations of the backfill soil friction angle, the tensile strength of reinforcement, horizontal seismic acceleration on the reliability index against tension failure and pullout failure of reinforced earth structure have been discussed.