基于貝葉斯理論的工作流任務(wù)分配模型的設(shè)計(jì)

王 寧，李 煒，沈奇威

(1.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100876;2.東信北郵信息技術(shù)有限公司，北京 100191)

0 引言

工作流是指全部或部分由計(jì)算機(jī)支持或自動處理的業(yè)務(wù)過程。工作流管理系統(tǒng)是一個詳細(xì)定義、管理、并按照定義執(zhí)行工作流的軟件的集合［1］。

工作流任務(wù)分配策略是工作流管理系統(tǒng)的關(guān)鍵技術(shù)之一，是實(shí)現(xiàn)其過程自動化處理的必要手段［2］。工作流任務(wù)分配策略是描述在流程的運(yùn)行過程中，將任務(wù)在合適的時機(jī)分配給合適的人，以減少任務(wù)的處理時間，增加系統(tǒng)的吞吐量。目前對人工型任務(wù)分配的研究比較全面，但這些任務(wù)分配策略都基于這樣的前提:任務(wù)需要人來完成。當(dāng)前，針對為合適的人分配合適任務(wù)的課題進(jìn)行了較多研究［3－5］，對那些初始需要人處理，在運(yùn)行過程中是否仍需要人處理的任務(wù)尚未見相關(guān)研究。據(jù)此，本研究嘗試采用一種新的策略，利用在運(yùn)行中積累的歷史數(shù)據(jù)，減少盡可能多的流程，提高整個系統(tǒng)的性能。

任務(wù)的分配是先對任務(wù)和人分類，然后把合適的任務(wù)分配給合適的人。在任務(wù)歷史數(shù)據(jù)的積累下，對任務(wù)的分類，目前可以采用的方法有:統(tǒng)計(jì)方法、決策樹、神經(jīng)網(wǎng)絡(luò)等。決策樹大多是以不完備信息或主觀概率作為決策依據(jù)，并且對調(diào)查結(jié)果的可能性沒有一個量化的評價;神經(jīng)網(wǎng)絡(luò)雖然可靠性較高，但網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)的不確定性、復(fù)雜性以及模型本身缺乏較好的可解釋性和理解性，造成使用上存在困難，并且神經(jīng)網(wǎng)絡(luò)構(gòu)建往往過分依賴于技巧［6－8］。貝葉斯決策能對信息的價值或是否需要采集新的信息做出科學(xué)判斷，對調(diào)查結(jié)果的可能性加以量化評價，能把先驗(yàn)知識和調(diào)查結(jié)果結(jié)合起來，在決策過程中根據(jù)具體情況不斷地使用，使決策逐步完善和科學(xué)，并且屬性對應(yīng)現(xiàn)實(shí)中的語義，具有較好的可解釋性［9－10］。所以，本文主要利用貝葉斯網(wǎng)絡(luò)對任務(wù)的相關(guān)屬性建模，在歷史數(shù)據(jù)的支持下，對任務(wù)進(jìn)行分類，并依此為依據(jù)為任務(wù)分配合適的資源，優(yōu)化業(yè)務(wù)流程，減少任務(wù)處理時間，提高系統(tǒng)效率。

1 移動廣告任務(wù)分配分析

移動廣告(mobile advertising，MA)是由移動通信網(wǎng)及移動業(yè)務(wù)承載，具有移動通信網(wǎng)絡(luò)的業(yè)務(wù)特征，用戶能夠隨時隨地接受廣告信息。出于對系統(tǒng)安全性、商業(yè)邏輯合法性以及內(nèi)容傳播廣泛性的考慮，移動廣告管理平臺需要對相關(guān)的信息進(jìn)行審核。工作流主要應(yīng)用在MA的所有審批流程中。

工作流的任務(wù)分配主要應(yīng)用在移動廣告中的對象的審批過程中。以廣告訂單為例，訂單任務(wù)的審批主要分為3類:地市級操作員審批、省級操作員審批、自動審批。訂單任務(wù)的分配主要考慮以下2個方面。

1 )訂單的創(chuàng)建者:創(chuàng)建者的屬性主要集中在3個方面:角色R，所屬地區(qū)D，級別L。這些屬性決定訂單任務(wù)的審批流程，具體流程如表1所示。

表1 常規(guī)任務(wù)分配Tab.1 General task assignment

根據(jù)表1所示規(guī)則可得

(1)式中:R表示角色;L表示級別;S={s1，s2，s3}表示3種不同的任務(wù)分配結(jié)果;F(R，L)是(R，L)→S的映射。

