一类基于FSP问题Block性质的快速TS算法

Fast TS algorithm based on Block properties of FSP

为解决现有算法在求解大规模流水线调度问题(FSP)时计算时间过长的问题,从缩小邻域的角度出发,提出一种基于FSP问题Block性质的快速禁忌搜索(TS)算法.利用Block性质,算法在保证不丢失最优解的基础上,将邻域中大部分劣解排除,将搜索重点集中在邻域中“最优希望”的区域,以缩小邻域和减少计算时间.数值仿真实验表明,该算法能在较短时间内获得大规模FSP问题的满意解.

To the problem that it takes a long time for current available algorithms to solve large-scale flow shop scheduling problems （FSPs）, a fast taboo search algorithm based on Block properties of FSP is proposed to reduce the neighborhood size. With the Block properties, most bad solutions in the neighborhood are excluded without losing the optimal solution. The point of search is focused on the ＂most promising＂ area to reduce the size of neighborhood and running time. Numerical experiments show that good solutions of large-scale FSPs are found in a short time with the proposed algorithm.