Multi-objective hierarchical genetic algorithms for multilevel redundancy allocation optimization

Multilevel redundancy allocation optimization problems (MRAOPs) occur frequently when attempting to maximize the system reliability of a hierarchical system, and almost all complex engineering systems are hierarchical. Despite their practical significance, limited research has been done concerning the solving of simple MRAOPs. These problems are not only NP hard but also involve hierarchical design variables. Genetic algorithms (GAs) have been applied in solving MRAOPs, since they are computationally efficient in solving such problems, unlike exact methods, but their applications has been confined to single-objective formulation of MRAOPs. This paper proposes a multi-objective formulation of MRAOPs and a methodology for solving such problems. In this methodology, a hierarchical GA framework for multi-objective optimization is proposed by introducing hierarchical genotype encoding for design variables. In addition, we implement the proposed approach by integrating the hierarchical genotype encoding scheme with two popular multi-objective genetic algorithms (MOGAs)—the strength Pareto evolutionary genetic algorithm (SPEA2) and the non-dominated sorting genetic algorithm (NSGA-II). In the provided numerical examples, the proposed multi-objective hierarchical approach is applied to solve two hierarchical MRAOPs, a 4- and a 3-level problems. The proposed method is compared with a single-objective optimization method that uses a hierarchical genetic algorithm (HGA), also applied to solve the 3- and 4-level problems. The results show that a multi-objective hierarchical GA (MOHGA) that includes elitism and mechanism for diversity preserving performed better than a single-objective GA that only uses elitism, when solving large-scale MRAOPs. Additionally, the experimental results show that the proposed method with NSGA-II outperformed the proposed method with SPEA2 in finding useful Pareto optimal solution sets.     

Genetic algorithms for job shop scheduling problems with alternative routings

The purpose of this research is to solve a general job shop problem with alternative machine routings. We consider four performance measures: mean flow time, makespan, maximum lateness, and total absolute deviation from the due dates. We first develop mixed-integer linear programming (MILP) formulations for the problems. The MILP formulations can be used either to compute optimal solutions for small-sized problems or to test the performance of existing heuristic algorithms. In addition, we have developed a genetic algorithm that can be used to generate relatively good solutions quickly. Further, computational experiments have been performed to compare the solution of the MILP formulations with that of existing algorithms.     

A review of the research methodology for the re-entrant scheduling problem

This paper considers the re-entrant scheduling problem, wherein the most remarkable character is that the jobs enter the processing lines more than once. The objective is to provide a comprehensive review which gives the researchers and practitioners an overview of the applicability of techniques in re-entrant scheduling. Few published reviews dealt with this particular kind of problem and only some research regards the re-entrant character as a hypotaxis of their main problems. This paper is the first paper that gives a full picture of the re-entrant scheduling problem. Considered as a NP-hard problem, a growing number of researchers have employed various methods to solve this complex problem. A survey has been conducted from the recently published literature on the re-entrant problem. This paper has summarised the problem and the relative research methodologies have been studied. Mathematical methods and meta-heuristics, especially Petri net, dispatching rules and genetic algorithm, emerge as the most frequently used methods in recent years, which are presented in detail. Moreover, future research implications have been identified and are suggested. It may help to bring in more awareness of the problem and new techniques to solve it.     

Application of genetic algorithms in production and operations management: a review

Over the last decade, there has been a rapid growth of the use of genetic algorithms in the various areas of production and operations management. This paper provides a review of genetic algorithms research published in twenty-one major production and operations management journals from 1990–2001. More specifically, it identifies research trends and publication outlets of genetic algorithms applications. Our findings show that there are only a handful of production and operations management areas to which genetic algorithms have been applied as the solution approach. Furthermore, we recognize and discuss potential research areas and outlets in which researchers may target their work as well as the need for top ranked POM journals to consider publishing genetic algorithms related papers.     

Flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints

The purpose of this research is to solve flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints in the operations. We first formulate the problem as a Mixed-Integer Linear Program (MILP). The MILP can be used to compute optimal solutions for small-sized problems. We also developed a heuristic algorithm that can obtain a good solution for the problem regardless of its size. Moreover, we have developed a representation and schedule builder that always produces a legal and feasible solution for the problem, and developed genetic and tabu search algorithms based on the proposed schedule builder. The results of the computational experiments show that the developed meta-heuristics are very effective.     

Fracture mechanics and mechanical fault detection by artificial intelligence methods: A review

