基于遗传退火算法的质检扰动应对方法

葛 艳，王爱民，叶介然

(北京理工大学 机械与车辆学院，北京 100081)

1 问题的提出

车间调度是在有限的设备资源上安排工件进行加工，车间调度问题在最近几十年已经成为工程领域的研究热点。作业车间调度问题(Job-shop Scheduling Problem, JSP)被证明是非确定性多项式(Non-deterministic Polynomial, NP)难问题[1]。针对JSP，VAN LAARHOVEN等[2]以最小化Cmax为目标，提出一种基于模拟退火的近似算法；GONÇALVES等[3]利用混合遗传算法对JSP进行了优化。更多研究致力于解决与实际生产更接近的柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)，该问题是比JSP更为复杂的NP难问题[4]，BRCUKER等[5]率先提出求解包括两个工件的FJSP多项式算法。随着全局优化算法的出现和普及，更多研究采用元启发式算法求解FJSP。LEE等[6]以最小化Cmax为目标，设计了一种改进遗传算法，实现了FJSP的优化求解；SAIDI-MEHRABAD等[7]针对具有工序准备时间的FJSP，提出一种基于禁忌搜索的层次逼近算法，并证明该算法在大规模问题和实际加工问题求解中表现突出；LI等[8]提出一种基于混合Pareto前沿的离散人工蜂群算法，实现了对多目标FJSP的求解。

在JSP和FJSP中，对于任意一道工序，只要其工艺路线约束下的前一道工序加工完成，且该工序的可加工设备存在空闲，便可开始加工。然而，随着企业对精益生产的贯彻执行，在生产过程中经常穿插质检环节，使得相邻工序之间不能直接衔接。根据生产实际，产品的质检结果一般分为合格、返修、报废3种。若工件的某一道工序质检结果为合格，则该工件可直接安排进入下一道工序；若工件的某一道工序质检结果为返修，则该工件需要重新安排当前加工工序，直至质检合格或报废，如图1所示；若某一道工序的质检结果为报废，则该工件不能进行后续工序加工，已经加工完成的工序也会作废，在原问题规模涉及的n个工件中应相应增加一个新的与报废工件相同的工件，重新从第一道工序开始安排，如图1所示。

传统调度问题不涉及工件质检，其排产方法更不涉及如何应对质检结果出现返修的情况；而对于质检出现工件报废的情况，通常根据预先估计的工件废品率，在工件加工开始就增加工件的排产数量，从而增加排产方案对报废件的容忍度。这种排产方式没有考虑加工过程中由质检返修带来的单道工序重入和由质检报废带来的工件重新投产的情况，使作业计划与生产实际脱节，无法持续指导实际生产。

因此，作业计划需要根据质检结果实时调整，确保调度方案对生产实际的持续指导，即动态调度[9]。另外，由于在实际生产中，车间会根据已生成的静态作业计划形成物料准备方案，调整作业计划可能导致已生成的物料准备方案不可行。为减少物料准备方案的频繁变更，本文动态调度所形成的排产方案不仅需要如传统FJSP一样保证工件最大完工时间(Cmax)最小化，还应保证排产计划与初始计划的差距最小化。

HOLLOWAY等[10]率先对作业车间动态调度问题进行研究，通过周期性地进行排产计算不断生成新的调度方案，并证明了这种周期策略对求解动态调度问题的有效性；HOLTHAUS[11]针对设备故障引发的工序加工时间延迟问题，提出一种基于仿真的调度规则分析方法；FANG等[12]将调度规则融入遗传算法，求解具有工序准备时间、工件交货期约束和设备故障的作业车间动态调度问题；XIONG等[13]以最小化Cmax和最小化排产方案的鲁棒性为目标，提出一种多目标进化算法，实现了具有随机设备故障的FJSP动态调度。

