Groupe d’études et de recherche en analyse des décisions


Solution approaches for equidistant double- and multi-row facility layout problems

, et

The facility layout problem is a well-known operations research problem that arises in multiple applications. This paper is concerned with the multi-row layout problem in which one-dimensional departments are to be placed on a given number of rows so that the sum of the weighted center-to-center distances is minimized. While the optimal solution for a single-row problem will normally have no spaces between departments, for multi-row layout problems it is necessary to allow for the presence of spaces of arbitrary lengths between departments. We consider the special case of equidistant row layout problems in which all departments have the same length, taken to be unity without loss of generality. For this class of problems we prove two theoretical results that facilitate the handling of spaces. First we show that although the lengths of the spaces are in general continuous quantities, every multi-row equidistant problem has an optimal solution on the grid. This implies that only spaces of unit length need to be used when modeling the problem, and hence that the problem can be formulated as a purely discrete optimization problem. Second we state and prove exact expressions for the minimum number of spaces that need to be added so as to preserve at least one optimal solution. One important consequence of these results is that multi-row equidistant layout problems can be modeled using only binary variables; this has a significant impact for a computational perspective. These results are used to formulate two new models for the equidistant problem, an integer linear optimization model and a semidefinite optimization model. Special attention is paid to the double-row layout case that has received much attention recently and is particularly important in practice. Our computational results with the new formulations as well as with a recent formulation by Amaral show that the semidefinite approach dominates for medium- to large-sized instances and that it is well-suited for providing high-quality lower bounds for large-scale instances in reasonable computation time. Specifically for double-row instances, we attain global optimality for some instances with up to 25 departments, and achieve optimality gaps smaller than 1% for instances with up to 50 departments.

, 37 pages