許廣繁

[摘 ? ?要] 為使工作流中的任務(wù)能根據(jù)內(nèi)外部因素的變化進(jìn)行自適應(yīng)調(diào)度，在分布式工作流模型的基礎(chǔ)上，通過基于數(shù)據(jù)驅(qū)動(dòng)，引入流程版本信息和優(yōu)化彈簧算法對(duì)工作流中的任務(wù)進(jìn)行動(dòng)態(tài)負(fù)載平衡調(diào)度，提出了一種數(shù)據(jù)驅(qū)動(dòng)的柔性分布式工作流自適應(yīng)任務(wù)調(diào)度方法，以支持工作流中的任務(wù)動(dòng)態(tài)自適應(yīng)調(diào)整，以使系統(tǒng)更好地適應(yīng)環(huán)境、優(yōu)化流程、提高效率。

[關(guān)鍵詞] 分布式工作流;任務(wù)調(diào)度;數(shù)據(jù)驅(qū)動(dòng);自適應(yīng)調(diào)度

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2019. 19. 067

[中圖分類號(hào)] TP311 ? ?[文獻(xiàn)標(biāo)識(shí)碼] ?A ? ? ?[文章編號(hào)] ?1673 - 0194（2019）19- 0157- 02

1 ? ? ?概 ? ?述

工作流是指業(yè)務(wù)流程完全或部分自動(dòng)化運(yùn)行[1]，它通過將工作活動(dòng)分解成定義明確的任務(wù)、角色、規(guī)則和過程，來完成工作的整體執(zhí)行和監(jiān)控，是現(xiàn)實(shí)生活中各種工作活動(dòng)在信息世界中的映像。同時(shí)，由于業(yè)務(wù)的發(fā)展、客戶需求的變更及科學(xué)技術(shù)的更新，工作流需要根據(jù)內(nèi)外部因素的變化進(jìn)行自適應(yīng)調(diào)整以使系統(tǒng)適應(yīng)環(huán)境、優(yōu)化流程、提高效率和提升收益。

因工作流的任務(wù)調(diào)度在對(duì)任務(wù)的運(yùn)行、管理、監(jiān)控及分析執(zhí)行過程等方面的作用較為重要。文獻(xiàn)[2]對(duì)柔性工作流理論方法進(jìn)行全面的綜述，并對(duì)各種方法的優(yōu)缺點(diǎn)和適用領(lǐng)域進(jìn)行了對(duì)了對(duì)比分析。文獻(xiàn)[3]則提出了一種基于比例-積分-微分控制的自適應(yīng)任務(wù)調(diào)度方法，以提高分布式工作流中實(shí)時(shí)任務(wù)調(diào)度的效率。文獻(xiàn)[4]則在業(yè)務(wù)流程模型的基礎(chǔ)上提出了一種業(yè)務(wù)流程變更自適應(yīng)模型。但在最初的工作流程定義時(shí)就考慮到所有可能的業(yè)務(wù)流程，并完整精確地將流程模型中的每個(gè)細(xì)節(jié)都清晰地制定出來是極為困難的，因此傳統(tǒng)的工作流技術(shù)已不能滿足企業(yè)對(duì)日益增長(zhǎng)的內(nèi)外部資源的統(tǒng)一利用和企業(yè)間相互協(xié)作的迫切需求。而基于數(shù)據(jù)驅(qū)動(dòng)的分布式工作流可有效克服傳統(tǒng)的工作流的局限性，從而能很好地對(duì)業(yè)務(wù)工作進(jìn)行建模，具有良好的可擴(kuò)展性及互操作性，實(shí)現(xiàn)自適應(yīng)的任務(wù)調(diào)度，動(dòng)態(tài)細(xì)化具體的執(zhí)行路徑，帶來更強(qiáng)的柔性和可靠性。

2 ? ? ?數(shù)據(jù)驅(qū)動(dòng)的分布式工作流模型

基于Petri網(wǎng)流程模型[5]，通過結(jié)合控制流和數(shù)據(jù)流建模與分析，引入工作流版本信息、業(yè)務(wù)流程圖、流程任務(wù)信息及優(yōu)化彈簧算法，提出一種基于數(shù)據(jù)驅(qū)動(dòng)的柔性分布式工作流自適應(yīng)任務(wù)調(diào)度方法，實(shí)現(xiàn)工作流的可擴(kuò)展性、柔韌性、動(dòng)態(tài)性及自適應(yīng)性，以適應(yīng)大吞吐量要求的高性能及實(shí)現(xiàn)處理復(fù)雜業(yè)務(wù)流程的能力。

2.1 ? 工作流版本信息

工作流版本信息是服務(wù)單流程信息中一個(gè)簡(jiǎn)化的數(shù)據(jù)集，可描述為：

F=（F_ID，F(xiàn)D，L）（1）

