基于串歸約的時間約束下工作流精確率優(yōu)化算法

羅智勇　朱梓豪　尤波　苗世迪

摘要：復雜產(chǎn)品的業(yè)務調(diào)度依賴于完工時間和精確率等屬性，追求單一的目標不能保證這兩個方面的平衡。傳統(tǒng)的算法經(jīng)常是以花費時間最小或者保證完工質(zhì)量最佳為目標，這樣會導致產(chǎn)品質(zhì)量過低或者完成產(chǎn)品所用的時間過多。針對這種弊端，提出了約束時間下精確率串歸約優(yōu)化算法SRA，通過約束任務得到活動區(qū)間來進行優(yōu)化路徑。最后在典型案例中，分別利用了傳統(tǒng)的單向目標算法和串歸約算法求解對應的路徑，并對算法SRA優(yōu)化效果的其他參數(shù)進行了研究。研究表明，這種算法具有簡單、高效、方便執(zhí)行等優(yōu)點。

關(guān)鍵詞：

工作流調(diào)度；時間一致性；準確率優(yōu)化；截止期

DOI：10.15938/j.jhust.2018.05.012

中圖分類號： TP393

文獻標志碼： A

文章編號： 1007-2683（2018）05-0068-07

Abstract：Complex business scheduling depends on the completion of the time and accuracy and other attributes， the pursuit of a single goal cannot guarantee the balance of the aspects Traditional algorithms often take the least time or the best quality as goal， it leads to the low quality low or the more time taken to complete the product Aiming at this drawback， the SRA of the exact rate with string reduction optimization under the constraint time proposed， and obtains the active interval by the constraint task Finally， in the typical case， the traditional oneway target algorithm and the string reduction algorithm are used to solve the corresponding path respectively， and analyzed the other parameters that affect the performance of SRA The research shows that this algorithm has the advantages of simple， efficient and convenient implementation

Keywords：workflow scheduling； time consistent； accuracy optimization； deadline

0引言

復雜產(chǎn)品工作流是以網(wǎng)絡流為基礎(chǔ)，結(jié)合調(diào)度技術(shù)，并以服務為基本構(gòu)成單位的一種架構(gòu)技術(shù)[1-2]，主要用于表征多服務相互協(xié)調(diào)工作來完成整個產(chǎn)品加工的過程。工作流將業(yè)務流程抽象化，劃分為諸多工序，結(jié)合工序中服務屬性，確定最佳完工路徑。在工作流中，每個任務中服務的選擇極為重要，它決定著整個業(yè)務的效率及完工質(zhì)量。能否合理地選擇任務中對應的服務，對整個業(yè)務流程的有效執(zhí)行起著重要的影響。

目前企業(yè)在復雜項目的實施過程中，工作流模型所需要的資源類型在模型的構(gòu)建中就已經(jīng)確定了，在實際的項目下發(fā)后，企業(yè)也能夠及時地分配好任務，并利用對應的服務展開工作。但是項目流程作為一個整體，并被分成幾個工序，往往因為一個或者幾個工序存在問題，諸如追求效率從而忽略了服務質(zhì)量或者追求服務質(zhì)量而拖延了完工時間，使得整個項目的完工時間和完工質(zhì)量失衡。因此單方面地追求效率，將會導致準確率過低，相反單方面追求服務準確率，反而影響復雜產(chǎn)品的完工時間。為此，應該使用更合理的方法，在業(yè)務流程規(guī)定的截止期內(nèi)，選擇一條能夠有效提升復雜項目準確率的路徑，達到既能充分利用資源，又能使效率和準確率實現(xiàn)平衡的目的[3]。本文提出了一種在限定完工時間內(nèi)，通過串歸約算法（serial reduction algorithm， SRA）來優(yōu)化生產(chǎn)精確率的解決辦法，達到時間和生產(chǎn)精確率的相對平衡。

1相關(guān)工作