LIU等[14]针对具有模糊处理时间的柔性作业车间动态调度问题(Dynamic Flexible Job-shop Scheduling Problem, DFJSP)，提出一种快速分布估计算法(fast Distribution Estimation Algorithm, fDEA)，实现了快速寻优；SHEN等[15]提出一种多目标进化算法，解决了DFJSP，并通过实例验证了该算法具有较好的整体性能；WANG等[16]采用改进遗传算法求解了具有设备故障、紧急插单和工件损坏的DFJSP；ZHOU等[17]针对多目标DFJSP，提出一种基于协同进化机制的非支配遗传算法，并验证了该算法的有效性和竞争力。以上文献解决了DFJSP，但是均未考虑动态调度之后的方案对初始方案的继承性，新方案一味追求优化调度目标，而与初始方案相去甚远，使原来的物料准备计划变得不可行。

综上所述，本文针对工序质检结果造成的原作业计划不具备持续生产指导依据的现状，以及保持新旧排产计划一致性的需求，以最小化Cmax和最小化新旧计划方案差异性为目标，研究具有质检环节的DFJSP。针对问题特点和两个目标，本文结合遗传算法的全局搜索能力和模拟退火算法的局部寻优能力，提出一种基于局面评价的遗传退火算法。该算法通过基于局面评价的解码规则，提高每一个个体在新旧排产计划一致性方面的性能；同时，通过遗传退火算法的快速寻优机制，重点优化最小化Cmax的调度目标。

2 问题描述与数学建模

2.1 问题描述及内涵分析

本文研究的具有质检环节的FJSP是传统FJSP的扩展。传统FJSP涉及n个待加工工件Ji(i=1,2,…,n)和m台设备Mp(p=1,2,…,m)；每个工件Ji包含一系列具有严格顺序的加工工序，每一道工序都可由一台或多台设备加工；当某一道工序完成加工后，后续工序即可开始加工。

与传统FJSP不同的是，在本文研究的动态调度问题中，工序分为质检工序和普通工序。对于质检工序，其加工完成后不能如普通工序一样直接转向下一道工序，而须进行质检，只有当质检结果为合格时，才能开始工件的下一道工序，否则需要重新在当前工序加工(质检结果为返修)，或从第一道工序开始重新加工当前工件(质检结果为报废)。

由于无法事先预测每一道质检工序的质检结果，制定初始作业计划时只能假设所有质检工序的质检结果均为合格。在工件加工过程中，一旦出现某一道工序的质检结果为返修或报废，就意味着当前工件甚至其余工件均无法根据原作业计划继续生产，需要根据当前计划和当前工件的完成情况重新制定生产计划。本文研究的具有质检环节的DFJSP特征如下：

(1)问题同样涉及n个工件Ji(i=1,2,…，n)和m台设备Mp(p=1,2,…,m)，每个工件Ji包含一系列有严格顺序的加工工序，每一道工序都可由一台或多台设备加工。

(2)有一个初始计划，初始计划中规定了每一道工序的原加工设备、原加工开始时间和原加工结束时间。

(3)有扰动节点，即质检结果为不合格或返修的工序的原加工结束时间。

(4)原计划中，在扰动节点前开始的工序已经开始加工或已经完成加工，无需参与重排，动态调度仅重新安排原计划中在扰动节点后开始的工序。

(5)在进行动态调度时，所有设备的可用时间由原先FJSP中的0时刻变为当前问题中的扰动节点。

(6)问题的调度目标为最小化Cmax的同时最小化新旧方案的差异，以减少对根据原方案所制定的物料准备方案的变更。

根据以上描述，具有质检环节的DFJSP的求解难点在于：

(1)新旧方案差异程度的量化 新旧方案的差异主要体现在所有工序的加工设备差异和加工开始时间差异两方面，如何建立合适的评价机制，量化两个方案的相似程度，是一大难点。

(2)调度目标之间的平衡 问题涉及的两个调度目标在一定程度上存在冲突，即获得最低Cmax的调度方案与其旧方案的差异未必最小；同样，与原排产计划最接近的方案未必能获得最低的Cmax。如何获得能够综合优化两个目标的方案是亟待解决的问题。

为了更好更严谨地解决该问题，提出以下假设：

(1)同一工序在不同设备上加工所需的处理时间相同。

(2)属于不同工件的工序之间没有顺序约束。

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

(4)任意一道工序在加工时不能被打断，直到该工序加工结束。

