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

被引：25

作者：

谷文祥

李向涛

朱磊

周俊萍

胡艳梅

机构：

[1] 东北师范大学计算机学院

来源：

智能系统学报 | 2010年 / 5卷 / 05期

关键词：

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

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

研究了以最大完工时间为目标的流水线调度问题,使用万有引力算法求解调度问题,提出了一种最大排序规则,利用物体间各个位置分量值存在的大小次序关系,并结合随机键编码的方法产生,将物体的连续位置转变成了一个可行的调度方案;提出了一种边界变异的策略使得越界的物体不再聚集在边界上,而是分布在边界附近的可行空间内,从而增加种群的多样性;结合交换算子和插入算子提出了一种新的局部搜索算法,有效地避免了算法陷入局部最优值,进一步提高了解的质量.最后证明了算法的收敛性,并且计算了算法的时间复杂度和空间复杂度,仿真实验说明了所得算法的有效性.

引用

页码：411 / 418

页数：8

共 3 条

[1] 求解车间调度问题的自适应混合粒子群算法 [J].

张长胜 ;

孙吉贵 ;

欧阳丹彤 ;

张永刚 .

计算机学报, 2009, 32 (11) :2137-2146

[2]

An Effective Hybrid Heuristic for Flow Shop Scheduling[J] . D.-Z. Zheng,L. Wang.International Journal of Advanced Manufacturing Technology . 2003 (1)

[3] The two-machine total completion time flow shop problem [J].

DellaCroce, F ;

Narayan, V ;

Tadei, R .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 90 (02) :227-237

← 1 →