面向可持续生产中多任务调度的双重增强模因算法

卢 弘 王耀南 乔 非 方 遒

可持续生产调度 (Sustainable production scheduling) 是顺应当下制造业绿色与可持续发展需求的新兴研究课题[1-2].相比于以优化经济维度为核心的传统调度,可持续生产调度在此基础上,从调度目标或者约束角度扩充环境维度 (高能效、低碳排放等) 和社会维度 (工作公平、人员安全等) 的可持续制造指标[3-5],从而有效地兼顾制造业的正面绩效和负面影响,有利于企业的长远发展.

依据考虑的可持续维度,可持续生产调度研究可以细分为: 1) 高能效调度 (Energy-efficient scheduling),旨在通过制造调度实现能源效率最大化,由此得到的调度方案既降低能耗又兼顾生产性能[6-9];2) 低碳调度 (Low carbon scheduling),指的是通过制造调度优化生产性能,同时降低制造过程中的碳排放量[10-12];3) 考虑需求响应策略的调度(Scheduling with demand response strategies),是在调度过程中考虑供电方制定的策略,从而在保证生产性能的基础上优化电力消耗[13-14].在综述文献方面,Giret 等在文献[15]的基础上,整理经济、环境以及社会3 个维度的可持续制造性能指标,并从制造车间、目标系统、模型类型、目标函数、约束条件以及求解方法这6 个角度进行整理和归纳[3].结合已有综述和细分领域的研究现状来看,目前成果在优化目标或者约束上有各自的侧重和不同,但关注的可持续性指标大多局限于经济和环境两个维度,对社会维度关注较少.随着制造业用工合理和工人安全等社会性问题频发,全面考虑经济-环境-社会三维可持续性的调度研究有待深入开展.

随着指标维度的拓宽,可持续生产调度的任务也由传统生产任务 (投料、工件排序与机器指派)向机器控制与人员安排等相关任务泛化.环境维度上,引入包括调整机器加工速度[16-17]和选择机器开关机[18-19]的机器控制任务,进一步降低能源消耗.社会维度上,工人是重要的考量因素,保证其工作负荷的公平是实现生产可持续性的必然要求[20].为满足不同维度可持续指标的优化需求,调度决策过程中必将面临多种不同类型的调度任务.因此,研究多类型任务的调度优化对提高制造企业生产方案的全方位可持续性有着重要的意义.针对制造生产中经典的并行机场景,本文将优化来自3 个维度的可持续目标,因而调度决策时包含机器指派、工件排序、工人安排以及机器开关机控制在内的4 种任务.

本文研究多维度目标和多类型任务的调度问题,相应的调度模型必然具有多目标优化和多决策变量的特点.算法在求解模型时,搜索空间的范围大且结构复杂.在这样的搜索空间中,算法往往极易陷入局部最优解,因此提高局部寻优能力是求解本文问题的研究重点.模因算法 (Memetic algorithm,MA) 是一类针对复杂优化问题的元启发式方法,在平衡全局探索和局部开发上具有良好的性能[21-22].该算法使用交叉和变异等全局搜索算子,同时引入局部搜索技术增强其局部搜索能力.近年来有学者开始将其用于求解可持续调度问题,Geng等[23]针对考量工人安排的柔性流水车间调度问题,提出一种多目标模因算法优化最大完工时间、拖期时间以及工人负荷差异.Zhu 等[24]研究具有工人学习因子的低碳柔性作业车间调度问题,设计一种包含遗传算法和变邻域搜索的模因算法.Wu 等[16]提出一种多目标的模因差分进化算法,同时优化最大完工时间和总能耗这两个目标.Zhang 等[25]针对考虑机器速度可调的高能效调度问题,在遗传算法的基础上,设计两种优化策略以分别优化拖期时间和总能耗.

在上述基于模因算法的求解方法中,全局搜索基本是基于交叉和变异的遗传算子,而局部搜索主要分为以下两类: 1) 基于跳变的随机搜索策略,即将当前的候选解作为起点,在该点附近的邻域内,以迭代的方式随机生成新解[24].这种方式往往是基于变邻域搜索、模拟退火等已有算法,设计简便但参数调整困难.2) 基于问题结构的特定策略,这是针对具体问题而设计的定向优化方法[16,23,25],通过分析问题的优化需求,构建针对性的启发式策略,设计难度相对较高.已有研究在构建模因算法时,大多仅利用单一类型的策略,鲜有结合两种策略的研究工作.对于复杂的可持续调度优化问题,这两种局部搜索策略各有优势,如何将两者有效地结合起来以实现双重优化,是一种值得探索的研究思路.