(5)不考虑设备故障的情况。

(6)不考虑工序周转的时间。

2.2 数学建模

(1)参数

Ji表示工件i,i=1,2,…,n,n为工件的数量；

Mp表示设备p,p=1,2,…,m,m为设备的数量；

Oij表示Ji的第j道工序,j=1,2,…,Gi,Gi为Ji的工序数量；

Tij为工序Oij的加工工时；

OSij为原计划中工序Oij的加工开始时刻；

OEij为原计划中工序Oij的加工结束时刻；

RT为扰动节点；

L为一个足够大的常数；

α为工序加工设备变动影响系数，是一个常数；

β为工序加工开始时间变动影响系数，是一个常数。

(2)决策变量

STij为新计划中工序Oij的加工开始时间；

ETij为新计划中工序Oij的加工结束时间；

Cmax为新计划中所有工序的最大完工时间；

基于以上假设和符号，建立如下数学模型：

minCmax；

(1)

(2)

Cmax=max(ETij),∀i。

(3)

s.t.

STij+Tij=ETij,∀i,j；

(4)

OSij+Tij=OEij,∀i,j；

(5)

(6)

RT=max(Rij·OEij),∀i,j；

(7)

ifOSij

(8)

ifOSij

(9)

(10)

Xijp-Uijp≥0,∀i,j,p；

(11)

Xijp-Vijp≥0,∀i,j,p；

(12)

(13)

(14)

STi(j+1)≥ETij,∀i,j；

(15)

OSi(j+1)≥OEij,∀i,j;

(16)

STij+(1-Bi′j′p-ijp)·L≥STi′j′+Ti′j′,

∀i,i′∈(1,2,…,n),j,j′∈(1,2,…,Gi),

p∈(1,2,…,m)；

(17)

OSij+(1-Ci′j′p-ijp)·L≥OSi′j′+Ti′j′,

∀i,i′∈(1,2,…,n),j,j′∈(1,2,…,Gi),

p∈(1,2,…,m)。

(18)

其中：式(3)为工序最大完工时间的具体计算方法；式(4)和式(5)为新旧方案中工序的加工开始时间、加工结束时间和加工时长之间的数值关系；式(6)表示每次重新排产时，扰动工序只有一个；式(7)为扰动节点的计算方法，即扰动工序在原方案中的加工结束时间；式(8)和式(9)表示若工序在原方案中的加工开始时间在扰动节点之前，则新方案中工序的加工时间和加工设备保持不变；式(10)～式(14)为设备约束，表示无论在新方案还是原方案中，任意一道工序的加工设备仅有一台，且属于其可选加工设备集合；式(15)和式(16)为工件加工的工艺路线约束，即任意一道工序都需要在其工艺路线约束下的前一道工序完工后才能开始加工；式(17)和式(18)保证每一台设备在同一时刻最多只能加工一道工序。

3 基于局面评价的遗传退火算法

本文提出的基于局面评价的模拟退火算法是传统模拟退火算法与遗传算法的结合。模拟退火算法来源于固体退火原理，算法迭代从某一较高初温出发，随温度参数的不断下降，结合概率突跳特性在解空间随机寻找目标函数的全局最优解，即能以一定概率跳出局部最优解并达到全局最优解，然而这种概率突跳是以牺牲算法运行时间为代价[18]。如果初始温度设置得不够高或者降温太快，则容易陷入局部最优；如果为了跳出局部最优，将初始温度设置得足够高，降温足够慢，则会增加算法时间。

为了利用模拟退火算法优秀的局部寻优能力，同时避免其在寻找全局最优解过程中耗费大量时间，从而在有限计算时间内找到全局最优解的近似解，本文将遗传算法的种群和变异思想引入模拟退火算法，提出遗传退火算法。该算法首先通过遗传算法产生一系列初始解，作为模拟退火算法的输入；然后根据初始解，采用模拟退火算法快速迭代生成一个局部最优解；在当前陷入局部最优种群的基础上，再执行遗传算法的变异操作，使种群重新分布于解空间，继续寻找下一个局部最优解。通过“获得局部最优解1→变异→获得局部最优解2→……→获得局部最优解k”的过程，从多个局部最优解中产生全局近优解。该算法没有刻意避免算法陷入局部最优，反而利用模拟退火算法本身容易陷入局部最优的特点，甚至通过调节模拟退火算法的降温速度来促进算法更加快速地达到局部最优，然后从多个局部最优解中选择最好解。图2所示为本文所提遗传退火算法的流程。

