We introduce a new facility layout problem, the so-called T-Row Facility Layout Problem (TRFLP). The TRFLP consists of a set of one-dimensional departments with pairwise transport weights between them and two orthogonal rows which form a T such that departments in different rows cannot overlap. The aim is to find a non-overlapping assignment of the departments to the rows such that the sum of the weighted center-to-center distances measured rectilinear directions is minimized. The TRFLP is a generalization of the well-known Multi-Bay Facility Layout Problem with three rows (3-BFLP). Both problems, the TRFLP and the 3-BFLP, have wide applications, e.g., factory planning, semiconductor fabrication and arranging rooms in hospitals. In this work we present a mixed-integer linear programming approach for the TRFLP and the 3-BFLP based on an extension of the well-known betweenness variables which now can be equal to one if the corresponding departments lie in different rows. One advantage of our formulation is the calculation of inter-row distances without big-M-type constraints. We provide cutting planes exploiting the crossroad structure in the layout, and hence T-row (3-Bay) instances with up to 18 (17) departments are solved to optimality in less than 7 hours. The best known approach for the 3-BFLP is clearly outperformed. Additionally, tight lower bounds for larger instances are calculated to evaluate our heuristically determined layouts.
Citation
Faculty of Business and Economics, TU Dortmund University, Vogelpothsweg 87, D-44227 Dortmund; March 2020