设备故障条件下柔性作业车间重调度方法

包 博，张 琳，张 搏

空军工程大学 防空反导学院，西安 710051

1 引言

在实际生产环境中，各类不确定因素，如：加工设备故障、紧急件加入、物料供应短缺等，会导致车间工况变化，使得原调度方案不再可行，进而需要重新制定调度方案以进行后续生产，即重调度[1-2]。设备故障是生产中最为普遍的一类不确定因素，针对车间调度中的设备随机故障问题，学者们提出了许多行之有效的动态调度方法[3-5]。文献[6]针对调度过程中的设备故障干扰，基于滚动时域优化框架，提出改进的事件和周期混合驱动的动态调度方法。文献[7]将多代理系统、遗传算法与滚动窗口法有机地结合，提出了一种车间动态调度方法。文献[8]分析车间生产环境复杂和生产过程中各种随机扰动，提出车间动态重调度优化方法。重调度方法在动态调度中显示了较好的效果，重调度方法、策略逐渐成为了车间调度问题中的研究重点。文献[9]针对机器故障条件下的混合流水车间重调度问题，提出了一种新的重调度模型。文献[10]在开放式车间中，针对机器持续不可用干扰，提出了三种特定的重调度策略。文献[11]提出了插入重调度和完全重调度策略，有效缩短了车间的加工时间。但相关研究主要存在两方面不足：首先，重调度必然导致调度成本的增加，已有方法往往忽视了重调度成本而仅侧重于调度效率。其次，已有重调度方法在运用多种重调度策略时，通常先选择重调度策略进而在此策略下制定重调度方案，而这种方式难以确保重调度策略所得方案能够适应该扰动景况。

针对设备随机故障条件下的柔性作业车间调度问题，本文系统分析重调度成本，综合运用部分右移重调度策略以及完全重调度策略，从而提出一种重调度方法。采用免疫遗传算法实现模型的求解计算，并结合算例验证方法的有效性。

2 问题描述

柔性作业车间调度，可简单描述为：若干工件Ji(i=1,2,…,n)在设备 Mj(j=1,2,…,m)上进行加工；Oik表示工件的第k(k=1,2,…,l)道工序；工件可选择加工设备 Mj开展工序Oik，表示为 pijk，Tijk表示 pijk对应的处理时间；工件严格依照工艺路线进行加工，每道工序可选择若干设备执行操作。在满足特定约束条件下，需将工件的全部工序合理安排至机器设备上，并使调度方案达到最优性能指标[12]。

结合上述分析，以最小化完工时间为目标，柔性作业车间调度问题可描述为数学模型：

其中，式（1）为目标函数，eik是工序Oik的结束时刻，开始时刻为sik；式（2）表示每道工序仅选择一台设备执行操作，xijk为0/1变量，为1时表示工序Oik选择了机器Mj执行操作；式（3）表示工序自身的时间约束关系；式（4）、（5）分别表示工件在工序上的时间约束和机器设备上各工序的时间约束，其中siu、eiu分别表示设备Mj上第u道工序的开始、结束时刻。

在实际的车间生产调度中，设备故障将使得生产无法按照原有的调度计划继续进行。设备故障的发生表现出随机性，其随机性可以从三个方面进行描述：故障发生设备的随机性；故障发生时刻的随机性；故障持续时间的随机性。

3 重调度方法

重调度是在扰动发生后，重新编制调度方案，对调度计划进行局部或全局调整。针对设备随机故障，重调度方法要求能够适应各种景况的设备故障干扰，在不同程度扰动下保证重调度效果。另外，在重调度过程中需要考虑调度成本的合理性。本文提出重调度方法，首先基于工件信息生成初始调度方案，当扰动发生，输入扰动信息并通过重调度生成新方案。重调度的关键步骤包括构建重调度成本函数、设计重调度策略等[13]。

3.1 重调度成本

在重调度方案中，工序的开始加工时间偏移、工序加工设备的调整和以及相同工序在不同设备上的操作时间不相同，造成的物料调动量增加以及存储时间变动等，使得重调度成本增加。本文基于工件与设备两个层面，从时间偏差的角度，建立重调度成本函数。

