能耗和噪声约束下的柔性车间调度决策优化

张斯琪，倪 静，郭起轩

1(上海理工大学 管理学院，上海 200093)2(上海理工大学 机械学院，上海 200093)

1 引 言

随着工业化进程的飞速发展，能源危机不容小觑.我国有将近三分之二的能源用于制造业的生产和加工[1]，短缺的能源对资源可持续发展造成严重威胁，降低制造业能源消耗和噪声污染的需求日益明显.

制造业的核心生产单位是车间，柔性作业车间调度(Flexible Job-Shop scheduling problem,FJSP)对每个工件的工序排序和工序的机器选择同时提出了可优化的要求，很大程度上增加了调度的灵活性和计算的复杂度.在现有研究中，已有学者利用杂草算法、人工蜂群算法和化学反应算法[2-4]等智能优化算法求解FJSP问题.而对于FJSP问题的讨论大多集中在完工时间和机器负荷上，随着社会对低碳生产的大力倡导，节能低碳的调度优化开始成为学者关注的热点.Uhan[5]采用整数规划公式，用于限制峰值功耗的流水车间调度.蒋增强[6]等人考虑了设备—能耗曲线，采用基于血缘变异的非支配排序遗传算法求解低碳策略下的FJSP问题.Luo[7]等考虑了分时电价的优化算法用于流水车间调度.LIU[8]等以总延迟时间、峰值负载和碳排放为目标研究流水车间调度优化.刘琼[9]考虑了工序之间的搬运时间对调度产生的影响，通过改进果蝇算法优化车间布局和调度方案从而降低能耗.

综上所述，现有文献在考虑低碳问题时主要分析加工能耗和峰值载荷，尚未考虑到噪声对生产的影响，而且大多文献以简单的系统作为研究对象，本文将同时优化最大完工时间、能耗和噪声三个目标.随着新型智能优化算法的发展，我们需要探寻更多有效的求解途径去缓解制造企业生产带来的环境压力.鲸鱼算法(WOA)是Mirjalilis等人[10]于2016年最新提出的智能优化算法，并开始逐步应用于故障诊断[11]，水库优化[12]等领域，本文将鲸鱼优化算法应用于多目标FJSP低碳优化问题，并结合小生境技术构建外部文档存储多目标Pareto非劣解，最后根据评价系数权重确定决策方案，通过一系列的仿真实验表明，改进后的算法有效的提高了搜索性能和收敛精度，同时有利于决策者从中获得偏好的结果.

2 柔性作业车间调度问题

2.1 问题描述

FJSP问题可以描述为：n个工件在m台机器上加工，每个工件包含ni道工序，每道工序可选择所有加工机器中的一台或多台设备.FJSP的调度目标就是为每个工件的每道工序安排最合适的机器，明确每台可用机器上的每道工序的最佳加工顺序和开始加工时间，使得给定的目标最优.

FJSP应满足如下假设：

1)同一时刻一道工序只能选择一台加工设备加工；

2)同一时刻同一台可用设备只能加工一道工序；

3)不同工件之间的加工优先级相同；

4)同一工件的不同工序之间加工路线确定；

5)工序的加工过程是不间断的；

6)所有工件的初始加工时刻假设为零，所有加工设备的开始作业时间也假设为零.

2.2 模型建立

本文将最大完工时间、能耗和噪声三个函数共同构建FJSP多目标优化模型.其中，n为工件数量，m为机器数量，ni为工件i包含的工序数，Oij为第i个工件的第j道工序，L为一个足够大的正数，Ci为第i个工件的完工时间，Pk为机器k切割能耗，sij为Oij的开始加工时间，cij为Oij的结束加工时间，pijk为Oij在机器k上的加工时间，l为A级等效声音在曝光时间所产生的瞬时值，Tk为噪音的曝光时间，nijk为Oij在机器k上加工的噪声值.xijk表示如果Oij在机器k上加工，则xijk=1，否则xijk为0；yijhlk表示如果Oij先于Ohl在机器k上加工，则yijhlk=1，否则为0.

1)最大完工时间最小函数.所有工件加工完成后最大的那个时间就是最大完工时间.