3.1 初始化种群

本节采用基于工序的编码方式生成表示工序顺序的染色体。染色体中的每个基因表示对应工件的编号，相同的基因表示属于同一工件的不同工序。图3所示为一个包括3个工件的染色体编码，其表示所有工序的安排顺序为O31→O11→O21→O32→O12→O22→O33→O13。

3.2 基于局面评价的解码策略

解码是从染色体生成排产方案的过程。针对本文研究的具有质检工序的DFJSP，当某一工序的质检结果为不合格时，扰动节点之前已经开始的工序保持其原调度计划中的加工时间和加工设备不变，对扰动节点之后开始的工序进行重调度。为响应问题的调度目标，在安排每一道工序的加工时间和加工设备时，应考虑本次安排对最小化新计划的Cmax和最小化新旧计划差异程度的影响。

由于编码只能反映工序的安排顺序，并不能规定工序的设备选择和时间安排。对于任意一条编码，每个基因所代表的工序可能是已安排工序，也可能是未安排工序，对于未安排工序，需要重新为其安排设备和加工时间，如图4所示。

因为每一道工序的设备选择不唯一，所以每一道工序的安排都有很多种方案。为了避免产生劣质解，本文建立一种局面评估机制来评估每一道工序在当前状态下的不同安排方案，从中选择当前该工序最好的设备和加工时间安排。基于局面评价的解码策略流程如图5a所示。

以一个包括4个工件、5台设备的DFJSP为例(基础数据如表1)，介绍局面评价策略在某一道具体工序上的应用。

根据图5a，首先获得扰动工序O41和扰动节点4，在该节点前开始的工序(O31，O21，O11，O22)保持原计划的设备和加工时间安排，其余工序进行重调度。在重新安排工序O41时有5台可选设备，因此生成5个备选方案。

根据式(19)分别计算各个备选方案的评价值

Pijp=(STij-OSij)2/(Uijp+Vijp)。

(19)

式中：Pijp为工序Oij选择设备Mp为加工设备时，当前备选方案的评价值；分子表示新旧方案中工序Oij的加工开始时间差异，分母表示新旧方案中工序Oij的加工设备差异。可以看出，新旧方案中工序Oij的加工时间和加工设备差异越大，Pijp的值越小。

根据式(19)，图5b所示各备选方案的评价值分别为16，64，16，8，36，因此选择评价值最小的备选方案4作为工序O41的安排方案。

表1 柔性作业车间工序加工时间表

按照上述方法，执行图5a中的步骤，可完成对当前染色体的解码。

3.3 适应度函数

本文研究的存在质检工序的DFJSP有两个目标函数：①最小化工件的最大完工时间；②最小化重调度方案与原计划之间的差异。由于解码操作中已经对新旧方案的差异进行了控制，此处仅以Cmax的值作为个体的适应度值。

3.4 基于模拟退火算法的局部寻优

局部寻优即利用模拟退火算法，对遗传算法产生的初始解和大规模变异后的解进行迭代搜索，得到局部最优解的过程。传统的模拟退火算法为了避免陷入局部最优，要求初始温度T足够大，降温足够慢，往往需要耗费大量的时间。而本文提出的遗传退火算法不刻意避免算法陷入早熟，反而利用模拟退火算法容易陷入早熟的特点，快速产生局部最优解。图6所示为基于模拟退火算法的局部最优解的产生流程。

根据图6，利用模拟退火算法进行局部寻优的步骤如下：

(1)初始化模拟退火算法的温度T和温度的单位变化量ΔT。

(2)以染色体中基因置换的方式获得每一个个体的邻域，如图7所示。

(3)计算每一个邻域个体i′的适应度f(i′)，并获得该适应度值与原个体i的适应度值f(i)的增量ΔEi=f(i′)-f(i)。

