求解柔性流水车间调度问题的粒子群优化算法

范雅男，逄焕利

(长春工业大学 计算机科学与工程学院， 吉林 长春 130102)

0 引 言

车间调度问题[1](Job Shop scheduling， JSP)是对资源和时间路径进行整合分配达到实际生产需求的过程。流水车间调度问题[2]是生产制造业中极其重要的规划问题，一般该类问题的研究任务数都需要大于3，被证明是NP-hard问题。在智能生产制造业高速发展的背景下，车间的柔性生产越来越受到重视，柔性流水车间调度问题[3](Flexible Flow Shop scheduling Problem， FFSP)已成为实际生产调度问题研究领域的新热点，对提高企业生产效率具有重要意义。

粒子群算法(Particle Swarm Optimization， PSO)[4-5]的突出优点在于容易实现，收敛效率较高，涉及到的可调整参数比较少。它可以利用实数进行编码，算法结构不复杂的同时又适用于多个领域，既适合做理论研究，也能应用到具体的工程问题中。因此，PSO算法得到了各领域研究者的广泛关注，在被提出后的短短几年内便产生了许多科研成果，成为热门的研究方向，并且被应用到许多工程领域。

目前对FFSP问题的研究主要集中在采用精确算法、元启发式算法[6]、启发式算法[7]方向上。如Ihong Kuo等[8]将全新的编码方式和个体更新方案融入PSO算法中以求解FFSP问题。 Marichelvam M K等[9]对布谷鸟搜索算法进行优化，将改进的算法应用于HFSP问题的求解。田野等[10]将多种元启发式方法混合后用于PFSP问题的求解。裴小兵等[11]提出的一种基于NEH的混合萤火虫算法在解决含有多个目标的置换流水车间调度问题时效果良好。景会成等[12]针对搜索效率低、容易收敛于局部最优解等问题，采用模拟退火算法、粒子群算法、遗传算法三种算法融合的方式对FSSP问题进行求解。

文中将禁忌策略和粒子群算法相结合形成一种新的优化算法，并将其应用于FFSP问题的求解。采用NEH算法产生初始种群，并引入非线性自适应惯性权重因子和扰动因子。最终通过仿真对比实验的分析结果验证了所提算法的有效性。

1 问题描述

柔性流水车间调度问题可以描述为：n个待加工工件Ji(i=1，2，…，n)在m台机器Mk(k=1，2，…，m)上进行加工，每个工件包括一道或多道工序Oij(j=1，2，…，Pi)。任何工件的每次操作都必须遵循相同的机器顺序。FFSP存在以下假设：开始时刻所有的机器都可以执行加工操作；各工件的每个操作可以在相应阶段上选择任意一台并行处理机进行加工；工件中的任一操作每次只能在一台机器上执行；每台机器在任何作业上一次只能执行一次操作；机器上的操作一旦开始，就不得终止。文中涉及的模型参数见表1。

表1 模型参数表

问题目标是调配工件的加工处理顺序以及机器调度方案，使得最大完成时间指标达到极小。因此该问题的数学公式描述如下：

minCmax=maxCmin;

(1)

Cijk=Sijk+tijk;

(2)

Sijk=max{S(i-1)(j-1)k+t(i-1)(j-1)k,Ci(j-1)(k-1)}；

(3)

Ck=Ci′j′k′。

(4)

式(1)为提出模型的目标函数；式(2)表示工件操作完成时间由开始处理时间和处理过程花费时间的总和；式(3)表示某工件上一个操作的完成时间，该机器上一次操作的处理完成时间决定了该工件开始处理的时间；式(4)表示某机器的处理完成时间为它上面最后一个操作的处理完工时间。

2 改进粒子群算法设计

2.1 编码与解码

采用基于工序和机器的编码方式。假设一个3×3问题解决方案是{1，3，2，1，2，1，2，3，2，3，1，3，2，1，2，1}，前半部分用来判断各工序的先后加工顺序，后半部分用来选择各工件操作的加工机器。{1，3，2，1，2，1，2，3}为工序调度，其中最前面的 “1”代表工件1的第一道工序O11，第二个“1”代表工件1的第二道工序O12，依此类推。{2，3，1，3，2，1，2，1}为机器分配部分与工序调度相匹配，其中“2”代表操作O11被分配到机器2上进行处理，“3”代表操作O31被分配到机器3上进行处理，依此类推。解码为编码的逆过程可以确定各工件在机器上的加工顺序。

2.2 种群初始化

传统粒子群算法对种群进行初始化时采用随机策略，但随机策略面对大规模实际组合优化问题时效果不好，并且会使初始种群中粒子的质量降低。因此，文中采用NEH启发式算法生成初始种群，该算法假定在所有加工机器上总加工时间大的工件会获得更高的优先权。具体步骤为：

1)n个工件在加工机器上的加工时间总长按照由大到小的顺序进行排列;

2)取前两个工件调度，使其最大流程时间达到最小;

3)从k=3到n,将第k个工件插入到k个可能的位置,求得最大流程时间。

2.3 粒子寻优操作

粒子速度和位置更新公式为：

vij(t+1)=ωvij(t)+

c1r1(pbestij(t)-xij(t))+

c2r2(gbestij(t)-xij(t))+d,

(5)

xij(t+1)=xij(t)+vij(t+1),

(6)

式中:vij(t)----粒子速度;

xij(t)----粒子位置；

pbestij(t)----粒子的个体最优位置;

gbestij(t)----粒子的群体最优位置；

ω----惯性权重系数；

d----扰动因子；

c1、c2----学习因子；

