-
题名求解流水线调度问题的万有引力搜索算法
被引量:23
- 1
-
-
作者
谷文祥
李向涛
朱磊
周俊萍
胡艳梅
-
机构
东北师范大学计算机学院
-
出处
《智能系统学报》
2010年第5期411-418,共8页
-
基金
国家自然科学基金资助项目(60473042
60573067
60803102)
-
文摘
研究了以最大完工时间为目标的流水线调度问题,使用万有引力算法求解调度问题,提出了一种最大排序规则,利用物体间各个位置分量值存在的大小次序关系,并结合随机键编码的方法产生,将物体的连续位置转变成了一个可行的调度方案;提出了一种边界变异的策略使得越界的物体不再聚集在边界上,而是分布在边界附近的可行空间内,从而增加种群的多样性;结合交换算子和插入算子提出了一种新的局部搜索算法,有效地避免了算法陷入局部最优值,进一步提高了解的质量.最后证明了算法的收敛性,并且计算了算法的时间复杂度和空间复杂度,仿真实验说明了所得算法的有效性.
-
关键词
万有引力搜索算法
流水线调度
局部搜索算法
边界变异
最大排序规则
最大完工时间
-
Keywords
gravitational search algorithm
flow shop rule
production time minimizing scheduling
local search
boundary mutation
largest rank
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-