Graph theoretic heuristics for the plant layout problem

Abstract

The plant layout problem is an important industrial problem that remains unsolved. Seppanen and Moore considered an important subproblem: that of the optimal specification of which facilities are to be adjacent in the final layout without regard to the area or shape of the individual facilities. They present a string processing heuristic which relies on using a test for graph planarity. This paper further develops their graph theoretic formulation of the problem. This development is used to present two procedures which usually yield near-optimal solutions. The procedures circumvent the considerable difficulty of graph planarity testing by working entirely within a family of graphs known to be planar and also to contain the solution. Ways of improving suboptimal solutions are discussed. Computational experience in using the methods on a variety of problems suggests that the methods are efficient.