A New Graph-Theoretic Heuristic for Facility Layout

The facility layout problem is important in the modern manufacturing environment because increased machine flexibility and product diversification create additional complexities in scheduling and material handling. An important first step in facility layout is the determination of which machines should be adjacent. This problem can be modelled as that of finding a maximum weight planar subgraph of a graph, given a measure of the desirability that two machines be adjacent based on the anticipated flows and technological constraints. We present a new heuristic that is a generalization of previous work of Foulds and Robinson. Preliminary computational results are presented which suggest that this heuristic performs well.