本文针对多类型任务的可持续并行机调度问题,提出一种融合两种局部优化策略的双重增强模因算法 (Dual-enhanced memetic algorithm,DMA).考虑多决策变量,构造单步变邻域搜索 (Onestep variable neighborhood search,1S-VNS).考虑多目标优化,设计分步优化的可持续目标导向策略(Sustainable goals-oriented strategy,SGS).最后,实验对所提双重模因算法在求解本文问题上的有效性和优越性开展验证和分析.

1 问题描述和建模

带多类型任务的不相关并行机三维可持续制造调度问题可以描述为: 车间里有N个独立工件(i=1, 2,···,N) 和M台不相关并行机(j=1, 2,···,M),由K个工人 (v=1, 2,···,K) 负责操作机器加工工件.问题的实际背景可参见车辆装配生产过程[20,26],在组装车辆外部构件时,要求工人操作机器完成上料、组装以及下料等工作.出于生产效率的考虑,工人数量往往不大于投入使用的机器数量.因而,对于某个工件来说,会出现机器可用而工人不可用 (正在加工其他工件) 的情况.此外,这里假设机器允许出于节能考虑而出现开关机情况[18].调度问题的任务类型包含4 类: 1) 为机器指派所加工的工件;2) 为各个机器上的工件排序;3) 为工人安排所负责的工件;4) 控制处于非加工状态的机器进入待机或者关机.

研究的调度目标涵盖了可持续制造指标体系的全部维度: 1) 在经济维度上,考虑最小化最大完工时间Cmax;2) 在环境维度上,最小化加工过程中的总能耗Eall,包括加工能耗Ep和非加工能耗Enp;3) 在社会维度上,最小化工人之间工作负荷的不平衡度W[20].

决策变量的定义如下:xijlv为决策变量,工件i在机器j上的第l个位置由工人v操作时xijlv=1 ;否则,xijlv=0.该决策变量对应工件排序、机器指派以及工人安排这3 个调度任务.ymac是辅助变量,用来指代机器开关机的决策条件,假如机器待机能耗比关机能耗低,则ymac=1;否则,ymac=0.

基于上述的问题定义和描述,带多类型任务的不相关并行机三维可持续制造调度问题的三元命名是R|xijlv,ymac|Cmax,Eall,W,相应的数学模型如下所示.

目标函数为

在目标函数中,式(1)表明优化的是3 个不同维度的调度目标,各个调度目标的具体计算方式如式(2)～ (7)所示.在约束条件中,式(8)表示任何一个工件只能被安排到一台机器上的一个位置并且由一个工人进行加工;式(9)约束了机器每个位置上最多加工一个工件;式(10)明确了最大工作负荷的计算方式;式(11)表示在机器j的l位置上工件的结束时间cj,l的计算方式;式(12)表示在机器j的l+1 位置上工件的开始时间sj,l+1的计算方式;式(13)表示决策变量xijlv是0-1 变量.

相比于文献[27]中经典的并行机调度模型,本文研究的调度模型呈现以下特点: 1) 调度目标上,本文同时优化3 个可持续目标Cmax、Eall和W, 其中Cmax和W属于时间量纲,Eall属于能耗量纲,因此本文目标数量更多且量纲不一致.2) 决策变量上,本文不仅考虑传统的机器指派和工件排序,而且拓展了工人安排和机器控制两种任务.因此,决策变量xijlv的数量 (M×N×K) 远大于传统调度模型 (M×N).3) 约束条件上,随着目标和决策变量的复杂化,约束条件的数量(2×N+1+2×M×N+M×N×K)也明显更多.

鉴于调度模型的复杂度,本文基于模因算法框架,从目标优化需求和决策变量特点两个角度入手设计双重局部优化策略,进而提出一种融合两种策略优势的双重增强模因算法.

2 双重局部优化策略

2.1 任务对应的个体编码

编码是将问题的解空间转变为算法寻优的个体,因此编码方法与调度问题的决策任务直接相关.为匹配个体与R|xijlv,ymac|Cmax,Eall,W问题的调度方案,下面针对问题中的4 类调度任务设计编码方式.考虑到机器开关机的选择需要以其他三类任务的确定为前提,因此采取三段式编码方式将算法个体与调度问题中的机器指派、工人安排以及工件排序三类任务相对应.图1 给出了一个三段式个体的示例说明,针对的是5 个工件在3 台机器上由2 个工人加工的案例.在图1 的个体中,α段表示各个工件的加工顺序,β段表示各个工件的机器指派,γ段则代表了各个工件的工人安排.基于三段式编码形式,以随机的方式形成初始种群.

