Cycle decomposition, Steiner trees, and the facility layout problem

The facility layout problem is modelled as a cycle decomposition process in which the maximum-weight clique and travelling salesman problems are utilized to extract cycles from the graph adjacency matrix. The space between cycles is triangulated so the graph is maximally planar. The adjacency graph is then systematically developed into a block plan layout. With use of the maximum-weight clique algorithm, the procedure addresses layout problems that are not 100% dense. Many examples are utilized to demonstrate the flexibility of the algorithm and the resulting adjacency graph and block plan layout drawings. The Steiner Circulation Network solution derived from an adjacency graph solution and its dual graph, provides a minimum cost system of hallways and connecting links for the material handling system. Using the flows between activities and departments in a layout problem, the circulation network provides the necessary link between the steps of finding the adjacency graph solution and finding useful block plan layout. A case study demonstrates how the solution for the layout and its material handling system can be integrated. Computational results up to size n = 100 are presented along with a comparative study with a competitive algorithm