王仕存，唐敦兵，朱海华，聂庆炜，潘俊峰，杨雷

(1. 南京航空航天大学 机电学院，江苏 南京 210016；2. 江苏天安智联科技股份有限公司，江苏 无锡 214171)

0 引言

随着云制造[1]和生产全球化的不断发展，基于云平台的大规模协同制造渐渐成为国内外制造业研究的重点。在此背景下，传统集中式制造工厂渐渐向分布式工厂转变[2]。随着工厂数目的增多，传统的车间调度已难以满足云平台的需要。如何对各个分布式工厂的生产任务进行合理有效的调度，已成为当前迫切需要解决的问题。

近年来，国内外对分布式多工厂生产调度问题(distributed multi-plants production scheduling problem，DMPPSP)进行了相关的研究。根据车间之间是否存在交互，本文将每个工厂划分为多个独立的柔性制造单元(flexible manufacturing unit，FMU)，把DMPPSP转化为分布式柔性车间调度问题(distributed and flexible job shop scheduling problem, DFJSP)，从而解决了DMPPSP的问题。

由于该问题包含柔性作业车间调度问题(flexible job shop scheduling problem, FJSP)，属于NP-hard问题[3]，目前研究多采用智能优化算法进行求解。在国外，CHAOUCH I等[4]在混合蚁群算法的基础上提出了一套新型的动态调度规则，高效求解了DMPPSP；MARZOUKI B等[5]为了得到最小化、最大完工时间，采用了基于化学反应优化的元启发式算法进行求解；在国内，吴锐等[6]设计了一种包含三维向量的编码方案，运用改进人工蚁群算法提升了算法的局部搜索能力。这些研究都在一定程度上解决了DMPPSP，但其算法多数存在不确定性大、易陷入局部最优解的缺陷。

本文将DMPPSP转化为DFJSP，提出了一种改进的混合粒子群算法，提高了全局搜索能力，实现了以最小化、最大完工时间为目标的分布式多工厂生产调度问题的求解。

1 分布式柔性车间调度问题

1.1 符号描述

文中使用的符号含义如表1所示。

表1 符号含义表

1.2 问题描述

问题描述：云平台上存在工件类型集合为T={T1，T2，…，Tt}的待加工工件集合J={J1，J2，…，Jn}，需要将J中的工件分配至FMU集合U={U1，U2，…，Ur}进行加工，其中各个FMU与仓库中心的距离集合为H={H1，H2，…，Hr}。每个FMU有多个加工机器Mu={Mu,1,Mu,2,…,Mu,lu}，每个工件加工过程共分为pi道工序。

由上述描述可知，DFJSP分为3个子问题，即FMU选择、机器选择和工序选择，如图1所示。

图1 DFJSP示意图

1.3 模型建立

本文模型基于的假设如下：

假设1：在初始时刻，待加工工件集合确定，FMU内任何机器都可用；

假设2：每个FMU都能加工任意类型的工件，每个工件只能分配至一个FMU；

假设3：每个机器在某一时刻只能最多加工一个工件；

假设4：每个工件的某个工序只能被某个机器连续独立加工完成；

假设5：同一个FMU内的同类型加工机器对同一道工序的加工效果相同。

基于以上假设，本文建立了以最小化、最大完工时间为目标函数的模型，如下所示。

目标函数：

(1)

约束条件：

Di,j≤Bi,j+1

(2)

Qu,m,c-Pu,m,c=tu,m,i,j

(3)

Pu,m,c+1≥Qu,m,c

(4)

(5)

(6)

(7)

其中：式(2)表示各工件工序具有先后顺序；式(3)表示每个机器正在加工的工序不能被打断；式(4)表示单个机器加工具有顺序性，在同一时刻只能加工一个工件；式(5)表示每个工件只能分配给一个FMU进行加工；式(6)表示各个FMU有能力加工完成任意工件；式(7)表示工件的每个工序只能分配至一个机器上进行加工。

2 模型求解

2.1 整体思想

模型求解的整体思路为将机器选择和工序选择作为FJSP嵌套于FMU的选择问题中。FMU选择产生的解作为FJSP的输入，FJSP的输出作为FMU选择解的评价指标，用于指导FMU选择产生更优解。

由于该研究问题属于NP-hard问题，故选用粒子群算法进行求解。标准粒子群算法收敛速度快，能够较为容易地得到较优解，但同时存在着早熟收敛的缺陷[7]。为了解决该问题，本文对标准粒子群算法进行改进，提出了基于二阶振荡的随机权重混合粒子群算法(RWSecVibratPSO)，提高算法的全局搜索能力，算法流程图如图2所示。

图2 RWSecVibratPSO流程图

2.2 算法具体设计

算法分为FMU选择和FJSP两部分。FMU选择嵌套FJSP。二者均采用RWSecVibratPSO算法进行求解。

a)FMU选择

1)粒子编码

本文设计FMU选择的每个粒子表示的信息为各个待加工工件分配至各个FMU的概率，概率变化范围为(0,1)。

2)粒子初始化

假设单个粒子的维度为D1，则每个粒子的速度和位置可分别表示为vi=(vi1,vi2,…,viD1)和xi=(xi1,xi2,…,xiD1)。随机初始化各粒子的速度和位置，并将各粒子的位置进行转化，得到各个FMU的分配方案。

