GRAPH-THEORETIC HEURISTICS FOR UNEQUAL-SIZED FACILITY LAYOUT PROBLEMS

Abstract

We consider 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 facilities in the layout. We propose new graph theoretic 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 facilities 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.