r1、r2----(0，1)之间的随机数。

2.4 自适应惯性权重系数

在PSO算法中惯性权重至关重要，它拥有平衡局部勘探和全局勘探的能力。因此，文中采用非线性的、自适应的惯性因子调整方式，迭代开始阶段算法在解空间内的寻优能力增强，不容易陷入局部极值，加快算法后期的收敛速度。

(7)

k=rand+Ε(0.5),

(8)

式中:t----当前迭代次数;

MaxDT----算法允许的最大迭代次数;

Ε(0.5)----平均值为0.5的指数分布;

rand----(0，1)之间的随机数。

ωstart通常取0.9，这使得在迭代初期算法拥有比较好的勘探能力，能够扩大搜索范围。ωend一般取0.4，随着迭代次数的不断增加，算法的开发能力逐步增强，这促使粒子加速向全局最佳值逼近。惯性权重ω的曲线如图1所示。

图1 惯性权重ω的曲线

2.5 扰动因子

经典PSO算法在寻优阶段容易陷入局部极值，为此在原速度更新公式中加入了扰动因子d，进而促使粒子在解空间中继续进行搜索。将扰动因子d设置为一个二进制变量，它取0的概率比较大。当粒子在种群中呈聚集状态时，扰动因子可以将其打散，防止算法收敛于局部最优值；当种群中的粒子呈分散状态时，算法受扰动因子的影响较小，可以忽略。

2.6 禁忌搜索

禁忌搜索算法[13](Tabu Search， TS)对局部搜索算法的优化，它能够避免传统的局部搜索算法因粒子重复搜索固定区域(方向)而造成粒子收敛于局部极小值。通过建立禁忌表来记录被禁止的局部极小点，使粒子更新时绕开这些点。并通过破禁准则释放一些在禁忌表中的点，保证多样化、有效地探索。

文中引入一种基于位置相似度的禁忌搜索策略[14]，并将它与粒子群算法相结合。对于N维空间中有位置x1=(x11，x12，…，x1N)和位置x2=(x21，x22，…，x2N)，那么位置相似度可表示为λ=N′/N，其中N′为位置x1和位置x2中可行解数值相同的维数。首先建立一个长度为l的禁忌表，用以记录粒子在搜索过程中所到达的位置。并根据位置相似度阈值更新禁忌表，规则如下：每当粒子抵达全新的位置时，粒子都与禁忌表中的每个记录做λ计算，超过相似度阈值的位置则被放弃，而小于阈值的粒子所在的位置将加入到当前迭代的候选解队列中，计算适应度值并更新禁忌表。

2.7 算法流程

采用TIPSO求解FFSP的详细流程如下：

1)设置算法的基本参数。给定问题规模，迭代次数M，学习因子c1和c2，种群规模N，禁忌表长度。

2)种群初始化，禁忌表初始化。结合NEH算法初始化种群。

3)判断粒子是否在禁忌表中。若在禁忌表中则执行5)，否则执行4)。

4)更新禁忌表，计算适应度值,并更新个体和种群最优(将目标函数作为适应度评价指标)。

5)利用式(5)、式(6)指导种群中粒子速度以及位置更新。

6)判断是否达到终止标准。若达到条件，则将最优位置输出；若不满足,则重新执行3)。

改进粒子群算法流程如图2所示。

图2 改进粒子群算法流程

3 仿真结果与分析

为验证文中提出的改进算法有效性，以Matlab2016a为开发环境，分别使用标准粒子群算法、改进型算法[14]和文中提出的算法在 LA01[15]、FT06[16]、FT10[16]三个不同规模的问题进行了实验仿真。

算法参数设置如下：粒子个数N=50，LA01、FT06问题规模相对来说比较小，所以最大迭代次数设置为MaxIter=500，FT10问题复杂规模大，其最大迭代次数设置为MaxIter=1 000，学习因子c1=c2=2，ωmin=0.4，ωmax=0.9，禁忌表长度l=2，禁忌阈值η1=0.85，η2=0.95。

TIPSO算法在FT06问题上的最优调度方案如图3所示。

图3 最优甘特图

由图3可知,最短完工时间为47 s。

标准粒子群算法、改进型PSO算法[14]和禁忌粒子群优化算法(TIPSO)求解FT06基准算例、LA01基准算例、FT10基准算例的收敛结果对比图，分别如图4～图6所示。

图4 收敛速度对比图(FT06)

图5 收敛速度对比图(LA01)

图6 收敛速度对比图(FT10)

由上图可知，TIPSO可以求出FT06算例的最优解47、LA01算例的最优解453和FT10算例的最优解706，其他两种算法均找不到最优解。在搜索后期TIPSO得到的种群最大流程时间比较短，说明TIPSO算法具有较优的收敛性能，而且TIPSO算法在面对大规模问题时表现依然良好。这是因为TIPSO 算法结合禁忌搜索策略对种群的初始化、权重因子进行了改进，保证了算法初始种群的多样性，更接近全局最优解，并且收敛效率也更好，而扰动因子的引入能够帮助跳出局部最优解，继续在解空间内进行搜索。

4 结 语

设计了一种禁忌粒子群优化算法，在求解FFSP问题时表现出良好的性能。将基于位置相似度的禁忌策略和粒子群算法结合起来，自适应惯性权重因子和扰动因子的加入，可以有效地避免粒子过早收敛的情况，帮助粒子提高其全局搜索能力，同时将NEH 启发式算法引入种群的初始化中，提高了粒子种群的多样性，可以帮助算法在较短时间内收敛于最优解。最后通过仿真实验证明了该算法的可行性与有效性。