基于贝叶斯决策的柔性作业车间扰动处理方法研究

吴正佳 朱颖颖，2 龚 稳 吴县洋

(1.三峡大学 水电机械设备设计与维护湖北省重点实验室， 湖北 宜昌443002；2.三峡大学 机械与动力学院，湖北 宜昌 443002)

近年来，许多学者针对不同扰动因子(机器扰动、订单扰动、原材料短缺等)的机加工车间生产调度问题做了大量研究工作.比如，刘明周[1]等提出在重调度优化集内按规则选取待加工工件，采用主动和被动触发式重调度驱动规则响应各种扰动.朱传军[2]等针对动态事件特点，采用工件到达发生器和机器故障预维护发生器模拟动态事件.刘乐[3]针对开放式车间中的急件到达干扰，基于匹配式调度策略探索扰后实施重调度的具体方法.有文献[4-5]针对机器故障这一类动态调度问题，提出插入空闲时间、工件右移调度和变路径调度方法来提高调度方案的稳定性和鲁棒性.也有文献[6-7]考虑生产过程中订单不确定、加工时间不确定等因素，建立鲁棒调度模型并求解.但由于实际生产过程的复杂性，扰动因子的多样性和不确定性，上述方法对扰动的处理缺乏灵活性和针对性，能处理的扰动事件单一，研究成果很难符合生产实际.实现对各类扰动的有效处理，探究扰动实质和扰动下生产调度重回稳健状态的机制成为车间作业调度问题研究的瓶颈.

贝叶斯网络为解决这类问题提供了思路.本文首先构建了生产和扰动要素的贝叶斯网络模型，利用贝叶斯网络的决策机制来分析和处理各类扰动事件，实现生产调度系统由扰动恢复到稳定的过程，最后用仿真实验验证了该方法能有效应对各类不确定扰动事件，减弱和吸收扰动事件的扰动程度，进而减少重调度次数.

1 贝叶斯网络概述

贝叶斯网络(bayesian networks，BN)是用来表示变量间概率分布的图解化模型，它与规则库、神经网络或决策树等知识表示形式相比，具有直观的模型和推理，局部及分布式的学习机制，适用于表达和分析不确定性和概率性事物的优点[8].

贝叶斯网络是一个有向无环图(directed acyclic graph，DAG)，它由代表变量的节点及连接这些节点的有向边构成.其中节点代表论域中的变量，每一个节点X i都有一个条件概率P(X i|parents(X i))表示父节点对该节点的影响程度.对于连续变量，用一个条件概率分布(conditional probability distribution，CPD)来表示，对于离散变量，则用条件概率表(conditional probability table，CPT)以表格的形式表示.如果存在从节点X到节点Y的有向边，则节点X是节点Y的一个父节点，表示X对Y有直接影响.贝叶斯网络提供了对域的完整描述，域中所有变量节点的条件概率都可通过贝叶斯网络的信息计算出来.即

其中X i是第i个随机变量，x i是X i的特定取值，parents(X i)是X i的父节点，表示X i的一个特定取值.式(1)表明每一个节点的条件概率都可表示为贝叶斯网络条件概率表中适当元素的乘积.在贝叶斯网络中，一个节点与其父节点和子节点以外的节点是条件独立的，表达了变量间的条件独立性.

构建一个完整的网络一般分为3步：确定变量集，确定网络结构，确定各变量的条件概率.现以一个简单的贝叶斯网络具体说明构建方法和正向推理过程.

1)确定变量集.如图1中有4个变量s，c，b，d，分别表示吸烟、肺癌、支气管炎和呼吸困难.

2)确定网络结构.即确定变量间的有向边的连接，可根据变量间的条件独立性或根据变量间的因果关系来确定有向边的存在性和方向.图中吸烟会造成肺癌、支气管炎和呼吸困难，而吸烟先造成肺癌和支气管炎，然后造成呼吸困难，因此吸烟和呼吸困难两个变量不存在条件独立性.最终形成的网络结构如图1所示.

3)确定各变量的条件概率.可根据实验数据或者专家知识来确定.如图1，变量取1或0表示事件为真或假，P(s=1)=0.5表示吸烟概率为0.5.P(d=1|c=1，b=0)=0.9表示患肺癌而没有支气管炎的情况下，呼吸困难的概率为0.9，其他概率表示类似上述推理.

图1 简单贝叶斯网络图

由于各变量间具有条件独立性，上图中各节点的概率可表示为：

2 不确定扰动下调度车间的贝叶斯网络

2.1 调度车间的贝叶斯网络构建思想

生产系统在进行工序的加工时，来自于系统内部和外部因素的扰动，往往会破坏生产调度系统中调度资源的平衡关系.具体地说，当扰动事件对某一个工序或多个工序的加工产生影响时，受影响的工序继而对后续工序的加工也有可能带来干扰.如果能用一种网络去描述扰动情形下工序的这种相互影响关系，并用定量的数值去评估工序受扰动影响的大小，进而推导出生产系统受扰动影响的大小，这种扰动评估方法的实现有利于生产调度人员针对不确定扰动发生情况，进行有效的调度决策.