其中，F(xiàn)_ID是當(dāng)前工作流版本號(hào);FD是服務(wù)單數(shù)據(jù)子集，包括服務(wù)單ID和服務(wù)單當(dāng)前狀態(tài);L是業(yè)務(wù)流程，代表工作流任務(wù)及事件的邏輯關(guān)系，其是由事件和任務(wù)及其相關(guān)關(guān)系組成的有向無環(huán)圖，表示流程實(shí)例的執(zhí)行方向;流程實(shí)例中的工作流程版本信息F包含業(yè)務(wù)流程L及流程實(shí)例狀態(tài)數(shù)據(jù)。

2.2 ? 工作流版本信息

工作流約束指的是在工作流定義時(shí)必須滿足且在運(yùn)行及變更時(shí)也必須滿足的規(guī)則。為確保業(yè)務(wù)流程按給定的方向流轉(zhuǎn)和業(yè)務(wù)流程自適應(yīng)調(diào)整時(shí)版本正確的決策及系統(tǒng)的穩(wěn)定，防止業(yè)務(wù)流程進(jìn)入死循環(huán)和出現(xiàn)未知的執(zhí)行結(jié)果，業(yè)務(wù)流程需滿足相關(guān)約束。

（1）版本約束。任意流程實(shí)例在某一給定的時(shí)刻僅允許按照某一特定的流程執(zhí)行。

（2）隔離約束。任意流程實(shí)例的執(zhí)行都必須互相獨(dú)立，互不影響，流程實(shí)例對(duì)應(yīng)的服務(wù)單據(jù)間沒有直接的訪問聯(lián)系。

（3）更新約束。不允許出現(xiàn)任務(wù)事件沖突、任務(wù)順序沖突和流程方向沖突，若出現(xiàn)則將禁止本次流程中的任務(wù)調(diào)度。任務(wù)事件沖突指的是兩個(gè)任務(wù)由一個(gè)事件引發(fā)或一個(gè)事件可有兩個(gè)任務(wù)相對(duì)應(yīng);任務(wù)順序沖突指的是某一任務(wù)的前序任務(wù)也是其后序任務(wù)，導(dǎo)致出現(xiàn)回路;流程方向沖突指的是存在路徑到達(dá)某一中間事件，但卻終止于該中間事件，導(dǎo)致該事件的后序任務(wù)無法執(zhí)行。

2.3 ? 任務(wù)調(diào)整策略

任務(wù)調(diào)節(jié)策略使用的是優(yōu)化的彈簧算法。彈簧算法的思想是通過將系統(tǒng)中的每一個(gè)任務(wù)負(fù)載當(dāng)成一根單獨(dú)的彈簧，將系統(tǒng)中的任務(wù)集當(dāng)作具有前后續(xù)關(guān)聯(lián)的彈簧集，通過對(duì)每根彈簧的彈性系數(shù)進(jìn)行調(diào)整來實(shí)時(shí)反映每個(gè)任務(wù)的負(fù)載變化，進(jìn)而實(shí)現(xiàn)對(duì)整個(gè)系統(tǒng)任務(wù)負(fù)載調(diào)節(jié)。

記實(shí)時(shí)任務(wù)T=（D，Zmin，Zmax，Q，Vmin，Vmax），其中D表示任務(wù)到達(dá)時(shí)間，Zmin表示任務(wù)最小的執(zhí)行時(shí)間，Zmax表示任務(wù)最大的執(zhí)行時(shí)間，Q表示任務(wù)的截止時(shí)間，Vmin表示任務(wù)最小到達(dá)時(shí)間間隔，Vmax表示任務(wù)最大到達(dá)時(shí)間間隔。其中任務(wù)必須要在到達(dá)時(shí)間D之后的截止時(shí)間Q內(nèi)完成，任務(wù)負(fù)載W=Z/V，其取值范圍為W∈[Wmin，Wmax]，其中Wmin=Zmin/Vmax，Wmax=Zmax/Vmin。則單個(gè)任務(wù)的負(fù)載調(diào)整策略為：

Ci=Ci0-（Cv0+Cf-Cq）■（2）

其中，Ci為任務(wù)Ti調(diào)節(jié)前的負(fù)載值，Ci0為任務(wù)Ti調(diào)節(jié)后的負(fù)載值，Cv0表示所有可調(diào)節(jié)任務(wù)的負(fù)載值之和，Cf表示所有不可調(diào)節(jié)任務(wù)的負(fù)載值之和，Cq為期望調(diào)節(jié)負(fù)載值，Ev為所有可調(diào)節(jié)任務(wù)的彈性系數(shù)之和，其任務(wù)的彈性系數(shù)為Ei=max■

2.4 ? 任務(wù)分配策略