工作流模型主要由任務和服務組成，其中任務代表了加工工序，而服務則代表了完成該任務所用的成本、工期和生產(chǎn)精度等屬性[4]，合理平衡服務中的各屬性參數(shù)對優(yōu)化工作流模型中的任務調(diào)度具有關(guān)鍵性作用[5-6]。隨著工作流技術(shù)的不斷完善，已不再以單純的優(yōu)化工期為研究目的，而是向著動態(tài)平衡工期和生產(chǎn)精度等更深層次優(yōu)化提出了嚴格的要求。文[7]提出在時間限制條件下優(yōu)化成本的問題實際上是一種NPhard問題；文[8]基于時間約束下提出了3種降低成本的啟發(fā)式算法；文[9]對截止期約束下的優(yōu)化成本問題提出了正向分層的策略，在每個環(huán)節(jié)的約束時間內(nèi)選擇費用最小的服務；文[10]提出了串行和并行的實例集合，在網(wǎng)絡模型的基礎(chǔ)上進行建模；文[11]在業(yè)務的網(wǎng)絡圖中，將整個業(yè)務分解為多個環(huán)節(jié)，對每個分量做出了時間約束并進行優(yōu)化；文[12]中Pawel通過對工作流程中成本與時間的分析，對每個任務選擇合適的服務，優(yōu)化了工作流的線性組合；文[13]通過AMPL模型實現(xiàn)了約束時間下成本的最小化；文[14]通過并行方式進行資源整合，降低了成本并且提高了質(zhì)量。

基于在約束時間下降低成本的問題，國內(nèi)也開展了相應的研究。文[15]采用動態(tài)資源選擇策略，在相對較小的完工時間范圍內(nèi)，實現(xiàn)業(yè)務成本的最小化。文[16]運用了基于Markov鏈技術(shù)實現(xiàn)了工作流成本最小化。可見在工作流模型的服務屬性中，確實存在著時間、成本和服務質(zhì)量問題，如何保證在業(yè)務流程約束時間下對完工質(zhì)量進行優(yōu)化也是一個研究熱點[17]。

2問題描述

21相關(guān)定義

定義1工作流模型。若用M表示模型，則M可形式化為二元組M=（R，Wr），其中R為任務池，由工序所涉及到的所有工作任務構(gòu)成的集合，可表示為R=（r1，r2rirn），n為任務數(shù)；Wr為任務ri的服務池，是由完成該任務可選用的服務構(gòu)成的集合，可表示為Wi=（w1，w2wjwm），m為服務數(shù)；在具體的業(yè)務過程中，任務ri與任務rj之間（i≠j）存在順序關(guān)系，且每個任務r對應著服務池Wr，通過每個任務對應服務的合理搭配，實現(xiàn)整個工作流；任務池r中任意任務r所對應的Wr中的數(shù)目稱為服務池的秩，可表示為zr。

定義2工作流圖F。是一個有向無環(huán)圖DAG，且F={wrk，rhrk，L}，其中：wrk代表任意任務r選擇服務池Wr中第k個服務來加工；rhrk為服務屬性且rhrk=（hrk，erk），代表著服務wrk全部的屬性參數(shù)，hrk表示選擇Wr中第k個服務w來加工任務r所用的時間參數(shù)，erk則表示生產(chǎn)精確率；L為有向邊集合，代表各服務wi之間的偏序關(guān)系，且只有前驅(qū)層服務完成相關(guān)的任務ri后才允許開始后繼層任務rj；r∈R，0

定義3任務自由度。指模型M中任務r的活動工作區(qū)間，表示為FDr=[IMr，ALr]，其中：IMr為任務r的最早啟動時間，ALr為任務r的最晚啟動時間，可由式（1）求得：

IMr=∑r-1i=1min（hik），0

ALr=DL-∑ri=nmin（hik），0

定理1工作流圖F中，任意任務r其自由度FDr有且只有一個。

證明：存在FDr=[IMr，ALr]，有任務結(jié)點r，r′，并滿足順序關(guān)系，即r′在r之前執(zhí)。

1）證明最早開始時間IMr′有且只有一個：此時假設(shè)任務r′的第k個服務的運行時間最短，即hr′k，則任務r最早開始時間IMr=IMr′+hr′k，依次遞推，即每個任務的最早開始時間，則任務r的最早開始時間有且只有一個。

2）證明最晚開始時間ALr有且只有一個：反證法假設(shè)第r′的任務的最遲開始時間為ALr′，假設(shè)存在AL′r′ALr′ ，則AL′r′+hrk>DL，此時完工時間超過截止期，因此假設(shè)不成立。

綜上所述，任務r的最早開始時間和最晚開始時間有且只有一個，所以任務自由度FDr也有且只有一個。

22工作流圖生成算法

工作流圖能有效地模擬出業(yè)務流程中的任務及對應服務，對管理人員詳細掌握所有工作路徑有著至關(guān)重要的作用。本文在以往的研究基礎(chǔ)上[18-19]，結(jié)合工作流特點，給出生成工作流圖的步驟如下：

1）劃分業(yè)務流程的任務集合R，對R中所有任務r安排順序，并對任務r規(guī)劃出能夠完成該任務的服務Wr；

2）在結(jié)點Begin處開始，添加任務層，將第一個任務的服務放到同一層中；