图1 任务对应的个体编码说明图Fig.1 An example graph of individual coding corresponding for tasks

2.2 单步变邻域随机搜索策略

变邻域搜索是围绕单个解的邻域展开迭代搜索,其关键在于设计合适的邻域动作,以达到产生更优个体的效果[28].针对第2.1 节中三段式个体,每段代表不同的任务,因此需要为各段设计相应的邻域动作.可选的邻域动作包括插入、突变和交换等方式[29-34].本文借鉴已有方法的经验,并通过多次试验,设计了如下4 种邻域动作:

1) 对机器指派β段,随机改变一个工件的机器指派,以N1指代该邻域动作;

2) 对工人安排γ段,随机改变一个工件的工人安排,以N2指代该邻域动作;

3) 对加工顺序α段和机器指派β段做组合动作,对α段以插入的方式改变,同时以方式N1改变β段,以N3指代该邻域动作;

4) 对加工顺序α段和工人安排γ段做组合动作,对α段以插入的方式改变,同时以方式N2改变γ段,以N4指代该邻域动作.

传统的变邻域搜索算法往往需要进行多次迭代,迭代是以计算时间换取解质量的方式.在模因算法的框架中,每一次全局寻优后,都会运行多次局部迭代.假设全局寻优次数是num_global,局部迭代次数是num_local,那么算法总的迭代次数将是num_global×num_local.如此大量的迭代次数,必然造成算法整体的搜索效率不高.另一方面,鉴于本文将融合两种局部优化策略,无需展开过多的随机搜索.因此,以单步的方式运作变邻域随机搜索策略,其更新单个个体的作用流程如算法1 所示.

算法1.单步变邻域随机搜索策略

2.3 可持续目标导向优化策略

基于单步变邻域随机搜索策略有助于产生新个体,但随机性使其优化效果难以得到保障.通过探索问题的特征来构建的优化策略,往往能够直接有效地改善解质量,并且时间复杂度也较低[16,25].因此,本文将针对带多类型任务的可持续调度问题,分析各个维度目标与不同调度任务之间对应关系,进而设计针对性的优化策略.然后,考虑到不同目标之间的冲突耦合关系,构建了分步作用方式以逐步优化不同维度的目标.

2.3.1 社会维度目标导向的优化策略

研究问题中的社会维度目标,是降低工人工作负荷差异度W,这可以通过减小各个工人工作负荷bv与最大工作负荷bmax之间的差值(式(6))实现.在所有差值中,工作负荷最小值bmin与工作负荷最大值bmax的差值 ∆b是最大的,因而降低 ∆b对于优化W而言是最为直接且简便的.鉴于此,下面针对 ∆b开展优化策略的设计.

在R|xijlv,ymac|Cmax,Eall,W问题中,调整工人安排即改变工人负责的工件,可以有效改变 ∆b.假设目前具有bmax和bmin的两位工人分别是v和v′,社会维度目标导向的优化策略核心是从工人v负责的工件集Jmv中挑选合适的工件转变为v′负责加工,以此来减小bmax同时增大bmin.在这样的调整方式下,其余工人的工作负荷并不会发生改变.在不造成新bmin大于原bmax的情况下,其 余工人与bmax之间的负荷差异也会随着bmax的减小而下降,结果是整体的W值得到优化.该优化策略是在不改变加工顺序和机器指派的情况下,通过调整工人安排以优化社会维度目标,具体步骤如算法2 所示.

算法2.社会维度目标导向的优化策略

为了进一步说明社会维度目标导向优化策略的特点,图2 基于附录A 中的案例数据给出了该策略的作用效果.在未作用的调度方案(图2(a))中,两个工人的负荷分别是b1=16、b2=4,此时的社会维度指标W的值是12.将所提优化策略作用于此调度方案: 首先,bmax和bmin分别对应b1和b2,两者之间的差异 ∆b=12.接着,统计负荷是bmax的工人W1 所负责的工件集合Jmv及其加工时间:J1(3),J2(4),J3(3),J4(6).在不改变机器指派的情况下,由工人W2 负责Jmv,那么各个工件的加工时间是:J1(6),J2(2),J3(3),J4(2).按照设计步骤,针对Jmv中的每个工件计算 ∆b′,即尝试替换工人安排.可以发现,当J1 替换为W2 负责后,∆b′=3.依据替换条件,加工J1 的工人由W1 调整为W2,由此形成了新调度方案(图2(b)).此时b1=13,b2=10,目标值W的值是3.对比图2(a)和图2(b)两种调度方案,社会维度目标W由12 降低为3,因此设计的优化策略改善了社会维度目标.