提出假设：假设预调度方案为Q，即正在执行的调度方案。扰动后经重调度生成的调度方案为Q′，此时并不表示为最终所选择的重调度方案。Q、Q′的任务完成时间分别表示为Z、Z′，工件工序Oik的开始时刻分别表示为 sik、s′ik，结束时刻分别表示为 eik、e′ik，工序Oik的工时分别为tik、t′ik，工序Oik选择的操作设备分别表示为 pijk、p′ijk。

（1）工序开始时间偏差成本

工序由于开始时间的提前或延后，导致物料准备时间产生变动，使得运输、储存成本增加，因此采用开始时间偏差成本对此类重调度成本进行描述。

工序Oik在新旧方案中的开始加工时间偏差为：

工件总的偏差成本表示为：

（2）工时偏差成本

工时的增加，导致人工作业时间、设备使用时间增加，因此采用工序工时偏差成本对此类重调度成本进行描述。

工时增加量为：

工时偏差成本表示为：

（3）设备变更成本

工件工序操作设备的变更，将增加人力劳动及调运成本，因此采用设备变更成本对此类重调度成本进行描述。

工序Oik变更，则表示为：

设备变更成本表示为：

综上，重调度成本函数表示为：

其中，ω1、ω2、ω3为3类重调度成本的权重系数，ω1+ω2+ω3=1。权重系数表示3个子成本所占重调度成本的比重，权重系数由专家采用“德尔菲法”确定，经过调查、征询意见、汇总综合、反馈、再调查这一反复过程。

重调度目标函数综合考虑任务完工时间增量、重调度成本两方面，表示为：

其中，有 μ1+μ2=1，μ1、μ2为两类指标的权重系数，同样采用“德尔菲法”进行确定。

3.2 重调度策略

重调度将部分重调度策略与完全重调度策略相结合，利用两者优势，以在不同扰动景况下，保证重调度方案的先进性。

3.2.1完全重调度

完全重调度是指对故障发生后的所有工件进行重新调度安排，它与静态调度的根本区别在于每个机器的开始加工时间不同。完全重调度可保证重调度方案的优化性，但会随之产生额外较大的重调度成本。

完全重调度的基本步骤为：

步骤1确定重调度工序集合。重调度工序集合包含未开始的所有工序，以及因为设备故障导致中断的工序。

步骤2确定每个机器的开始加工时间，机器的开始加工时间为故障发生后该机器的最早空闲时间。故障发生时，如果第 j台机器正好处于空闲，则该机器的开始加工时间为0；如果第 j台机器正在加工某道工序，且该工序的剩余加工时间为t，则该机器的开始加工时间为t。

步骤3基于优化算法，对重调度工序集合中的工序进行优化调度，形成重调度方案。

3.2.2部分右移重调度

部分右移重调度是指对受到设备故障直接或间接影响的工序执行调整。该策略只对受影响工序的开始时间进行推迟处理，不改变工序次序和工序对应的操作设备，避免了完全重调度带来的额外成本过度增大的问题，但同时存在工序开始时间移动量较大的问题。

部分右移重调度的基本步骤为：

步骤1确定故障设备位置，并预估故障修复时间。

步骤2基于“二元分支”机理，从受到直接干扰的工序开始，分析确定出预调度方案中直接或间接的受影响的工序集合。

步骤3逐步后移调整工序计划，直到满足各类时间约束条件，形成重调度方案。

部分右移重调度具体操作方法可参见文献[10]。

3.3 重调度流程

在整个调度过程中，预调度方案生成阶段以最小化完成时间作为目标，而在重调度方案生成阶段中，由于考虑了方案变动带来的调度成本增加，因而兼顾最小化完成时间和最小化重调度成本两方面目标。为保证重调度方案的质量，重调度同时采用部分右移重调度和完全重调度两种策略，在两者形成的方案中选择较优方案。重调度流程如图1所示。

图1 重调度方法流程

重调度策略的基本步骤：

步骤1以最小化任务完成时间作为目标函数1，如式（1），基于智能优化算法产生预调度方案。

