Solving facility layout problems with geometric constraints using parallel genetic algorithms: Experimentation and findings

In this paper, we present a parallel genetic algorithm approach to the facility layout problem which improves on previous work in terms of schema coding and solution method. The current study builds on earlier work by adopting a slicing tree representation of a floor layout. However, the new coding scheme 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. In addition, the implicit parallelism of genetic algorithms is exploited at the physical level using an MIMD Paragon parallel machine. Four coarse-grained parallel genetic algorithms for the layout problem are developed and compared based on sound statistical experimental design. Experimental results indicate that the distributed and totally distributed parallel genetic algorithms consistently out-perform others, independent of problem size and number of processors. Our findings provide the empirical basis for selecting parallel genetic algorithms in layout design. The current work also demonstrates the potential of parallel genetic algorithms as a viable tool to tackle hard combinatorial management science problems.