基于改进斑点鬣狗算法的作业车间协同调度*

董 海，范英建

(沈阳大学a.应用技术学院；b.机械工程学院，沈阳 110044)

0 引言

如今在云制造的大背景下，制造企业通常采用分布式柔性作业车间进行生产[1-2]，分布式柔性作业车间相比于其他作业车间，其更贴近于企业的绿色制造模式，实现经济与环境的高度平衡。

分布式作业车间调度问题(distributed job-shop scheduling problem，DJSP)是典型的NP-hard问题。合理的调度方案能有效减少资源消耗和环境污染，因此DJSP问题也成为国内外学者广泛研究的热点问题。目前，对于求解DJSP问题，精确算法已经不适应大规模通用性问题，近似算法中的智能算法因其求解效率高、求解速度快而被广泛应用[3]。吴锐等[4]提出一种改进人工蜂群算法，设计了多种有效的进化操作算子，并引入基于关键路径的局部搜索算子。吴秀丽等[5]同时优化模型的总成本和提前/延期惩罚，提出改进的差分进化算法，设计了两种变异机制以及两种交叉方式。郭晨等[6]提出了一种混合差分搜索及变邻域搜索的分布估计算法，提出基于概率模型的相似系数和两种变异算子，并且设计了5种变邻域结构。孟磊磊等[7]提出一种混合蛙跳算法解决DFJSP，引入变邻域搜索算法提升蛙跳算法的局部搜索能力。CHAOUCH等[8]建立一种新的工厂作业动态分配规则，提出一种结合局部搜索的混合蚁群算法解决DJSP。XIE等[9]提出一种多目标人工蜂群算法，构造混合整数规划模型，使其完工时间和总能耗两目标达到平衡。MAHMOODJANLOO等[10]设计了一种自适应差分进化算法，提出2个基于位置和序列的决策变量MILP模型。ZHANG等[11]基于分布式装配车间调度问题，提出一种元启发式算法，将蚁群算法的局部搜索能力提高。XU等[12]针对考虑作业外包的分布式柔性作业车间调度问题，提出一种具有三层编码的混合遗传禁忌搜索算法。MOU等[13]提出了一种基于学习机制的双种群协同搜索机制，同时解决最大完工时间和能源消耗的双控问题。

斑点鬣狗算法最早是由DHIMAN等[14]提出的一种优化算法，其主要模拟了斑点鬣狗的狩猎行为。近年来，斑点鬣狗算法在电网调度[15]、旅行商问题[16]等方面展开应用，然而针对本文DJSP，鲜有研究。

因此，本文根据DJSP特性，设计一种离散型斑点鬣狗算法(discrete spotted hyena optimization，DSHO)应用于求解DJSP问题。利用斑点鬣狗算法的聚集特性控制多样性，使得在斑点鬣狗算法的搜索空间中创建各种候选解，提高算法的局部搜索能力，并且将贪婪启发式方法应用到作业排序阶段，消除冗余排列，提供更好的作业排序，缩短相关设施的完工时间，减少机器能耗。

1 分布式作业车间调度

1.1 问题描述

分布式作业车间调度问题(DJSP)主要面临两大挑战，第一是将合适的作业分配给合适的设备；第二是对机器上作业进行排序，达到最小化最大完工时间的目标。分布式作业车间调度问题(DJSP)可描述为如下：云数据库里有n个工件需要加工，协调分配给f个工厂，工件交给m台机器进行加工制造，工件在特定机器上操作具有固定的时间预计值，且加工时间和能耗各不相同。为方便建立数学模型和分析问题，给出如下假设：

①所有机器与工件都是相互独立且在0时刻都可工作或被加工；

②一个工件只能在一个时间被一台机器加工；

③一台机器只能加工一个工件，并且一旦加工不可中断；

④一个工件只可选择一个工厂进行加工，不可跨工厂进行操作；

⑤不同工件之间无优先级排序，同一工件有工序顺序约束；

⑥忽略工件在工厂的设备的运输时间，只计算机器加工时间。

1.2 符号说明

本文以最大完工时间及总能耗最小化建立数学模型。为便于模型的建立和描述，定义符号和变量如表1所示。

表1 符号和变量

续表

1.3 DJSP数学模型

针对DJSP问题，本文构建了一种MILP数学模型，实现工序的可排序化，相关公式如下：

Min(Cmax,TEC)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(Si,t+Wi,t,z)yi,j,t≤Si,j,∀i,t,j≠t,z

(8)

Sr,j+Wr,j,z≤Si,j+U(1-xr,i,j,k),∀r>0,i≠r,j,k,z

(9)

Sj,k≤Si,j+U(1-x0,i,j,k),∀i,j,k

(10)

(11)

Si,j+Wi,j,z≤Qi,j,∀i,j,z

(12)

Qi,j≤Cmax,∀i,j

(13)

(14)

