Decorous combinatorial lower bounds for row layout problems

Abstract 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 compute…