Decorous combinatorial lower bounds for row layout problems

In this paper we consider the Double-Row Facility Layout Problem (DRFLP). Given a set of departments and pairwise transport weights between them the DRFLP asks for a non-overlapping arrangement of the departments along both sides of a common path such that the weighted sum of the center-to-center distances between the departments is minimized. Despite its broad applicability in factory planning, only small instances can be solved to optimality in reasonable time. Apart from this even deriving good lower bounds using existing integer programming formulations and branch-and-cut methods is a challenging problem. We focus here on deriving combinatorial lower bounds which can be computed very fast. These bounds generalize the star inequalities of the Minimum Linear Arrangement Problem. Furthermore we exploit a connection of the DRFLP to some parallel identical machine scheduling problem. Our lower bounds can be further improved by combining them with a new distance-based mixed-integer linear programming model, which is not a formulation for the DRFLP, but can be solved close to optimality quickly. We compare the new lower bounds to some heuristically determined upper bounds on medium-sized and large DRFLP instances. Special consideration is given to the case when all departments have the same length. Furthermore we show that the lower bounds that we derive using adapted variants of our approaches for the Parallel Row Ordering Problem, a DRFLP variant where the row assignment of the departments is given in advance and spaces between neighboring departments are not allowed, are even better with respect to the gaps.