求解流水线调度问题的万有引力搜索算法  

A gravitational search algorithm for flow shop scheduling

作　　者：谷文祥[1] 李向涛[1] 朱磊[1] 周俊萍[1] 胡艳梅[1] 

机构地区：[1]东北师范大学计算机学院,吉林长春130117

出　　处：《智能系统学报》2010年第5期411-418,共8页CAAI Transactions on Intelligent Systems

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

摘　　要：研究了以最大完工时间为目标的流水线调度问题,使用万有引力算法求解调度问题,提出了一种最大排序规则,利用物体间各个位置分量值存在的大小次序关系,并结合随机键编码的方法产生,将物体的连续位置转变成了一个可行的调度方案;提出了一种边界变异的策略使得越界的物体不再聚集在边界上,而是分布在边界附近的可行空间内,从而增加种群的多样性;结合交换算子和插入算子提出了一种新的局部搜索算法,有效地避免了算法陷入局部最优值,进一步提高了解的质量.最后证明了算法的收敛性,并且计算了算法的时间复杂度和空间复杂度,仿真实验说明了所得算法的有效性.An improved gravitational search algorithm （IGSA） was proposed to solve the flow shop scheduling problem with the objective of minimizing production time. First, to make a GSA suitable for permutation of the flow shop scheduling problem （PFSSP） , a new largest-rank-rule based on a random key was introduced to convert the continuous position of the GSA into the discrete job permutation so that the GSA could be used for solving PFSSP. Second, a new boundary mutation was proposed. This operation stopped the agents which have mutations as a result of using the above method from gathering at the border. They were distributed at a feasible distance from the bound- ary. This improvement also improved the population diversity. Third, by combining the communicating operator and inserting operator, the new local search was designed to help the algorithm escape from the local minimum. Finally, the convergence of the iterative algorithm and its complexities in time and space were proven. Additionally, simulations and comparisons based on PFSSP benchmarks were carried out, which show that the proposed algorithm is both effective and efficient.

关 键 词：万有引力搜索算法 流水线调度 局部搜索算法 边界变异 最大排序规则 最大完工时间 

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