Optimal placement of multiple finite-size rectangular facilities in an existing layout

In this paper, we investigate a new problem of optimal placement of multiple finite-size rectangular facilities with known dimensions in the presence of existing rectangular facilities. This problem has applications in facility layout (re)design in manufacturing, distribution systems, services, and electronic circuit design. Three types of facility interactions are considered: between new facilities and existing facilities; between pairs of existing facilities; and between pairs of new facilities. All interactions are serviced through a finite number of input/output points located on the facility boundaries. Travel is assumed to occur according to the rectilinear (or Manhattan) metric and travel through facilities is prohibited. The objective is to find the simultaneous and non-overlapping placement of new facilities, which minimises the total weighted distance (Minisum objective) between the interacting facilities. To arrive at a solution, we divide the feasible region into sub-regions and prove that the candidates for optimal placement of the new facilities can be drawn from the sub-region boundaries. Being a continuous generalisation of the quadratic assignment problem, the solution complexity of this procedure is exponential in the number of new facilities. Our main contribution is the rigorous treatment of an important problem that unifies facility location and layout theories with minisum objective and rectilinear metrics.