Genetic Algorithm and Its Application in Layout Problems

GA plus slicing tree is also widely developed in VLSI. Nallasamy mani, et al. 1997 describes a combined genetic algorithm and slicing approach for floorplan area optimization during the early stage of integrated circuit design. It applies a partition procedure to reduce the complexity routing problem. Genetic Algorithm (GA) is wide applied in almost any field, including solving FLP. Tam 1992 introduced the coding of layouts as a string of characters of finite length and used a fixed slicing tree structure defined by a clustering algorithm to represent a layout as a chromosome of string of characters.

Its improvement is presented in Tam 1998 with a parallel GA approach in terms of schema coding and solution method. It relaxes the assumption of a fixed slicing tree structure by coding the structure, internal and external nodes of a tree as substrings in the schema. Based on the application limitation of the classical crossover and mutation operators of Tam 1998, L. Al-Hakim2000 introduced a preserving operation, referred to as transplanting, to produce feasible offspring.

It also discusses the improvement of each of the GA development procedures with comparison with Tam1998. Though the use of GA has gained popularity with the application of slicing tree structure for layout problems, most implementations require repairing procedures to ensure the legality of the chromosome representations of the layout after application of genetic operators. To overcome this limitation, E. SHAYAN 2004 reported the design and development results of a new GA named GA. FLP. STS producing legal chromosomes without any need for repairing procedures.

It introduced a penalty system to facilitate generating facilities with acceptable dimensions. With the popularity and maturity of GA with slicing tree structure, more researches focus into the different aspects of FLP solutions. Kyu-Yeul Lee2002 and 2005 proposed a hybrid GA to derive solutions for facility layouts with inner walls and passages. Y. Wu2002 presents the method of slicing floorplan to solve the layout and aisle structure problems simultaneously combined with GA optimization. Terushige Honiden2004 proposed a tree structure model to represent the nequal-area facility layout with different rectangular shape specified by area and aspect ratio. GA is applied for finding non-dominated solutions. But the model is built based on the assumption of enough shop floor space and no constraints considered. G. H. Hu2006 applied GA to obtain optimal Cell System layout (CSL) layouts and material handling system in Cellular Manufacturing Systems (CMSs) based on the contour distances between the pickup/delivery stations combining sequence-pair based CSL-generating algorithm.

K. Balamurugan2006 presents an approach for solving multi-row, unequal area, manufacturing facility layout problems using GA with limitations like single design criterion, manual reversion and approximated shape. However, the proposed model mainly aims to minimize the cost associated with material handling during normal and breakdown periods, while many practical factors like floor space utilization are not considered in his paper. J. A.

Diego-Mas 2007 developed a two-phase GA to solve FLPs strictly representing the geometric constraints imposed on worker activities with an optimum slicing tree to group the activities. B. Sirinaovakul 2007 introduces a maximum weight-matching algorithm to generate the initial slicing tree as the foundation of alternative layouts for further selection. It is proved to be able to generate good result compared with other approaches. But it still exists limitation to deal with non-border predetermined location.

Leave a Reply

Your email address will not be published. Required fields are marked *