A combined zone-LP and simulated annealing algorithm for unequal-area facility layout problem

Facility layout problem (FLP) is one of well-known NP-hard problems and has been demonstrated to be useful in enhancing the productivity of manufacturing systems in practice. This paper focuses on the unequal-area FLP (UA-FLP) whose goal is to locate departments with different areas within a given facility so as to minimize the total material handling cost. A novel approach, which we call a combined zone-linear programming (zone-LP) and simulated annealing algorithm, is developed for solving the UA-FLP. The zone-LP approach is a layout construction technique for the unequal-area departments and consists of two phases. In the first phase, a zoning algorithm is implemented to determine the relative positions between the departments. In this algorithm, for the sake of problem simplification and computational efficiency, each department is treated as a rectangle with an allowable aspect ratio and the area of the facility is assumed to be unbounded. In the second phase, by using the relative positions obtained in the first phase as input, a linear programming (LP) model is developed to identify the exact locations and dimensions of departments within the facility with specified sizes while satisfying their maximum aspect ratio requirement and the shape constraints. We also design a simulated annealing algorithm to improve the placing sequence. Finally, our computational results suggest that our proposed algorithm is efficient compared with the best existing approach in the literature.