基于大规模FSP问题Block性质的SA算法

对于大规模流水线调度问题(FSP),模拟退火算法(SA)中邻域候选解的被接受概率,因邻域增大和邻域中的劣解数的增多而大大降低,SA算法的性能因而大为降低。针对这一问题,提出一种基于FSP问题Block性质的SA算法。将邻域划分成若干个子邻域,用子邻域中的最好解作为候选解,以提高候选解被接受的概率。引入FSP问题的Block性质,减小邻域尺寸,将搜索集中在邻域中“最有希望”的区域,进一步增强算法性能。数值仿真实验表明,该算法能在较短时间内获得大规模FSP问题的近优解。

SA algorithm based on block properties of large-scale FSPs

Simulated annealing(SA) algorithm is one of the commonly used approaches in solving flow shop scheduling problems(FSPs).For the large-scale FSPs,the accepting probability of the candidate neighbor decreases greatly as the size of neighborhood and the number of bad neighbors increase,which leads to low performance of SA.A kind of simulated annealing algorithm based on the Block properties of FSP is proposed to solve the problem.In the proposed algorithm,the whole neighborhood is first divided into several small sub-neighborhoods.The best neighbor in the whole sub-neighborhood is selected as the candidate neighbor so as to increase the accepting probability.Moreover,the Block properties of FSP is introduced,with which the size of neighborhood is greatly reduced,and search is then focused on the promising area of the neighborhood,which enhance the performance more.Numerical experiments show that the near-optimal solutions of large-scale FSPs can be found in a short time with the proposed algorithm.