(15)

EIj=ψj/4

(16)

(17)

xr,i,j,k∈{0,1}

(18)

yi,j,t∈{0,1}

(19)

hi,j,z∈{0,1}

(20)

其中，式(1)表示目标函数，式(2)表示每个工件只能分配到一个工厂的约束，式(3)、式(4)用来约束同一工作的所有操作必须分配到满足加工路线的同一工厂中，式(5)表示每台机器上的第一个作业，式(6)表示在任何机器上，任何一个工件不能在另一个作业之前和之后相邻，式(7)、式(8)表示在同一时间，一个工件最多只能在一台机器上进行处理，式(9)表示在同一时间，一台机器最多只能处理一个工件，式(10)确定每台机器的启动时间，式(11)表示每个工厂的完工时间约束，式(12)、式(13)用来约束最大完工时间，式(14)用来约束每个操作都以同一种速度进行，式(15)表示机器加工能耗，式(16)表示机器闲置下的能耗，式(17)表示生产总能耗，式(18)～式(20)定义决策变量。

2 斑点鬣狗算法求解DJSP

2.1 斑点鬣狗算法介绍

斑点鬣狗算法是一个基于生物模仿的元启发式算法，描述了斑点鬣狗的社会关系和狩猎技术，模仿斑点鬣狗在自然界的行为[17]。通过式(21)在预定的搜索空间里随机均匀生成斑点鬣狗种群：

Pij=Lj+φ*(Hj-Lj)

(21)

式中，Pij为斑点鬣狗所在位置的第j维度；Lj为搜索空间的下限的第j维度；Hj为搜索空间的上限第j维度；φ为0～1中的随机数值。斑点鬣狗算法分别使用了包围、猎狩和攻击三种手段，通过式(22)～式(26)进行模拟。

A=2a·r1-a

(22)

C=2·r2

(23)

a=5-(t*(5/tmax))

(24)

D=|C·P*-P|

(25)

P(t+1)=P*(t)-A·D

(26)

图1 斑点鬣狗种群猎狩

式中，D表示斑点鬣狗到猎物的距离矢量；P*表示猎物的位置矢量；P表示斑点鬣狗的位置矢量；A、C表示系数向量；t表示当前迭代次数；tmax表示最大迭代次数；a表示每次迭代由5减少到0；r1和r2为0～1中的随机数值。同时斑点鬣狗是一个群体猎狩种族，同伴间有着良好的信息交流能力，有时会召集同伴一起参与猎狩，如图1所示。其行为通过式(27)～式(29)进行模拟：

D=|C·Pbest-Pk|

(27)

Pk=Pbest-A·D

(28)

(29)

式中，Pbest表示迭代后斑点鬣狗最好的位置矢量；Pk表示斑点鬣狗的同伴位置矢量；Ch表示斑点鬣狗群体；M表示绝对值在0.5～0之间的随机向量；N表示加上M之后最容易接近猎物的斑点鬣狗的位置矢量。在攻击阶段，所有的斑点鬣狗的动作通过式(30)进行模拟。

P(t+1)=Ch/N

(30)

2.2 离散编码

在斑点鬣狗算法中，斑点鬣狗位置的初始向量不是用离散值生成的，且其只能表示顺序关系，并不能表示工作处理的顺序，所以需要对斑点鬣狗的位置值进行离散型编码。本文采用一种随机型离散编码方法(RK)对斑点鬣狗进行编码，将连续变量映射到作业索引编码方案中。假设现有两个工件，每个工件需要3道工序，引入实数数值，采用RK方式将连续值转换为离散值，如表2所示。

表2 作业编码映射方案

在表2中，斑点鬣狗的连续值(Pij)位于第一行，排序索引(Sij)位于第二行，工序索引通过式(31)计算出来。

φij=(Sijmodn)+1

(31)

式中，φij表示工序索引中的第j维度的第i只斑点鬣狗；Sij表示第j维度的第i只斑点鬣狗的位置；n表示工件数量。

在这个离散化阶段结束时，可以对操作序列进行编码，采用RK之后，操作向量的作业处理序列可以被正确映射。

2.3 工作负载规则

本文同时考虑机器的处理时间和机器的作业顺序，以每台机器的负载作为分配规则，并且将之称为工作负载规则。在工作负载规则中，使用等式(32)评估机器的工作负载。

(32)

式中，m是每台机器的索引；M是机器的集合；j是作业的索引；J是作业的集合；k是当前机器的索引；PM是前面机器的集合；PT是处理时间矩阵。

为更好地描述并解释DJSP中的工作负载规则，列举出一个数值实例，其中f=2，n=5，m=3(f表示设备数量，n表示工序数量，m表示作业数量)。实例的处理时间和工序排列和作业处理的工作量分别如表3和表4所示。

表3 作业处理时间和工序

表4 作业处理的工作量