图2 社会维度目标导向的优化策略作用效果说明图Fig.2 Explanation of the effectiveness of optimization strategy guided by social dimension goal

2.3.2 经济维度目标导向的优化策略

研究问题中的经济维度目标,是降低最大完工时间Cmax(式(2)).针对具有最大完工时间的机器,其消耗的时间主要由必要加工时间和空闲时间两个部分组成,其中空闲时间是无效的非必要时间.本节通过调整工件之间的加工顺序减少空闲时间,以优化该机器上所有工件的完工时间.为此,经济维度目标导向优化策略的核心思路是,将完工时间靠后的工件提前至空闲时间段进行加工.因此,该策略调整的是工件的加工顺序,而不改变机器指派和工人安排,其具体的优化步骤如算法3 所示.

算法3.经济维度目标导向的优化策略

为了进一步说明经济维度目标导向优化策略的效果,图3 同样基于附录A 数据给出了优化策略作用前后的效果对比.作用前,调度方案(图3(a))的经济维度指标Cmax=21.将优化策略应用于该调度方案: 首先找到Cmax对应的机器是M3,其加工的工件集合Jmc包含了J3 和J4.接着,尝试将J4的开始时间前移至J3 之前以降低机器的完工时间.由于此时J4 的加工时间是6,而J3 的开工时间是12,因而满足前移条件.将J4 提前至J3 之前加工,形成了新调度方案(图3(b)).对比作用前后的两种调度方案,经济维度目标Cmax从21 降低至了15,因此设计的优化策略改善了经济维度目标.

图3 经济维度目标导向的优化策略作用效果说明图Fig.3 Explanation of the effectiveness of optimization strategy guided by economic dimension goal

2.3.3 不同优化策略的分步作用方式

在第2.3.1 节和第2.3.2 节中,考虑社会维度目标导向的优化策略,也会影响其他两个维度的目标值.对于经济维度目标导向的优化策略,会同时影响经济维度目标以及环境维度目标,但不会对社会维度目标造成影响.假如策略作用顺序不当,相互的优化效果就会出现冲突,进而导致无效优化的情况.为了避免不同策略的优化冲突,有必要设计一种分步作用方式.

第1 步是运作社会维度目标导向的优化策略,第2 步是运作经济维度目标导向的优化策略.在经济维度目标导向设计的作用后,针对空闲时间段以调度机器控制任务的方式优化环境维度目标值 (控制机器处于待机或关机的任务),并将其作为分步作用方式的第3 步.这样的分步作用方式使得三个维度目标依次得到针对性的调整,并且保证了后一步的优化策略不会破坏上一步的优化结果,不同优化策略分步作用方式的具体步骤如算法4 所示.

算法4.不同优化策略的分步作用方式

3 双重增强模因算法

在模因算法框架中,寻优过程由全局搜索算子和局部搜索策略两个部分完成.针对本文问题,全局搜索算子仍延续传统交叉和变异的设计思路,对应上文个体做了相应的设计.针对多目标和多任务带来的局部寻优困境,提出了随机跳变和定向优化双重优化策略.并且,依据不同策略的各自特点,将两种策略作用于不同个体的更新,以融合各自的优势.

3.1 全局搜索算子

对应第2.1 节中三段式个体,这里设计分段作用的全局搜索算子,以充分地更新每一段上的基因.依据各个个体支配等级,采取轮盘赌的方式挑选出PS×0.8个个体作为全局搜索算子的作用对象.

针对具有三段结构的个体,分段作用的全局搜索算子包括了交叉算子和变异算子,具体设计是:对于代表加工顺序的α段,交叉操作以顺序交叉(Ordered crossover) 的方式进行,变异操作以交换(Swap) 的方式进行;对于表示机器指派的β段,交叉操作以均匀交叉 (Uniform crossover) 的方式进行,变异操作则以单点 (Single point) 的方式进行突变;最后对于代表工人安排的γ段,交叉操作也采取均匀交叉,变异操作以单点突变.

