1│fuzzy│min sum from i=1 to n (C_i)模型的禁忌搜索算法

Tabu search algorithm for model 1│fuzzy│min sum from i=1 to n (C_i)

根据三角形模糊数的特性,在对总加工时间模糊度有约束的条件下,构造出NP-困难的1 fuzzy min∑ni=1Ci排序模型的禁忌搜索(TS)算法.构造的邻域函数为互换操作.针对1 fuzzy min∑ni=1Ci模型的特点,设计带有惩罚项的分段线性适应度函数,以规避解的不可行性.并且,取不同的禁忌长度,观察禁忌搜索状态随迭代步数的移动轨迹,以寻求较好的计算参数组合.实例计算表明,该算法的实际应用可行,具有良好的收敛性和较高的搜索效率,且目标函数轨迹呈三阶段变化模式.迭代步数充分大后,目标函数周期性振荡,陷入循环搜索.这种性质能够帮助选择禁忌(tabu)参数值,确定迭代终止条件.

According to the property of triangular fuzzy number, a tabu search（TS） algorithm about n the scheduling model nondeter ministic polynomial hard （NP-hard） of [1｜fuzzy｜min n∑i=1 Ci]was constructed under the condition of restricted makespan fuzzy extent. The neighborhood function constructed was swap. Focusing on the characteristic of 1｜fuzzy｜min n∑i=1 Ci model, segmental linear fitness function with penalty function was designed to avoid the infeasible solution. Tabu length is also alterable. In order to explore better parameters combination, the move track of TS along with iterative process was observed. The practical example shows that the algorithm is feasible in practical case, and has better astringency and searching efficiency. The track of the objective function reports three-stage variation model. If the number of iterative process steps are big enough, the objective function will surge periodically, and fall into circulating search. This property is good for choosing values of tabu parameter, and helpful to determine the condition to finish iterative process.