Solving the constrained Single-Row Facility Layout Problem with Integer Linear Programming

Abstract

The Single-Row Facility Layout Problem (SRFLP) is one of the most studied facility layout problems in the literature. It asks for an optimal arrangement of departments with given lengths on a row such that the weighted sum of all centre-to-centre distances between department pairs is minimised. Real-world facility layouts may require taking different restrictions on the placement of departments into account, such as arrangement on a fixed position, pairwise placement, or precedence considerations. Therefore, we consider the constrained Single-Row Facility Layout Problem (cSRFLP) that additionally considers positioning, ordering, and relation constraints on single-row facility layouts. In this work, we suggest a new Integer Linear Programming (ILP) formulation for the cSRFLP, which outperforms the best available exact approach in literature. In an extensive computational study, we apply our ILP approach as well as an LP-based cutting plane algorithm on SRFLP and cSRFLP instances from the literature. We provide optimal cSRFLP layouts as well as strong lower bounds for instances with up to 42 departments. Further, we present new results for SRFLP instances from the literature. Additionally, we demonstrate the individual impact of the constraint sets on the run times of cSRFLP instances to emphasise further research on this rarely studied practice-oriented Facility Layout Problem.

Keywords:

• Facility planning and design
• Facility Layout Problem
• single-row layout
• Integer Linear Programming
• cutting planes

Disclosure statement

No potential conflict of interest was reported by the authors.

Data availability statement

The data that support the findings of this study are openly available in ResearchGate at http://doi.org/10.13140/RG.2.2.32563.14886, reference number Maier and Pachatz (2021). Note that the instances MaPa_2021_28dept_* are generated by the authors of this paper. The other instances are used from the papers (Heragu and Kusiak 1991; Amaral 2006; Anjos and Vannelli 2008; Amaral 2008; Anjos and Yen 2009; Hungerländer and Anjos 2014; Hungerländer and Rendl 2013).

Notes

1 It does not depend on the order of departments i and j if a department k lies between them or not. Therefore, $x_{ikj}=x_{jki}$ holds, and with $i<j$ the number of variables is reduced by half.

2 See https://www.cpubenchmark.net/compare/Intel-Xeon-E5-2630-v3-vs-Intel-i5-8400/2386vs3097. for the single-thread rating of the CPUs used.

Additional information

Funding

This work was supported by European Regional Development Fund and the Carinthian Economic Promotion Fund (KWF) [20214/31942/45906].

Notes on contributors

Kerstin Maier

Kerstin Maier received a Ph.D. degree in Technical Mathematics and two master's degrees in Applied Computer Science and Technical Mathematics from Alpen-Adria-Universität Klagenfurt. Her research focus lies in the development of optimisation approaches for various kinds of facility layout and vehicle routing problems. Currently, she is a Computer Science Professor at Higher Technical College Wolfsberg in Austria.

Veronika Taferner

Veronika Taferner has a Ph.D. degree in Technical Mathematics from Alpen-Adria-Universität Klagenfurt. During her Ph.D. she focused on operations research of real-world problems in production and logistics, as vehicle routing and facility layouts. Current research, conducted at the Anexia GmbH, focuses on the design and implementation of effective algorithms for sustainable share-a-ride systems and railway optimisation.