基于激素调节机制IPSO算法的相同并行机混合流水车间调度问题

顾文斌，李育鑫，钱煜晖，肖紫涵，秦展鹏

(河海大学 机电工程学院，江苏 常州 213022)

0 引言

混合流水车间调度问题(Hybrid Flow-shop Scheduling Problem, HFSP)又被称为柔性流水车间调度问题，是传统流水车间调度问题和并行机调度问题的综合。SALVADOR[1]基于石油工业中的调度问题，于1973年首次提出了混合流水车间调度问题。在HFSP中，所有工件都以相同的顺序流经各个加工阶段，每个阶段都有一台或多台加工机器，且至少有一个阶段的并行机器数大于1。问题的研究目标是如何安排所有工件在各个阶段的加工顺序以及加工机器，以改善企业生产的一些性能指标，如最小化最大完工时间、最小化生产能耗、最小化关键机器负载率等。海量的工件，以及繁多的加工阶段和加工机器使得HFSP具有很高的复杂性，它已被证明是NP-Hard问题。HFSP具有很强的工程背景，尤其是流程工业和离散制造工业，现已广泛应用于机械、钢铁、化工、物流、食品、纺织和半导体等领域，因此研究HFSP具有重要的实际意义。

HFSP通常被分为相同并行机、均匀并行机和不相关并行机3类[2]。相同并行机HFSP是指同一工件在一个阶段的加工时间是固定的，与机器无关；均匀并行机HFSP是指同一工件在一个阶段的加工时间与所选择机器的加工速度成反比；不相关并行机HFSP是指同一工件在一个阶段的加工时间取决于工件与加工机器的匹配程度。本文研究相同并行机HFSP(HFSP with Identical Parallel Machine, HFSP-IPM)。

目前求解HFSP-IPM的方法通常分为精确方法、启发式方法和元启发式方法3类。精确方法包括数学规划法、分支定界法和拉式松弛算法等，能够解决小规模的简单问题，但实际问题的解空间通常很大，其计算时间令人难以接受;启发式方法包括NEH(Nawaz-Enscore-Ham)算法、Palmer算法和CDS(Campbell-Duder-Simth)算法等，虽然能够在短时间内获得问题的解，但往往容易陷入局部最优，解的质量得不到保证;元启发式方法通过模拟自然界的规则和现象，能够很好地求解HFSP，近年来相关算法不断出现，如遗传算法(Genetic Algorithm, GA)[3]、蚁群优化(Ant Colony Optimization, ACO)算法[4]、人工蜂群(Artificial Bee Colony, ABC)算法[5]、分布估计算法(Estimation of Distribution Algorithm, EDA)[6]、候鸟优化(Migrating Birds Optimization, MBO)算法[7]等。元启发式方法通过构造一系列初始排列，经过一定数量的循环迭代从而得到问题的最优解，是一种智能优化算法。例如，王圣尧等[8]提出一种基于概率模型的分布估计算法来求解HFSP;崔琪等[9]针对混合流水车间调度问题提出一种改进的混合变邻域搜索的遗传算法，该算法融入变邻域搜索的思想，以增强局部搜索能力;轩华等[10]针对以最小化总加权完成时间为目标的可重入HFSP，提出一种自适应的改进遗传算法;PAN等[11]提出24种启发式规则，将其与离散人工蜂群算法混合，从而求解混合流水车间调度问题;CAI等[12]针对分布式HFSP提出一种动态混合蛙跳算法，该算法采用全局搜索和动态多邻域搜索，有效提高了搜索质量;OZTOP等[13]针对HFSP提出一种双目标混合整数线性规划模型和一种双目标约束规划模型，并设计了7种双目标元启发式算法来解决该问题。

粒子群优化(Particle Swarm Optimization, PSO)算法最早由KENNEDY等[14]于1995年提出，其基本思想是模拟鸟群随机搜寻食物的捕食行为。PSO算法具有实现容易、搜索能力较强、控制参数少、收敛快等优点，因此受到研究人员的广泛关注，常用于函数优化、神经网络训练、模糊系统控制等领域。

