基于改进的多目标PSO算法的离散型FJSP的研究*

张 博，梁艳艳

(平顶山工业职业技术学院机械工程学院，平顶山 467001)

0 引言

现代制造业是制造业未来的发展方向[1]，已向柔性化、自动化方向发展[2]，并最终实现高效、柔性的智能化生产模式[3]。作业车间调度是生产企业面临的复杂问题，特别是涉及多品种、小批量个性化定制的智能化生产[4]，其生产过程具有复杂性、离散型和动态性，需要给工序分配设备，其FJSP问题属于NP-hard问题，是国内外学者研究的焦点[5]。

目前，已有较多用于求解JSP问题的优化方法和调度模型被提出，针对优化方法的研究主要有遗传算法[6]、拉格朗日松弛法[7]、模拟退火法[8]、遗传算法[9-10]等。针对调度模型的研究主要是根据工件工序存在的不足设计最小化完工时间的调度模型，且考虑了加工设备的柔性[11]，以及考虑设备的恶化特性[12]、冗余特性[13]，分别建立满足鲁棒性和调度次序约束的多加工调度模型，获得较好的调度效果。但是FJSP问题比一般的JSP问题具有更复杂、更困难性，且多品种、小批量智能生产过程具有离散型、多目标和不确定性，面临多机器选择的问题，现有的研究主要集中在经典的JSP问题设计优化算法，以及作业加工顺序是预先设计、加工设备是预先指定，不能很好的满足离散型FJSP问题。且传统算法求解时存在收敛速度慢、陷入局部最优解等缺点。针对上述问题，将速度松弛迭代策略引入更新工序排序和设备分配粒子中，采用带有压缩因子和惯性权重相结合的策略改进学习因子，以及将基于工序和机器的两级基因策略引入粒子的编码和解码操作。最后利用离散制造业智能生产过程的FJSP算例进行分析，验证了改进粒子群算法的优越性和求解效率。

1 离散型FJSP模型的建立

1.1 离散型FJSP的约束矩阵

在具体的智能制造生产模式下，柔性作业车间调度问题具有复杂性、动态性、多约束和多目标等特点。按照复杂程度可分为单机和多机并行调度，按照性能指标目标可分为调度费用和性能的优化，按照生产环境可分为确定性和随机性调度，按照加工特点可分为静态和动态调度。

在柔性作业车间调度问题中，设有n个待加工工件，m台机床设备，每个工件需要Pi道工序，每台机床上共有Lj道工序，则：

工件集合N={N1,N2,…,Nn}；机床设备集合M={M1,M2,…,Mm}；工件Ni的工序集合PNi={PNi1,PNi2,…,PNipi}。

(1)

式中，P为n×max{P1,…,Pn}的工序矩阵；P(i,j)为第i个工件的第j道工序：

(2)

式中，JM为n×max{P1,…,Pn}的机器编号矩阵；JM(i,j)为第i个工件的第j道工序在机床上加工的编号。

(3)

式中，T为n×max{P1,…,Pn}的加工时间矩阵；T(i,j)为第i个工件的第j道工序在机床JM(i,j)上的加工时间。

车间柔性作业调度函数的最优解表达式为：

(4)

式中，Mj为n×max{P1,…,Pn}的工件排列矩阵；Mj(i,j)为在机床i上排在第j个加工的工件序号。

离散型FJSP的目标就是在满足约束条件的情况下，选择最合适的机床以及确定每台机床上的最佳加工工序，最后使得调度系统的某些性能指标最优，约束条件如下[14-15]：

(1)所有机床一开始都处于空闲状态；

(2)不同工件之间具备相同的优先级，在0时刻，所有工件都可被加工；

(3)工件的工序之间没有固定的先后顺序，工序一旦进行不能中断；

(4)各工件的准备时间和移动时间一起计入加工时间；

(5)每台设备在同一时刻只能加工一道工序。

随着车间智能化水平的提高及客户个性化定制需求增多，柔性作业车间调度问题也由最开始的单目标优化变成现在的多目标优化，如最大完工时间和加工成本的最小化等。

表1描述了3种待加工工件和3台机床设备的小批量的车间作业柔性调度问题，表中数据表示机床加工时间，“-”表示该设备不能完成本道工序的加工任务，机床设备M后的数据表示该设备单位时间的加工成本、工作能耗和闲置能耗。

表1 多品种小批量柔性作业调度示例

由表1可得到，柔性调度车间作业和工序之间的关联矩阵为：

(5)

车间柔性作业调度时间矩阵为：

(6)

1.2 离散型FJSP的优化目标函数

本文构建的离散型FJSP为多目标动态调度模型，在实际生产中主要关心的调度优化目标有总加工时间T，总加工成本C，总能源消耗E，总加工质量Q，工件加工过程负载平衡B。

(1)总加工时间T。生产过程的总加工时间T可用最大完工时间表示，实际生产取最小值。

T=max(Ti)

(7)