考虑到本文问题中的多目标优化,采用了NSGA-II 中的非支配解排序和拥挤度计算等方法[20],可参考相关文献,这里不再赘述.

3.2 双重增强模因算法的主流程

基于上述设计,所提算法 (DMA) 求解R|xijlv,ymac|Cmax,Eall,W问题的主流程如下:

步骤 1.初始化种群PG,精英集合PE,令迭代次数i=0.

步骤 2.初始化精英集合,精英集合是由每代中对应非支配解的个体所构成,PE=PG×20%.当精英集合超过限定大小时,按照拥挤度挑选新的精英集合.

步骤 3.判断是否终止迭代,如果达到终止条件,则算法终止并输出非支配解;否则,令i=i+1.

步骤 4.针对种群PG,以第3.1 节中的全局搜索算子,形成新种群.

步骤 5.对于,以第2.2 节中的单步变邻域随机搜索策略,形成种群.

步骤 6.针对精英集合PE,以第2.3 节中的可持续目标导向优化策略更新精英集合中的个体,得到新精英集合.

步骤 7.结合和,更新种群PG和精英集合PE.返回步骤3.

从上述步骤中看出,双重优化策略的融合方法是: 首先,将单步变邻域随机搜索作用于种群中的所有个体;接着,可持续目标导向策略进一步更新精英集合中的个体.之所以将可持续导向策略独立作用于精英个体而非参与到所有个体的更新过程,主要是为了避免算法过早陷入局部最优解.假如将单步变邻域随机搜索策略和定向优化策略同时作用于种群,那么种群会早早地出现较多优质个体.在这些个体的引导下,算法会因为缺乏个体多样性而过早收敛.其次是,相比所有个体参与优化策略,仅部分个体参与消耗的计算时间更少.综上,所提DMA在全局搜索算子的基础上,有效地融合两种局部搜索策略,以期达到兼顾全局探索和局部开发的寻优效果.

4 实验验证

为了验证双重增强模因算法 (DMA) 在求解多目标和多任务的R|xijlv,ymac|Cmax,Eall,W问题上的有效性和优势,接下来开展多组对比实验和分析讨论.所有测试实验均采用MATLAB 2016b 编程实现,在8.0 GB 的RAM、2.30 GHz 的CPU 环境下运行.

实验案例来源于Costa 等[26]的研究工作,文献[26]在不相关并行机调度问题中考虑了人员安排,构建了相应的标准测试案例.基于此,本文从小规模和大规模案例中各选8 种,组成16 种测试场景.加工过程中的其余参数设置如下: 加工时间从均匀分布区间[2,6]随机获取;单位时间的加工能耗和空闲能耗分别从均匀分布区间[3,8]和[1,4]中随机获取;机器的开关机所需的能耗和时间分别从均匀分布区间[1,12]和[1,3]中随机得到.考虑到参数随机性,本文在各个场景下构建了5 个具有不同参数的案例,形成的测试案例总数是 16×5=80 个.

本文引入反转世代距离 (Inverted generational distance,IGD) 和非支配解占比两种性能指标,对算法求解案例的结果做分析和对比.反转世代距离是常用于比较多目标算法在收敛性和多样性上优劣的综合指标.算法的IGD 值越小,则算法的性能越好.对于某一类算法来说,其IGD 的计算方式为

其中,A代表某一类算法;F表示所有对比算法求解结果中的非支配解集,即近似最优Pareto 解集.F的构造方式是将所有对比算法求解问题获得的解集合并,然后以快速非支配排序的方式处理,最终获得的非支配解集即为F.|F|代表F中解的个数,d(y∗,y) 表示y∗和y两点之间的欧氏距离.

非支配解占比以Rnd表示,是将算法所得的非支配解集与近似最优解集F比较.算法的Rnd值越大,代表相应的算法越好,其Rnd的计算方式为

其中,Nnd(A) 表示算法所得非支配解同样也存在于F中的数量.

为了保证比较的公平性,所有对比算法的运行时间均相同,即终止条件相同,都是N×M×K×100ms.此外,所有实验中各个算法均独立重复运行10 次后取平均结果,以消除随机误差.

4.1 双重局部优化策略的提升作用

4.1.1 单步变邻域随机搜索策略的有效性