基于式(32)计算作业的总工作量，作业按降序排列为{2，3，4，1，5}，并在表4中列出。工作设施分配被编码为一个向量，设施作业分配为{1，1，2，2，2}，则表明作业1和2将分配给第一个设施，作业3、4和5将分配给第二个设施。

2.4 设施中的作业排序

在DJSP中，工作负载规则确定后，需要对每个设施的作业进行适当排序。作业被编码为操作向量，编码向量中的第一个参数表示相关作业的第一次操作，在向量中再次看到相同参数的位置，其表示该作业的第二次操作，并继续以此类推。

向量中所述作业的所有操作分别使用贪婪启发式逐个执行。贪婪启发式中存在两个冗余状态，如果α是通过交换两个操作而产生的置换β，并且两个操作属于相同的作业，则其是冗余置换。如果α是通过交换不同机器处理中的不同作业的两个操作或者两个相邻操作而产生的置换β，则也是冗余置换。在贪婪启发式中，一些冗余排列不被评估以获得计算时间优势。评估向量中操作的排列，选择提供最小完工时间的最佳解决方案的排列，得到最终的工序排序。

2.5 算法流程

离散型斑点鬣狗算法的流程图如图2所示。首先录入DJSP相关数据，根据工作负载规则，将具体作业分配给某一设备。然后使用RK作业索引将每个斑点鬣狗的连续位置转换为操作向量，用贪婪启发式重组设备的操作向量，以提高解决方案的质量。计算每个设施的操作向量的最大完工时间和生产能耗，并将设施的最大完工时间和生产能耗确定为目标函数(Cmax、TEC)。在分别达到指定的终止标准之前，更新斑点鬣狗的位置，通过RK作业索引使其离散化，使用贪婪启发式改进作业序列，并存储最佳解。最后，当满足终止标准时，获得的最小完工时间和能耗最小(Cmax、TEC)报告为最佳解决方案。

图2 离散型斑点鬣狗算法流程图

3 试验验证

算法程序是在MATLAB上进行编码的，仿真实验是在具有Windows Server 2016操作系统的Intel(R)Core(TM)i5-6700CPU3.4 GHz和8.00 GB内存的PC机上进行的。通过大量试验表明将迭代参数设置为500，c1和c2参数都设置为2时，算法性能较好，因此本文采用该参数组合。

为验证DSHO的优劣性，本文将DSHO与离散型粒子群算法(discrete particle swarm optimization，DPSO)，动态局部蚁群算法(ant colony optimization and local search procedure and dynamic assignment，DAHACO)，局部蚁群算法(ant colony optimization and local search procedure，HACO)，蚁群算法(ant colony optimization，ACO)等算法进行对比进行比较，选用15个作业和15台机器到500个作业和20台机器，基准实例的维度介于225～2000之间，设施数量使用2～7个工厂来解决DJSP问题。算法求解后采用相对百分比偏差(relative percentage deviation，RPD)用以比较DSHO和其他算法的性能差异。PRD 的值计算如下：

(33)

式中，alg是通过相关算法获得的最大完工时间；min是给定实例的最小完工时间。为了评估算法在不同设施数量下的性能，图3绘制了不同设施数量算法平均RPD结果。

图3 不同设施数量下各种算法的RPD

如图3所示，当设施数量为2时，算法差异较大，随着设施的数量增加，可以更有效地组织生产操作，算法之间的RPD差异减小。

在2个、3个和4个分布式设施的80个基准案例上，DSHO都获得了最佳解决方案；在5个分布式设施中，DSHO获得了78个基准问题的最佳解决方案；在6个分布式设施中，DSHO获得了79个基准问题的最佳解决方案；在7个分布式设施中，获得了77个基准问题的最佳解决方案。因此，DSHO在最大完工时间方面优于DPSO、DAHACO、HACO和ACO。图4为采用DSHO算法在7个分布式设备数量下Tai76案例第四分布式设备上的作业序列，设施4的最大完工时间值为1640。

图4 分布式设备4的最佳调度方案

式(34)为Friedman测试中评价各算法的指标函数，其中参数k和N分别是算法的数量和实例的数量，qa取3.091。

(34)

Friedman检验同样是在MATLAB上进行，数据如表5所示，Friedman检验等级如图5所示，该图表明DSHO明显优于其他比较算法。

表5 Friedman检验平均值

图5 Friedman检验等级

4 结论

本文以云制造分布式柔性作业车间为研究对象，将工作负载规则和贪婪启发式算法融合到离散型斑点鬣狗算法中，提出一种新的离散型斑点鬣狗优化算法。经验证得到以下结论：

(1)离散型斑点鬣狗算法应用于分布式作业车间调度优化是有效的，可以有效减少完工时间、车间总能耗。

(2)离散型斑点鬣狗算法在相对百分比偏差、最佳实验方案和算法稳定性等指标均优于其他智能算法。