A semidefinite optimization-based approach for global optimization of multi-row facility layout

This paper is concerned with the Multi-Row Facility Layout Problem. Given a set of rectangular departments, a fixed number of rows, and weights for each pair of departments, the problem consists of finding an assignment of departments to rows and the positions of the departments in each row so that the total weighted sum of the center-to-center distances between all pairs of departments is minimized. We show how to extend our recent approach for the Space-Free Multi-Row Facility Layout Problem to general Multi-Row Facility Layout as well as some special cases thereof. To the best of our knowledge this is the first global optimization approach for multi-row layout that is applicable beyond the double-row case. A key aspect of our proposed approach is a model for multi-row layout that expresses the problem as a discrete optimization problem, and thus makes it possible to exploit the underlying combinatorial structure. In particular we can explicitly control the number and size of the spaces between departments. We construct a semidefinite relaxation of the discrete optimization formulation and present computational results showing that the proposed approach gives promising results for several variants of multi-row layout problems on a variety of benchmark instances.