(1)

2)总能耗最小函数.本文主要考虑了工件在加工过程中的切割能耗，即机器切割作业时所产生的能耗.

(2)

3)噪声最小函数.工件的加工过程所产生的噪声主要有两部分：结构噪声和切割噪声.其中，机器的结构噪声是机体结构受激励振动以及振动传递所产生的噪声，结构噪声主要来源于机架，通常是通过测量空转机的噪声来评估；切割噪声则是由于工件切割过程的动态力量所产生的噪声.已有研究所得，如果在同一加工车间内每道工序采用相同的工艺参数，那么整个加工系统中切削所消耗的能量，动态切削力和切削噪声可视为近似相等，因此本文对噪声的研究聚焦在结构噪声上.

噪声的可划分为ACZ三个等级，而A声级是反映人主观感觉的基本评价量.通常意义上，一段循环时间内的平均噪声所产生的能量等于给定一个时段内发生波动变化的每个声音等级A中的能量，所以在被选择的等效时段中用连续且稳定的A级声压来表示噪音强度.A级声压通常用l来表示，可由公式(3)表示为：

(3)

本文的研究对象中，由于加工车间的每台机床都是以恒定的主轴转速进行作业的，因此在每个循环周期内所辐射出的噪声值也都是稳定的，将连续型噪声公式(3)可离散化成如下公式：

(4)

现将噪声发射理论和评估模式公式用于车间调度的实际情况中，构建出模型公式(5)：

(5)

基于以上分析，本文对完工时间、能耗和噪声可建立多目标优化模型如公式(6)：

minF=(FC,FE,FN)

(6)

s.t:

sij+xijk×pijk≤cij,1≤i≤n,1≤j≤ni,1≤k≤m

(7)

cij≤si(j+1),1≤i≤n,1≤j≤ni-1

(8)

sij+pijk≤shl+L(1-yijhlk),1≤i,h≤n,1≤j,
l≤ni,1≤k≤m

(9)

cij≤si(j+1)+L(1-yijh(l+1)k),1≤i≤n,1≤j≤ni,
1≤h≤n,1≤l≤ni-1

(10)

(11)

sij≥0,cij≥0

(12)

公式(7)和公式(8)表示工序的顺序约束，公式(9)和公式(10)表示同一时刻同一台可用设备只能加工一道工序，公式(11)表示同一时刻一道工序只能选择一台加工设备加工，公式(12)表示各个参数变量非负.

3 基本鲸鱼算法

鲸鱼算法(WOA)模仿座头鲸的捕食过程，每一头座头鲸代表所求可行域中的一个可行解.WOA的觅食过程可分为三个环节：包围猎物，气泡攻击和随机搜寻.

3.1 猎物包围过程

假设此时被捕食猎物的位置为最优候选解的位置，其他鲸鱼都根据目标猎物的位置来更新自己的位置，具体的数学模型如下：

(13)

(14)

(15)

(16)

a=2-2t/Tmax

(17)

3.2 气泡攻击过程

鲸鱼在袭击猎物的时候，首先会吐出气泡将猎物包围在气泡中，然后根据概率p实现螺旋上升(同3.1)和缩小包围圈同时进行的方式靠近食物.Mirjalili将概率p设为0.5[10]，即两种方式各有二分之一的概率会被选择.

(18)

(19)

其中，b定义对数螺旋形状的常数，l∈[-1,1]表示随机向量.

3.3 随机搜寻过程

(20)

(21)

4 混合鲸鱼优化算法

4.1 编码规则

已知FJSP有两个子问题构成，分别是基于工序的排序和基于机器的排序，如表1所示，其中，表中的数字表示该工序在此机器上的加工时间，“—”表示该工序不能在此机器上加工.由于鲸鱼算法一般用在连续优化问题上，柔性作业车间调度属于离散型的组合优化问题，需要通过合适的方式将鲸鱼算法离散化用来求解调度车间问题.

表1 3×5 FJSP实例
Table 1 3×5 FJSP instances

工件工序可以选择的加工机器M1M2M3M4M5J1O1124362O12—3—24J2O215—7—4O22—23——O2337—5—J3O31119—9—O32—6358

