求解单向环型布局问题的一种禁忌搜索算法

A Tabu Search Algorithm for Unidirectional Loop Layout Problem

单向环型布局在柔性制造系统中得到广泛应用,在分析该布局特点的基础上,提出了一种改进的禁忌搜索算法来求解该布局优化问题。基于总零件重新载入次数最小的原则,建立数学模型。设计禁忌搜索算法时,采用插入法产生初始解,以两台设备的交换作为禁忌对象构建禁忌表,采用2-opt方式产生邻域结构,在此基础上编写相关程序实现模型计算。通过对算例和实际问题进行求解验证,说明了该算法的有效性。

Unidirectional loop layout has been widely used in flexible manufacturing system. In this paper, an improved tabu search algorithm is proposed to solve the unidirectional loop layout problem based on analysising the character of this layout. First, a mathematical model is established to minimize the number of the total parts reloaded. When designing the tabu search algorithm, the interpolation method is used to generate an initial solution. And then, the exchange of the two devices as a taboo object are adopted to develop a tabu list and take 2-opt way to generate neighborhood, realizing the calculation of the model with some relative programs. Finally, the feasibility and efficiency of the algorithm is illustrated via dealing with different examples and practical solution verification.