2 )訂單的屬性:訂單的重要性是判斷審批任務(wù)分配的重要依據(jù)，越重要的訂單，越需要人的參與，越需要按照規(guī)則分配。訂單的重要性主要體現(xiàn)在3個方面:訂單的金額x1，訂單的持續(xù)時間x2，訂單的類型x3。訂單的優(yōu)惠條件涉及到人為因素，需要人來監(jiān)督這個權(quán)利的使用，并且還涉及到不同代理商的公平競爭問題。訂單的優(yōu)惠條件主要考慮2個方面:折扣率x4，配送比例x5。訂單的付費(fèi)形式x6和訂單的創(chuàng)建者x7也是影響訂單越級處理的重要因素。從安全角度考慮預(yù)付費(fèi)安全度高于后付費(fèi)，而訂單的創(chuàng)建者體現(xiàn)了個人信用度，因此實(shí)際操作過程中，創(chuàng)建者提交的訂單審批通過的概率越高，其提交的新訂單審批通過的概率越高。

常規(guī)任務(wù)分配策略體現(xiàn)了固有業(yè)務(wù)流程。在實(shí)際應(yīng)用中，某些訂單審批具有極高的審批通過率，這意味著訂單在審批的業(yè)務(wù)流程中可直接審批通過流轉(zhuǎn)給下一級人員操作。顯而易見，訂單審批的必要性和訂單的屬性息息相關(guān)，因此可以利用貝葉斯分類模型，通過對訂單任務(wù)的相關(guān)屬性進(jìn)行建模分析，對訂單審批的必要性進(jìn)行合理分類，并在此分類的基礎(chǔ)上對訂單任務(wù)進(jìn)行分配。

2 構(gòu)建貝葉斯任務(wù)分配模型

(3)式中 xk表示 xi=(x1，x2，…，x7)中第 k個屬性變量。本文中我們基于樸素貝葉斯網(wǎng)絡(luò)進(jìn)行建模分析，即假定訂單任務(wù)的各屬性在已經(jīng)類的條件下相互獨(dú)立，則(3)式可簡化為

對于一個給定的訂單任務(wù)，(4)式中的α為一個定值，因此只需求(4)式中其他部分的值，選取使(4)式取值最大的審批趨勢，作為訂單任務(wù)分配考慮的因素。

2.1 基于貝葉斯網(wǎng)絡(luò)的任務(wù)分配模型

根據(jù)上節(jié)的分析，基于貝葉斯網(wǎng)絡(luò)的任務(wù)分配可按照下列步驟進(jìn)行。

1 )輸入訓(xùn)練樣本，初始化為統(tǒng)一的格式，定義類變量和屬性變量。

2 )判斷:如果是分類任務(wù)，則轉(zhuǎn)向4)，否則(訓(xùn)練任務(wù))轉(zhuǎn)向3)。

3 )參數(shù)學(xué)習(xí)。掃描所有訓(xùn)練樣本:

①計(jì)算所有屬性的先驗(yàn)概率，對離散屬性和連續(xù)屬性分別按照(5)式和(6)式計(jì)算;

②計(jì)算P(C=ci)，即類變量取值為ci時的先驗(yàn)概率;③生成貝葉斯概率表，即所需的貝葉斯分類器。4)根據(jù)(1)式獲得待分配的結(jié)果。如果是自動審批通過，則對任務(wù)執(zhí)行自動審批通過;否則轉(zhuǎn)向5)。

5 )調(diào)用貝葉斯概率表，得出審批趨勢結(jié)果。如果是必須審批，則按照常規(guī)分配審批任務(wù);否則，分配給下一級人員。

6 )定時把新的任務(wù)以及審批結(jié)果作為樣本，轉(zhuǎn)到3)，動態(tài)調(diào)整訓(xùn)練集。

2.2 系統(tǒng)結(jié)構(gòu)圖

引入任務(wù)分配模型，對工作流引擎的任務(wù)調(diào)度模塊進(jìn)行修改。系統(tǒng)結(jié)構(gòu)如圖1所示，工作流在對訂單審批任務(wù)進(jìn)行分配時，不再直接按照固定的模式分配。先根據(jù)任務(wù)的相關(guān)屬性，獲得常規(guī)的任務(wù)分配結(jié)果，如果是自動審批，則直接輸出。如果不是，則利用貝葉斯網(wǎng)絡(luò)對必須審批和不用審批這2種分類進(jìn)行驗(yàn)證，選取概率最高的結(jié)果，然后以此為依據(jù)，對任務(wù)進(jìn)行分配。如果必須審批的概率最高，則按照流程規(guī)則，分配給對應(yīng)的角色。反之，則跳過這級審批，直接分配給下一級的人審批。

