改进的萤火虫算法求解阻塞流水线调度问题  

An improved firefly algorithm for the blocking flow shop scheduling problem

作　　者：郭丽萍[1] 李向涛[1] 谷文祥[1,2] 殷明浩[1] 

机构地区：[1]东北师范大学计算机科学与信息技术学院,吉林长春130117 [2]长春建筑学院基础教学部,吉林长春130607

出　　处：《智能系统学报》2013年第1期33-38,共6页CAAI Transactions on Intelligent Systems

基　　金：国家自然科学基金资助项目(60803102;61070084)

摘　　要：为了提高阻塞流水线调度问题的求解性能,提出了一种改进的萤火虫算法来求解阻塞流水线调度问题.首先,提出一种离散机制把个体的实数编码形式转换成离散的作业序列,从而使算法能够应用于离散问题求解;其次,设计一种双重初始化方法,并将NEH启发式方法应用到初始化中来,使算法有一个较优的初始化环境,提高初始种群的解的质量;此外,重新设计了算法中个体的移动方式来增大搜索域;最后,以一定概率对种群中的个体进行局部搜索,加强算法的局部搜索性能.通过对Taillard数据集中部分实例进行求解,实验结果验证了新算法的有效性.In order to improve the solving performance of the blocking flow shop scheduling problem, the researcher proposes to examine an improved firefly algorithm. Firstly, a discrete mechanism was proposed to convert the real coded form of individuals to discrete job sequences, so that the algorithm could be used to deal with discrete problems. Secondly, a double-initialization method was designed and the NEH （Nawaz-Enscore-Ham） heuristic method was applied to the initialization, which provided a superior initial environment and improved the quality of the solu- tion of the initial population. In addition, the research paper focused on redesigning the movement pattern of indi- viduals to enhance the search space. Finally, a local search algorithm was applied to individuals with a certain probability, for the purpose of enhancing the ability to search locally. The improved firefly algorithm was then tested utilizing the Taillard datasets, and the results verified the effectiveness of the new algorithm.

关 键 词：阻塞流水线调度问题 萤火虫算法 离散机制 NEH启发式 局部搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]