近年来，PSO算法在生产调度领域被广泛运用，尤其是求解HFSP。张其亮等[15]将PSO算法应用于双向无等待混合流水车间调度问题，该算法融合工件冲突的检测和化解方法，高效地求解了高速磁浮列车调度问题;张志鹏等[16]提出一种遗传粒子群混合算法，用于求解多目标混合流水车间调度问题，该算法将两个分支算法产生的最优解分别作为彼此的初始因子，增强了算法的进化速度;MARICHELVAM等[17]针对多阶段HFSP提出一种改进的粒子群算法，该算法引入调度规则、构造式启发式算法以改进初始解，同时结合变邻域搜索算法缩短了收敛时间;ZHOU等[18]针对两阶段混合流水车间调度问题提出了混合差分进化粒子群算法，该算法创造性地融入卡尔曼滤波算法和多级学习策略，以增强全局搜索能力;GOLNESHINI等[19]针对具有模糊加工时间和模糊交货期的不相关并行机HFSP提出一种基于聚类的混合遗传粒子群算法;ROOEINFAR等[20]针对具有有限缓冲区和固定间隔预防性维修的HFSP提出一种混合方法，该方法融合了计算机仿真模型、遗传算法、模拟退火算法和粒子群优化算法，以提高搜索质量。同其他智能优化算法一样，粒子群算法存在易早熟、容易陷入局部收敛的缺点，因此研究人员常将该算法与其他优化算法进行混合，以提高其全局搜索能力。

FARHY[21]确立了激素分泌的基本原理，该原理描述了生物体内激素的调节规律。激素调节规律具有单调性和很好的收敛性，但鲜有研究人员尝试将其与优化算法相结合来解决调度问题，目前仅找到两篇相关文献。顾文斌等[22]针对置换流水车间调度问题提出了基于激素调节机制的改进型自适应粒子群算法，该算法引入了贪婪随机自适应算法和激素调节因子以提高搜索效率;GU等[23]针对具有运输约束的作业车间实时调度问题提出一种基于生物启发的动态调度优化方法。

本文对PSO算法的改进主要体现在以下几个方面：①基于NEH启发式算法提出了NNEH(new NEH)启发式算法，在保证初始种群多样性的同时提高了个体的质量；②基于激素调节函数的特性创造性地将其融入惯性因子中，使算法不易早熟，同时提出相关系数法改变了速度更新公式的自身认知项和社会认知项，提高了算法的搜索质量；③提出一种随机拓补结构，将每次迭代过程的种群最优位置改为可变的邻域最优位置，同时融入GA的基于两点和位置的两种交叉操作，以及插入、反转逆序、打乱互换3种变异操作，使算法不易陷入局部最优。

针对以最小化完工时间为目标的HFSP-IPM，本文提出一种改进粒子群优化(Improved Particle Swarm Optimization, IPSO)算法。首先，设计了基于排列的编码解码方法；然后，提出了NNEH启发式算法用于产生初始种群；接着，基于激素调节机制和相关系数法设计了一种新的粒子群速度更新改进公式；最后，结合随机拓扑结构、交叉和变异3种方法，扩大了算法的搜索空间。本文应用IPSO算法求解CARLIER等[24]提出的经典算例，获得了良好的可行解，验证了所提算法的有效性和优越性能。

1 混合流水车间调度问题

1.1 符号定义

记n为工件总数，i为工件序号(i=1,…,n)，s为阶段总数，k为阶段序号(k=1,…,s)，mk为阶段k上的并行机器总数(mk≥1)，j为机器序号，Pik为工件i在阶段k的加工时间，Sik为工件i在阶段k的开始加工时间，Cik为工件i在阶段k的加工完成时间，Mi为工件i的完工时间，Mmax={M1,M2,…,Mn}为加工任务的最大完工时间。

1.2 问题描述

HFSP-IPM可描述为：现有n个工件，s个加工阶段，每个加工阶段有mk台并行机器。要求满足以下约束条件：①每个工件在流水线上要以相同的顺序依次进行各个阶段的加工；②至少有一个加工阶段的并行机器数量大于1；③同一工件在同一阶段的加工时间是固定的；④每个工件在每一阶段只能选择一台机器进行加工；⑤一台机器在同一时刻只能加工一个工件。

