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

Miguel F. Anjos, Anja Fischer, Philipp Hungerländer

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)514-529
JournalEuropean Journal of Operational Research
Issue number2
Early online date13 Apr 2018
Publication statusPublished - 1 Oct 2018


Dive into the research topics of 'Improved exact approaches for row layout problems with departments of equal length'. Together they form a unique fingerprint.

Cite this