4.1.1 工序编码

本文在对工序设计编码规则时采用了文献[13]中的随机键编码规则混合转化序列方式.本文选取表1数据为例，表1是包含3个工件和7道工序的作业，一组个体的编码总长度为2l，即编码长度为14，初始的工序序列l为[1 1 2 2 2 3 3]，并对各个元素在[-2,2]内任意取值，按照一定的顺序存储为λi=[λi,1,λi,2,λi,3,…，λi,n]，然后按照数字由大到小的顺序编号得到序列ωi=[ωi,1,ωi,2,ωi,3，…,ωi,n]，利用公式θi,ωi,k=k得到转化序列θi=[θi,1,θi,2,…,θi,n]，将工序的初始排序序列经过转化序列转化后得到新的编码排序，具体的转换过程如表2.

表2 工序编码方案
Table 2 Process coding scheme

初始序列1122233k1234567随机数λi-1.50.91.3-0.61.11.7-1.2wi7425316θi6352471新序列13212213新序列22321321

4.1.2 机器编码

在完成工序的排序之后，下一步就开始为工序选择合适的机器.借鉴文献[14]的转换方法，这一部分需要将λi∈[-σ,σ]对应到相应的m(j)∈[1,s(j)]上去.首先通过线性变换将λi求解为属于[1,s(j)]的实数，然后通过round函数将其转为最接近此实数的整数值，具体见公式(22).

(22)

其中，round函数表示将数字四舍五入至最接近的整数，整数s(j)表示的是元素j对应工序所能选择的加工设备数，整数m(j)表示的是每道工序在可选择的加工设备集合中所选择第几台设备的编码，而不是对应的机器号.以表1中的数据为例，一个机器编码为[1 2 3 1 1 2 4]，可以解释为第一整数位数字1，代表工件1的第一道工序O11选择它所能使用的机器设备集合中的第一台设备M1，第二个整数位上的数字2，代表工件1的第二道工序O12选择它所能使用的机器设备集合中的第二台设备M4，依次类推，可得到加工设备排序[M1,M4,M5,M2,M1,M2,M5]，见图1.

图1 编码示意图Fig.1 Coding diagram

4.2 基于反向学习策略初始化种群

种群初始解对算法的全局搜索起到至关重要的作用，种群的多样性程度影响算法的搜索性能.据文献[15]研究，反向解有50%的可能性比当前解更靠近最优解，目前反向学习方式也被成功用于WOA算法[16]，因此本文采用反向学习法对种群进行初始化处理.

(23)

4.3 非线性调整收敛因子

a=amax-(amax-amin)ln(1+t(e-1)/Tmax)

(24)

通过非线性改变a的值，实现算法在迭代早期a的值较大，偏向于全局搜索；迭代后期a的值较小，偏向于局部搜索的目的.

4.4 二次插值算子变异

为了增加解的多样性，本文对进化后的个体按照一定的比例进行二次插值算子变异.

通过拟合函数寻找未知点数据的方式叫做插值，以三个点做插值可以得到二次插值，其本质是寻找三个点之间构成的二次超曲面的极小点.具体过程如下：

Step1.设置个体插值比例P*；

Step2.在每一次迭代完成后，分别对每个个体按照概率P*进行判断是否需要插值；

Step3.若需要插值处理，则选择当前个体a，全局最优解b，和一个随机个体c三点进行二次插值，按照公式(25)寻找D维空间内的二次超曲面的极小点R=(R1,R2,…,RD)，其中

(25)

Step4.判断原个体是否被插值得到的结果所支配，若当前解支配原个体则用其替换掉原个体，反之舍弃.

二次超曲面的极小点很大概率上是优于a，b，c三点的，通过引入二次插值算子一方面可以寻找更优的个体，另一方面可以通过变异增进种群的多样性.

4.5 小生境策略混合鲸鱼算法

基本的WOA在算法后期种群可能向着局部最优个体进行位置更新，难以保证找到全局最优解.为了改善WOA的收敛性能，本文引入了基于小生境生物行为的策略[17].首先利用鲸鱼优化算法来更新种群中的鲸鱼位置，产生新的解集，在以Pareto支配关系的准则下，选择非劣解存储到外部文档；再根据一定的淘汰机制，不断更新外部文档的数据；最后在多个非劣解中选择决策者最满意的解.

