Optimal and heuristic solutions for placing multiple finite-size rectangular facilities in an existing layout
研究了在已有矩形设施布局中放置多个已知尺寸矩形设施的问题，提出了针对小规模问题的最优解法和针对工业规模问题的启发式解法，帮助实践者根据问题特征选择方法。
In a companion paper (Date, K., and R. Nagi. [(2023) Optimal Placement of Multiple Finite-size Rectangular Facilities in an Existing Layout. International Journal of Production Research, THIS ISSUE]) we investigated a new problem of optimal placement of multiple finite-size rectangular facilities with known dimensions in the presence of existing rectangular facilities. We introduced the requisite theory to arrive at a solution by dividing the feasible region into sub-regions whose boundaries provide the candidates for the optimal placement. In this paper, we focus on developing optimal and heuristic solution methods for solving problem instances with various facility counts. To solve small instances with fewer facilities, we develop two optimal methods: (1) efficient explicit enumeration based on a tree state-space representation and (2) an implicit enumeration scheme that uses a flow-decomposition-based lower bound to reduce the search space and time. To solve industrial-sized instances, we have to resort to a family of construction and improvement heuristics given that the problem is NP-hard. The heuristic procedures perform well for non-pathological cases with an acceptable optimality gap. The main contribution of this paper is a range of optimal to heuristic methods that can be applied by the practitioner depending on their problem characteristics and desired efficiency.