基于贝叶斯理论的工作流任务分配模型的设计

王 宁，李 炜，沈奇威

(1.北京邮电大学网络与交换技术国家重点实验室，北京 100876;2.东信北邮信息技术有限公司，北京 100191)

0 引言

工作流是指全部或部分由计算机支持或自动处理的业务过程。工作流管理系统是一个详细定义、管理、并按照定义执行工作流的软件的集合［1］。

工作流任务分配策略是工作流管理系统的关键技术之一，是实现其过程自动化处理的必要手段［2］。工作流任务分配策略是描述在流程的运行过程中，将任务在合适的时机分配给合适的人，以减少任务的处理时间，增加系统的吞吐量。目前对人工型任务分配的研究比较全面，但这些任务分配策略都基于这样的前提:任务需要人来完成。当前，针对为合适的人分配合适任务的课题进行了较多研究［3－5］，对那些初始需要人处理，在运行过程中是否仍需要人处理的任务尚未见相关研究。据此，本研究尝试采用一种新的策略，利用在运行中积累的历史数据，减少尽可能多的流程，提高整个系统的性能。

任务的分配是先对任务和人分类，然后把合适的任务分配给合适的人。在任务历史数据的积累下，对任务的分类，目前可以采用的方法有:统计方法、决策树、神经网络等。决策树大多是以不完备信息或主观概率作为决策依据，并且对调查结果的可能性没有一个量化的评价;神经网络虽然可靠性较高，但网络结构设计的不确定性、复杂性以及模型本身缺乏较好的可解释性和理解性，造成使用上存在困难，并且神经网络构建往往过分依赖于技巧［6－8］。贝叶斯决策能对信息的价值或是否需要采集新的信息做出科学判断，对调查结果的可能性加以量化评价，能把先验知识和调查结果结合起来，在决策过程中根据具体情况不断地使用，使决策逐步完善和科学，并且属性对应现实中的语义，具有较好的可解释性［9－10］。所以，本文主要利用贝叶斯网络对任务的相关属性建模，在历史数据的支持下，对任务进行分类，并依此为依据为任务分配合适的资源，优化业务流程，减少任务处理时间，提高系统效率。

1 移动广告任务分配分析

移动广告(mobile advertising，MA)是由移动通信网及移动业务承载，具有移动通信网络的业务特征，用户能够随时随地接受广告信息。出于对系统安全性、商业逻辑合法性以及内容传播广泛性的考虑，移动广告管理平台需要对相关的信息进行审核。工作流主要应用在MA的所有审批流程中。

工作流的任务分配主要应用在移动广告中的对象的审批过程中。以广告订单为例，订单任务的审批主要分为3类:地市级操作员审批、省级操作员审批、自动审批。订单任务的分配主要考虑以下2个方面。

1 )订单的创建者:创建者的属性主要集中在3个方面:角色R，所属地区D，级别L。这些属性决定订单任务的审批流程，具体流程如表1所示。

表1 常规任务分配Tab.1 General task assignment

根据表1所示规则可得

(1)式中:R表示角色;L表示级别;S={s1，s2，s3}表示3种不同的任务分配结果;F(R，L)是(R，L)→S的映射。

2 )订单的属性:订单的重要性是判断审批任务分配的重要依据，越重要的订单，越需要人的参与，越需要按照规则分配。订单的重要性主要体现在3个方面:订单的金额x1，订单的持续时间x2，订单的类型x3。订单的优惠条件涉及到人为因素，需要人来监督这个权利的使用，并且还涉及到不同代理商的公平竞争问题。订单的优惠条件主要考虑2个方面:折扣率x4，配送比例x5。订单的付费形式x6和订单的创建者x7也是影响订单越级处理的重要因素。从安全角度考虑预付费安全度高于后付费，而订单的创建者体现了个人信用度，因此实际操作过程中，创建者提交的订单审批通过的概率越高，其提交的新订单审批通过的概率越高。

常规任务分配策略体现了固有业务流程。在实际应用中，某些订单审批具有极高的审批通过率，这意味着订单在审批的业务流程中可直接审批通过流转给下一级人员操作。显而易见，订单审批的必要性和订单的属性息息相关，因此可以利用贝叶斯分类模型，通过对订单任务的相关属性进行建模分析，对订单审批的必要性进行合理分类，并在此分类的基础上对订单任务进行分配。

2 构建贝叶斯任务分配模型

(3)式中 xk表示 xi=(x1，x2，…，x7)中第 k个属性变量。本文中我们基于朴素贝叶斯网络进行建模分析，即假定订单任务的各属性在已经类的条件下相互独立，则(3)式可简化为

对于一个给定的订单任务，(4)式中的α为一个定值，因此只需求(4)式中其他部分的值，选取使(4)式取值最大的审批趋势，作为订单任务分配考虑的因素。

2.1 基于贝叶斯网络的任务分配模型

根据上节的分析，基于贝叶斯网络的任务分配可按照下列步骤进行。

1 )输入训练样本，初始化为统一的格式，定义类变量和属性变量。

2 )判断:如果是分类任务，则转向4)，否则(训练任务)转向3)。

3 )参数学习。扫描所有训练样本:

①计算所有属性的先验概率，对离散属性和连续属性分别按照(5)式和(6)式计算;

②计算P(C=ci)，即类变量取值为ci时的先验概率;③生成贝叶斯概率表，即所需的贝叶斯分类器。4)根据(1)式获得待分配的结果。如果是自动审批通过，则对任务执行自动审批通过;否则转向5)。

5 )调用贝叶斯概率表，得出审批趋势结果。如果是必须审批，则按照常规分配审批任务;否则，分配给下一级人员。

6 )定时把新的任务以及审批结果作为样本，转到3)，动态调整训练集。

2.2 系统结构图

