·34 智能系统学报 第8卷 阻塞流水线调度问题 时间的最小值e3.3为21，对应的作业执行顺序为 1 {J3,J2,J1},如图1所示。 阻塞流水线调度问题可以描述为：n个作业J1, M J2,…,Jn要在m台机器M1,M2,…,Mm上运行，每 M 个作业包含m道工序，每个作业的工序必须按照统 M 一顺序在m台机器上执行，每个作业在每台机器上 的运行时间是固定的，要求协调不同作业的执行顺 4 序，使得某种生产性能指标达到最优.阻塞流水线调 812 162024 度问题的约束条件包括如下： 图1问题的甘特图表示 1)每个作业在每台机器上只能加工1次； Fig.1 The Gantt chart of the example 2)每台机器每次最多只能加工1道工序； 2萤火虫算法 3)每台机器上的作业加工顺序相同； 4)作业的某道工序在某台机器上的加工一旦 萤火虫算法是一种通过模拟自然界中萤火虫发 开始，便不能终止； 光行为的仿生算法.目前，人们对自然界中萤火虫的 5)一个作业完成某道工序后，该作业将在当前 发光行为的意义还存在很多争议，不过有2点是确 机器上滞留直到下游机器变为可用为止。 定的：吸引配偶和吸引潜在的猎物. 在该问题中，用π={π1，π2，…，πn}表示一个 般情况下，可见光的强度随着当前位置到光 调度序列，00=1,2，…，n;k=1,2,…,m)表示作 源距离的增大而减小，另外，空气还要吸收一部分光 业j在机器k上执行一个无间断的工序，其所需时 源.因此，董火虫发出光只在一定的距离范围内可以 间为P.k=1,2,…,n;k=1,2,…,m),e,(=1,2, 被其他萤火虫看见.萤火虫算法约定9)：1)萤火虫 …,;k=0,1,…,m)表示第j个作业在第k台机器 之间不存在性别之分，每只萤火虫都可以吸引其他 上的离开时间.则有： 的萤火虫，也可以被其他的萤火虫吸引；2)萤火虫 e1,0=0, (1) 的吸引力和它们发出的光的亮度成正比，因此，对于 e1,k=e1,k-1+p1,k,k=1,2,…,m-1,(2) 任意2只萤火虫来说，亮度较弱的萤火虫会朝着亮 e.0=e-11,j=2,3,…,n, (3) 度较强的萤火虫飞行；如果当前可见光距离范围内， ek=max{,k-1+P.k,e-l,k1},j=2,3,…,n, 没有比自己更亮的萤火虫时，则该萤火虫实行随机 k=1,2,…,m-1, (4) 飞行策略：3)光的亮度一般由求解问题的目标函数 em=e,m-1+Dm,j=1,2,…,n. (5) 决定. 本文选取最大完工时间最小为优化指标，那么 在萤火虫算法中，每只萤火虫称为一个“个 最大完工时间C=(π)=em,m,且它的计算复杂性为 体”，每个个体包含亮度、吸引力、位置等属性.在该 0(mn). 算法中，个体在某个固定位置的亮度I是固定的，该 以3个作业J1、J2、J为例，下面举例说明如何 变量的设定取决于具体问题的目标函数.其他个体 求解阻塞流水线调度问题，3个作业在3台机器上 看到该个体的亮度则随着它们之间距离的增大而减 运行所需时间如表1所示.第1个作业在第1台机 小，此外，传播介质也会吸收一部分光线，因此，个体 器上运行所需要的时间为3，第1个作业在第2台 在距离当前位置「处的亮度还和介质的吸收率有 机器上运行所需要的时间为4，依此类推， 关9].一般把一个个体在距离该个体r处的亮度表 表1时间矩阵 示为 Table 1 Time matrix of an example I(r）=1oer2. (6) 机器 式中：1，为个体在当前所处位置的亮度，y为介质的 作业 M M M 吸收率.有时，为了减小个体亮度变弱的速率，式 (6)也可用如下公式代替： J 3 3 2 6 5 1()=1+7 7 每个个体对其他个体的吸引力B也是相对的， 由式(1)~(5)可以计算出该问题的最大完工 它随着2个个体之间距离的增大而减小；此外，吸引