Artificial intelligence (AI) researchers created new techniques, developed and applied them to solve engineering problems since two decades. Although lots of AI techniques and approaches are available in mechanical engineering, there isn’t any survey aiming to review the existing works, systems and applications in the field of fracture mechanics. In this paper, the state of the art of five AI methods which are used in the field of fracture mechanics, is surveyed. This review is performed from the technical point of view on particular applications of artificial neural networks, Bayesian networks, genetic algorithms, fuzzy logic and case-based reasoning.After an overview of AI methods, sub-domains of engineering fracture mechanics with respect to the fault and failure analysis are described. The existing works from 1990 to 2016 are analysed and discussed in four categories as sub-domains of fracture mechanics: (a) failure mode and failure mechanism identification, (b) damage and failure detection and diagnosis, (c) fault and error detection, diagnosis and (d) mechanical fracture and fracture parameters. We analyse literature based on a classification of these five AI methods in order to highlight their main concepts and explain how they are applied in these sub-domains of fracture mechanics. Our analysis and discussion in this paper shows the advantages, limitations and research gaps in this field. Finally, perspectives and future research directions are outlined.     

An ant colony system-based hybrid algorithm for square root concave cost transhipment problems

Concave cost transhipment problems are difficult to optimally solve for large-scale problems within a limited period of time. Recently, some modern meta-heuristics have been employed for the development of advanced local search based or population-based stochastic search algorithms that can improve the conventional heuristics. Besides these meta-heuristics, the ant colony system algorithm is a population-based stochastic search algorithm which has been used to obtain good results in many applications. This study employs the ant colony system algorithm, coupled with some genetic algorithm and threshold accepting algorithm techniques, to develop a population based stochastic search algorithm for efficiently solving square root concave cost transhipment problems. The developed algorithms are evaluated with a number of problem instances. The results indicate that the proposed algorithm is more effective for solving square root concave cost transhipment problems than other recently designed local search based algorithms and genetic algorithm.     

A genetic search algorithm to optimize job sequencing under a technological constraint in a rolling-mill facility

This article presents some results from the application of a genetic search algorithm to solve a job scheduling problem where setup costs depend on the order of the jobs. An empirical study shows that, for small problems, the solutions given by the genetic algorithm are as good as those obtained with a mixed-integer linear program. For larger problems that are computationally infeasible, we benchmark the genetic solutions against traditional scheduling heuristics. We also study different population management strategies that can improve the performance of the algorithm. Finally, future research avenues are discussed.     

Genetic-algorithms-based algorithm portfolio for inventory routing problem with stochastic demand

This paper presents an algorithm portfolio methodology based on evolutionary algorithms to solve complex dynamic optimisation problems. These problems are known to have computationally complex objective functions, which make their solutions computationally hard to find, when problem instances of large dimensions are considered. This is due to the inability of the algorithms to provide an optimal or near-optimal solution within an allocated time interval. Therefore, this paper employs a bundle of evolutionary algorithms (EAs) tied together with several processors, known as an algorithm portfolio, to solve a complex optimisation problem such as the inventory routing problem (IRP) with stochastic demands. EAs considered for algorithm portfolios are the genetic algorithm and its four variants such as the memetic algorithm, genetic algorithm with chromosome differentiation, age-genetic algorithm, and gender-specific genetic algorithm. In order to illustrate the applicability of the proposed methodology, a generic method for algorithm portfolios design, evaluation, and analysis is discussed in detail. Experiments were performed on varying dimensions of IRP instances to validate different properties of algorithm portfolio. A case study was conducted to illustrate that the set of EAs allocated to a certain number of processors performed better than their individual counterparts.     

Scheduling job shop associated with multiple routings with genetic and ant colony heuristics

The general job shop problem is one of the well known machine scheduling problems, in which the operation sequence of jobs are fixed that correspond to their optimal process plans and/or resource availability. Scheduling and sequencing problems, in general, are very difficult to solve to optimality and are well known as combinatorial optimisation problems. The existence of multiple job routings makes such problems more cumbersome and complicated. This paper addresses a job shop scheduling problem associated with multiple job routings, which belongs to the class of NP hard problems. To solve such NP-hard problems, metaheuristics have emerged as a promising alternative to the traditional mathematical approaches. Two metaheuristic approaches, a genetic algorithm and an ant colony algorithm are proposed for the optimal allocation of operations to the machines for minimum makespan time criterion. ILOG Solver, a scheduler package, is used to evaluate the performance of the proposed algorithms. The comparison reveals that both the algorithms are capable of providing solutions better than the solution obtained with ILOG Solver.     

