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

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

European Journal of Operational Research, 2018, vol. 270, issue 2, 514-529

Abstract: 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.

Keywords: Facilities planning and design; Facility layout; Mixed integer linear programming; Semidefinite programming; Computational experiments (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718303114
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:270:y:2018:i:2:p:514-529

DOI: 10.1016/j.ejor.2018.04.008

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().