Exact and heuristic approaches for a new circular layout problem

We discuss a new facility layout problem, the so-called Directed Circular Facility Layout Problem (DCFLP). The DCFLP aims to find an optimal arrangement of machines on a circular material handling system such that the total weighted sum of the center-to-center distances between all pairs of machines measured in clockwise direction is minimized. Several real-world applications, like for example the optimal arrangement of a set of cutting tools on a tool turret, can be modeled as a DCFLP. Further, the DCFLP generalizes a couple of layout problems that are well-discussed in literature. We show that the DCFLP can be modeled as a Linear Ordering Problem (LOP). Hence, it can be solved efficiently by using exact and heuristic approaches for the LOP. First, we apply a Semidefinite Programming as well as an Integer Linear Programming approach. Moreover, we use a Tabu Search and a Variable Neighborhood Search heuristic, for solving the DCFLP. Finally, we compare the practical performance of our approaches in a computational study.