邻域动作是单步变邻域随机搜索策略 (1S-VNS)能否发挥作用的关键,因此通过对比不同邻域动作,以验证本文所设计的方法是适用于问题的.这里参与对比的邻域动作包括3 种,都是来源于第2.2 节中的变种.基于此,具体用于对比分析的算法如下:

1) MOA: 代表解决问题的多目标优化算法,即仅具有第3.1 节中全局搜索算子;

2) MMA_1: 代表在MOA 中加入第2.2 节中邻域动作的第1 变种;

3) MMA_2: 代表在MOA 中加入第2.2 节中邻域动作的第2 变种;

4) MMA_3: 代表在MOA 中加入第2.2 节中邻域动作的第3 变种;

5) MMA: 代表在MOA 中加入第2.2 节中邻域动作.

对比MMA 与MOA,可验证局部优化方法(1S-VNS)是否有效.对比MMA 与其余变种,可验证所设计的邻域动作是否更为适用.5 种算法的初始种群大小均为100,交叉和变异概率均分别设置为0.9 和0.1.基于此,表1 统计了各算法求解不同案例所得的平均性能值,加粗形式表示占优的结果.

表1 MMA 与MOA、MMA_1、MMA_2、MMA_3 的性能指标结果Table 1 Results for MMA,MOA,MMA_1,MMA_2 and MMA_3

从表1 可知,MMA 在所有的小规模场景(前8 种)上占据优势.无论是IGD还是Rnd,MMA 都比其他算法表现得更好,这说明所设计的1S-VNS在算法求解小规模场景时具有提升作用.对于大规模场景(后8 种),MMA 并没有在所有案例上都取得最好的结果.尤其是20&12&10 场景,MOA 与MMA 的性能指标结果十分相近,这说明此时邻域搜索并没有起到改善算法性能的作用.究其原因,1S-VNS 本质是随机寻优,在计算时间限定时,难以保证在大规模场景的复杂搜索空间中产生更优的个体.需要说明的是,表中的结果是多次测试后的平均值,因此有可能会出现IGD不同而Rnd相同的情况.对于20&12&8 场景,MMA 虽然表现不如MMA_2,但两者的性能差距较小.综合16 种场景,MMA 在大多数(15 种)结果上是具有求解优势的.

本文进一步采用方差分析法 (Analysis of variance,ANOVA),对表1 中的算法性能差异展开显著性检验.以5 种算法为控制变量,将2 种性能指标作为响应量,检验结果如图4 所示.无论是指标IGD还是Rnd,MMA 与其他对比算法的置信区间都没有重合,这表明MMA 的算法优势是显著的.综合16 种案例的结果来看,1S-VNS 方法能够明显地提升算法性能,尤其是对于小规模案例.此外,MOA 与MMA_1、MMA_3 的置信区间存在重合,表明这些算法之间的差异并不显著,这说明不合适的邻域动作并不能有效改善算法求解结果.MMA_2 虽然与MOA 不存在明显重合,但其性能远不如MMA.因此,相比其他3 个变种,MMA 中的邻域动作是最为适合本文问题的.

图4 MMA 与MOA、MMA_1、MMA_2、MMA_3 性能指标的均值和95%置信区间Fig.4 Mean and 95% confidence interval of performance indicators of MMA,MOA,MMA_1,MMA_2 and MMA_3

4.1.2 目标导向优化策略的有效性

对于可持续目标导向策略(SGS)有效性的验证,本文从有无策略以及融合方式两个角度开展.因此,将所提DMA 与以下2 种算法进行对比:

1) MMA: 表示没有融合目标导向优化策略的多目标模因算法(同第4.1.1 节);

2) MMA&SGS: 表示将SGS 作用于多目标模因算法中所有个体的算法.

对比DMA 和MMA,可以验证SGS 是否有提升算法性能的作用.对比DMA 和MMA&SGS,能够分析SGS 作用于个体和种群之间的效果差异.3种算法中种群大小均为100,交叉和变异概率都设置为0.9 和0.1.DMA 中的精英集合大小均设置为20.表2 统计了各个算法求解不同场景中案例所得的平均性能值,加粗的字体表示占优的结果.

表2 DMA 与MMA、MMA&SGS 的性能指标结果Table 2 Results for DMA,MMA and MMA&SGS

