Solving the constrained Single-Row Facility Layout Problem with Integer Linear Programming
针对带位置、顺序和关系约束的单行设施布局问题，提出一种新的整数线性规划模型，在计算实验中优于现有精确方法，为多达42个部门的实例提供了最优解和强下界。
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.