本文选择FJSP作为FMU选择的适应度函数。FJSP的输入为粒子产生的各个FMU的分配方案，输出为FJSP的最小化、最大完工时间。考虑到各个FMU与仓库中心的距离不同，故根据距离设计影响系数τu，将各个FMU的最小化、最大完工时间乘以τu得到的结果作为单个FMU的最小化、最大完工时间。比较各个FMU的最小化、最大完工时间，取最大值作为该粒子的适应度，并初始化局部最优适应度与全局最优适应度。

3)粒子更新策略

针对早熟收敛的问题，本文提出了改进的混合粒子群算法RWSecVibratPSO，利用二阶振荡提高全局搜索能力，同时引入随机权重，平衡全局和局部搜索能力。该算法的速度与位置更新方程如下：

vij(t+1)=ωvij(t)+c1r1[pij(t)-(1+ξ1)xij(t)+ξ1xij(t-1)]+

c2r2[pgd-(1+ξ2)xij(t)+ξ2xij(t-1)]

(8)

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

(9)

ω=μ+σ×N(0,1)

(10)

μ=μmin+(μmax-μmin)×rand(0,1)

(11)

在前二分之一迭代次数中，取

(12)

在后二分之一迭代次数中，取

(13)

式中：ω为随机权重；c1与c2为学习因子；r1、r2和rand(0,1)为0～1的随机数；ξ1和ξ2为随机数，表示二阶振荡的搜索能力，前期利用式(12)提高全局搜索能力，后期利用式(13)提高局部搜索能力；pij为粒子i的局部最优适应度；pgd为粒子群的全局最优适应度；μ、μmax和μmin分别为随机权重平均值、最大值和最小值；σ为随机权重方差；N(0,1)为符合正态分布的随机数。

b)FJSP

1)粒子编码

本文FJSP的粒子表示工件在加工序列中下一个被加工的概率。通过对概率排序，根据工件的工艺规程得到相应的加工序列。

2)粒子初始化

随机初始化粒子的速度与位置，经排序后得到加工序列，作为适应度函数的输入。

FJSP适应度函数的核心是利用加工序列将加工任务分配至空闲的加工机器。分配的原则为保证当前工序结束时间尽可能早。

根据FJSP的适应度函数，可得到输入加工序列的机器加工方案，从而确定最大完工时间的适应度。根据初始化粒子的加工序列，可对其适应度进行初始化，进而对局部最优适应度与全局最优适应度完成初始化。

3 仿真验证与分析

为了验证RWSecVibratPSO算法的有效性，本文设计了相关的仿真实验，利用该算法对DMPPSP进行求解，同时选择标准粒子群算法作为对比算法进行比较分析。

3.1 仿真实验设计

设定共有3个分布式工厂，其与仓库中心的距离的比值分别为130、110、100，包含的FMU分别为FMU1、FMU2和FMU3、FMU4。每个FMU包含多个加工机器，其中FMU1与FMU2均包含3台车床、2台铣床、2台磨床与2台镗床，FMU3与FMU4均包含2台车床、2台铣床、2台磨床与2台镗床。待加工工件共6种，每种工件的加工工序及加工时间如表2所示。现需要加工工件集合A={4,4,4,4,4,4}，其中各个数字表示从左到右的序号为工件类型的加工数量。各种类型工件的加工信息如表2所示。

表2 各种类型工件的加工信息

RWSecVibratPSO算法的参数设置分为FMU选择和FJSP。对于FMU选择，设定粒子个数为30，迭代次数为50。c1和c2分别取0.5和1.5。对于FJSP，设定粒子个数为50，迭代次数为50。c1和c2分别取2和2.1。随机权重的取值两部分相同，即ωmax、ωmin和σ分别取值为0.95、0.75和0.5。

由于各个FMU与仓库中心的距离不同，故根据距离的比值设计τ1、τ2、τ3、τ4分别为1.3、1.1、1.1、1。

3.2 仿真结果分析

利用RWSecVibratPSO算法求解，得到一个较优解，即将A分解成4部分，分别为{1,2,1,0,0,2}、{2,1,1,2,1,0}、{0,1,1,2,1,0}和{1,0,1,0,2,2}，并将其对应分配至FMU1、FMU2、FMU3和FMU4。其最小化、最大完工时间为63.25。各个FMU调度安排的甘特图如图3所示。其中纵轴为各FMU的机器编号，横轴为加工时间，不同颜色区块对应不同的加工工件，区块上的编号与6的余数代表其对应的工件类型，当余数为0时代表第6种工件(本刊为黑白印刷，如有疑问可咨询作者)。

图3 各FMU调度的甘特图

为验证本文算法的优越性，本文采用标准粒子群算法作为对比算法，与RWSecVibratPSO算法在粒子数为30、迭代次数为50的条件下，各独立运行10次，比较两种算法得到最小化、最大完工时间的最大值、最小值和平均值，如表3所示。

表3 RWSecVibratPSO与PSO结果对比表 单位：h

由表3可知，本文提出的算法相比于PSO算法具有较强的鲁棒性和搜索性，在处理DMPPSP问题方面能力更优。

4 结语

本文针对DMPPSP，将其转化为DFJSP，提出了基于二阶振荡的随机权重混合粒子群算法。首先明确了要研究的问题，构建了DFJSP的数学模型；其次确定了算法的整体框架，将FJSP嵌套于FMU选择中进行求解；再者，设计了基于二阶振荡的随机权重混合粒子群算法，采用随机权重平衡全局和局部搜索能力，利用学习因子的二阶振荡提高全局搜索能力；最后，通过实例仿真，验证了本文算法的有效性和优越性。