步骤2依照预调度方案进行生产，当扰动发生，转至步骤3；否则，依照预调度方案继续生产。

步骤3人工输入扰动信息，包括故障位置、故障时刻、预计故障修复时间。

步骤4采用部分右移重调度形成方案A，并计算该方案对应目标函数2的函数值，重调度目标函数2如式（13）；同时，依据目标函数2，采用完全重调度策略，基于智能优化算法形成重调度方案B；比较重调度方案A、B的重调度目标函数值大小，选取两者中较优的方案作为重调度方案，更新预调度方案，转至步骤2。

4 免疫遗传算法

柔性作业车间调度问题是一类典型的NP难问题，学者们针对此类问题提出了许多求解算法，如禁忌搜索算法[14]、遗传算法[15]、蚁群算法[16]、粒子群算法[17]等。遗传算法在解决同类问题上显示出较好的适用性，但存在迭代后期由于个体多样性缺失从而易陷入局部最优的问题。为克服遗传算法在计算中的早熟收敛问题，提高算法的全局收索能力，本文将免疫系统与遗传算法相结合，形成免疫遗传算法，对问题进行求解计算。

基本流程如图2所示。

4.1 染色体编码

染色体同时对工件的工序加工顺序和机器设备两方面信息进行描述。本文采用双层编码结构对染色体进行编码，染色体前半部分描述装备的工序加工顺序，后半部分描述工序所对应的加工设备。设染色体如：

图2 算法流程

其中，xk(k=1,2,…,N)为工序的序号，yk(k=1,2,…,N)为工序所对应的加工设备。

染色体解码需依据工序可选设备信息以及工序工时信息。对于染色体[1，2，1，2，3，3，2，1，3，3，1，2]，不考虑具体工序工时，依据解码规则，解码过程如图3所示。

图3 染色体解码示意图

4.2 适应度函数

在预调度方案生成阶段，目标函数为最小化任务完成时间。而在重调度方案生成阶段中，目标函数综合任务完成时间偏差以及重调度成本。

预调度方案制定时，依据目标函数1，适应度函数分别表示为：

重调度方案制定时，依据目标函数2，适应度函数分别表示为：

由于在初预调度方案制定、重调度方案制定中均采用免疫遗传算法，区别仅在于适应度函数，因此在后续步骤操作设计中，适应度函数均用 fv表示。

4.3 亲和力、抗体浓度

抗体与抗原之间的亲和力用于表示抗体对抗原的识别程度，针对本文中车间调度问题，亲和力定义为：

相似度是指抗体与其他抗体的相似度。本文采用T0位连续方法计算抗体与抗体间的亲和力，首先确定一个亲和度判定阈值T0，当两个个体有超过T0位或者连续T0位的编码相同，则认为这两种个体“相似”，否则认为“不相似”。此处借鉴变形的T0位连续方法来计算抗体间的亲和度，即：

其中，ku,v为抗体u与抗体s中相同的位数，L为抗体长度。

抗体的浓度是指群体中相似抗体所占的比例，表示为：

期望繁殖概率由亲和力Av与抗体浓度Cv共同决定，表示为：

其中，α为0-1间常数。由上式可知，染色体适应度越好，期望繁殖概率越大；个体浓度越大，则期望繁殖概率越小。

4.4 选择、交叉、变异

选择操作采用轮盘赌的方法，依据概率选择出染色体，染色体被选择的概率为期望繁殖概率，如式（19）。

交叉操作可分为两步：对两个染色体在交叉点处进行基因互换；对交叉后的染色体进行局部调整，使得染色体满足约束条件。交叉操作如：对两个染色体进行交叉处理，假设交叉位置为3。在对交叉点处进行基因互换后，出现某些工件工序增加、或者减少的情况，对此，把工件工序多出的操作变为缺失操作，染色体后半部分不变，从而避免产生非法染色体：

变异操作首先在前半部分随机选择两个变异点，然后将前半部分工件工序码和后半部分机器设备码的对应位置上的基因进行互换。例如，对某染色体选择在位置2、3上进行交叉变异操作：

5 算例分析