在表2 的小规模场景 (前8 种) 求解结果中,DMA 在其中的5 种场景占据优势,而MMA 在2种场景上表现最佳,3 个算法在最小规模场景下同时最优.这一方面说明,在精英个体上作用SGS,对DMA 在大多数小规模场景的求解性能的确具有提升效果.另一方面,MMA 求解结果占优表明,随机局部搜索 (1S-VNS) 比定向优化 (SGS) 效果更好的作用场景是存在的.可以理解的是,小规模场景下的寻优个体简单,算法寻优空间小,1S-VNS 通过邻域动作仍可以有效地搜索到更优个体.并且,由于无需在定向优化上花费计算时间,MMA 相比DMA 有更多的随机搜索次数.综合搜索次数和单次寻优能力,才使得MMA 在小规模案例上仍保持着一定的竞争力.

对于表2 中大规模场景 (后8 种) 的求解结果,其中6 种场景由DMA 占优,而剩余2 种则是MMA&SGS 更优,MMA 在所有场景中都表现最差.相比小规模场景的结果,定向优化策略SGS 起到了更加明显的作用.因为随着场景规模变大,寻优空间随之扩展,随机搜索的盲目性更加明显,而定向优化产生更优个体的概率更高.此外,DMA 在更多场景下优于MMA&SGS,这也说明将SGS 作用于精英个体比作用于所有个体对提升性能更为合适.主要原因是,当SGS 作用于所有个体,就意味着定向优化将消耗更多的计算时间.在限定运行时间的情况下,寻优过程难以平衡全局寻优、随机搜索以及定向优化,这导致MMA&SGS 算法的整体搜索效率不高.

为了验证上述算法性能之间的差异是否具有统计意义,接着利用ANOVA 对表2 中的实验结果进行差异性检验,结果如图5 所示.可以看出,在IGD和Rnd上,DMA 与其他两种算法的置信区间都没有重合,这说明DMA 是显著地优于对比算法,验证了作用于精英个体的SGS 是可以显著提升算法性能的.此外,MMA 和MMA&SGS 在两种性能指标上的差异都不显著,这也侧面说明SGS 作用于所有个体时不具有明显提升性能的作用.

图5 DMA 与MMA、MMA&SGS 性能指标的均值和95%置信区间Fig.5 Mean and 95% confidence interval of performance indicators of DMA,MAA and MMA&SGS

4.2 与其他算法对比

鉴于鲜有与本文R|xijlv,ymac|Cmax,Eall,W问题一样的研究工作,这里从问题所属的可持续制造调度领域研究中选取了3 种较为常见的求解方法,并从应用角度做了针对性的变更.通过对比现有技术,以验证所提DMA 在求解本文问题上的有效性.对比算法的来源文献以及应用说明具体是:

1) V-NSGA-II: 来自Akbar 等[20]提出的求解考虑人员安排的调度研究,是一种基于经典NSGAII 的变种算法.为了将其应用于本文问题,采用第2.1 节中的编码和初始化,沿用了原文中的交叉和变异方式.

2) IABC: 来自Li 等[35]的研究工作,其在基本人工蜂群算法的基础上引入遗传算子,求解考虑3 种调度任务的多目标柔性作业车间调度问题,获得了良好的性能结果.在将其应用于本文问题时,同样采用第2.1 节中的编码和初始化,沿用了原文中的更新方式.

3) MA: 选自文献[24]中的研究成果,该模因算法是以变邻域搜索算法对局部范围展开搜索,用于求解考虑人员的柔性作业车间低碳调度问题.为了将该算法应用于本文问题,这里采用第2.1 节中的初始化以及第3.1 节中的全局搜索算子,沿用了文献[24]中的变邻域搜索算法.

DMA 的参数设置同第4.1.2 节,4 种算法的初始种群大小均为100,V-NSGA-II 的交叉和变异概率与DMA 相同,IABC 中的精英集合大小也与DMA保持一致.MA 中变邻域搜索算法的迭代次数设置为50.基于上述设置,表3 统计了各个算法求解不同场景下案例所得的平均性能值,加粗形式表示占优的结果.

表3 DMA 与V-NSGA-II、IABC、MA 的性能指标结果Table 3 Results for DMA,V-NSGA-II,IABC and MA

从表3 可以看出,无论是IGD还是Rnd,DMA在所有场景的求解结果都是占据优势的,这说明DMA 求解本文问题的性能优于其他3 种算法.与MA 相比,虽然两种算法都同时具备了全局优化和邻域搜索,但很明显DMA 中的更新方式是针对本文问题设计的.不仅如此,DMA 还融合了可持续目标导向的定向优化策略,因此求解性能更具优势.此外,MA 比IABC 和V-NSGA-II 表现更佳,这也验证了模因求解框架在本文问题上比单一的全局优化更为合适.值得说明的是,IABC 和V-NSGA-II的更新方式仍是以沿用原文为主,原文问题和本文问题上的较大差异会造成算法力有不逮,尤其是在大规模场景上体现的较为明显.

