Facilities Layout Adjacency Determination: An Experimental Comparison of Three Graph Theoretic Heuristics

The facilities layout problem is concerned with laying out facilities on a planar site in order to design systems that are as efficient as possible. One approach to the problem involves the use of REL charts, which are tables that estimate the desirability of locating facilities next to each other, and the construction of a maximum weight planar graph that represents an efficient layout design. This method is not a complete one, however, since it specifies only which facilities are to be adjacent. Nevertheless, whenever the analyst has a great deal of freedom of design, it is a useful tool in the initial stages of laying out a new system. In this paper, we describe three graph theoretic heuristics that attempt to determine an optimal planar adjacency graph from a REL chart. Our computational experience suggests that these methods can provide effective solutions to problems of the size frequently encountered in practice by designers.