假设某生产车间利用5组机器设备，对6个工件进行加工处理，每个工件均有5道工序。工件工序的可选操作设备以及对应的加工时间如表1所示（[可选设备序号]/[对应时间（天）]）。依据表中信息，制定调度方案。

表1 工序可选机器及对应时间

5.1 参数设置及生成预调度方案

采用MATLAB编码完成上述调度算法，设置种群数为40，遗传代数为50，交叉率为0.5，变异率为0.4，记忆库容量为10，阈值T0为0.9，期望繁殖概率中参数α为0.5。运行该算法，得到一套预调度方案，如图4甘特图所示，图中“a-b”表示装备a的第b道工序。

图4 预调度方案

从图中可以清晰地了解到各道工序对应的机器设备，以及开始、结束时间。在未发生扰动情况下，加工生产依照图中调度方案执行。

5.2 生成重调度方案

基于图4预调度方案，假设第20天机器2上出现故障，工序O33中断。专家预估故障修复时间为8天，现需要执行重调度得到重调度方案。

采取本文重调度方法，依据“德尔菲法”确定重调度成本函数中指标权重 (ω1,ω2,ω3)=(0.1,0.4,0.5)，重调度目标函数中指标权重(μ1,μ2)=(0.3,0.7)，其他参数设置如5.1节不变。得到重调度方案如图5，其中完全重调度的寻优结果曲线如图6。

图5 重调度方案

图6 重调度寻优收敛曲线

在故障发生时刻，未开始进行处理的工件工序参与了重调度。从图中结果可以看出，部分工序所选择操作的机器发生了变化，由此可以判断，在重调度中完全重调度所得到的调度结果优于部分右移重调度的调度结果，因而该方法自动选择了完全重调度策略所得到的重调度方案。

为了验证上述分析判断，即重调度中完全重调度所得到的调度结果优于部分右移重调度的调度结果，依据部分右移重调度策略的算法规则得到相应的重调度方案，并计算重调度目标函数值。重调度方案甘特图如图7所示。

图7 部分右移重调度方案

从图中可以看出，工件工序并未改变操作设备，在开始、结束时间上发生了不同程度的后移。对比图5可以发现，采用右移重调度，完工时间推迟了8天；而采用完全重调度，完工时间仅推迟了2天，因而在完成时间这一指标上完全重调度所得方案表现较好。通过计算，部分右移重调度相应的重调度目标函数值为5.47，大于完全重调度相应的重调度目标函数值。分析可知，虽然完全重调度所得方案在执行成本上表现较差，但综合两方面指标进行计算，完全重调度所得方案表现更优。

5.3 设备故障景况分析

故障不同发生时间、不同修复时长都将对重调度效果造成影响，为探究不同扰动景况下重调度方法中两种策略的表现，通过对比实验对两种策略进行比较分析。

设置4组故障发生时间（5，15，25，35（天）），4组故障修复时间（2，4，6，8（天））。在16种景况下，分别采用完全重调度策略和部分右移重调度策略进行重调度实验，分别计算出重调度目标函数值。16种景况均随机重复10次，并计算平均值。

从图8结果中可以看出，在晚期、微小扰动下，部分右移重调度策略往往得到更好的重调度结果，而在早期、扰动较大情况下，完全重调度通常能得到较好重调度结果。作为本文方法中的两种策略，综合使用两种方法，弥补了单一方法的弊端，能够实现不同扰动情境下，尽可能保证重调度方案的先进性。

图8 两种策略重调度结果

6 结束语

本文针对设备随机故障条件下的柔性作业车间调度问题进行了研究，提出了一种基于组合策略的重调度方法。在重调度方法中，对重调度成本进行了详细分析并建立重调度成本函数，综合运用了两种重调度策略，结合免疫算法对遗传算法进行了改进，用于模型的求解计算。通过算例分析，验证了方法的可行性和有效性。结果表明，不同扰动景况下各种策略表现存在差异，本文所提出方法能够更好适应多种景况。在后续研究中，需要进一步挖掘设备故障的重调度策略，横向上对其他不确定事件的重调度方法进行研究。