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

摘要

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