The NP-hard Multi-Row Facility Layout Problem (MRFLP) consists of a set of one-dimensional departments and pairwise transport weights between them. It asks for a non-overlapping arrangement of the departments along a given number of rows such that the weighted sum of the horizontal center-to-center distances between the departments is minimized. We mainly focus on the MRFLP with exactly two rows, the so called Double-Row Facility Layout Problem (DRFLP), and on the case with exactly one row, the so called Single-Row Facility Layout Problem (SRFLP). Although the MRFLP has wide applications in factory planning, only small instances can be solved to optimality in reasonable time for the MRFLP with at least two rows while provably good or optimal solutions for the SRFLP can be derived very fast. In the equidistant case, where all departments have the same size, we prove that the optimal value of the MRFLP is less than or equal to the optimal value of the SRFLP divided by the number of rows of the MRFLP. We derive equidistant double-row layouts satisfying this property in a very short time and we improve some of the best known upper bounds for the equidistant DRFLP. Given a double-row instance with arbitrary department lengths we provide a formula for the relation of the optimal value of the DRFLP and the SRFLP and provide an example which shows that this bound is tight. In addition, we present heuristic approaches for the DRFLP based on good or optimal single-row layouts. For instances with up to 40 departments we obtain small gaps to the best known upper bounds and for even larger instances we improve the best known upper bounds. Our approaches are significantly faster than the ones in the literature.
Citation
Faculty of Business and Economics, TU Dortmund University, Vogelpothsweg 87, D-44227 Dortmund; November 2020