Abstract: The facility layout problem is a critical issue in the manufacturing industry. Designing a reasonable facility layout scheme can not only significantly reduce the overall operating cost of the production system, but also improve the material disposal efficiency and shorten the residence time of materials in the production plant. Therefore, the study of facility layout is of great value and practical significance for manufacturing companies to reduce unreasonable production costs and improve production efficiency. In recent years, some scholars have conducted extensive research on the layout of facilities, but most of them focus on the static facility layout problem (SFLP). With the continuous development of industrial engineering, the traditional SFLP has become increasingly limited: it is difficult for enterprises to adjust facility layout plans in a timely manner according to updated product demand, in order to quickly respond to market changes. Since the dynamic facility layout problem (DFLP) considers the rapid response to market changes and is more in line with the modern actual facility layout in workshop, it has attracted widespread attention from scholars in recent years.
The dynamic facility layout problem with multiple rows (MR-DFLP) refers to the layout of N given facilities in each period for T future production planning periods on the basis of predictable product demands, so as to minimize logistic handling costs and facility replacement costs and satisfy some constraints. The constraints mainly include: (1)all facilities must be placed in rows and do not extend beyond boundaries of the shop floor; (2)all facilities cannot overlap each other and must satisfy certain spacing requirements. Given the length and the width of a rectangular shop floor, all facilities are placed sequentially in the shop floor, following a bottom-to-top, left-to-right rule of placing by rows, with an automatic row change once the right boundary of a facility exceeds that of the shop floor.
To solve the MR-DFLP, an improved genetic algorithm (iGA) is first put forward based on adaptive crossover operations and four mutation operations with adaptive selection probability which include insertion, single-point exchange, multi-point exchange, and inversion. Furthermore, considering the strong memory and global optimization ability of the backtracking search algorithm (BSA), the BSA is introduced to solve the MR-DFLP at the first time. To further enhance the BSA’s development ability and variety of population, four improved backtracking search algorithms (iBSA1-iBSA4) are proposed by improving the selection, Map mapping mechanism and population update strategy of the BSA algorithm.
The three test instances are cited from the literature. The experimental results show that for every instance the overall performance of the five BSA algorithms is significantly better than that of the iGA algorithm, while the target value and execution time of the iBSA4 algorithm are better than those of the BSA algorithm and other three improved BSA algorithms, indicating the effectiveness of the improvement strategies proposed in this article. In addition, the running time of various BSAs is significantly shorter than that of the iGA, which is mainly due to the lower time complexity of the BSAs algorithms.
Overall, this article provides an in-depth analysis of the background and research significance of the MR-DFLP. The research not only puts forward a mathematical optimization model for solving the problem, but also achieves substantial research results by introducing multiple improved algorithms. However, there are still some potential challenges, indicating future research directions. Due to the fact that irregular shaped mechanical equipment is generally used in the actual production activities of manufacturing enterprises, it is necessary to study the dynamic layout of irregular facilities (where the difficulties of problem mainly involve such things as how to calculate the embedding amount between overlapping facilities and how to handle the non-overlap constraints, etc.) and other DFLPs in a variety of real-world scenarios in the future.

Key words: dynamic facility layout problem, genetic algorithm, backtracking search algorithm, partial matching mapping crossover, adaptive mutation

摘要： 针对多行动态设施布局问题(MR-DFLP),首先基于自适应概率的交叉操作和四种变异操作(包括插入操作、单点交换、多点交换和逆序操作),提出一种改进的遗传算法(iGA)。在此基础上,考虑到回溯搜索算法(BSA)具有较强“记忆”功能和全局寻优能力,将BSA算法首次引入MR-DFLP进行求解。为进一步提升算法的开发能力和种群多样性,对BSA算法的选择、Map映射机制以及种群更新策略进行改进,提出了四种改进的回溯搜索算法(iBSAs)。通过对三组实际算例进行计算,实验结果验证了所提出的各种改进算法的有效性。

关键词: 动态设施布局, 遗传算法, 回溯搜索算法, 部分匹配映射交叉, 自适应变异