对于算法求解性能差异的显著性,图6 展示了ANOVA 方法对表3 数据的检验结果.可以看出,DMA 与对比算法的置信区间在IGD和Rnd上都不重合,这表明DMA 的求解性能是显著地优于其他算法.MA 与V-NSGA-II、IABC 也没有性能值上的重合,说明模因框架的优势也是较为显著的.此外,V-NSGA-II 和IABC 在两种性能指标上的检验结果都有明显的重合,这表明这两种算法在统计意义下具有相似的求解性能.

图6 DMA 与V-NSGA-II、IABC、MA 性能指标的均值和95%置信区间Fig.6 Mean and 95% confidence interval of performance indicators of DMA,V-NSGA-II,IABC and MA

为了进一步可视化上述比较算法的求解性能,图7 绘制了4 种算法求解大规模场景(40&10&6)所得的Pareto 前沿.图7(a)展示了含所有目标的总体情况,其余子图是含部分目标.在图7(b)和图7(c)中,可以清楚地看到3 种对比算法的解都被DMA的解所支配.在图7(d)中,虽然DMA 所得解有少部分不如MA,但仍明显优于IABC 和V-NSGAII 所得解.

图7 DMA 与V-NSGA-II、IABC、MA 获得的Pareto 前沿Fig.7 Pareto frontiers obtained by DMA,V-NSGA-II,IABC and MA

此外,从图7 也可以看出最大完工时间Cmax与总能耗Eall之间存在一定的负相关性.当某个调度方案的最大完工时间较大时,往往其总能耗会较低.其主要原因是: 为了降低加工能耗,在挑选工人时会尽量选取加工时间或者能耗低的.结果会出现机器等待工人的情况,造成大量的非加工时间,因此延长了相应的完工时间.关于总能耗Eall与工人负荷差异度W,两者之间存在明显的冲突关系.相比出于降低能耗而尽可能挑选低加工时间的策略,优化工人负荷差异度是以增大某些工件的加工时间为代价来降低工人负荷差异的.最大完工时间Cmax与工人负荷差异度W两者存在相对正相关关系.当某个调度方案的最大完工时间较高时,其相应的工人负荷差异度也较高.这里的原因也是由于降低工人负荷差异度时,往往会以增加加工时间为代价,由此机器完成工件的完工时间就会变大.

综上所述,本文设计的DMA 算法对于带多类型任务的不相关并行机三维可持续制造调度问题具有良好的寻优性能,其优势可归结为以下几点: 1) 设计的单步变邻域随机搜索策略适用于本文问题,有效地加强了对局部范围的寻优能力;2) 可持续目标导向策略针对问题优化需求并且作用于精英个体的构造,有效地提高了算法寻优效率;3) 相比领域文献中的V-NSGA-II、IABC 和MA 这3 种算法,DMA求解本文问题所得解的质量更高.

5 结束语

本文提出了一种双重局部优化策略增强的模因算法 (DMA) 求解带多类型任务的不相关并行机三维可持续制造调度问题.考虑多任务决策,设计了单步变邻域随机搜索策略 (1S-VNS),有效地更新任务分配以产生新解.进一步分析不同维度目标的优化需求与任务调度之间的关系,设计了可持续目标导向的优化策略 (SGS),并分步作用于精英个体,实现调度目标的定向优化.在实验过程中,验证了单步变邻域随机搜索策略的有效性,并且说明了可持续目标导向策略能够显著地提升算法的求解性能.最后,与文献中V-NSGA-II、IABC 和MA 这3 种算法对比,实验结果表明所提DMA 求得的非支配解集在多样性和收敛性上更具优势.

由于本文研究的问题是在静态环境下,实际生产中往往会存在不确定情况,下一步将着手研究考虑不确定性的可持续调度问题.当问题从确定转变为不确定后,模因算法的设计也将要求兼顾高效和适应性,以应对生产过程中的变化.另外,随着机器人在生产制造过程中的广泛应用,如何集成调度机器人和传统资源也是未来的另一个研究方向.

附录 A 可持续目标导向优化策略的说明案例

表A1 各个工件的基本加工数据Table A1 Basic machining data for each job