圖1 系統(tǒng)結(jié)構(gòu)Fig.1 System structure

3 實(shí)驗(yàn)

實(shí)驗(yàn)使用的環(huán)境為Pentium(R)IV 2.53 GHz的CPU，內(nèi)存為1 GByte，操作系統(tǒng)為Windows XP，算法使用JAVA語言編寫。實(shí)驗(yàn)中從浙江移動廣告管理平臺的訂單審批記錄中隨機(jī)采取1 000個數(shù)據(jù)樣本，每個樣本用7個變量描述，表2給出了數(shù)據(jù)的格式。其中c表示審批趨勢(c=0表示審批駁回，c=1表示審批通過)，其他信息為樣本屬性變量。在實(shí)際操作過程中，由于某些不可抗拒的因素可能造成任務(wù)的等待，平均等待時間為120 s，平均審批時間為60 s。

表2 樣本數(shù)據(jù)結(jié)構(gòu)Tab.2 Sample data structure

從浙江移動廣告管理平臺的訂單審批記錄中分別隨機(jī)采取50，100，150，200個審批任務(wù)，這些任務(wù)有僅需要一次審批的，也有需要兩級審批的。分別統(tǒng)計(jì)審批時間，并以此任務(wù)為樣本重新創(chuàng)建新的審批任務(wù)，試驗(yàn)改進(jìn)的任務(wù)分配算法，實(shí)驗(yàn)結(jié)果如表3所示。

表3 實(shí)驗(yàn)結(jié)果Tab.3 Experimental results

表3中“前”表示常規(guī)任務(wù)分配花費(fèi)的時間，“后”表示基于貝葉斯理論的工作流任務(wù)分配花費(fèi)的時間。

通過表3可以看出，采用改進(jìn)的任務(wù)分配策略，在不同任務(wù)數(shù)目的條件下運(yùn)行程序，任務(wù)的總時間、平均等待時間等都有明顯縮短，其中平均等待時間降低17%左右，平均處理時間減少20%，任務(wù)處理效率提高了約1/5。這是因?yàn)楦倪M(jìn)的任務(wù)分配策略減少了任務(wù)在系統(tǒng)中非必須的審批流程，達(dá)到了減少任務(wù)在系統(tǒng)中的流轉(zhuǎn)時間的目的，使得任務(wù)的平均等待時間和平均處理時間都得到了極大的改善，從而系統(tǒng)的吞吐量得到了提升，系統(tǒng)性能也得到了改善。

4 結(jié)束語

本文針對任務(wù)審批過程中，初始需要人審批，在運(yùn)行過程中是否仍需要人審批這一問題進(jìn)行研究。利用貝葉斯網(wǎng)絡(luò)，以任務(wù)的發(fā)起者和任務(wù)本身的屬性為分類依據(jù)，對任務(wù)進(jìn)行分類，進(jìn)而確定任務(wù)的最終完成者。通過對廣告訂單審批任務(wù)進(jìn)行仿真實(shí)驗(yàn)，證明了本文提出的任務(wù)分配模型可以明顯縮短任務(wù)的平均等待時間和平均處理時間，從而提升系統(tǒng)的吞吐量，改善系統(tǒng)性能。但是在工作流任務(wù)的動態(tài)定制方面的研究還有待進(jìn)一步深入。

［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］汪濤，譚慶平，陳火旺.工作流任務(wù)分派的現(xiàn)狀及其發(fā)展［J］. 計(jì)算機(jī)科學(xué)，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］洪帆，趙曉斐.基于任務(wù)的訪問控制模型及其實(shí)現(xiàn)［J］.華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，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］劉怡，張戡.基于負(fù)載平衡和經(jīng)驗(yàn)值的工作流任務(wù)分配策略［J］. 計(jì)算機(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的工作流管理系統(tǒng)授權(quán)約束方法［J］. 計(jì)算機(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］范明，牛常勇.數(shù)據(jù)挖掘基礎(chǔ)教程［M］.北京:機(jī)械工業(yè)出版社，2009:148－160.

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

［7］郭春香，李旭升.貝葉斯網(wǎng)絡(luò)個人信用評估模型［J］.系統(tǒng)管理學(xué)報(bào)，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］張成，廖建新，朱曉民.一種基于增量貝葉斯疑似度的事件驅(qū)動故障定位算法［J］.電子與信息學(xué)報(bào)，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系統(tǒng)多用戶檢測研究［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，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.

(編輯:田海江)