Step1.创建小生境种群.每一次鲸鱼算法的迭代都会产生一组非劣解，在算法运行的过程中，把产生的非劣解用一个外部文档来进行存储.设定外部文档的范围Q以及小生境的数量W，根据解的分布范围确定m维目标空间的体积，再将体积分块，类比为球体的体积反推r，由此可以计算出每个小生境种群的半径r.随机选择一个个体i作为中心，以r为半径，根据式(26)判断其他个体与该个体之间的欧式距离Dij.通过Dij与r的距离判断该个体是否在小生境中群内，并且选择不在该小生境种群中的另一个体作为中心确定新种群，直到生成小生境种群数量到达W.

(26)

Step2.计算个体间密度和拥挤度.对于每个存储在外部文档的个体，需要有一定的标准判断其优劣.这里引入个体之间的密度和拥挤距离的概念.所谓密度，就是每个小生境内的所拥有个体的排列的紧密程度.个体密度越低，陷入局部解的几率就越小.所谓拥挤距离，就是每个非劣解个体与和它最接近的Pareto间的欧式距离.拥挤距离越近，算法的收敛性就越好.个体密度和拥挤距离分别用公式(27)和公式(28)表示.

(27)

(28)

Step3.制定淘汰机制.为了避免外部文档解的数量过于膨胀，需要按照一定的规则设置淘汰概率，本文根据密度和拥挤距离对外部文档中的每个个体如公式(29)计算淘汰的概率，淘汰概率值最小的会被保留下来作为下一次WOA更新种群的最优个体.如果在下次迭代时有更优解，则将外部文档中淘汰概率较大的解删除掉，将新解添加至外部文档.

(29)

4.6 基于评价准则确定最优解

整个迭代算法完成之后，在外部文档中会存有规定规模的Pareto最优解，对于多目标问题来说，各个目标之间是相互制约的关系，由于决策者对目标的关注度不同，可能导致他们对解的不同维度会有各自的衡量.本文采用评价准则帮助决策者在自己需求的基础上合理选择最优解.首先通过公式(30)计算出每个解在不同目标函数下所占的比例，然后根据决策者对生产的需求(高速、节能、降噪)定义的评价系数加权求和，评价准则如公式(31)所示：

(30)

f=αfC+βfE+χfN

(31)

α+β+χ=1

(32)

Fmin,Fmax是当前目标下对应函数的最大值和最小值，f值最大的解对应的是当前评价系数下最合理的解，α,β,χ分别是高速评价系数，节能评价系数和降噪评价系数.

4.7 算法流程

Step1.设置算法参数，种群数量N，最大迭代次数、编码的上下限以及位置矩阵.

Step2.根据公式(23)采用反向学习策略初始化种群.

Step3.根据改进WOA对每个个体进行位置的更新，并选择非劣解存储至外部档案.

Step4.如果全部鲸鱼个体完成迭代，则基于Pareto支配关系选择出新种群更新外部文档，基于小生境技术计算各个个体的密度、拥挤度以及淘汰概率，淘汰概率最小的个体作为最优个体，根据外部文档规模将淘汰概率较大的个体删除；否则继续Step 3.

Step5.判断迭代是否达到最大迭代次数，如果是则输出外部文档保存的最优解集，否则回到Step 3.

Step6.根据4.6的描述选择外部文档中的Pareto综合最优解，确定最符合决策者目标的结果.

图2 算法求解流程图Fig.2 Algorithm flow chart

算法的具体流程可如图2所示.

5 试验仿真与分析

5.1 测试函数

本文将改进后的混合小生境鲸鱼算法简写为SWOA，为了验证其求解性能，本文选择两个单峰函数Sphere和Schwefel 2.21用来测试算法收敛的速度，以及两个多峰函数Griewank和Zakharov用来测试全局搜索性能，将改进后的鲸鱼算法(SWOA)与粒子群算法(PSO)、遗传算法(GA)和基本鲸鱼算法(WOA)作对比，在维度n=10下分别对每个函数测试10组数据，选取平均精度 Ave、标准差 Std和寻优成功率 SR 作为求解结果的评价指标，寻优成功率表示算法求解结果收敛到最优解的比例，表3给出几种常见算法的基本参数设置，为了保证实验的公平性，不同算法的种群规模和最大迭代次数均设置为相同.

