Graph theoretic heuristics for unequal-sized facility layout problems

This paper considers the unequal-sized facility layout problem with the objective of minimizing total transportation distance. The total transportation distance is defined as the sum of products of flow amounts and rectilinear distances between facilities, where flow amount represents the number of trips per time period between facilities. In the layout problem, it is assumed that shapes of facilities are not fixed and that there is no empty space between facilties in the layout. The paper proposes new graph theoretifc heuristics for the problem. In the heuristics, an initial layout is obtained by constructing a planar adjacency graph and then the solution is improved by changing the adjacency graph (not the physical layout). Therefore, these heuristics do not need an initial layout in advance, and sizes and locations of facilties do not have to be considered in the improvement procedure. Computational results showed that the proposed algorithms gave better solutions than those from CRAFT, which is one of the most popular algorithms for unequal-sized facility layout problems.