Optimization of Reliability–Redundancy Allocation Problems: A Review of the Evolutionary Algorithms

The study of optimization methods for reliability–redundancy allocation problems is a constantly changing field. New algorithms are continually being designed on the basis of observations of nature, wildlife, and humanity. In this paper, we review eight major evolutionary algorithms that emulate the behavior of civilization, ants, bees, fishes, and birds (i.e., genetic algorithms, bee colony optimization, simulated annealing, particle swarm optimization, biogeography-based optimization, artificial immune system optimization, cuckoo algorithm and imperialist competitive algorithm). We evaluate the mathematical formulations and pseudo-codes of each algorithm and discuss how these apply to reliability–redundancy allocation problems. Results from a literature survey show the best results found for series, series–parallel, bridge, and applied case problems (e.g., overspeeding gas turbine benchmark). Review of literature from recent years indicates an extensive improvement in the algorithm reliability performance. However, this improvement has been difficult to achieve for high-reliability applications. Insights and future challenges in reliability–redundancy allocation problems optimization are also discussed in this paper.     

HEURISTIC NONSERIAL DYNAMIC PROGRAMMING FOR LARGE PROBLEMS

Dynamic programming is an extremely powerful optimization approach used for the solution of problems which can be formulated to exhibit a serial stage-state structure. However, many design problems are not serial but have highly connected interdependent structures. Existing methods, for the solution of nonserial problems require the problem to possess a certain structure or limit the size of the problem due to storage and computational time requirements. The aim of this paper is to show that nonserial problems can be solved by the use of dynamic programming incorporating algorithms based on heuristics. Two such algorithms are developed using artificial intelligence concepts of estimating the likelihood of future results on present decisions. The algorithms are explained in detail, A small problem is solved and the results of testing them on large scale problems are given. The method is then used to solve a problem drawn from the literature.     

A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem

Solving optimization problems with multiple objectives under uncertainty is generally a very difficult task. Evolutionary algorithms, particularly genetic algorithms, have shown to be effective in solving this type of complex problems. In this paper, we develop a simulation-based multi-objective genetic algorithm (SMOGA) procedure to solve the build-operate-transfer (BOT) network design problem with multiple objectives under demand uncertainty. The SMOGA procedure integrates stochastic simulation, a traffic assignment algorithm, a distance-based method, and a genetic algorithm (GA) to solve a multi-objective BOT network design problem formulated as a stochastic bi-level mathematical program. To demonstrate the feasibility of SMOGA procedure, we solve two mean-variance models for determining the optimal toll and capacity in a BOT roadway project subject to demand uncertainty. Using the inter-city expressway in the Pearl River Delta Region of South China as a case study, numerical results show that the SMOGA procedure is robust in generating ‘good’ non-dominated solutions with respect to a number of parameters used in the GA, and performs better than the weighted-sum method in terms of the quality of non-dominated solutions.     

Two efficient algorithms for constructing almost even approximations of the Pareto front in multi-objective optimization problems

In this article, two algorithms are proposed for constructing almost even approximations of the Pareto front of multi-objective optimization problems. The first algorithm is a hybrid of the ε-constraint and Pascoletti–Serafini scalarization methods for solving bi-objective problems. The second is a modification of the successive Pareto optimization (SPO) algorithm for solving three-objective problems. In these algorithms, the MATLAB fmincon solver is used to solve single-objective optimization problems, which returns a local optimal solution. Some metrics are considered to evaluate the quality of approximations obtained by the suggested algorithms on six test problems, and their results are compared with other algorithms (normal constraint, weighted constraint, SPO, differential evolution, multi-objective evolutionary algorithm/decomposition–differential evolution, non-dominated sorting genetic algorithm-II and S-metric selection evolutionary multi-objective algorithm). Experimental results show that the proposed algorithms provide almost even approximations of the whole Pareto front, and better quality of approximation and CPU time compared with established algorithms.     

A Comparison of Evolutionary Algorithms for Mechanical Design Components

Two evolutionary algorithms - the genetic algorithm and the evolution strategy - are compared in respect of mechanical design problems. Mechanical design problems are real world problems, characterized by a number of inequality constraints, nonlinear equations, mixed discrete-continuous variables and the presence of interdependent discrete parameters whose values are taken from standardized tables. The selection, recombination and mutation operators, and the chosen constraint-handling method are presented for both the genetic algorithm and the evolution strategy. In order to find the best combination of operators for each algorithm which will solve mechanical design problems, a number of selection and recombination operators are compared in respect of these problems. A comparison of these two algorithms with regard to three mechanical design problems extends the results of comparisons presented in the literature for unimodal and multimodal test functions with continuous variables only, and without constraints.     