表3 算法参数设置
Table 3 Algorithm parameter settings

算 法 参数值设置各个算法的相同部分种群规模N=50,最大迭代次数MaxGen=200,维度n=10PSO学习因子c1=c2=2,惯性权重w=0.6GA交叉概率pc=0.9,变异概率pm=0.1WOAa由2到0线性减小,b=1SWOAa由2到0非线性减小,b=1,P∗=0.5

图3 四种算法运行不同函数下的收敛图Fig.3 Convergence graphs of four algorithmsrunning different functions

表4给出了不同算法运行测试函数后的数值，图3分别为不同函数下的收敛曲线对比图.改进的鲸鱼算法SWOA在四组独立实验中均一致收敛到全局最优解，尤其是求解函数f1，f3，f4时，SWOA算法表现出较大优势，能收敛到理论最优值0，而对于f2，该算法求得的最优结果也非常接近于0，并且能够达到函数给定的收敛精度.从图3中可以明显地看出，相比于WOA，PSO和GA，SWOA在求解的快速性和准确性性能上都比较优秀，PSO和GA在运算中未能找到最优结果，WOA 在运算函数f2和f4时陷入了局部最优解，但改进后的算法很容易便突破了局部最优解，在其他函数上也比普通的鲸鱼算法更快找到最优解位置.f1和f3可以看出SWOA和WOA相比明显提升了收敛速度，迭代到第30次左右便找到最优解，虽然WOA也取得很好的收敛效果，但是仍不及 SWOA 的收敛性能明显，结果表明改进后的算法无论是收敛速度还是收敛精度，都起到一定的改善效果.

表4 测试函数的求解结果对比
Table 4 Comparison of solution results of test functions

函数名称PSOAVESTDSRGAAVESTDSRWOAAVESTDSRSWOAAVESTDSRSpheref1(n=10)0.0001860.00031050.1486134.058601.20E-883.77E-8810000100Schwefel2.21f2(n=10)0.0794840.08018902.7337270.75982501.4124541.94521404.93E-1081.28E-107100Griewankf3(n=10)73.7958715.3996403.6985021.79171500.0888080.1497486000100Zakharovf4(n=10)0.0027630.0067940119.146155.5752024.2154523.14148000100

5.2 测试数据

为了验证改进算法求解FJSP问题的有效性，现选取具有代表性的柔性作业车间调度问题进行分析，与两种经典的算法：文献[18]中的多目标遗传算法(Multi-Objective Genetic Algorithm，MOGA)和常用的求解多目标问题的非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm，NSGA-II)以及基本鲸鱼算法(WOA)进行比较，同时以最大完工时间C(min)，车间调度总能耗E(kwh)，车间噪声辐射N(dB)作为优化目标求解，根据文献[18]中的4×5，10×6，20×5三组实例进行分析验证，本文采用MatlabR2016a实现算法编程，实验环境为操作系统window10，处理器为Intel(R)Core(TM)i5-4210M.

表5将SWOA、MOGA、NSGA-II和WOA分别运行十次同样的数据集进行对比测试，计算每组结果的最优值Best和平均值Avg.参考文献[17]的参数定义，本文将算法参数设置为：种群规模为N=60，外部文档规模Q=20，迭代次数MaxGen=200，小生境种群W=4，并且设置完工时间的评价系数α最高，在α=0.6，β=0.2，χ=0.2时得到的结果如表5所示，本文列出SWOA求解10×6实例问题的甘特图见图4，每个方格代表加工时长，括号中第一个数字代表加工工件序号，第二个数字代表该工件所选择的设备，其对应Pareto解的分布见图5，并得到以时间、能耗和噪声为评价导向的各个目标下的迭代收敛曲线见图6.

表5 测试结果对比
Table 5 Comparison of test results

