A Parallel Genetic Algorithm for the Geometrically Constrained Site Layout Problem with Unequal-Size Facilities

Abstract

Parallel genetic algorithms techniques have been used in a variety of computer engineering and science areas. This paper presents a parallel genetic algorithm to solve the site layout problem with unequal-size and constrained facilities. The problem involves coordinating the use of limited space to accommodate temporary facilities subject to geometric constraints. The problem is characterised by affinity weights used to model transportation costs between facilities, and by geometric constraints between relative positions of facilities on site. The algorithm is parallelised based on a message passing SPMD architecture using parallel search and chromosomes migration. The algorithm is tested on a variety of layout problems to illustrate its performance. In specific, in the case of: (1) loosely versus tightly constrained layouts with equal levels of interaction between facilities, (2) loosely versus tightly packed layouts with variable levels of interactions between facilities, and (3) loosely versus tightly constrained layouts. Favorable results are reported.