式中，Ti为机床设备M总体加工任务结束时间，i=1,2,…,m。

(2)总加工成本C。工件的加工成本C一般由原材料成本CM和工序加工成本CP组成。

(8)

式中，mci为工件i的原材料成本；Oijk为工件i的第j到工序在设备k上加工；Tijk为工件i的第j道工序在设备k上的加工时间；Pck为机床设备k单位时间的加工成本。

(3)工件加工过程负载平衡B。工件加工过程负载平衡E包括机床设备总负荷和瓶颈设备负荷。

(9)

综上可知，柔性作业车间的多目标动态调度目标函数为：

F=(T,C,E,Q,B)

(10)

(4)总能源消耗E。总能源消耗E为完成所有加工任务所有机床设备耗能的总和，包括设备启动能耗Es，加工能耗Ep和设备空载能耗Ee。

E=∑Es+∑Ep+∑Ee

(11)

(5)总加工质量Q。总加工质量Q采用工序成本加权质量不稳定系数来表示，则总的成本加权不稳定系数为：

(12)

式中，Lijk表示设备k加工工件i的第j道工序的成本加权质量不稳定系数。

则调度的优化目标可表示为：

MinF=min(T,C,E,Q,B)

(13)

2 多目标PSO算法的基本原理与改进

2.1 车间调度问题优化方法的对比分析

离散型FJSP作为多目标优化问题，其求解方法有多种，主要分为传统方法和智能算法两大类，如表2所示。

表2 柔性作业车间调度算法分类

由表2可知，传统方法通过加权求和，将多目标问题转化为单目标函数求解，这种方法对于复杂问题的处理响应慢，容易出现局部最优解现象，无法满足实际生产需求，而智能算法使得离散型FJSP的求解易于获得最优解。多目标粒子群优化算法(particle swarm optimization,PSO)是一种群体智能算法，可通过粒子的位置和速度得到一组候选解决方案，并通过迭代来改进候选方案，具有独特的搜索机理和很好的收敛性，广泛应用于求解柔离散型FJSP领域。

2.2 多目标PSO算法基本原理与流程

多目标PSO算法来源于鸟群捕食行为的启发，是一种群体智能的进化计算技术。其基本思想是在观察粒子集群行为的基础上，利用个体粒子的信息共享使整个粒子群体的运动在求解空间中产生最优解的演化过程。

多目标PSO算法在可行解空间中初始化一群粒子，每个粒子代表极值优化问题的潜在最优解，可用速度V、位置P和适应度值F三项指标表示每个粒子的特征。粒子在可行解空间中运动，通过追踪个体粒子适应度最优值Pbest的位置以及群体粒子适应度最优值Gbest的位置来更新个体位置。粒子每更新一次位置就计算一次适应度值，个体极值和群体极值会随着他们的位置变化而更新。

假设有M个粒子组成一个N维目标的搜索空间，用第i个粒子表示一个N维向量，则，

第i个粒子的位置Pi为：

Pi=(Pi1,Pi2,…,PiN),i=1,2,…,M

第i个粒子移动的速度Vi为：

Vi=(Vi1,Vi2,…,ViN),i=1,2,…,M

第i个粒子搜索的个体最优位置Ebest为：

Ebest=(Pi1,Pi2,…,PiN),i=1,2,…,M

群体粒子搜索的全局最优位置Gbest为：

Gbest=(Pg1,Pg2,…,PgN)

(14)

多目标PSO算法采用学习因子及惯性权重来更新速度和位置，其公式为：

(15)

式中，C1和C2是学习因子，一般取C1=C2∈[0,4]；ωk是惯性常量；R1和R2是[0,1]范围内的随机数。

多目标PSO算法主要分为：①初始化粒子群；②评价粒子(计算适应度值)；③寻找个体最优解值Pbest；④寻找全局的最优解值Gbest；⑤修改粒子的速度和位置。其程序流程图如图1所示。

图1 PSO算法的基本流程图

2.3 改进的多目标PSO算法在离散型FJSP中的设计

(1)初始化参数。由基础粒子群算法思想可知，学习因子C1、C2以及惯性权重因子ωk的取值对多目标PSO算法的性能有较大影响。因此，通过改进学习因子和惯性权重达到改善多目标PSO算法的目的。

采取带有压缩因子的方式来改进学习因子，使粒子的更新公式为：

(16)

随着迭代次数的增加，惯性权重从最大变化到最小，改进后惯性权重的表达式为：

(17)

(2)粒子编码方法设计。在智能加工过程中，工序和机器的选择顺序十分重要，可将加工工序和加工机器看着两级基因的策略进行编码，加工工序基因可确定作业在备选设备上对应的加工顺序，加工机器基因可确定作业加工顺序对应的加工机器的使用编号。

表1中所示的多品种小批量柔性作业车间调度模型包含4种产品、3台加工机器、8道工序，基因编码长度为8，根据上述编码策略形成的粒子编码序列如图2所示。

图2 粒子编码方法