HFSP-IPM通常有如下假设：①机器一旦进行加工便不可中断；②机器和工件在0时刻都可被获得；③所有工件在各个阶段的加工时间已知；④任意两个相邻加工阶段之间的缓冲区无限大；⑤不考虑工件在相邻阶段之间的运输时间以及机器转换工件的时间。本文求解以最小化完工时间为目标的HFSP-IPM，即确定各阶段的工件加工顺序以及对应的机器分配方案，从而使整个任务的最大完工时间(Mmax)最小。HFSP-IPM的示意图如图1所示。

1.3 HFSP-IPM数学模型

HFSP-IPM的数学模型表述如下：

T=minMmax,

(1)

Mmax≥Cis,i=1,…,n。

(2)

(3)

Yki1i2=

(4)

Cik=Sik+Pik,i=1,…,n;k=1,…,s；

(5)

(6)

Si(k+1)-Sik≥Pik,i=1,…,n;k=1,…,s；

(7)

Yki1i2+Yki2i1≤1,i=1,…,n;k=1,…,s；

(8)

Si1k-Ci2k+L*(3-Yki2i1-Xi1kj-Xi2kj)≥0,

i=1,…,n;i1≠i2;k=1,…,s;j=1,…,mk;

L是一个足够大的常数。

(9)

其中：式(1)是调度性能指标，即本文的适应度函数；式(2)代表整个加工任务的总完工时间大于等于在最后阶段任意工件的加工完成时间；式(3)和式(4)是两个变量的0-1变量约束；式(5)是任意工件在任意阶段的加工完成时间表达式；式(6)代表每个工件在任意阶段均只能在该阶段的一台机器上加工；式(7)代表任意工件需完成上一阶段的加工才能开始下一阶段的加工；式(8)和式(9)代表一台机器在同一时刻只能加工一个工件。

2 粒子群算法

在PSO算法中，优化问题在D维空间里的每一个D维解称为“粒子”[25]，每个粒子具有位置和速度两个属性，位置代表粒子在搜索空间里的位置，速度代表粒子移动的方向和快慢程度。在每次迭代过程中，粒子根据速度更新公式和位置更新公式不断调整自身的搜索路径。粒子每完成一次迭代，便根据适应度函数评估自身的适应度，以此更新个体最优位置pbest和种群最优位置gbest。一次次迭代后，便能很快找到问题的最优解。其中，粒子的速度更新公式和位置更新公式如式(10)和式(11)所示：

Vid(k+1)=w×Vid(k)+c1×r1×(Pid(k)-

Xid(k))+c2×r2×(Pgd(k)-Xid(k))，

(10)

Xid(k+1)=Xid(k)+Vid(k+1)。

(11)

其中：k表示当前迭代次数;w表示惯性因子;Vid(k)表示经过k次迭代后第i个粒子的第d个变量的速度;c1、c2表示学习因子或加速因子;r1、r2表示[0,1]内均匀分布的随机数;Pid(k)表示经过k次迭代后第i个粒子自身搜索到的最优位置的第d个变量;Xid(k)表示经过k次迭代后第i个粒子的第d个变量的位置;Pgd(k)表示经过k次迭代后种群搜索到的最优位置的第d个变量。

标准PSO算法流程如下：

步骤1初始化粒子群。

步骤2根据适应度函数计算每个初始粒子的适应度,对每个粒子的pbest和种群的gbest进行初始化。

步骤3根据速度更新式(10)和位置更新式(11)更新每个粒子。

步骤4根据适应度函数计算每个粒子的适应度。

步骤5更新pbest。判断粒子当前位置的适应度是否优于个体最优位置pbest的适应度，是则将当前位置赋给pbest，否则pbest保持不变。

步骤6更新gbest。判断粒子当前位置的适应度是否优于种群最优位置gbest的适应度，是则将当前位置赋给gbest，否则gbest保持不变。

步骤7判断是否满足迭代终止条件，是则结束迭代，否则迭代次数加1，转步骤3。

步骤8输出种群最优位置gbest。

3 基于激素调节机制的IPSO算法

3.1 编码和解码

3.1.1 编码方式

HFSP通常有矩阵编码[26]和排列编码两种编码方式。矩阵编码虽然详细地列出了每一阶段各个工件对应的加工机器和工件之间的先后加工顺序，但表达方式太过繁琐，不易对其进行操作。相比之下，排列编码简单易行，容易处理，因此本文采用排列编码作为HFSP-IPM的编码方法。排列编码是一种基于操作的编码方式，即取所有工件序号进行随机排列，从而形成一个个体，个体的长度等于待加工的工件数n，工件在个体中的位置代表工件在第一阶段的加工顺序。例如，对于具有6个待加工工件的HFSP-IPM，取P1={3,1,5,4,2,6}，则个体P1表示在第一阶段先加工工件3，然后依次对工件1,5,4,2,6进行加工。