3）查詢下一個任務，并將其對應的所有服務添加到同一層中，與前一層的所有任務形成順序關(guān)系；

4）重復步驟3），直至沒有任務為止，此時將最后一層服務集合連接到最終狀態(tài)Final；

5）對所有的服務wrk添加屬性rhrk；

6）工作流圖完成。

根據(jù)上述的策略，可設(shè)計的工作流圖生成算法WGGA的偽代碼如下：

輸入：參數(shù)wrk；rhrk；Begin；Final；len；zr；// len為集合R中的任務數(shù)目

輸出：工作流圖F

算法WGGA

Service_queue=NULL，F(xiàn)=NULL，len=Rlength；

For（intr=1；r<=len；i++）{ For（intk=1；k<=zr；k++）{Insert（Service_queue，wrk）}}；

r=1；For（k=1；k<=zr；k++）{Delete（Service_queue，wrk）；} //把任務1的服務出隊

ADD wrk TO F； //把服務加入工作流程圖F中；

Contact（Begin，wrk）；} //連接開始結(jié)點Begin和任務1的所有服務

For（r=2；r<=len；r++） {For（k=1；k<=zr；k++）{Delete（Service_queue，wrk）；}}

ADD wrkTOF； //把對應的服務加入到F中

Contact（wr-1k，wrk）；} //把前一層的任務的所有服務連接到下一層的所有服務

Contact（wrk，F(xiàn)inal）； //把最后一層服務連接到結(jié)束結(jié)點Final

ADDrhrk TO wrk； //把服務屬性添加進去

Return F。

該算法的時間復雜度為O（mn）。

23工作流圖生成算法WGGA舉例

假設(shè)工作流模型M的任務集合R為{α，β，γ，δ}，且每個任務都有對應的服務池Wα，Wβ，Wγ，Wδ，利用工作流圖生成算法WGGA，輸入基本參數(shù)后，生成該實例的工作流圖F及相應參數(shù)如圖1所示。

24工作流圖F所滿足的約束

工作流圖F中各任務加工需滿足一定的約束條件才能達到工業(yè)需求，式（2）為工作流圖F用于計算截止期下生產(chǎn)精確率的公式及遵循的約束條件：

E=∏crkerk，H=∑crkhrk<=DL

st∑zrk=1crk=1，r∈R，crk∈{0，1}，0

式中：E為生產(chǎn)精確率，指沿著某路徑所經(jīng)過的不同任務r選擇對應的服務wrk加工產(chǎn)品所得到的精確率；H為加工時間，指沿著某路徑加工產(chǎn)品所花費的時間；DL為截止期，指加工產(chǎn)品的最晚完工時間；crk為互斥變量取值為1或0。

復雜產(chǎn)品的加工要求在不超過截止期DL內(nèi)，以式（2）為目標函數(shù)，計算各工作流調(diào)度策略的加工時間H和精確率E，比較優(yōu)化效果和性能指標。

3單指標優(yōu)傳統(tǒng)化調(diào)度算法[20]

31基于單指標H的傳統(tǒng)優(yōu)化調(diào)度策略O(shè)DSH

以優(yōu)化最小完工時間Hmin為目標的傳統(tǒng)工作流調(diào)度策略可節(jié)省更多的加工時間，這種策略在工作流圖F中每次選擇最小的加工時間h來進行調(diào)度，式（3）為在這種調(diào)度策略下求得的生產(chǎn)精確率E：

Hmin=∑min（hrk）

E=∏erk，0

32基于單指標E的傳統(tǒng)優(yōu)化調(diào)度策略O(shè)DSE

以優(yōu)化最大加工精確率Emax為目標的傳統(tǒng)工作流調(diào)度策略可獲得最高的加工精確率，這種策略在工作流圖F中每次選擇最大的加工精確率erk來進行調(diào)度，式（4）為在這種調(diào)度策略下求得的完工時間H：

Emax=∏max（erk）

H=∑hrk，0

分析以上兩種單指標優(yōu)化調(diào)度策略發(fā)現(xiàn)其存在如下弊端：①實現(xiàn)完工時間Hmin最小化，則該路徑完工精確率E可能會降低；②實現(xiàn)完工精確率Emax最大化，則該路徑所用時間可能超過截止期DL，不能滿足工業(yè)需求。

4基于串歸約的時間-精確率優(yōu)化策略SRA

