A multi-improved genetic algorithm for facility layout optimisation based on slicing tree

For the facility layout optimisation problem, we use the slicing tree structure based on the order of traversal to form a new chromosome encoding system demonstrating facilities’ order, the relationship and the location. We generate the initial solution based on two principles namely the facilities’ adjacency and random generation. The structure of chromosome is made up with three sections in the research so that we can do the genetic operations to these three sections respectively, and we use dynamic and feedback mechanisms to improve the penalty function. As a result, the analysis of typical cases shows that there are certain improvements to this algorithm both in effectiveness and efficiency.     

Slicing tree's geometric potential: an indicator for layout problems based on slicing tree structure

In this paper we propose an indicator to measure the capacity of a slicing tree to generate geometrically acceptable solutions for layout problems based on the slicing tree structure. This indicator can predict if, by making the appropriate cuts, the tree structure is able to generate layouts that satisfy the geometrical restrictions imposed on the items to be arranged. It also permits the determination of the most suitable aspect ratio of the layout zone in order to minimize non-compliance with the geometric restrictions. The method of calculating the indicator and its application to the facility layout problem are described, and the results obtained in the experiments carried out are also given.     

An iterative facility layout algorithm

In this paper we present a facility layout algorithm that iterates between a genetic algorithm with a slicing tree representation and a mixed-integer program with a subset of the binary variables set via the genetic algorithm. The genetic algorithm is very good at finding low-cost solutions while maintaining shape constraints on the departments. The slicing tree representation and the mixed-integer program are compatible in terms of layout representation, with the mixed-integer program representation more general. The mixed-integer program allows us to relax the last remaining constraints of the slicing tree representation of the genetic algorithm. We present our genetic algorithm and the iterative algorithm, while illustrating their performance on test problems from the literature. In 10 of the 12 problems, new lower best-cost solutions are found.     

Solving facility layout problems with strict geometric constraints using a two-phase genetic algorithm

This article puts forward a two-phase genetic algorithm that is able to solve facility layout problems strictly respecting the geometric constraints imposed on activities. In the first phase the algorithm attempts to locate an optimum slicing tree to group the activities appropriately. In the second phase the layout is obtained from this tree. In order to assess the slicing trees in the first phase we propose an evaluation function able to predict if, by making the appropriate cuts, the tree structure is able to generate layouts that satisfy the geometric restrictions imposed on the facilities to be arranged, and to minimize the cost of transporting materials between the production activities. It also permits the determination of the most suitable aspect ratio of the layout zone in order to minimize non-compliance with the geometric restrictions. The algorithm and the method of calculating the indicator proposed in the evaluation function are described, and the results obtained in the experiments carried out are also given.     

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.     

Simulated annealing based parallel genetic algorithm for facility layout problem

The facility layout problem (FLP), a typical combinational optimisation problem, is addressed in this paper by implementing parallel simulated annealing (SA) and genetic algorithms (GAs) based on a coarse-grained model to derive solutions for solving the static FLP with rectangle shape areas. Based on the consideration of minimising the material flow factor cost (MFFC), shape ratio factor (SRF) and area utilisation factor (AUF), a total layout cost (TLC) function is derived by conducting a weighted summation of MFFC, SRF and AUF. The evolution operations (including crossover, mutation, and selection) of GA provide a population-based global search in the space of possible solutions, and the SA algorithm can lead to an efficient local search near the optimal solution. By combing the characteristics of GA and SA, better solutions will be obtained. Moreover, the parallel implementation of simulated annealing based genetic algorithm (SAGA) enables a quick search for the optimal solution. The proposed method is tested by performing a case study simulation and the results confirm its feasibility and superiority to other approaches for solving FLP.     

Solution of facility layout problems with pickup/drop-off locations using random search techniques