3.1.2 解码方式

HFSP通常有两种置换解码和排列解码解码方式。本文基于排列解码提出以下解码方法来构造HFSP-IPM的调度方案：

(1)在工件排序方面，在第一阶段按照给定的加工序列对工件进行加工，在后续阶段里，按照先到先加工的原则对工件进行加工，即在阶段k(k>1)，先按照阶段k-1的完工时间进行升序排列，得到阶段k的加工序列，然后按照新的加工序列对各个工件进行加工。研究发现，工件需要完成所有工序的剩余时间越多，该工件对整个任务完工的影响越大，对其进行先加工能够减小任务的总完工时间。因此，若存在多个工件在上阶段的完工时间相同，则计算其剩余完工时间，将剩余完工时间进行降序排列，得到这些工件的加工序列。若剩余完工时间仍然一样，则这些工件之间进行随机排列。

3.2 种群初始化

初始化种群时既要考虑到种群内个体的质量，又要考虑到种群的多样性。NAWAZ等[27]提出的NEH启发式算法被认为是解决以最小化完工时间为目标的流水车间排序问题的最好的启发式算法，近些年，研究人员尝试将NEH启发式算法用于HFSP并取得了良好的效果[10]。NEH启发式算法的提出基于以下假设：对于完成所有工序的加工，具有更多总加工时间的工件应被赋予比具有较少总加工时间的工件更高的加工优先级。因此，本文提出一种NNEH启发式算法用以生成HFSP-IPM的初始种群，具体步骤如下：

步骤1计算所有工件完成各自所有工序加工所需要的总加工时间，然后根据总加工时间对工件进行降序排列，对于部分总加工时间相同的工件，它们之间进行随机排列，从而得到工件序列W。

步骤2从工件序列W中选择前两个工件，通过计算两个可能序列的完工时间来找到这两个工件的最佳序列，即完工时间较小的序列，将其加入到加工序列P中，并将这两个工件从工件序列W中删除。

步骤3随机选取工件序列W中的一个工件，然后遍历加工序列P中的每一个可插入位置，找到最佳插入位置，即计算工件插入每一个可插入位置时加工序列P的完工时间，选择完工时间最小的位置，并将该工件从工件序列W中删除。

步骤4从工件序列W中选择第一个工件，将其随机插入到当前加工序列P中，并将其从工件序列W中删除。

步骤5重复步骤3和步骤4，直至所有工件插入完成，形成一个个体。

步骤6重复执行以上步骤n遍，形成规模为n的初始种群。

上述步骤中，步骤1和步骤2保证个体的质量，步骤3和步骤4保证种群的多样性，然后NNEH启发式算法通过多次循环从而产生HFSP-IPM的初始种群。

3.3 速度更新公式的改进

3.3.1 基于激素调节机制的惯性因子设计

生物的体液环境中存在许多腺体，这些腺体可以分泌和扩散激素，并且它们会与相应的激素发生化学反应。如图2所示，腺体“A”在外界刺激下分泌激素“a”，并向外部体液环境释放，在激素“a”的刺激下，腺体“B”分泌激素“ab”和自分泌激素“b”，然后，腺体“B”将它们反馈给腺体“A”，形成一个循环过程。

激素调节机制符合Hill函数，Hill函数由上升函数(Fup)和下降函数(Fdown)组成，如式(12)所示。

(12)

式中：X为激素浓度变量，即自变量；n为Hill系数，n≥1；T为激素浓度阈值，T>0，n和T决定函数曲线的斜率。Hill函数的变化曲线如图3所示。

生物体内的激素分泌有如下4个特点：①微量高效；②通过体液运输；③特异性；④协同与拮抗作用。第④点尤其重要，在内分泌系统中，不同激素对同一腺体有协同和拮抗作用。例如，胰腺可以分泌胰高血糖素和胰岛素，胰高血糖素能够提高人体血糖浓度，胰岛素能够降低人体血糖浓度。当人体血糖水平较低时，胰高血糖素的分泌量增加，以提高人体血糖浓度。但随着人体血糖浓度的升高，胰岛素的分泌量会逐渐增加，使人体血糖浓度不会提升过高。以此种方式，人体的血糖浓度始终维持在正常的水准。由此可以看出，激素的分泌具有维持生物机体内外环境稳定的功能，激素调节机制即Hill函数具有单调性和非负性，并且能够很好地收敛。

