王 寧,李 煒,沈奇威
(1.北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100876;2.東信北郵信息技術(shù)有限公司,北京 100191)
工作流是指全部或部分由計(jì)算機(jī)支持或自動(dòng)處理的業(yè)務(wù)過程。工作流管理系統(tǒng)是一個(gè)詳細(xì)定義、管理、并按照定義執(zhí)行工作流的軟件的集合[1]。
工作流任務(wù)分配策略是工作流管理系統(tǒng)的關(guān)鍵技術(shù)之一,是實(shí)現(xiàn)其過程自動(dòng)化處理的必要手段[2]。工作流任務(wù)分配策略是描述在流程的運(yùn)行過程中,將任務(wù)在合適的時(shí)機(jī)分配給合適的人,以減少任務(wù)的處理時(shí)間,增加系統(tǒng)的吞吐量。目前對(duì)人工型任務(wù)分配的研究比較全面,但這些任務(wù)分配策略都基于這樣的前提:任務(wù)需要人來完成。當(dāng)前,針對(duì)為合適的人分配合適任務(wù)的課題進(jìn)行了較多研究[3-5],對(duì)那些初始需要人處理,在運(yùn)行過程中是否仍需要人處理的任務(wù)尚未見相關(guān)研究。據(jù)此,本研究嘗試采用一種新的策略,利用在運(yùn)行中積累的歷史數(shù)據(jù),減少盡可能多的流程,提高整個(gè)系統(tǒng)的性能。
任務(wù)的分配是先對(duì)任務(wù)和人分類,然后把合適的任務(wù)分配給合適的人。在任務(wù)歷史數(shù)據(jù)的積累下,對(duì)任務(wù)的分類,目前可以采用的方法有:統(tǒng)計(jì)方法、決策樹、神經(jīng)網(wǎng)絡(luò)等。決策樹大多是以不完備信息或主觀概率作為決策依據(jù),并且對(duì)調(diào)查結(jié)果的可能性沒有一個(gè)量化的評(píng)價(jià);神經(jīng)網(wǎng)絡(luò)雖然可靠性較高,但網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)的不確定性、復(fù)雜性以及模型本身缺乏較好的可解釋性和理解性,造成使用上存在困難,并且神經(jīng)網(wǎng)絡(luò)構(gòu)建往往過分依賴于技巧[6-8]。貝葉斯決策能對(duì)信息的價(jià)值或是否需要采集新的信息做出科學(xué)判斷,對(duì)調(diào)查結(jié)果的可能性加以量化評(píng)價(jià),能把先驗(yàn)知識(shí)和調(diào)查結(jié)果結(jié)合起來,在決策過程中根據(jù)具體情況不斷地使用,使決策逐步完善和科學(xué),并且屬性對(duì)應(yīng)現(xiàn)實(shí)中的語(yǔ)義,具有較好的可解釋性[9-10]。所以,本文主要利用貝葉斯網(wǎng)絡(luò)對(duì)任務(wù)的相關(guān)屬性建模,在歷史數(shù)據(jù)的支持下,對(duì)任務(wù)進(jìn)行分類,并依此為依據(jù)為任務(wù)分配合適的資源,優(yōu)化業(yè)務(wù)流程,減少任務(wù)處理時(shí)間,提高系統(tǒng)效率。
移動(dòng)廣告(mobile advertising,MA)是由移動(dòng)通信網(wǎng)及移動(dòng)業(yè)務(wù)承載,具有移動(dòng)通信網(wǎng)絡(luò)的業(yè)務(wù)特征,用戶能夠隨時(shí)隨地接受廣告信息。出于對(duì)系統(tǒng)安全性、商業(yè)邏輯合法性以及內(nèi)容傳播廣泛性的考慮,移動(dòng)廣告管理平臺(tái)需要對(duì)相關(guān)的信息進(jìn)行審核。工作流主要應(yīng)用在MA的所有審批流程中。
工作流的任務(wù)分配主要應(yīng)用在移動(dòng)廣告中的對(duì)象的審批過程中。以廣告訂單為例,訂單任務(wù)的審批主要分為3類:地市級(jí)操作員審批、省級(jí)操作員審批、自動(dòng)審批。訂單任務(wù)的分配主要考慮以下2個(gè)方面。
1 )訂單的創(chuàng)建者:創(chuàng)建者的屬性主要集中在3個(gè)方面:角色R,所屬地區(qū)D,級(jí)別L。這些屬性決定訂單任務(wù)的審批流程,具體流程如表1所示。
表1 常規(guī)任務(wù)分配Tab.1 General task assignment
根據(jù)表1所示規(guī)則可得
(1)式中:R表示角色;L表示級(jí)別;S={s1,s2,s3}表示3種不同的任務(wù)分配結(jié)果;F(R,L)是(R,L)→S的映射。
2 )訂單的屬性:訂單的重要性是判斷審批任務(wù)分配的重要依據(jù),越重要的訂單,越需要人的參與,越需要按照規(guī)則分配。訂單的重要性主要體現(xiàn)在3個(gè)方面:訂單的金額x1,訂單的持續(xù)時(shí)間x2,訂單的類型x3。訂單的優(yōu)惠條件涉及到人為因素,需要人來監(jiān)督這個(gè)權(quán)利的使用,并且還涉及到不同代理商的公平競(jìng)爭(zhēng)問題。訂單的優(yōu)惠條件主要考慮2個(gè)方面:折扣率x4,配送比例x5。訂單的付費(fèi)形式x6和訂單的創(chuàng)建者x7也是影響訂單越級(jí)處理的重要因素。從安全角度考慮預(yù)付費(fèi)安全度高于后付費(fèi),而訂單的創(chuàng)建者體現(xiàn)了個(gè)人信用度,因此實(shí)際操作過程中,創(chuàng)建者提交的訂單審批通過的概率越高,其提交的新訂單審批通過的概率越高。
常規(guī)任務(wù)分配策略體現(xiàn)了固有業(yè)務(wù)流程。在實(shí)際應(yīng)用中,某些訂單審批具有極高的審批通過率,這意味著訂單在審批的業(yè)務(wù)流程中可直接審批通過流轉(zhuǎn)給下一級(jí)人員操作。顯而易見,訂單審批的必要性和訂單的屬性息息相關(guān),因此可以利用貝葉斯分類模型,通過對(duì)訂單任務(wù)的相關(guān)屬性進(jìn)行建模分析,對(duì)訂單審批的必要性進(jìn)行合理分類,并在此分類的基礎(chǔ)上對(duì)訂單任務(wù)進(jìn)行分配。
(3)式中 xk表示 xi=(x1,x2,…,x7)中第 k個(gè)屬性變量。本文中我們基于樸素貝葉斯網(wǎng)絡(luò)進(jìn)行建模分析,即假定訂單任務(wù)的各屬性在已經(jīng)類的條件下相互獨(dú)立,則(3)式可簡(jiǎn)化為
對(duì)于一個(gè)給定的訂單任務(wù),(4)式中的α為一個(gè)定值,因此只需求(4)式中其他部分的值,選取使(4)式取值最大的審批趨勢(shì),作為訂單任務(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)概率,對(duì)離散屬性和連續(xù)屬性分別按照(5)式和(6)式計(jì)算;
②計(jì)算P(C=ci),即類變量取值為ci時(shí)的先驗(yàn)概率;③生成貝葉斯概率表,即所需的貝葉斯分類器。4)根據(jù)(1)式獲得待分配的結(jié)果。如果是自動(dòng)審批通過,則對(duì)任務(wù)執(zhí)行自動(dòng)審批通過;否則轉(zhuǎn)向5)。
5 )調(diào)用貝葉斯概率表,得出審批趨勢(shì)結(jié)果。如果是必須審批,則按照常規(guī)分配審批任務(wù);否則,分配給下一級(jí)人員。
6 )定時(shí)把新的任務(wù)以及審批結(jié)果作為樣本,轉(zhuǎn)到3),動(dòng)態(tài)調(diào)整訓(xùn)練集。
引入任務(wù)分配模型,對(duì)工作流引擎的任務(wù)調(diào)度模塊進(jìn)行修改。系統(tǒng)結(jié)構(gòu)如圖1所示,工作流在對(duì)訂單審批任務(wù)進(jìn)行分配時(shí),不再直接按照固定的模式分配。先根據(jù)任務(wù)的相關(guān)屬性,獲得常規(guī)的任務(wù)分配結(jié)果,如果是自動(dòng)審批,則直接輸出。如果不是,則利用貝葉斯網(wǎng)絡(luò)對(duì)必須審批和不用審批這2種分類進(jìn)行驗(yàn)證,選取概率最高的結(jié)果,然后以此為依據(jù),對(duì)任務(wù)進(jìn)行分配。如果必須審批的概率最高,則按照流程規(guī)則,分配給對(duì)應(yīng)的角色。反之,則跳過這級(jí)審批,直接分配給下一級(jí)的人審批。
圖1 系統(tǒng)結(jié)構(gòu)Fig.1 System structure
實(shí)驗(yàn)使用的環(huán)境為Pentium(R)IV 2.53 GHz的CPU,內(nèi)存為1 GByte,操作系統(tǒng)為Windows XP,算法使用JAVA語(yǔ)言編寫。實(shí)驗(yàn)中從浙江移動(dòng)廣告管理平臺(tái)的訂單審批記錄中隨機(jī)采取1 000個(gè)數(shù)據(jù)樣本,每個(gè)樣本用7個(gè)變量描述,表2給出了數(shù)據(jù)的格式。其中c表示審批趨勢(shì)(c=0表示審批駁回,c=1表示審批通過),其他信息為樣本屬性變量。在實(shí)際操作過程中,由于某些不可抗拒的因素可能造成任務(wù)的等待,平均等待時(shí)間為120 s,平均審批時(shí)間為60 s。
表2 樣本數(shù)據(jù)結(jié)構(gòu)Tab.2 Sample data structure
從浙江移動(dòng)廣告管理平臺(tái)的訂單審批記錄中分別隨機(jī)采取50,100,150,200個(gè)審批任務(wù),這些任務(wù)有僅需要一次審批的,也有需要兩級(jí)審批的。分別統(tǒng)計(jì)審批時(shí)間,并以此任務(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)的時(shí)間,“后”表示基于貝葉斯理論的工作流任務(wù)分配花費(fèi)的時(shí)間。
通過表3可以看出,采用改進(jìn)的任務(wù)分配策略,在不同任務(wù)數(shù)目的條件下運(yùn)行程序,任務(wù)的總時(shí)間、平均等待時(shí)間等都有明顯縮短,其中平均等待時(shí)間降低17%左右,平均處理時(shí)間減少20%,任務(wù)處理效率提高了約1/5。這是因?yàn)楦倪M(jìn)的任務(wù)分配策略減少了任務(wù)在系統(tǒng)中非必須的審批流程,達(dá)到了減少任務(wù)在系統(tǒng)中的流轉(zhuǎn)時(shí)間的目的,使得任務(wù)的平均等待時(shí)間和平均處理時(shí)間都得到了極大的改善,從而系統(tǒng)的吞吐量得到了提升,系統(tǒng)性能也得到了改善。
本文針對(duì)任務(wù)審批過程中,初始需要人審批,在運(yùn)行過程中是否仍需要人審批這一問題進(jìn)行研究。利用貝葉斯網(wǎng)絡(luò),以任務(wù)的發(fā)起者和任務(wù)本身的屬性為分類依據(jù),對(duì)任務(wù)進(jìn)行分類,進(jìn)而確定任務(wù)的最終完成者。通過對(duì)廣告訂單審批任務(wù)進(jìn)行仿真實(shí)驗(yàn),證明了本文提出的任務(wù)分配模型可以明顯縮短任務(wù)的平均等待時(shí)間和平均處理時(shí)間,從而提升系統(tǒng)的吞吐量,改善系統(tǒng)性能。但是在工作流任務(wù)的動(dòng)態(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ò)個(gè)人信用評(píng)估模型[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ū)動(dòng)故障定位算法[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)多用戶檢測(cè)研究[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.
(編輯:田海江)