(4)对于某一个体i，若适应度值的增量满足ΔEi<0，则个体i的邻域个体i′获得的Cmax值较小，解的质量更优，将个体i更新为个体i′。

(5)对于某一个体i，若适应度值的增量满足ΔEi≥0，则根据式(20)计算个体i′的接受度，式中T为当前温度值，k为算法当前的迭代次数。

(20)

(6)生成一个(0,1)范围内的随机数rand，若ri>rand，则将个体i更新为个体i′，否则保留个体i。

(7)根据ΔT的值更新当前温度T，并判断算法是否达到终止条件。若是，则结束算法，输出多个局部最优解；否则，进行下一次迭代，转步骤(2)。

3.5 跳出局部最优——大规模变异策略

变异是改变染色体中的某些基因、生成新的染色体的过程。当模拟退火算法结束时，由于其卓越的局部搜索能力，算法得到的解大多集中在局部最优解附近，为使算法跳出局部最优，需要对这些解进行大规模变异，以增强种群多样性，改善算法的全局搜索能力。变异算子的设计如图8所示。

4 实例验证与算法比较

为了验证基于局面评价的设备选择规则对缩小解空间、减小重调度前后排产方案差异性的贡献，以及遗传退火算法对提高算法收敛性的贡献，本文以文献[19]的案例MK1～MK3为例，在每一个案例中设置若干质检工序，利用所提算法和文献中的其他3种算法对每道质检工序返修和报废两种扰动进行响应，探索扰动节点对算法求解结果的影响。

表2所示为案例的详细信息，表中N和M分别为工件数量和设备数量，Tnop和Qnop分别为案例的总工序数量和质检工序数量，meq为每一道工序的可选加工设备数，proc为每一道工序加工工时的取值范围，ICmax为初始方案的最大完工时间。

表2 案例详细信息

本章采用Visual C#语言编程实现参与对比的4种算法，在处理器为i7-7500U CPU、主频为2.7 GHz、内存为24 GB的个人计算机上运行，求解上述3个案例。在求解案例时，每种算法连续运行20次，取最好结果，4种算法的详细信息和运行结果分别如表3和表4所示。算法运行时，A1和A3采用直线降温策略共降温10次，每个温度下迭代60次，种群规模为6，大规模变异次数设置为10，最大迭代600次；A2和A4的种群数量为60，迭代次数为600。

表3 4种算法的详细信息

表4 案例运行结果

续表4

注：dt为扰动工序在初始调度方案中的结束时间；dn为按照式(2)计算的新旧方案的差异；α和β分别设置为1/Tnop和1/ICmax。

根据表4中的运行结果，分别从横向和纵向两个维度对算法进行Cmax、新旧方案差异程度、运行时间、迭代性能4个方面的比较和分析。其中，纵向分析主要探索算法运行结果随dt变化的趋势，横向对比主要比较4种算法的优劣。

(1)案例规模对Cmax的影响分析

如图9所示，应对返修扰动时，对于小规模案例，重调度方案的Cmax与初始方案差异较小，基本与dt无关；对于大规模案例MK3，Cmax随dt的增大呈下降趋势。原因是，在小规模案例中，返修扰动造成的受影响工序较少，无论dt为多少，最好的情况下，重调度方案仅需要比初始方案多安排一道工序(当前扰动工序)，因此Cmax的差异较小；在大规模案例中，dt越小，返修扰动造成的受影响工序越多，在初始方案足够完备的情况下，需要重排的工序越多，Cmax值增大得越明显。

应对报废扰动时，重调度方案需要重新安排包括当前扰动工序在内的所属工件之前的所有工序，一般dt越大，需要重新安排的工序越多，Cmax增大得越多。因此，图9中3种算法形成的重调度方案的Cmax随dt的增大呈上升趋势，这种趋势在小规模案例MK1和MK2的表现更为明显。

(2)算法对Cmax的影响分析