在PSO算法的设计中，惯性因子w一般取线性函数或常函数，但这种设计通常会使PSO算法陷入局部最优。根据对标准PSO算法的描述，惯性因子w是继承原来速度的系数，决定着粒子的步长，一般在算法运行前期，设置较大的w使粒子具有较强的全局寻优能力，到算法运行后期，使w逐渐减小，加快算法的收敛速度，因此设置惯性因子w为减函数。关于将惯性因子w设为何种减函数，从而使PSO算法能够获得更好的解，有学者做了专门的研究，研究结果如图4所示。

由图4可知，当惯性因子w为凹型减函数时，PSO算法能够在更短的时间内获得更好的解。而根据对生物体内的激素调节机制的描述可知，生物体内的激素调节机制即Hill函数是一种凹函数且在正数区域内呈递减趋势，具有单调性和非负性，有着很好的收敛性质。因此，将Hill函数用于式(10)中的惯性因子w上，粒子在解空间的探索过程便能够得到很好的控制。由此得出，基于生物体内的激素调节机制的惯性因子w如下：

(13)

式中：k表示当前迭代次数；w(k)表示第k次迭代的惯性因子；wmax表示惯性因子的最大值；wmin表示惯性因子的最小值；T表示阈值(T>0)；n表示Hill系数(n≥1)；w0表示惯性因子的初始值。

3.3.2 相关系数法

HO等[28]指出PSO算法在自身认知项(即c1×r1)和社会认知项(即c2×r2)是随机而又独立存在的，自身认知项调节粒子向个体最优粒子飞行的步长，社会认知项调节粒子向全局最优粒子飞行的步长，这两项对PSO算法的搜索能力具有重要影响。基于该思想，本文采用相关系数法，将原来式(10)中的c1×r1变为(1-r2)×c1×r1，c2×r2变为(1-r2)×c2×(1-r1)，以提高PSO算法的搜索质量。

3.3.3 改进的速度更新公式

综合基于激素调节机制的惯性因子设计和相关系数法，改进的速度更新公式如式(14)所示：

Vid(k)+(1-r2)×c1×r1×(Pid(k)-Xid(k))+

(1-r2)×c2×(1-r1)×(Pgd(k)-Xid(k))。

(14)

3.4 随机拓扑结构

PSO算法有全局版本(Global version PSO, GPSO)和局部版本(Local version PSO, LPSO)两个范式。这两个范式的区别在于粒子所处的“社会”不同。在GPSO中，粒子所处的“社会”是整个种群，即粒子在每次迭代过程中所涉及的种群最优位置gbest是整个种群的最优位置。而在LPSO中，粒子所处的“社会”仅是一个邻域，即粒子在每次迭代过程中会用个体最优位置pbest和邻域最优位置lbest(粒子所处邻域中最好的位置)作为更新的向导。由此可见，LPSO每次迭代所用作更新向导的位置要比GPSO多。因此，LPSO跳出局部极值的可能性更大，在处理复杂问题上往往能够表现出比GPSO更好的性能。考虑到HFSP-IPM是复杂的NP-Hard问题，因此本文基于LPSO提出一种随机拓扑结构。

随机拓扑结构为每个粒子定义一个规模为Z的邻域，该邻域是由从整个种群中随机挑选出的Z个粒子(包括粒子本身)所组成的。在每次迭代过程中，粒子根据个体最优位置pbest和邻域最优位置lbest进行更新。若迭代过后，邻域最优位置lbest得到了改善，则粒子的邻域不会发生改变，并在下一次迭代中继续沿用；若迭代过后，邻域最优位置lbest没有得到改善，则粒子的邻域将在下一次迭代中进行重新构造。因此，式(14)中的Pgd(k)变成表示经过k次迭代后邻域搜索到的最优位置的第d个变量。以此种随机拓扑结构来增强PSO算法的全局寻优能力，提高算法的性能。