从表5的实验结果可知，根据三组实验案例的测试结果，混合小生境的鲸鱼算法在给定的评价权重系数下均能找到较为满意的解，且在解的质量上有较大的提高.SWOA在处理4×5问题上，相较于其他三种算法，最优解相差不大，但是得到的三个目标的平均值均小于NSGA-II和WOA.在处理多工件问题上，SWOA对于完工时间的优化效果明显，表现出较大优势.在10×6问题上，SWOA取得的三个目标的平均值结果均优于MOGA和NSGA-II，有两个目标结果优于WOA.在20×5问题上，当SWOA和WOA获得相同的加工时间64时，SWOA的能耗值和噪声值都要低于 WOA的求解结果，说明SWOA能够有效求解多目标FJSP问题.根据图5可知，Pareto可行解的分布性比较分散且均匀，能够有效跳出局部收敛状态，说明小生境种群能够引领鲸鱼算法跳出局部最优，扩大搜索的范围，有效更新外部文档中个体的最优个体，保证种群的多样性.根据图4的甘特图和图6各个目标的解的变化和种群均值的变化可知，在近60次迭代过程中就能够陷入收敛状态，说明了种群的收敛速度较快.

图4 10×6实例对应的工序图 Fig.4 Process diagram corresponding to 10×6 instances

图5 10×6实例对应的Pareto解的分布Fig.5 Distribution of Pareto solution corresponding to 10×6

5.3 实例数据

为了验证选取的评价系数因子能够有效影响FJSP的多个目标往预期方向优化的可行性，现选取某汽车公司冷却系统的生产线[18]作为调度目标进行求解，对该冷却系统数据分析，得到10×6的FJSP，表6为根据实际生产任务的简化模型.算法中的各项参数与5.2的参数设置相同，只改变评价系数权重.

图6 10×6实例在各个目标上的收敛性图Fig.6 Convergence graph of 10×6 instances on each target

表6 工序在各机器上的加工时间、功率和噪声值Table 6 Processing time,power and noise values of each process on each machine

表7计算了在不同评价系数的影响下，小生境鲸鱼算法所计算得到的完工时间、能耗和噪声的Pareto最优解求解结果，图7为高速、节能、降噪的评价系数α，β，χ分别为[0.4,0.4,0.2],[0.4,0.2,0.4],[0.2,0.4,0.4]时的求解结果甘特图.从表7的数据结果可以观察到，最终的解的优化程度与评价系数的分配有着密切的关系，某项目标的评价权重所占比例越高，该评价权重所对应的目标优化结果会越为理想，比如当完工时间在价值系数α为0时，最终完工时间可高达121min，在价值系数α为1时，运行结果则在28到30min的范围内，能耗和噪声也可得到同样的规律.图7甘特图数据也表明，某项目标的评价系数为0.2时，求解的结果会劣于评价系数为0.4时的值，由此可以证明不同的偏好可以得到不同的目标值和不同的调度方案，评价系数越大，得到相应的目标值越小，在进行调度问题的选择时可以通过评价系数来得到决策者偏好的结果，有利于决策者均衡生产效率、能源消耗和噪声污染三者的协调关系，从而帮助决策者对车间调度的个性化生产起到指导作用，执行调度方案时在保证完工时间满足交货期的前提下尽量的减少能源和噪声的消耗.

6 结束语

本文采用混合小生境技术的鲸鱼优化算法对建立的三个目标的FJSP模型进行求解，通过与其他文献中的结果进行对比分析，验证了改进后的鲸鱼算法在求解多目标FJSP问题时的可行性和有效性.仿真结果表明，该策略有效发挥了两种算法的优势，提高了基本鲸鱼算法的求解性能和收敛精度，有效解决了多目标FJSP问题.另外也通过对具体实例的运算，说明可以通过改变评价系数来得到决策者偏好的结果.

表7 SWOA在不同价值系数求解结果的对比
Table 7 Comparison of SWOA results in different value coefficients

在实际生产过程中，工件的加工存在各种不确定的干扰因素，WOA算法仍有很多可改进之处，未来可以进一步研究WOA的最优性能，求解在复杂情况下FJSP动态重调度问题.