贝叶斯网络的拓扑网络结构具有描述各变量相互影响关系的特征，将这种网络结构表示生产加工过程中受扰动影响的工序的相互关系，根据工序受扰动影响的概率大小推理出系统受扰动影响的概率大小，能辅助选择一种较优的调度方法，实现对不确定扰动事件对系统影响程度的有效判断，解决了生产决策者面对复杂影响关系难以决策的难题.

根据生产调度车间机器加工工序的特点，用贝叶斯网络结构表示生产调度中受扰工序的相互关系时，受扰工序集为贝叶斯网络的节点集合，连接节点的有向边表示同一工件相邻工序或者不同工序在同一机器上加工的相互影响关系，节点的条件概率可用该工序在机器上加工时受扰动影响的概率来表示，简称受扰程度，贝叶斯网络表示车间工序的一一对应关系，见表1.

表1 调度车间的贝叶斯网络对应关系

2.2 不确定扰动下调度车间的贝叶斯网络构建过程

构建受扰工序的贝叶斯网络时，受扰工序用O ij表示，代表着工件i的第j道工序，有向边为受扰工序间的机器约束和工序约束，节点中O ij=1表示工序O ij受到扰动的影响，O ij=0表示工序O ij没有受扰动的影响.如图2所示，p(O12=1)=0.3表示O12工序受扰动影响的程度为0.3，p(O13=1|O12=1)=0.49表示工序O23受扰动影响的情况下，工序O13受扰动影响的程度为0.49，p(S=1|O23=1，O13=0)=0.6表示在工序O23受扰动影响，而工序O13没有受扰扰动影响的情况下，生产系统受扰动影响的程度为0.6.工序O12与O13工序之间的有向边代表工序约束，工序O12与O23工序之间的有向边代表机器约束，工序O12与工序O23之间具有条件独立性.

图2 受扰工序的贝叶斯网络结构

用贝叶斯的拓扑网络结构就可以计算出系统受扰动程度的大小，有

当生产系统发生扰动，首先找到直接受扰动影响的工序，然后分析当该工序采取部分重调度策略时，对后续工序产生的影响大小，如此类推，就能将受扰动影响的全部工序的关系用贝叶斯网络呈现出来.以8×8的FJSP调度问题为例，其初始调度甘特图如图3所示，设定一个随机扰动t=2时刻，工序O31延迟一个单位完工，表2用图解方式来说明柔性作业车间的贝叶斯网络构建过程.

图3 8×8的柔性作业车间甘特图

表2 基于贝叶斯网络的柔性作业车间扰动分析

确定了扰动下受扰工序的贝叶斯网络后，计算出各工序的受扰程度值，就可以利用网络结构推理出生产系统受扰动影响的程度P(S=1).当生产过程中出现两个及两个以上的扰动，同样可以用上述方法建立受扰工序的贝叶斯网络结构，对生产系统的受扰程度进行分析.

3 不确定扰动的评估

从工序的角度去分析，扰动事件对生产系统稳定性产生的影响主要表现为加工任务的扰动和成本的扰动.比如工序开工时间的偏差，机器负荷变化量.

1)开工时间偏差量R1

式中，C i表示扰动发生前工序的开工时间，C'i表示扰动发生后工序的预计开工时间，i=1，2，…，M.

2)机器负荷的变化量R2

式中，L i为未发生扰动时机器m i的负荷数，L'i为扰动发生后受扰工序在该加工机器上加工机器的实际加工负荷数.

上述两种指标给工序带来的影响程度各不相同，比如开工时间的提前或推迟影响后续工序的加工，而机器负荷量的变化仅影响机器的开工或停工，两指标给生产系统造成的不稳定性不同.因此在计算时，赋予各指标的权重分别为w1，w2，(w1≠w2且w1+w2=1)，得到工序的总的影响值W为

在不同的扰动事件的影响下，得到的W也会发生变化，且在一个大的扰动事件发生的样本中，可以认为W是一个连续性的变化值，所以两者可以建立一种函数映射关系：f：W→U，即当输入一个大于0的W值，对应地输出一个位于[0，1]区间的工序受扰程度值.且W与工序受扰程度呈正比关系，W越大，对应的工序受扰程度值也越大.W=0时，相应的工序的受扰程度值也为0，可以用一个过零点的二次函数表达式y=AW2+BW(y∈[0，1])来描述这种一一对应关系，结合生产实际状况来确定A，B、d的具体数值.当受扰工序的受扰程度接近1时，认为工序产生的局部扰动过大，直接采取重调度策略.

设定A=-1/9，B=2/3，w1=0.6，w2=0.4，用上述扰动评估方法，计算表2所述的各受扰工序的受扰程度值如图4所示.用公式(1)得到系统的受扰程度P(S=1).

图4 受扰工序的贝叶斯网络

4 不确定扰动下柔性作业车间重调度方法