負(fù)載平衡調(diào)度方法是一種解決流程引擎負(fù)載過重的調(diào)度方法，通過在以數(shù)據(jù)驅(qū)動(dòng)的分布式工作流中引進(jìn)彈簧算法調(diào)整策略，假定每個(gè)任務(wù)結(jié)點(diǎn)都是動(dòng)態(tài)產(chǎn)生的，本任務(wù)分配策略僅考慮動(dòng)態(tài)負(fù)載平衡調(diào)度，對(duì)工作流中的任務(wù)進(jìn)行分配時(shí)，考慮所有的流程引擎資源，且只有當(dāng)某一任務(wù)完全執(zhí)行成功后方能去調(diào)整流程狀態(tài)，當(dāng)某一任務(wù)的絕對(duì)最早開始時(shí)間和絕對(duì)最晚開始時(shí)間確定時(shí)，則僅考慮能為此任務(wù)提供最小執(zhí)行時(shí)間的流程引擎，而當(dāng)任務(wù)被分配到指定的流程引擎時(shí)，則其執(zhí)行時(shí)間和傳輸時(shí)間也同步進(jìn)行更新。

如果任務(wù)調(diào)度時(shí)的絕對(duì)最早開始時(shí)間和絕對(duì)最晚開始時(shí)間相等，則該任務(wù)處于流程的關(guān)鍵路徑上，且在每次任務(wù)分配時(shí)，將關(guān)鍵路徑上的任務(wù)按絕對(duì)最早開始時(shí)間從小到大進(jìn)行順序選擇，在確定了關(guān)鍵路徑上的關(guān)鍵任務(wù)后，檢查流程引擎上任務(wù)負(fù)載狀態(tài)與其他狀態(tài)的信息是否一致。若一致，則選擇能為該任務(wù)提供最小執(zhí)行時(shí)間的流程引擎來執(zhí)行該任務(wù);若不一致，則把該任務(wù)送到負(fù)載指數(shù)最小的臨近任務(wù)中，根據(jù)工作流版本信息和流程任務(wù)信息，按任務(wù)執(zhí)行時(shí)間和負(fù)載信息根據(jù)彈簧算法對(duì)任務(wù)進(jìn)行重新計(jì)算，并根據(jù)最優(yōu)路徑對(duì)任務(wù)調(diào)整。

2.5 ? 任務(wù)調(diào)度策略

基于數(shù)據(jù)驅(qū)動(dòng)的分布式工作流對(duì)當(dāng)前的活動(dòng)、事件及狀態(tài)相關(guān)參數(shù)進(jìn)行處理，當(dāng)任務(wù)及事件分配到特定的流程引擎后，流程引擎根據(jù)工作流版本信息和優(yōu)化彈簧算法進(jìn)行任務(wù)調(diào)度，在該負(fù)載均衡調(diào)度算法中，任務(wù)的權(quán)重和優(yōu)先級(jí)是動(dòng)態(tài)調(diào)整和變更的，系統(tǒng)中的任務(wù)和事件在任意時(shí)刻按其截止時(shí)間從早到晚進(jìn)行順序排列，版本信息越新和任務(wù)截止時(shí)間越早，則優(yōu)先級(jí)越高，反之則越低。流程引擎在任務(wù)調(diào)度時(shí)，會(huì)對(duì)滿足條件的任務(wù)進(jìn)行動(dòng)態(tài)排序，并選擇具有最早截止時(shí)間的任務(wù)及事件進(jìn)行調(diào)度。

3 ? ? ?結(jié) ? ?語

實(shí)時(shí)任務(wù)調(diào)度是保證系統(tǒng)實(shí)時(shí)處理的關(guān)鍵，而處理實(shí)時(shí)任務(wù)工作流兼顧分布式和實(shí)時(shí)性等特點(diǎn)，為提升系統(tǒng)的吞吐量和相應(yīng)時(shí)間，本文對(duì)在分布式工作流研究的基礎(chǔ)上，通過基于數(shù)據(jù)驅(qū)動(dòng)，引入流程版本信息和優(yōu)化彈簧算法對(duì)任務(wù)進(jìn)行動(dòng)態(tài)負(fù)載均衡調(diào)度，提出了一種數(shù)據(jù)驅(qū)動(dòng)的柔性分布式工作流自適應(yīng)任務(wù)調(diào)度方法，以支持工作流中的任務(wù)動(dòng)態(tài)自適應(yīng)調(diào)整以使系統(tǒng)更好地適應(yīng)環(huán)境、優(yōu)化流程、提高效率。

主要參考文獻(xiàn)

[1]Nathanid Palmer.Workflow Management Coalition[M].NewYork，NY：Springer，2016.

[2]李競(jìng)杰，王維平，楊峰. 柔性工作流理論方法綜述[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2010，16（8）： 1569-1577.

[3]譚宜甬，王銳，范玉順，等. 分布式工作流中的自適應(yīng)實(shí)時(shí)任務(wù)調(diào)度方法[J] . 計(jì)算機(jī)集成制造系統(tǒng)， 2010， 16（9）： 1887-1895.

[4]李帥，于守健. 以數(shù)據(jù)為中心的業(yè)務(wù)流程變更自適應(yīng)技術(shù)研究[J]. 智能計(jì)算機(jī)與應(yīng)用， 2016， 6（1）： 36-43.

[5]袁崇義. Petri網(wǎng)原理與應(yīng)用[M]. 北京：電子工業(yè)出版社， 2005： 58-62.