3.5 交叉和变异

3.5.1 交叉算子

在IPSO算法中，交叉算子的作用在于通过对两个粒子进行交叉操作，可能得到更为优异的两个粒子，增大算法的搜索空间，提高算法的全局寻优能力。本文采用基于两点的交叉和基于位置的交叉两种交叉算子。

(1)基于两点的交叉

基于两点的交叉具体步骤如下：

步骤1随机产生两个交叉点，将两个交叉点之间的片段称为“交叉片段”，然后将两个父代粒子(P1,P2)的交叉片段复制到子代粒子(C2,C1)中。

步骤2删除父代粒子(P1,P2)与子代粒子(C1,C2)维度值相同的维度

步骤3根据从左到右的顺序将父代粒子(P1,P2)剩余维度上的维度值依次填入子代粒子(C1,C2)余下的空位里。

以8个待加工工件为例，父代粒子(P1,P2)分别为{14576283}和{54786231}，选中交叉点为3和6，则复制过后子代粒子(C1,C2)分别为{XX7862XX}和{XX5762XX}，删除过后父代粒子(P1,P2)分别为{145XXXX3}和{X4X8XX31}，填入过后子代粒子(C1,C2)最终分别为{14786253}和{48576231}。

(2)基于位置的交叉

基于位置的交叉具体步骤如下：

步骤1随机产生一些交叉点，将父代粒子(P1,P2)在交叉点上的维度值复制到子代粒子(C2,C1)对应的维度上。

步骤2删除父代粒子(P1,P2)与子代粒子(C1,C2)维度值相同的维度。

步骤3根据从左到右的顺序将父代粒子(P1,P2)剩余维度上的维度值依次填入子代粒子(C1,C2)余下的空位里。

以8个待加工工件为例，父代粒子(P1,P2)分别为{14576283}和{54786231}，选中交叉点为1、3、6、7，则复制过后子代粒子(C1,C2)分别为{5X7XX23X}和{1X5XX28X}，删除过后父代粒子(P1,P2)分别为{14XX6X8X}和{X47X6X3X}，填入过后子代粒子(C1,C2)最终分别为{51746238}和{14576283}。

进行交叉操作时，IPSO算法随机采用上述两种交叉算子，即生成一个值为0或1的随机数Cr。当Cr=0时，采用基于两点的交叉；当Cr=1时，采用基于位置的交叉。

3.5.2 变异算子

在IPSO算法中，变异算子的作用在于通过变异操作打乱旧粒子，产生新粒子，从而改善算法局部的随机搜索能力。本文采用插入、反转逆序和打乱互换3种变异算子。

(1)插入

基于插入的变异方法是首先随机选中一个维度，然后将其随机插入到另一个维度的前面，从而形成新的粒子。例如，父代粒子P1为{14576283}，首先选中维度5，将其插入到维度2前面，则子代粒子C1为{16457283}。

(2)反转逆序

反转逆序方法是首先选中两个维度，然后对两个维度间的片段进行反转逆序。例如，父代粒子P1为{14576283}，选中维度2和5，则子代粒子C1为{16754283}。

(3)打乱互换

打乱互换方法是首先随机选中一些维度，然后将这些维度打乱互换。例如，父代粒子P1为{14576283}，首先选中维度1、3、5、8，此时维度值的顺序是“1563”，打乱后的顺序是“6351”，则子代粒子C1为{64375281}。

进行变异操作时，IPSO算法随机采用上述3种变异算子，即生成一个在[1,3]的随机整数Mu。当Mu=1时，采用基于插入的变异；当Mu=2时，采用反转逆序；当Mu为3时，采用打乱互换。

3.6 算法流程

根据上述设计，给出求解HFSP-IPM的IPSO算法的流程图，如图5所示。

本文解决以最小化总完工时间为目标的HFSP-IPM的IPSO算法的具体步骤如下：

步骤1确定各种参数、编码解码方式和适应度函数。预先设定种群规模、迭代次数、改进的速度更新公式参数、邻域规模Z、交叉概率Pc、变异概率Pm、编码解码方式和适应度函数。

步骤2初始化种群。利用NNEH启发式算法生成初始粒子群。

步骤3定义每个粒子的邻域，初始化pbest和lbest。构造每个粒子的邻域，并根据适应度函数计算每个粒子的适应度，从而对每个粒子的个体最优位置pbest和邻域最优位置lbest进行初始化。