在上述网络模型中，当有不确定扰动发生时，需根据具体的扰动情况选择重调度策略.部分重调度保护初始调度方案不受破坏的性能较好，但扰动较大时，生产系统的稳定性会遭到破坏；完全重调度固然能得到较好的调度效果，但执行成本较高.

在实际生产过程中，扰动事件的不同，生产系统受扰动影响的程度也有所差异.扰动发生时，是进行调度的局部调整以维持生产的稳定还是该扰动给生产带来较大的波动进而进行重调度，扰动事件对生产系统产生的扰动程度大小无法提前预知.根据企业经验规则，本文设定一个重调度阈值θ，通过比较系统的受扰程度值P(S=1)与重调度阈值θ的大小决定最终的重调度策略.

当生产过程中出现扰动时，对受扰工序进行局部调整，同时构建受扰工序的贝叶斯网络对系统受扰程度进行推理，计算出系统受扰动影响程度值P(S=1)：

1)当P(S=1)＜θ时，说明扰动对生产系统的影响较小，维持原有的调度方案，只对受扰工序进行局部调整；

2)当P(S=1)≥θ时，说明扰动对生产过程产生严重的干扰，需进行完全重调度.

这种将不确定扰动的评估值与重调度阈值相比较的方法，建立一种自适应的重调度策略，不论扰动事件扰动程度的大或小，都能实现对其进行灵活地处理.重调度策略用流程图如图5所示.

图5 重调度流程图

基于贝叶斯网络模型的柔性作业车间的扰动处理过程并不是孤立存在的，它表示受扰工序的相互影响关系，得到系统的受扰程度值，与扰动阈值进行比较，确定最终的扰动处理方案.图6用输入层、处理层和输出层的3层结构流程图来表示柔性作业车间的动态调度过程.输入层包含生产加工信息、初始调度方案、扰动事件的类型以及扰动发生的结果，这些输入信息有助于对扰动信息进行管理，为后续的扰动处理过程做好准备工作.处理层主要用贝叶斯网络实现对扰动的评估，工序按照初始调度方案加工过程中受扰动事件的干扰，通过各工序受扰动影响的大小推理得到系统受扰动影响程度值.如果得到的系统扰动评估值小于设定的阈值，执行局部修正方案；否则对未加工完工件进行全重排.将这种调度策略信息传递给输出层，生产调度人员根据输出的指令执行局部修正方案或者进行完全重调度，完成后续工序的生产.此过程可用图6来表示.

图6 车间扰动事件处理全过程

5 仿真验证

在工件按原方案加工的情形下，本文将设定3种扰动事件的详细信息，运用上述提到的基于贝叶斯网络模型的扰动处理方法对扰动进行处理.图7为5个工件在6台机器上加工的原调度方案.

图7 原调度方案(扰动前)

扰动情形1：在t=6时刻，工序O51的完工时间由6变为7；

扰动情形2：在t=10时刻，机器4故障，故障持续时间为5；

扰动情形3：在t=20时刻，有紧急订单插入，订单的加工信息见表3.

表3 紧急订单加工信息表

3种扰动事件按时间先后顺序分别进入输入层，记录扰动信息的种类、扰动时刻和持续时间等信息后，将此信息传递给扰动处理层，每种扰动处理完后将信息传递给输出层，最终的调度方案如图8所示，红色部分是对原方案的改动.

图8 最终调度方案(扰动后)

在扰动处理层中，针对扰动情形1，在t=6时刻，工序O51在M1上的加工时间由4变为5，扰动发生时刻，还有1/5的任务等待完成.通过贝叶斯网络模型图进行分析，如果继续在M1上加工，工序的受扰程度为1/6，如果转移到其他机器上加工，扰动程度如图7所示，所以最终选择在M5上加工，受扰程度为1/10.

针对扰动情形2，在t=10时刻，M4故障，会影响工序O41的加工.通过贝叶斯网络进行分析，工序的加工可在机器维修后使用，也可以将工序转移到其他机器上进行加工，如图9所示.工序O41最终选择在M1上加工，受扰程度为0.

图9 扰动后柔性作业车间调度的贝叶斯网络模型图

针对扰动情形3，在t=20时刻，有紧急订单插入.通过贝叶斯网络分析可知，订单的3道工序分别在M4，M5，M4上加工，如图8所示，对原方案无扰动产生.

表4分析了不同扰动事件下，常见处理结果与本文处理结果的对比，从对比结果中可以看出，本文提出的方法能应对各类不确定扰动事件，与常见处理方法相比，基于贝叶斯网路的车间扰动处理方法能有效减弱扰动程度，甚至能吸收扰动事件带来的扰动，减少重调度次数.

表4 扰动处理方法对比

6 结 论

1)针对调度车间中各类不确定扰动对生产带来的困扰，借鉴贝叶斯网络表达不确定性事件的特点，揭示了扰动事件的扰动实质，提出了基于贝叶斯网络的车间扰动处理方法，对扰动情形下的工序进行调度资源的评估和选择，有效应对各类不确定扰动事件.

2)实验结果表明，该方法优于常见的扰动处理方法，能有效减弱或吸收扰动事件对调度系统的影响，减少重调度次数，指导生产实践.