Due to non-polynomial hardness, the facility layout problem (FLP) becomes more critical when pickup/drop-off (P/D) locations are considered in the design of an open field layout under a manufacturing environment. This paper proposes an indigenous model of the facility layout problem based on random search techniques and its solution methodology using a genetic algorithm (GA), simulated annealing (SA) and a hybrid algorithm (HA). The paper illustrates the performance of different random search operating parameters in solving the facility layout problem considering P/D locations along the periphery of rectangular machine blocks. The preliminary experiments were carried out on three facility layout test problems having six, eight and ten machines in order to fix the different operating parameters such as crossover operator, crossover rate, initial temperature, temperature reduction factor, number of generations, population size, etc. The results of extensive preliminary experimentation were utilized to solve facility layout problems having 12 and 18 machines and, finally, were compared with the existing procedures in the literature. The experimental tables and related analysis performed via the solution methods by applying GA, SA and HA revealed that random-search-based modeling of FLP considering P/D and its solution as suggested in this paper is worth pursuing.     

A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem

This paper proposes a tabu search (TS) algorithm to solve an NP-hard cyclic robotic scheduling problem. The objective is to find a cyclic robot schedule that maximises the throughput. We first formulate the problem as a linear program, provided that the robot move sequence is given, and reduce the problem to searching for an optimal robot move sequence. We find that the solution space can be divided into some specific subspaces by the maximal number of works-in-process. Then, we propose a TS algorithm to synchronously perform local searches in each subspace. To speed up our algorithm, dominated subspaces are eliminated by lower and upper bounds of the cycle time during the iterations. In the TS, a constructive heuristic is developed to generate initial solutions for each subspace and a repairing procedure is proposed to maintain the feasibility of the solutions generated in the initialisation stage and the neighbours search process. Computational comparison both on benchmark instances and randomly generated instances indicates that our algorithm is efficient for the cyclic robotic scheduling problem.     

A genetic algorithm approach to the integrated inventory-distribution problem

We introduce a new genetic algorithm (GA) approach for the integrated inventory distribution problem (IIDP). We present the developed genetic representation and use a randomized version of a previously developed construction heuristic to generate the initial random population. We design suitable crossover and mutation operators for the GA improvement phase. The comparison of results shows the significance of the designed GA over the construction heuristic and demonstrates the capability of reaching solutions within 20% of the optimum on sets of randomly generated test problems.     

Multiplexed computer-generated holograms with polygonal-aperture layouts optimized by genetic algorithm

Using a novel genetic algorithm (GA) with a Lamarckian search we optimize the polygonal layout of a new type of multiplexed computer-generated hologram (MCGH) with polygonal apertures. A period ofthe MCGH is divided into cells, and the cell is further divided into polygonal apertures according to a polygonal layout, which is to be optimized. Among an ensemble of 1.21 x 10(24) possible polygonal layouts, we take a population of 102 solutions, which are coded as chromosomes of bits, and find the optimal solution with our GA. We introduce rank-based selection with cumulative normal distribution fitness, double crossover, exponentially decreasing mutation probability and Lamarckian downhill search with a small number of offspring chromosomes into our GA, which shows a rapid convergence to the global minimum of the cost function. In a second step of optimization the phase distributions over the subholograms in the MCGH are determined with our iterative subhologram design algorithm. Our MCGH designs show large-sie reconstructed images with high diffraction efficiency and low reconstruction error.     

Cyclic transfers in school timetabling

In this paper we propose a neighbourhood structure based on sequential/cyclic moves and a cyclic transfer algorithm for the high school timetabling problem. This method enables execution of complex moves for improving an existing solution, while dealing with the challenge of exploring the neighbourhood efficiently. An improvement graph is used in which certain negative cycles correspond to the neighbours; these cycles are explored using a recursive method. We address the problem of applying large neighbourhood structure methods on problems where the cost function is not exactly the sum of independent cost functions, as it is in the set partitioning problem. For computational experiments we use four real world data sets for high school timetabling in the Netherlands and England. We present results of the cyclic transfer algorithm with different settings on these data sets. The costs decrease by 8–28% if we use the cyclic transfers for local optimization compared to our initial solutions. The quality of the best initial solutions are comparable to the solutions found in practice by timetablers.     

