离散改进PSO求解模糊柔性作业车间多目标调度

辛 悦,顾 德

(江南大学物联网工程学院，江苏 无锡 214122)

0 引言

制造业是当今社会的支柱。随着“工业4.0”时代的到来以及国家相关政策的实施，智能制造受到了广泛关注[1]。作为智能制造生产过程的关键环节，车间需要在有限的设备生产性能约束下，合理决策工件、工序以及加工设备，使所得的生产调度方案能够实现一个或者多个目标。因此，调度方案的合理性对智能制造的效率有着巨大的影响。车间调度是智能制造的研究热点之一。

柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP)是车间调度问题的进一步拓展。其在车间调度问题的基础上考虑了同一工件工序所用设备的弹性选择。对于FJSP的研究，国内外取得了很多进展：Yuan等[2]提出了一种新的模因算法，并将一种新的局部搜索算法引入到适应的非支配排序遗传算法(non-dominated sorting genetic alogrithm,NSGA-II)中，以求解FJSP；Tianhua等[3]提出了一种基于双种群的离散猫群优化算法，以得到车间的最优调度方案；Pezzella等[4]提出了一种集成了不同初始种群生成策略、个体选择策略和新个体复制策略的遗传算法，以寻求最优调度方案；Xia等[5]将粒子群算法与模拟退火算法混合，有效求解大规模多目标调度问题；徐华等[6]利用呈指数递减的惯性权重策略改进蝙蝠算法，求解调度最优解。

虽然以上方法很好地求解了FJSP，但仅考虑了确定的生产参数。在实际情况下，设备的损耗、电费的涨幅等外界因素使得工序加工时间、生产成本等生产参数并不是一个确定值。对于此问题，将FJSP中加工时间、加工成本等不确定参数用三角模糊数来代替，利用三角模糊函数对车间调度优化的问题进行数学建模并设计相关问题的目标函数，所得到的调度结果更具鲁棒性。使用离散改进的粒子群优化(particle swarm optimization,PSO)算法对调度方案进行寻优，保留了调度算法的多样性，避免后期迭代过程陷入局部最优。同时，通过计算机仿真结果对比，反映改进算法的优越之处。

1 问题模型

1.1 问题描述以及约束

FJSP可以叙述为：车间有m台加工设备、n个工件，各工件有多道工序，每道工序有多台可选设备，工序的加工顺序固定，每台设备的性能不同。调度的目的是确定各个加工设备安放的工件及其工序，使得整个生产系统的加工时间、加工成本这两个目标最小化。其具体约束如下。

①每道工序开始处理后不允许暂停。

②一台设备在某一时刻只可处理一个工件。

③在t=0时，所有工件都可以被可选设备集中的机器加工。

④同一工件按照设定工序加工，不同工件优先级相同。

根据符号定义，本文的目标函数可表示为：

(1)

(2)

式中：minNcost为最小加工总成本；minNperiod为最小完工时间。

为便于分析，对建模涉及的变量进行定义，如表1所示。

表1 变量定义Tab.1 Variable definition

1.2 三角模糊数运算

③比较运算。

2 基本粒子群算法

粒子群算法模拟了鸟类群体的觅食特性[7]，是全世界群体算法研究者的研究热点。其主要遵循以下两个寻优规则。

①根据个体自身搜寻经验进行搜索。

②根据社会最优个体搜寻经验进行搜索。

其主要的速度和位置更新操作如式(3)与式(4)所示。

(3)

(4)

3 离散改进PSO

3.1 编码方式

FJSP包括两个子问题，分别为工序排序问题(operations sequencing，OS)与机器选择问题(machines selection，MS)。对于一个调度方案的编码示例如图1所示。

图1 编码示例Fig.1 Example of code

图1中：OS部分的首个1表示工件1的首道工序O11；MS部分的首个1表示O11的可选加工设备集的第一个设备。使用工序对应可选设备集的顺序编号，而不是原始的机器编号，可以保证后续引入交叉、变异操作后产生的解仍是可行解。

假设其加工设备集为{M1，M2}，则该数字表示M1；假设所有工件工序集合为{M1，M2}，则编码意义如图2所示。使用OS与MS分离的编码方式，能有效解决调度任务在计算机中的存储方式，便于算法运算。

图2 编码意义Fig.2 Meaning of code

3.2 重构公式

由于传统PSO算法是连续算法，在迭代后期存在多样性丧失的问题，无法处理FJSP之类的复杂组合优化问题。因此，本文根据广义粒子群思想[8]，设计新算法框架，重构了PSO的公式，使得算法具有解决离散问题的能力。在粒子群的位置与速度更新操作中引入遗传算法的交叉、变异操作，其改进公式如式(5)与式(6)所示。

(5)

(6)

则由式(6)可知，变异概率不会大于0.25。新设计的算法框架以遗传算法交叉变异操作的离散操作算子替换原有公式的加乘运算，可有效利用遗传算法能够保留多样性的特点、确保算法迭代后期的多样性、提升算法的寻优性能。