步骤4根据改进的速度更新公式(14)和位置更新公式(11)更新每个粒子。

步骤5交叉操作。给每个粒子一个随机数，将随机数与交叉概率Pc进行比较，若随机数小于Pc，则锁定粒子；若随机数大于等于Pc，则保留粒子。待扫描完整个种群，对锁定的粒子进行基于两种交叉算子的交叉操作，即生成一个值为0或1的随机数Cr，当Cr=0时，采用基于两点的交叉，当Cr=1时，采用基于位置的交叉。

步骤6变异操作。给每个粒子一个随机数，将随机数与变异概率Pm进行比较，若随机数小于Pm，则锁定粒子；若随机数大于等于Pm，则保留粒子。待扫描完整个种群，对锁定的粒子进行基于三种变异算子的变异操作，即生成一个在[1,3]的随机整数Mu，当Mu=1时，采用基于插入的变异，当Mu=2时，采用反转逆序，当Mu=3时，采用打乱互换。

步骤7根据适应度函数计算每个粒子的适应度。

步骤8更新pbest、lbest和判断是否重新构造邻域。逐个扫描每个粒子，若粒子当前适应度优于pbest的适应度，则将粒子当前位置赋给pbest，否则pbest不变；若粒子当前适应度优于lbest的适应度，则将粒子当前位置赋给lbest，否则重新构造该粒子的邻域，更新lbest。

步骤9判断是否满足迭代终止条件，是则结束迭代，否则转步骤4，进行新一轮的迭代。

步骤10对各个粒子的lbest进行比较，从而确定种群最优位置gbest，并输出对应的调度方案。

4 实验结果与分析

4.1 实验设计

以Visual Studio 2015为开发环境，以C++为编程语言，算法在Intel Core i5-6200U、内存为8 GB的笔记本电脑上运行。IPSO算法的实验参数如表1所示。

表1 实验参数

为验证本文所提出的IPSO算法的性能，开展以下对比实验：

(1)NNEH启发式算法对比实验。对比采用NNEH启发式算法产生初始种群和采用随机策略产生初始种群所得到的解的质量，为客观评价NNEH启发式算法产生的初始种群的质量提供依据。

(2)速度更新公式对比实验。对比PSO算法通过采用改进的速度更新公式和采用原始的速度更新公式分别得到的解的质量，为客观评价改进的速度更新公式对算法整体性能的提升提供依据。

(3)标准算例对比实验。选取CARLIER等[24]提出的经典算例进行测试，将IPSO算法与其他几种算法进行比较，为客观评价IPSO算法的性能提供依据。

在4.3节和4.4节中，对每次实验均测试5次，所涉及的数据均取5次结果中的最优值。

4.2 NNEH启发式算法对比实验

为验证NNEH启发式算法对初始种群的质量的影响，本文进行了NNEH启发式算法对比实验。选取CARLIER等[24]提出的经典算例中的j10c5c1问题进行实验，其中第1个字母“j”代表工件，第2个字母“c”代表阶段，第3个字母“c”代表并行机的布局方式，通常还有“a”、“b”、“d”、“e”等。因此，“j10c5c1”代表有10个待加工工件，5个加工阶段，中间阶段有两台可选机器，其余阶段各有3台可选机器的第一个问题。将NNEH启发式算法和随机策略两种产生初始种群的方法进行对比，以j10c5c1问题为例进行20次实验，实验结果如表2所示。

表2 NNEH启发式算法对比实验

在表2中：X表示NNEH启发式算法产生的初始种群的最小完工时间，Y表示随机策略产生的初始种群的最小完工时间，Xa表示NNEH启发式算法产生的初始种群的平均完工时间，Ya表示随机策略产生的初始种群的平均完工时间。通过表2可以看出，在20次实验中，X的平均值为69.25，Y的平均值为75.05，因此NNEH启发式算法产生的初始种群最优解的平均质量优于随机策略产生的初始种群最优解的平均质量；Xa的平均值为73.20，Ya的平均值为83.32，因此NNEH启发式算法产生的初始种群的平均质量优于随机策略产生的初始种群的平均质量。由NNEH启发式算法对比实验可以证明，在产生初始种群方面，NNEH启发式算法的性能优于随机策略。