串歸約分層技術(shù)的核心思想是充分考慮業(yè)務流程的完工時間和完工精確率，即在截止期DL范圍內(nèi)，對每層任務劃分活動區(qū)間，在其中尋找最優(yōu)的服務，將復雜產(chǎn)品的生產(chǎn)工序轉(zhuǎn)變?yōu)榫植拷Y(jié)點的執(zhí)行，通過迭代的方式，找到一條完工時間和完工精確率平衡的路徑。

若某工作流模型中的加工任務數(shù)為n，則令函數(shù)Φ（r，h）代表任務r從時刻hr開始在其活動區(qū)間[IMr，ALr]內(nèi)所能達到的最大生產(chǎn)精確率。函數(shù)Φ（r，h）的值可通過式（5）進行計算：

φ（r，hr）=max{erk}，r=n，0

hr∈[IMr，ALr]，hr+hrk<=DL（5）

假設(shè)任務r的前驅(qū)為r′，則工作流模型整體被歸約后，可通過先計算最后層任務的精確率反向求得前層任務的各自最大精確率，最終求得整個業(yè)務的最佳路徑，此過程可通過式（6）來進行計算：

φ（r′，hr′）=max{φ（r，hr′+hr′k）×er′k}

hr′∈[IMr′，ALr′]（6）

綜上所述，基于串歸約的時間-精確率優(yōu)化算法SRA如下：

1）調(diào)用算法WGGA生成工作流圖F；

2）利用業(yè)務截止期并結(jié)合式（1）求得每個任務的自由度FDr；

3）調(diào)用式（5）求得在最后一層任務的自由度內(nèi)，在不同時刻開始達到的最大精確率；

4）調(diào)用式（6），采用迭代的方式，求出每個服務在不同時間開始能達到的最大精確率；

5）比較最終的精確率，達到最大精確率的路徑即為最佳路徑。

5案例描述及算法應用

51案例描述

經(jīng)調(diào)研某卡車裝配的組裝業(yè)務的流程分為車架總成、總裝配流水線、布設(shè)電線、安裝零件、加注油料、安裝輪胎、膨脹水箱、調(diào)試下線等8個環(huán)節(jié)，經(jīng)分析可將申請和竣工環(huán)節(jié)當作虛擬任務，作為開始與結(jié)束，則該業(yè)務環(huán)節(jié)構(gòu)成了工作流里面的任務集合R，可抽象化表示為r1， r2， r3， r4， r5， r6， r7， r8，虛擬的申請、竣工環(huán)節(jié)為rB、rF；每個任務環(huán)節(jié)r對應一個服務池Wr。已知各服務集合中的任一元素的屬性rhrk，結(jié)合服務可表示為wrk（hrk，erk），如w11（3，095）表示審批環(huán)節(jié)r1用該服務集合W1中的第一個服務w11來完成需要的時間為3，達到的準確率為095。其他任務對應的服務及其工作時間和準確率如表1所示。

52算法分析

若規(guī)定業(yè)務流程的截止期DL=30，則圖2所示工作流圖在不同優(yōu)化算法下的調(diào)度過程如下：

分析圖3可見，使用算法ODSE進行優(yōu)化得到的完工準確率最大，但由于加工所用時間大于截止期DL而不能采用；采用算法ODSH和算法SRA進行優(yōu)化，最終的完工時間均未超過截止期DL，因此可以采用且所得最大完工準確率為E1=0622、E2=0670。對于算法ODSH，算法SRA的優(yōu)化提高率IR=（E2-E1）/E1×100%=771%。因此，算法SRA較傳統(tǒng)單項目標優(yōu)化算法具有更好的優(yōu)化效果。

6不同截止期DL對算法性能的影響

截止期DL是加工任務必須遵守的完工限定時間，是工作流中重要的參數(shù)。一般情況下，截止期的變大使得最佳路徑的完工準確率有所提高。算法SRA正是基于此參數(shù)的約束前提下，對各生產(chǎn)任務進行的優(yōu)化。若改變DL值，則工作流中各加工任務r的自由度FDr也將進行改變，這使得自由度變大的任務可以選擇準確率更高的服務，相反，自由度變小的任務由于不能超過最晚完工時間只能選擇準確率較小的服務。對于案例所述工作流模型，不同截止期DL對算法性能影響的數(shù)據(jù)如表2所示。

分析表2可知，增大DL值，相對以時間最小化和以準確率最大化為目標的算法，算法SRA的提高率隨之增大。因此，可通過適當增加工程要求的截止期，來達到增加算法SRA優(yōu)化性能的目的。

7結(jié)語