Genetic algorithm for facilities layout problems based on slicing tree structure

The use of genetic algorithms to solve facility layout problems has gained popularity in recent years among researchers. A difficult requirement for the use of genetic algorithms in layout problems is an efficient method of coding the relevant features of a layout as a chromosome. The slicing tree structure has gained popularity in developing genetic algorithms for layout problems. However, previous implementations based on slicing tree structure mostly require repairing procedures to ensure that the chromosomes represent legal layouts after application of genetic operators. Some representations do not permit an exhaustive search. This paper reports on design, development and experimentation results of a new genetic algorithm named (GA.FLP.STS), which always produces legal chromosomes without any need for repairing procedures. A penalty system was introduced to facilitate generating facilities with acceptable dimensions. (GA.STS.FLP) required insignificant processing times even for test problems of 100 facilities solved.     

Robot arc welding task sequencing using genetic algorithms

This paper addresses welding task sequencing for robot arc welding process planning. Although welding task sequencing is an essential step in welding process planning, it has been considered through empirical knowledge, rather than a systematic approach. Thus, an effective task sequencing method for robot arc welding is required. Welding operations can be classified by the number of weldlines and layers. Genetic algorithms are applied to tackle those welding task sequencing problems in productivity and welding quality aspects. A genetic algorithm for the Traveling Salesman Problem (TSP) is utilized to determine welding task sequencing for a multiweldline-singlepass problem. Further, welding task sequencing for multiweldline-multipass welding is investigated and appropriate genetic algorithms are introduced. A random key genetic algorithm is presented to solve multi-robot welding task sequencing: mutliweldline with multiple robots. Finally, the genetic algorithms are implemented for the welding task sequencing of three-dimensional weld plate assemblies. Various simulation tests for a welded structure are performed to find the combination of genetic algorithm parameters suitable to weld sequencing problems and to verify the quality of genetic algorithm solutions. Robot operations for weld sequences are simulated graphically using the robot simulation software IGRIP.     

Production-inventory policy for a deteriorating item with a single vendor-buyer system

In this paper, production-inventory models for a deteriorating item in a single vendor-buyer system has been developed with constant production and demand rate. Shortages at the buyer (when it is allowed) depends on time. The models have been formulated as cost minimization problem via both integrated and non-integrated approaches and solved using genetic algorithms developed to solve the single and multiobjective production inventory problems. Numerical illustrations of the models have been presented and the sensitivity analysis with respect to rates of production, demand and deterioration are performed.     

Refined h-adaptive finite element procedure for large deformation geotechnical problems

Adaptive finite element procedures automatically refine, coarsen, or relocate elements in a finite element mesh to obtain a solution with a specified accuracy. Although a significant amount of research has been devoted to adaptive finite element analysis, this method has not been widely applied to nonlinear geotechnical problems due to their complexity. In this paper, the h-adaptive finite element technique is employed to solve some complex geotechnical problems involving material nonlinearity and large deformations. The key components of h-adaptivity including robust mesh generation algorithms, error estimators and remapping procedures are discussed. This paper includes a brief literature review as well as formulation and implementation details of the h-adaptive technique. Finally, the method is used to solve some classical geotechnical problems and results are provided to illustrate the performance of the method.     

Design of high-performing hybrid meta-heuristics for unrelated parallel machine scheduling with machine eligibility and precedence constraints

This study involves an unrelated parallel machine scheduling problem in which sequence-dependent set-up times, different release dates, machine eligibility and precedence constraints are considered to minimize total late works. A new mixed-integer programming model is presented and two efficient hybrid meta-heuristics, genetic algorithm and ant colony optimization, combined with the acceptance strategy of the simulated annealing algorithm (Metropolis acceptance rule), are proposed to solve this problem. Manifestly, the precedence constraints greatly increase the complexity of the scheduling problem to generate feasible solutions, especially in a parallel machine environment. In this research, a new corrective algorithm is proposed to obtain the feasibility in all stages of the algorithms. The performance of the proposed algorithms is evaluated in numerical examples. The results indicate that the suggested hybrid ant colony optimization statistically outperformed the proposed hybrid genetic algorithm in solving large-size test problems.