Improved exact approaches for row layout problems with departments of equal length

Facility layout is a well-known operations research problem that arises in various applications. The multi-row layout is a challenging optimization problem where the task is to determine the optimal placement of one-dimensional departments on a given number of rows. This paper is concerned with multi-row facility layout problems in which all the departments have the same length. This is an important special case that includes most multi-row facility layout applications from the literature. We prove two theoretical results about the structure of optimal layouts, namely that only spaces of unit length are necessary to obtain an optimal solution, and that exact expressions exist for the minimum number of such spaces that need to be added so as to preserve at least one global optimal solution. Using these results we propose a binary linear optimization model and a binary semidefinite optimization model for the problem, neither of which uses continuous variables, which has a significant positive computational impact. Our computational experiments show that our specially tailored approaches can handle much larger instances than other exact methods applicable to this important problem class.