在应对返修扰动和报废扰动时，A1和A3获得的Cmax大致相同，均低于A2，而且这种差距随dt的增大逐渐减小。原因是，A1和A3采用本文所提遗传退火算法进行寻优，A2采用的是传统遗传算法，传统遗传算法易早熟，从而陷入局部最优。本文所提遗传退火算法在迭代过程中包括定期跳出局部最优的大规模变异操作，相当于从多个局部最优解中选出一个最终解，因此具有较好的全局搜索性能。然而，随着dt的增大，案例中需要重新安排的工序逐渐减少，解空间随之减小，甚至减小到1(例如原初始方案中的最后一道工序发生返修扰动)，这种情况下寻优算法的优势不能体现，出现图9中后期3条线重合的现象。

与其他3种算法相比，A4获得的Cmax没有明显的优势或劣势，原因是非支配遗传算法虽然具有多目标优化能力，但是多个目标之间地位平等、不分主次，难以应对本文要求的在最小化Cmax的前提下保证新旧方案差异程度的特殊性。

(3)案例规模和扰动类型对新旧方案差异程度的影响分析

如图10所示，应对返修扰动和报废扰动时，3种算法形成的重调度方案与初始方案的差异程度均随dt的增大而下降。原因是，随着dt的增大，应对扰动时需要重新排产的工序逐渐减少，新方案对初始方案的继承逐渐增多。

(4)算法对新旧方案差异程度的影响分析

当应对返修扰动和报废扰动时，A1和A2产生的新方案与初始方案的差异程度相近，均优于A3，而且随着dt的增大，3种算法的差距逐渐减小。原因是，A1和A2采用本文所提基于局面评价的解码策略，可以在安排工序时综合比较该工序的各种安排方案与初始计划的差异，通过局面评价策略选择差异较小的方案，从而减小整个计划与初始计划的差异；A3基于最早开始规则的解码策略不能在解码即进行这种考虑。同样，随着dt的不断增大，解空间不断减小，该解码策略的优势也会减弱。与(2)所述一样，与其他3种算法相比，A4获得的dn值没有明显的优势或劣势。

(5)不同算法运行时间对比分析

当应对返修扰动和报废扰动时，A1，A3，A4的运行时间接近，均明显小于A2，说明本文所提遗传退火算法较传统遗传算法具有较好的时间性能。

最后，为验证本文所提遗传退火算法的全局搜索性能，以案例MK3中dt=29时应对返修扰动的情况为例，比较4种算法的收敛性能。图11所示为4种算法的收敛曲线，其中横坐标表示算法的迭代次数，纵坐标为算法在对应迭代次数下获得的Cmax值。

由图11可见，A1和A3的迭代曲线中均有多个突变点，这些突变点即为发生大规模变异的时刻。多次大规模变异将算法的全局寻优过程分为多个局部寻优阶段，使算法从多个局部最优解中选出最终解。而A2在算法迭代的初始阶段便陷入早熟，这与前文的分析一致，这种早熟在一定程度上抑制了算法的全局寻优进程。经过改进，A4的寻优速度和深度均优于A2，但仍然易陷入早熟。

5 结束语

本文研究具有质检环节的DFJSP，该问题的部分工序加工完成后不能立刻开始下一道工序，而须经历质检环节。质检环节的结果有合格、返修和报废3种情况，一旦某道工序的质检结果为返修或报废，该工序甚至对应工件必须重新加工，因此需要重新生成排产方案。

根据分析问题约束和特点，本文以最小化工件的最大完工时间和最小化新旧方案差异为目标，建立了一个混合整数规划模型，描述了返修扰动和报废扰动的处理方式，然后提出一种基于局面评价的遗传退火算法求解问题。该算法将遗传算法的编码方式、变异算子和退火算法的逐温度寻优过程高效结合，以提高算法在有限运行时间内的全局搜索性能。在实例验证部分，本文选取Brandimarte[19]的案例MK1～MK3，在每一个案例中添加若干道质检工序，分别采用该算法与另外3种算法求解各工序对扰动的响应，验证扰动节点、案例规模和所用算法对案例求解结果的影响。实例验证表明，基于局面评价的遗传退火算法具有较好的全局搜索性能，可以有效解决本文涉及的带有质检环节的DFJSP，并能在一定程度上保证重调度方案与初始方案一致。