4.3 速度更新公式对比实验

为验证改进的速度更新公式对算法性能的影响，本文进行了速度更新公式对比实验。选取CARLIER等[24]提出的经典算例中的j10c5c1问题进行实验，将PSO算法通过采用改进的速度更新公式和采用原始的速度更新公式分别得到的解进行对比，进行20次实验，实验结果如表3所示。

表3 速度更新公式对比实验

在表3中：Sg表示采用改进的速度更新公式的PSO算法得到的最优解，Sy表示采用原始的速度更新公式的PSO算法得到的最优解。通过表3可以看出，在20次实验中，Sg的平均值为69.1，Sy的平均值为70.25，采用改进的速度更新公式的PSO算法得到的最优解的平均质量优于采用原始的速度更新公式的PSO算法得到的最优解的平均质量。由速度更新公式对比实验可以证明，采用改进的速度更新公式能够提高算法的搜索质量。

4.4 标准算例实验

为验证本文所提IPSO算法在解决HFSP-IPM上的优越性能，下面采用IPSO算法在CARLIER等[24]提出的经典算例中的36个算例上进行测试，并与遗传算法(GA)[29]、PSO[30]和人工免疫系统(Artificial Immune System, AIS)[31]三种算法进行比较。对比结果如表4～表6所示。

表4 基于j10c5-算例的4种算法对比结果

续表4

表5 基于j10c10-算例的4种算法对比结果

表6 基于j15c5-算例的4种算法对比结果

由表4～表6可以看出，IPSO算法在求解HFSP-IPM上优于其余3种算法。在表4中，GA、PSO、IPSO求出了12个目前最好的最优解，AIS求出了11个目前最好的最优解，因此在12个j10c5-算例上，GA、PSO、IPSO的性能相当，且都优于AIS；在表5中，IPSO求出了7个目前最好的最优解，GA、PSO、AIS求出了6个目前最好的最优解，且对于12个j10c10-算例，GA的平均偏差为4.17%，PSO的平均偏差为4.17%，AIS的平均偏差为4.39%，IPSO的平均偏差为4.03%，因此在12个j10c10-算例上，IPSO性能最优，其次是GA和PSO，AIS性能最劣；在表6中，IPSO求出了7个目前最好的最优解，PSO求出了6个目前最好的最优解，GA、AIS求出了5个目前最好的最优解，且对于12个j15c5-算例，GA的平均偏差为6.25%，PSO的平均偏差为5.70%，AIS的平均偏差为6.13%，IPSO的平均偏差为5.59%，因此在12个j15c5-算例上，IPSO性能最优，其次是PSO，然后是AIS，GA性能最劣。由此可知，IPSO算法求出的目前最好的最优解多于其他3种算法，证明了本文提出的IPSO算法在求解HFSP-IPM上具有良好的性能。如图6所示为算例j15c5c2的甘特图。

综上所述，本文所提IPSO算法在解决HFSP-IPM上具有良好的效果，首先NNEH启发式算法提供了高质量且多样化的初始种群，然后对速度更新公式进行改进，使算法具有良好的收敛性质，最后将随机拓扑结构、交叉和变异三者结合，扩大算法的搜索空间，使算法不易陷入局部收敛，从而提高算法在解空间的搜索性能。

5 结束语

本文提出了一种基于激素调节机制的改进粒子群(IPSO)算法，用于求解以最小化完工时间为目标的相同并行机HFSP。根据混合流水车间调度问题的特点，提出了基于排列的编码解码方式，然后设计了NNEH启发式算法用于产生高质量的初始种群。在IPSO算法中，首先基于激素调节机制和相关系数法对速度更新公式进行了改进，提高了算法的搜索质量，然后提出了随机拓扑结构将迭代过程中的种群最优位置换为可变的邻域最优位置，使得算法不易陷入局部最优，最后随机采用基于两点和位置的两种交叉算子，以及插入、反转逆序、打乱互换3种变异算子产生新粒子，扩大了算法的搜索范围。通过两项对比实验，证明了NNEH启发式算法和改进的速度更新公式均能够改善算法的搜索性能。通过标准算例对比实验，验证了本文所提改进粒子群算法的优越性。未来将继续优化该算法，尝试获得更好的最优解，或将该算法用于多目标混合流水车间调度问题上。