數(shù)據(jù)驅(qū)動的分布式工作流中的任務(wù)調(diào)度方法

許廣繁

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

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

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

[中圖分類號] TP311 ? ?[文獻標識碼] ?A ? ? ?[文章編號] ?1673 - 0194（2019）19- 0157- 02

1 ? ? ?概 ? ?述

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

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

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

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

2.1 ? 工作流版本信息

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

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

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

2.2 ? 工作流版本信息

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

主要參考文獻

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

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

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

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

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