On solving facility layout problems using genetic algorithms

Tam and Chan (1998) present a parallel genetic algorithm approach to solve the facility layout problem. They adopt a slicing tree representation of a floor layout. The coding scheme represents a layout as a string with three parts. This paper demonstrates the difficulties in applying classical crossover and mutation operators for solving facility layout problems. The paper modifies the representation of Tam and Chan and introduces a new preserving operation, referred to as transplanting , that manages to produce feasible offspring. It also studies the applicability of other genetic operations such as diagonal crossover and cloning in generating feasible offspring. The paper is written in a note format and the reader may refer to Tam and Chan for more details.     

A new simulated annealing algorithm for the facility layout problem

In this paper we present an application of simulated annealing to facility layout problems with single and multiple floors. The facility layout problem is highly combinatorial in nature and generally exhibits many local minima. These properties make it a suitable candidate for simulated annealing. Using a new candidate layout generation routine and spacefilling curves, we develop an improvement-type layout algorithm based on simulated annealing that considers an expanded set of department exchanges. The resulting algorithm achieves low-cost solutions that are much less dependent on the initial layout than other approaches. We compare the performance of the simulated-annealing based algorithm with both steepest-descent and randomized approaches from the literature. Unlike other simulated annealing papers which typically present a statistical experiment to evaluate the effect of numerous control settings, all the experiments presented in this paper were conducted with control settings that are constant or easily specified. This approach facilitates the application of the proposed algorithm to real-life facility layout problems in both single and multiple floor facilities. Although the algorithm presented here can be applied to many types of facilities, our primary focus is on production facilities.     

Using a modified genetic algorithm to find feasible regions of a desirability function

The multi‐response optimization (MRO) problem in response surface methodology is quite common in applications. Most of the MRO techniques such as the desirability function method by Derringer and Suich are utilized to find one or several optimal solutions. However, in fact, practitioners usually prefer to identify all of the near‐optimal solutions, or all feasible regions, because some feasible regions may be more desirable than others based on practical considerations. In this paper, with benefits from the stochastic property of a genetic algorithm (GA), we present an innovative procedure using a modified GA (MGA), a computational efficient GA with a local directional search incorporated into the GA process, to approximately generate all feasible regions for the desirability function without the limitation of the number of factors in the design space. The procedure is illustrated through a case study. The MGA is also compared with other commonly used methods for determining the set of feasible regions. Using Monte Carlo simulations with two benchmark functions and a case study, it is shown that the MGA can more efficiently determine the set of feasible regions than the GA, grid methods, and the Nelder–Mead simplex algorithm. Copyright © 2011 John Wiley & Sons, Ltd.     

Genetic algorithm with adaptive and dynamic penalty functions for the selection of cleaner production measures: a constrained optimization problem

This paper presents a new approach of genetic algorithm (GA) to solve the constrained optimization problem. In a constrained optimization problem, feasible and infeasible regions occupy the search space. The infeasible regions consist of the solutions that violate the constraint. Oftentimes classical genetic operators generate infeasible or invalid chromosomes. This situation takes a turn for the worse when infeasible chromosomes alone occupy the whole population. To address this problem, dynamic and adaptive penalty functions are proposed for the GA search process. This is a novel strategy because it will attempt to transform the constrained problem into an unconstrained problem by penalizing the GA fitness function dynamically and adaptively. New equations describing these functions are presented and tested. The effects of the proposed functions developed have been investigated and tested using different GA parameters such as mutation and crossover. Comparisons of the performance of the proposed adaptive and dynamic penalty functions with traditional static penalty functions are presented. The result from the experiments show that the proposed functions developed are more accurate, efficient, robust and easy to implement. The algorithms developed in this research can be applied to evaluate environmental impacts from process operations.     

A genetic algorithm for optimal unequal-area block layout design

