412 智能系统学报 第5卷 法.它通过群体中各粒子之间的万有引力相互作用 在特定的时间t,定义作用在物体i和物体j之 产生的群体智能指导优化搜索，但是目前对于GSA 间的重力搜索表示为 算法的研究还很少.实验证明，GSA的收敛性明显 优于PS0、遗传算法(GA)等其他智能优化算法，但 r=G(4x,9(0-0. Ri(t)+e 已提出的算法都存在早熟收敛，易陷入局部最优，缺 式中：M表示施力物j的质量；M表示受力物i的 少有效加速机制. 质量；8是一个小的常量；R,(t)是物体i和物体j之 为了解决以上的不足，本文提出了一种基于万 间的欧几里德距离： 有引力搜索算法的IGSA算法用于求解流水线调度 R(t)=‖X(t),X(t)‖2： 问题.考虑到连续的GSA算法不能处理离散的调度 G(t)是在时间t下的引力常量： 问题，提出了一种最大位置规则.为了提高GSA算 G(t)=Ge吃 法的效率，提出了一种边界变异策略，进而增加种群 则物体i在d维的合力可以表示为 的多样性.并且为了进一步提高解的质量，提出了一 N 种新的局部搜索算法.最后分析了IGSA算法的收 r=∑rand xF(t). i=1同*i 敛性，并证明该算法的空间复杂度为 通过运动法则，在时间t时物体i在第d维的加速度： O((6n+2m)×d)和群体每次进化的最坏渐进时间 F(t) 复杂度为O(md).仿真实验结果表明该算法是有 a(t)=M(t) 效的. 式中：M:(t)表示物体i的惯性质量.则物体的速度 1流水线调度问题的数学模型 更新为 (t+1)rand xv (t)a (t), 流水线调度问题可描述如下：n个待加工的作 x(t+1)=x()+(t+1). 业N=J1,2,…,Jn需要在m台机器加工M=M, 式中：rand是一个在[0,1]之间的随机数，用它可以 M2,·,Mn,每个作业由m道连贯的工序组成，每道 让搜索变得随机化 工序要求不同的机器完成，这些作业通过机器的顺 重力搜索和惯性质量通过适应度函数计算得 序是一样的，它们在每台机器上的顺序也是一样的， 到.质量高的物体吸引力强，移动地比较慢，假设引 每个作业J:在机器m上的处理时间为Pg·对于一 力质量和惯性质量相等，物体的质量可以使用1个 个可行调度π={π1，T2,…,πn},各作业的完工时 隐射.则 间可按如下方法计算： Ma=M=M:=M,i=1,2,…,N, C(π，1)=P1, m,()=m（)-me(t) C(m,1)=C(m-1,1)+P1j=2,3,…,n, met（t)-o(t)' C(π1，i)=C(π1，i-1)+Pmi,i=2,3,…,m, m,(t) M:(t)= C(mj,i)max(C(j-,i),C(mj,i-1))+pm.i, ∑m,(回 j=2,3,…,n,i=2,3,…,m. 式中：mm(t)表示在时刻t,物体i的最好适应度值， 最大完工时间可表示为 met(t)、oe(t)被定义为 Cms（π）=C(πn,m). 流水线调度的目标是发现一个最好的方案π·，使得 m=（)Fenm（), Cm(π)≤C(Ta,m),Vπ∈. ma（）(). 3IGSA调度算法 2 万有引力算法 3.1最大排序规则 万有引力搜索算法9]是基于引力法则，它们质 万有引力搜索算法(GSA)是一种连续的智能算 量的性质对它们之间的行为表现有着一定的作用. 法，标准的万有引力搜索算法所具有的连续编码不 物体之间都是相互吸引的，相互之间的作用力引起 能被直接地用于求解流水线调度.因此构造从物体 物体之间都朝着质量大的物体的方向移动，在GSA 位置矢量到工件排序的恰当映射是应用GSA算法 中，每个物体有4个特征：位置、惯性权重、施力物、 解决流水线调度问题的首要和关键问题.在本文中， 受力物.物体的位置就是问题的解.每个物体被定义 提出一种基于随机键的新的排序规则一最大排序 在一个n维的搜索空间内，由N个物体组成的种群 规则.使用这个规侧，可以将连续的物体位置转化为 X=(（x1,2,…,x),其中第i个物体的位置为X:= 离散的调度方案.在这个规则中，最大的实数将首先 (x,x,…,x,…,x),x代表物体i在d维空间的 被挑选出作为新的调度方案的第1个位置，稍小的 位置. 实数将被挑选出作为新的调度方案的第2个位置