針對時間約束下工作流生產(chǎn)精確率難于優(yōu)化等問題，本文提出了一種串歸約的時間-精確率優(yōu)化算法SRA。該算法采用分層的思想并由后向前循環(huán)迭代，求得每層任務的自由度。在每個任務的自由度范圍內(nèi)，算法選擇最佳服務，從而達到優(yōu)化整體加工準確率的目的。案例分析表明，先對于傳統(tǒng)優(yōu)化算法ODSH和ODSE，算法SRA的性能提高了771%。未來的工作將圍繞時間、精確率和成本等三方面以上因素來優(yōu)化工作流調(diào)度。

參 考 文 獻：

[1]I FOSTER C KESSELMAN，J M Nick， et al Grid Service for Distributed System Integration [J]. IEEE Computer，2002，35（6）：37-46

[2]DEELMANL E， BLYTHEL J Mapping Abstract Complex Workflows onto Grid Environments[J]. Journal of Grid Computing，2003，1（1）：25-39

[3]EDMONDS J，KARPR M Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems[J]. Journal of the ACM，2002，19（2）：248-264

[4]ALONSO G， CASATIF， KUNO H， et al Web Service Concepts， Architectures and Applications[M].Berlin： Springer，2004

[5]DUSTDAR S，SCHREINER W A Survey on Web Services Compositions[J]. International Journal of Web and Grid Services， 2005， 1（1）：1-30

[6]CHELLAMMAL S， GOPINATH G， MANIKANDAN S R An Approach for Selecting Best Available Services Through a New Method of Decomposing QoSconstraints[J]. Service Oriented Computing and Applications，2015，9（2）：107-138

[7]DE P， DUNNER E J， GHOSH J B， Wells C E Complexity of the Discrete Timecost Tradeoff Problem for Project Networks[J]. Operations Research， 1997， 45（2）： 302- 306

[8]BUYYA R， DAVID ABRAMSON， JONATHAN GIDDY， et al Economic Models for Resource Management and Scheduling in Grid Computing Concurrency and computation[J]. Practice and Experience Journal， Special Issue on Grid Computing Environment， 2002，14（13/15）： 1507-1542

[9]ABRAMSON D，BUYYA R，GIDDY J A Computational Economy for Gird Computing and Its Implementation in the NimrodG Resource Broker[J]. Future Generation Computer Systems（FGCS） Journal，2002，18（8）：1061-1074

[10]ADNENE G，F(xiàn)RANCOIS C Multiple Instantiation in a Dynamic Workflow Environment[C]//Proceedings of 16th International Conference on Advanced Information Systems Engineering，2004：175-188

[11]AKKAN C， DREX I A， KIMMS A Network Decompositionbased Bench Mark Results for the Discrete Timecost Tradeoff Problem[J].European Journal of Operational Research，2005， 165（2）： 339-358

[12]PAWEL CZAMUL Modeling， Runtime Optimization and Execution of Distributed Workflow Applications in the JEEbased BeesyClusterenvironment[J]. The Journal of Supercomputing， 2013， 63（1）：46-71

[13]MACIEJ M， KAMIL F， MARIAN B， et al Cost Optimization of Execution of Multilevel DeadlineConstrained Scientific Workflows on Clouds[C]// Parallel Processing and Applied Mathematics，2014，8384： 251-260

[14]WOOJOONG K， DONGKI K， SEONGHWAN K， et al Cost adaptive VM Management for Scientific Workflow Application in Mobile Cloud[C]// Mobile Networks and Application， 2015，20（3）： 328-336

[15]張偉，秦臻，苑迎春 網(wǎng)格環(huán)境下工作流的費用-時間調(diào)度算法[J].計算機工程，2006，32（16）：97-99

[16]武星，卓少劍，張武成本最優(yōu)化工作流技術(shù)驅(qū)動的研發(fā)協(xié)同軟件即服務應用[J].計算機集成制造系統(tǒng)， 2013， 19 （8）： 1748- 1754

[17]陳成，薛恒新，張慶民 基于本體與多Agent的可靠供應鏈網(wǎng)絡設(shè)計模型[J].計算機集成制造系統(tǒng)， 2011，17（1）： 142-150

[18]羅智勇，孫廣路，劉嘉輝，等 攻擊圖算法在入侵防御系統(tǒng)中的應用[J].云南大學學報， 2012，34（3），271-275

[19]羅智勇，尤波，許家忠，等 基于三層攻擊圖的入侵意圖自動識別模型[J].吉林大學學報， 2014， 44（5）：1392-1397

[20]苑迎春，李小平，王茜，等 基于逆向分層的網(wǎng)格工作流調(diào)度算法[J].計算機學報，2008， 31（2）： 282-290

（編輯：溫澤宇）