The use of a genetic algorithm (GA) to optimise the binary variables in a mixed-integer linear programming model for the block layout design problem with unequal areas that satisfies area requirements is analysed. The performance of a GA is improved using a local search through the possible binary variables assignment; results encourage the use of this technique to find a set of feasible solutions for the block layout design with more than nine departments.     

A GLOBAL FLOOR PLANNING TECHNIQUE FOR VLSI LAYOUT

Over the years, many CAD tools for VLSI macrocelf design have become available that automatically perform some of the physical synthesis phases to reduce development costs. Although floor planning imposes global constraints on the quality of the final layout, state-of-the-art tools do not completely support floor planning synthesis. A new floor planning method for macrocell layout style is presented. The floor plan state space is characterized by an equivalence relation to apply efficient solution techniques. A new pseudo-polynomial area optimization algorithm is proposed that derives from a given hierarchical floor plan tree the optimal slicing tree. The order of this floor plan tree is at least 2 and at most 5. Extensions of this approach to cover non-slicing floor plans are also described. Since floor planning and routing are interdependent tasks, an improved dynamic updating scheme is proposed to consider the interconnection area around each cell during the floor plan assembly. The method has been successfully applied to an industrial design with about 260,000 transistors.     

Facility layout objective functions and robust layouts

In this paper we examine the adjacency-based, distance-based, and weighted-criteria facility layout objective functions in an attempt to relate them to actual layout costs, which are typically dependent on material handling costs. As a result of this examination, we develop an objective function based on a basic material handling cost structure. We then show that this objective function is a generalization of the traditional weighted objective. Since specifying weights may not be an exact process, we explore the impact of imperfect weighting-value information on solution quality. In the process, we illustrate with test problems from the literature that robust solutions—good solutions as measured by more than one set of weights—can be found with a simple procedure we call the robust layout method. This leads us to our general conclusion that using imperfect weighting-value information while we generate the layouts is better than using complete weighting-value information only after we generate the layouts.     

Equivalence-set genes partitioning using an evolutionary-DP approach

Computation of transitive-closure equivalence sets has recently emerged as an important step for building static and dynamic models of gene network from DNA sequences. We present an evolutionary-DP approach in which dynamic programming (DP) is embedded into a genetic algorithm (GA) for fitness function evaluation of small equivalence sets (with m genes) within a large-scale genetic network of n genes, where n/spl Gt/m. This approach reduces a computation-intensive optimal problem of high dimension into a heuristic search problem on /sub n/C/sub m/ candidates. The DP computation of transitive closure forms the basic fitness evaluation for selecting candidate chromosomes generated by GA operators. By introducing bounded mutation and conditioned crossover operators to constrain the feasible solution domain, small transitive-closure equivalence sets for large genetic networks can be found with much reduced computational effort. Empirical results have successfully demonstrated the feasibility of our GA-DP approach for offering highly efficient solutions to large scale equivalence gene-set partitioning problem. We also describe dedicated GA-DP hardware using field programmable gate arrays (FPGAs), in which significant speedup could be obtained over software implementation.     

Integrated assembly and disassembly sequence planning using a GA approach

In a product life cycle, an assembly sequence is required to produce a new product at the start, whereas a disassembly sequence is needed at the end. In typical assembly and disassembly sequence planning approaches, the two are performed as two independent tasks. In this way, a good assembly sequence may contradict the cost considerations in the disassembly sequence, and vice versa. In this research, an integrated assembly and disassembly sequence planning model is presented. First, an assembly precedence graph (APG) and a disassembly precedence graph (DPG) are modelled. The two graphs are transformed into an assembly precedence matrix (APM) and a disassembly precedence matrix (DPM). Second, a two-loop genetic algorithm (GA) method is applied to generate and evaluate the solutions. The outer loop of the GA method performs assembly sequence planning. In the inner loop, the reverse order of the assembly sequence solution is used as the initial solution for disassembly sequence planning. A cost objective by integrating the assembly costs and disassembly costs is formulated as the fitness function. The test results show that the developed method using the GA approach is suitable and efficient for the integrated assembly and disassembly sequence planning. Example products are demonstrated and discussed.