引入任务分配模型，对工作流引擎的任务调度模块进行修改。系统结构如图1所示，工作流在对订单审批任务进行分配时，不再直接按照固定的模式分配。先根据任务的相关属性，获得常规的任务分配结果，如果是自动审批，则直接输出。如果不是，则利用贝叶斯网络对必须审批和不用审批这2种分类进行验证，选取概率最高的结果，然后以此为依据，对任务进行分配。如果必须审批的概率最高，则按照流程规则，分配给对应的角色。反之，则跳过这级审批，直接分配给下一级的人审批。

图1 系统结构Fig.1 System structure

3 实验

实验使用的环境为Pentium(R)IV 2.53 GHz的CPU，内存为1 GByte，操作系统为Windows XP，算法使用JAVA语言编写。实验中从浙江移动广告管理平台的订单审批记录中随机采取1 000个数据样本，每个样本用7个变量描述，表2给出了数据的格式。其中c表示审批趋势(c=0表示审批驳回，c=1表示审批通过)，其他信息为样本属性变量。在实际操作过程中，由于某些不可抗拒的因素可能造成任务的等待，平均等待时间为120 s，平均审批时间为60 s。

表2 样本数据结构Tab.2 Sample data structure

从浙江移动广告管理平台的订单审批记录中分别随机采取50，100，150，200个审批任务，这些任务有仅需要一次审批的，也有需要两级审批的。分别统计审批时间，并以此任务为样本重新创建新的审批任务，试验改进的任务分配算法，实验结果如表3所示。

表3 实验结果Tab.3 Experimental results

表3中“前”表示常规任务分配花费的时间，“后”表示基于贝叶斯理论的工作流任务分配花费的时间。

通过表3可以看出，采用改进的任务分配策略，在不同任务数目的条件下运行程序，任务的总时间、平均等待时间等都有明显缩短，其中平均等待时间降低17%左右，平均处理时间减少20%，任务处理效率提高了约1/5。这是因为改进的任务分配策略减少了任务在系统中非必须的审批流程，达到了减少任务在系统中的流转时间的目的，使得任务的平均等待时间和平均处理时间都得到了极大的改善，从而系统的吞吐量得到了提升，系统性能也得到了改善。

4 结束语

本文针对任务审批过程中，初始需要人审批，在运行过程中是否仍需要人审批这一问题进行研究。利用贝叶斯网络，以任务的发起者和任务本身的属性为分类依据，对任务进行分类，进而确定任务的最终完成者。通过对广告订单审批任务进行仿真实验，证明了本文提出的任务分配模型可以明显缩短任务的平均等待时间和平均处理时间，从而提升系统的吞吐量，改善系统性能。但是在工作流任务的动态定制方面的研究还有待进一步深入。

［1］WFMC.Workflow Management Coalition［EB/OL］.(1999－02－25)［2009－10－11］.http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.77.3060.

［2］汪涛，谭庆平，陈火旺.工作流任务分派的现状及其发展［J］. 计算机科学，2008，35(9):5－7.

WANG Tao，TAN Qing－ping，CHEN Huo－wang.Statusquo and Trends ofWorkflow Task Assignment［J］.Computer Science，2008，35(9):5－7.

［3］洪帆，赵晓斐.基于任务的访问控制模型及其实现［J］.华中科技大学学报:自然科学版，2002，30(1):17－19.

HONG Fan，ZHAO Xiao－pei.Task－based access control model and its implementation［J］.Journal of Huazhong University of Science and Technology:Nature Science E－dition，2002，30(1):17－19.

［4］刘怡，张戡.基于负载平衡和经验值的工作流任务分配策略［J］. 计算机工程，2009，35(21):57－60.

LIU Yi，ZHANG Kan.Strategy for Workflow Task Assignment Based on Load Balance and Experiential Value［J］.Computer Engineering，2009，35(21):57－60.

［5］单徐梅，虞慧群.基于RBAC的工作流管理系统授权约束方法［J］. 计算机工程，2010，36(2):152－154.

SHAN Xu－mei，YU Hui－qun.Authorization Constraint Method in Workflow Management Systems Based on RBAC［J］.Computer Engineering.2010，36(2):152－154.

［6］范明，牛常勇.数据挖掘基础教程［M］.北京:机械工业出版社，2009:148－160.

FAN Ming，NIU Chang－yong.Insight into Dato Mining:Theory and Practice［M］.Beijing:China Machine Press，2009:148－160.

［7］郭春香，李旭升.贝叶斯网络个人信用评估模型［J］.系统管理学报，2009，18(3):249－254.

GUO Chun－xiang，LIXu－sheng.Customer Credit Scoring Models on Bayesian Network Classification［J］.Journal of System and Management，2009，18(3):249－254.

［8］张成，廖建新，朱晓民.一种基于增量贝叶斯疑似度的事件驱动故障定位算法［J］.电子与信息学报，2009，31(6):1501－1504.

ZHANG Cheng，LIAO Jian－xin，ZHU Xiao－min.An Event－Driven Fault Localization Algorithm Based on Incremental Bayesian Suspected Degree［J］.Journal of Electronics and Information Technology，2009，31(6):1501－1504.

［9］尹振东，吴芝路.基于一类SVM贝叶斯算法的DSUWB系统多用户检测研究［J］.重庆邮电大学学报:自然科学版，2008，20(1):1－5.

YIN Zhen－dong，WU Zhi－lu.DS－UWBMulti－user Detection Based on one－class SVM Bayesian Algorithm.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2008，20(1):1－5.

［10］QIAO Yan，MENG Luo－ming.An Efficient Approach to Multi－Fault Diagnosis in Dynamic Networks［J］.Journal of Beijing University of Posts and Telecommunications，2009，32(6):1－4.

(编辑:田海江)