本文采用加入拥挤测度的快速NSGA-II[9]对粒子个体评价。更新个体历史最优位置的方式为：若粒子当前位置可以支配个体历史最优位置，则将其作为个体历史最优位置。而对于全局历史最优位置的更新方式为：若在所有粒子个体中，存在一个粒子位置能支配全局历史最优位置，则更新为该粒子的位置。

粒子更新过程伪代码如下：

01 初始化N个粒子位置xg，最大迭代次数G，粒子速度vg

02 Forg=1 toG

03 Fori=1 toN

04 Ifr

06 End If

07 Ifr

09 End If

10 Ifr

12 End For

14 End For

3.3 OX交叉操作

本文f2交叉操作采用的是顺序交叉方式，如图3所示。图3中，浅灰色子代编码来自父代1，深灰色子代编码来自父代2。首先，从父代1编码中选取相临的一段编码放入子代，其顺序与位置与父代1相同。然后，在父代2中找出剩余缺少的基因，并按照原来的顺序填入子代编码空位处。

图3 顺序交叉方式Fig.3 The way of order crossover

3.4 精英保留策略

为保护粒子的多样性，使用带外部记忆库的精英保留策略，如图4所示。

图4 精英保留策略Fig.4 Elite retention strategy

粒子位置更新后形成新种群，并对个体进行评价。每一次对新种群评价排序后，都需要对外部记忆库进行更新，将非支配等级最高的新精英个体与记忆库中的精英个体进行比较。若当前个体被记忆库中的某个体支配，则丢弃该解；若记忆库中的某个体被新精英个体支配，则将被支配个体剔除并将新个体存入记忆库。若记忆库的个体与新精英个体不存在支配与被支配关系，则直接将新的精英个体放入记忆库中。使用带外部记忆库的精英保留策略，使得算法能够充分利用迭代优化过程中的信息并将其用于指导子代的产生，以提高算法的寻优性与收敛性。

3.5 算法步骤

结合离散化改进和精英保留策略，整体的算法步骤如下。

①初始化个体位置和速度，全局最优及个体最优。

②利用变异操作随机探索个体位置。

③利用交叉操作获取个体最优位置信息，以更新个体位置。

④利用交叉操作获取全局最优位置信息，更新个体位置。

⑤更新粒子群中个体的位置与速度。

⑥对粒子个体进行快速非支配排序，更新全局最优、个体最优及外部记忆库。

⑦确认是否已达到最大迭代次数；若达到，则停止运算并输出最优解；若未达到，则返回步骤⑦。

4 试验仿真及结果分析

为验证本文算法的有效性，进行试验测试。测试环境为：Win7 x64 专业版系统，8 GB DDR3内存，I7-4900MQ处理器，编程语言为MATLAB 2016a，试验数据参考文献[10]。采用C测度来对比算法之间的性能优越性，测度函数如式(7)所示。

(7)

式中：a、b分别为算法A、B产生的Pareto解；Count为解集的个数。

若C(A,B)>C(B,A)，则算法A优于算法B。为便于比较，采用三角模糊数的准则一来使得模糊数近似于定值，以此构造近似Pareto前沿。

对比算法为文献[10]的自适应离散多目标花授粉算法(adaptive discrete multi-objective flower pollination algorithm,ADMOFPA)以及文献[11]的多目标粒子群优化(multi-objective particle swarm optimization,MOPSO)算法。本文算法仿真参数为w=0.4，c1、c2设置为1.5，对比算法按照原文设置参数，每个算法的种群规模为50，迭代次数为200。绘制迭代结束时三种算法的近似Pareto前沿，如图5所示。

图5 近似Pareto前沿示意图Fig.5 Approximate Pareto front

由图5可以看出，本文算法的近似Pareto前沿在ADMOFPA和MOPSO算法的左下方，因此更逼近最优解。由于粒子群初始值设置欠妥，导致Pareto解集存在少量劣解，但这不影响近似最优解的产生。三种算法的C测度结果如表4所示，可知本文所得Pareto解支配其余算法的比例远大于被支配的比例。

根据NSGA-II的拥挤测度对各算法所得的Pareto前沿进行排序，排在首位的解即该算法的最优解。

表4 算法对比Tab.4 Comparison of methods

本文算法最优解调度方式如图6所示。

图6 最优解调度方式Fig.6 Sispatching mode of optimal solution

图6中，下三角表示开始加工，上三角表示结束加工，编码意义为工件标号与工序标号。本文算法、MOPSO、ADMOFPA所得最大完工时间与生产成本的最优解值分别为(115,3 398),(116,3 425),(173,3 172)。由三组最优解可知,本文所得最优解支配MOPSO的解，相比ADMOFPA的最优解，近似成本虽然有略微的劣势但在完工时间上却有绝对的优势。因此，本文算法更优。

5 结论

本文针对多目标模糊柔性作业车间调度问题，提出了一种离散改进PSO算法。该算法使用遗传算法的交叉、变异算子重构了PSO的位置与速度更新公式，并针对多目标使用带外部记忆库的精英保留策略。最后，通过对比多种算法的车间实例仿真结果，验证了改进算法的合理性。今后，可将算法用于实际的生产中，以提高算法的适用性。