A Strategy for Solving the Plant Layout Problem

Abstract

We consider the problem of laying out the facilities of which a plant is composed, in terms of specifying which facilities are to be adjacent. For each pair of facilities a benefit from siting them adjacent to each other is known. We seek to maximise the sum of benefits over all pairs of adjacent facilities.

The problem is stated in terms of graph theory, and provision is made for some edges to be considered necessary and others forbidden, where each edge represents an adjacency. We describe a branch and bound algorithm for finding an optimal layout and a sequence of tests for determining whether or not the graphs constructed in the course of the algorithm are planar.