因此，图2中所示的粒子编码基因对应的工序和机器顺序为：[(O31,M2),(O11,M3),(O21,M1),(O12,M2),(O22,M2),(O23,M3),(O13,M2),(O32,M1)]。

多目标PSO算法的解码过程是为了寻找多目标优化问题的可行解，进而得到车间调度方案。假设工件i的第j道工序开始加工时间为Sijk，加工时间为Tijk，则染色体解码时工序Oij开始加工时间为：

Sijk=max(Si[j-i]+Ti[j-1],Sk[q-1]+Tk[q-1])

(18)

式中，Si[j-1]和Sk[q-1]分别表示工件上一道工序的开始加工时间；Ti[j-1]和Tk[q-1]分别表示上一道工序的加工时间。如果按照上述方式进行编码，解码后得到的只是染色体对应的半主动调度解。此时，需要按照工序的排序进行编码，然后尽可能早的将开始加工时刻往前移动到对应的加工设备上，直至所有工序都被合理的安排到最佳加工位置。

(3)粒子更新和条件设置。加工工序基因和加工机器基因采取随机的方式进行，设置群体规模为m。需要设置最大的速度区间，防止超出最大的区间。位置信息即为整个搜索空间，在速度区间和搜索空间上随机设置初始化速度和位置。

为了获得全局最优解，将速度松弛迭代策略和引入多目标PSO算法中，不仅可以减小更新速度时的运算量还可以增强粒子的局部搜索能力，加快运算的收敛性。速度松弛迭代策略定义如下：

(19)

在更新粒子位置时，需要对粒子的边界进行限定，设置粒子寻优空间的上限和下限。

(4)算法终止条件。最大迭代次数Gmax满足设定的要求时，算法停止，输出最优解。

3 改进的多目标PSO算法在离散型FJSP中的应用案例分析

某智能化生产车间有6台加工设备，加工有工序间相互约束关系的6个加工工件，共有17道加工工序的离散型FJSP实例，所需部分初始数据如表3所示。根据第1.2节构建离散型FJSP优化模型，优化目标为：总加工时间T、总加工成本C、总能源消耗E、总加工质量Q和工件加工过程负载平衡B。为了简化分析过程，只考虑机床一种资源，且不考虑机床故障和急件等非确定性因素。

表3 车间柔性作业调度实例分析

试验环境在Windows 10平台(硬件参数：CPU Intel(R) Core(M) 2.30 GHz 8 GB)，编程环境：MATLAB R2018a。参数设置：粒子个数PN=1000，IN=200，初始惯性权重ω0=0.8，最终惯性权重ωk=0.2，初始学习因子C1=3.5，初始学习因子C2=0.5。

求解后，得到的最优目标为：最优化最大加工时间为29 h，最优加工成本为704元，最优加工过程负载平衡为32.8 W，最优化能源消耗为23J，最优化加工质量为260。离散型FJSP的Pareto前沿解如图3和图4所示。

图3 Pareto前沿解(加工时间/机床负荷/加工成本) 图4 Pareto前沿解(加工时间/机床负荷)

输出的一组工序对应的机床加工分配情况，如表4所示。在表4中，用“＊”表示该工件的该道工序需要该机床设备进行加工，空白表示改道工序暂时未用到该台设备进行加工。

表4 工序加工机床分配表

以工件的最优化最大机床加工时间为决策对象，可获得这组调度方案对应的离散型FJSP优化调度方案甘特图，如图5所示，图中纵坐标序号表示加工机床编号，横坐标表示机床加工时间，甘特图中的文字“4,2”表示工件4的第2道工序。

图5 考虑最优化机床加工时间调度方案甘特图

可以看出，此时机床总加工时间的最优值为29 h，调度算法对工序的安排紧凑合理，有效的提高了设备利用率。并且借助计算机进行调度可减少人工调度产生的误差，因此本文提出的调度方法对求解离散型FJSP车间问题是可行且有效的，不仅提高了算法的性能，还降低了算法陷入局部最优解的几率。最后通过仿真实验和与其它实验的对比分析， 可以看出不管对于部分柔性和完全柔性作业车间调度， 改进的蚁群算法均可快速求得最优解。 证明改进蚁群算法在求解柔性作业车间调度不同规模算例中的优越性

4 结论

针对传统的优化算法收敛速度慢、求解效率低，无法满足离散制造业中多品种、小批量智能生产过程的FJSP优化问题，本文在粒子群算法的基础上，将速度松弛迭代策略引入更新工序排序和设备分配中，且将带有压缩因子和惯性权重相结合的策略用于改进粒子群的学习因子，并采用基于工序和机器的两级基因策略进行编码和解码操作，提高了算法的优化性能，扩大了算法的搜索范围，避免陷入局部最优解。最后通过实例分析，对于离散制造业智能生产中柔性作业车间调度问题，改进的粒子群算法可快速获得最优解，说明改进粒子群算法在求解智能生产的FJSP问题的优越性。