MSTC 網及調度算法小探

這是一篇關於mstc 網及調度算法小探的畢業論文提綱，歡迎瀏覽借鑑！

1 引言

工作流是一類能夠完全或者部分自動執行的經營過程，它根據一系列過程規則、文檔、信息或任務能夠在不同的執行者之間進行傳遞與執行，工作流管理系統是一個軟件系統，它完成工作流的定義和管理，並按照在計算機中預先定義好的工作流邏輯推進工作流實例的執行。工作流引擎是整個工作流管理系統的基礎，其功能直接決定了工作流管理系統的應用範圍和對變化的適應能力。工作流引擎的核心是工作流過程模型和流程的調度算法，工作流過程模型是對業務流程的抽象表示，而調度算法則是流程執行的控制規則，兩者共同實現了業務流程的自動執行。

工作流過程模型方面，有向圖模型最早被用來建立工作流模型，如流程圖、狀態圖等、活動網絡圖、epcm 模型（event-driven process chain，事件過程鏈模型）等。h.a. reijers等學者將event-driven process chains 擴展提出aggregate epc (aepc)模型，用一個統一的模型來描述一系列相似的業務流程。petri 網技術也是工作流建模的常用方法之一，如van deraalst 在petri 網的基礎上提出了工作流網wf-net，並進一步研究提出了一種新的工作流建模語言yawl，kees van hee 等學者基於工作流網提出了一個過程模型和數據模型的融合方法。jan hidders 等學者基於petri 網和嵌套關係演算理論提出了一個新的數據流語言。

也有人通過把已有的建模方法（如e-r 圖、面向對象方法）與有向圖模型相結合，以更有針對性地面向某些領域進行過程建模，如thomas allweyer 把epcm 與面向對象的uml 相結合，用於面向對象的業務過程建模。除了有向圖模型外，其它領域的工作流模型研究也取得了不少成果。如kacmar、carey 和alexaander 等人提出了基於活動樹（activity tree）的模型；範玉順、吳澄等提出一種基於協調理論和反饋機制的工作流建模方法，該方法擴展了傳統活動網絡模型；andreas geppert 等提出了代理/服務（broker/services）模型；winograd 和flores 在語言行為理論的基礎上提出了一種基於對話的工作流模型等。

工作流引擎任務調度方面，當前的研究主要集中在調度策略和調度算法兩個方面。調度策略分為靜態調度和動態調度兩種。靜態調度是在工作流建模時就綁定相應的資源，缺點是資源效率較低。動態調度在建模時只綁定資源的描述，因此在調度時能根據實際情況來利用合適的資源來執行任務，資源效率較高，缺點是存在資源競爭問題。tretola 等人還提出了一些考慮子任務內並行性的預調度策略來加快工作流的執行。

本文首先介紹了一種新的工作流過程模型——多步任務協同網（mstc nets），一個由角色(role，r)，任務(task，t)，工作(work，w)和轉發(deliver，d)構成的網絡，r 表示流程的參與者，而t 則描述了流程的業務活動， w 表示角色在任務中的分工，而d 用於表示業務流程的流轉方向（可以是有條件的），一個任務可以由多個角色共同完成，這種區別不僅使其更貼近於實際的業務流程，還使其獲得了更為強大的業務流程描述能力和更為豐富的信息加工能力。同時，由於w 表示角色在任務中的分工，改善了模型對角色及其和任務的交互關係的處理能力（例如可更好地處理由角色引起的異常）。為了更好的描述mstc 網的動態運行狀態，在其基礎上增加了轉發條件、起始工作、分組和循環的描述，構成mstc網系統。針對mstc 網系統的特點，我們研究了並給出了其8 個調度算法，並進行詳細分析。

本文第一節給出mstc 網的定義和相關概念，形式化的數學語義描述為進一步的深入研究提供基礎，直觀的圖形化描述為過程建模提供良好的圖形表示方法。第二節在建立了mstc 網中各建模元素的狀態集合的基礎上，對mstc 網的調度方法進行了深入研究。第三節通過案例解析詳細解釋了調度方法的調度過程。最後是小結。

2 mstc 網的定義和相關概念

2.1 mstc 網

定義 1（mstc 網，multi-step task collaborative nets）一個四元組n＝（r，t；w，d）是一個mstc 網的充分必要條件是：

（1）r ≠φ ；

（2）t ≠φ ；

（3）r ∩t =φ ；

（4）w ? r×t ；

（5）d ? t × r ；

（6）dom(w)∪cod(w) = r ∪t 。

其中，dom(w) = {x | ?y：(x，y)∈w}，cod (w) = {y | ?x：(x，y)∈w}.

mstc 網的定義中，r 和t 是基本成分，w 和d 是由r 和t 構造出來的，所以在定義中將r、t和w、d 用分號‘；’隔開。r和t是兩類不同的概念，所以r ∩t =φ 。r ≠φ 和t ≠φ表示在mstc 網中至少要有1 個角色和1 個任務。dom(w)∪cod(w) = r ∪t 表示在mstc網中不能有孤立的r 或孤立的t。顯然，mstc 網中至少要有1 個w。

mstc 網是一個由角色（role，r）、任務（task，t）、工作（work，w）和轉發（deliver，d）構成的網絡。其中，r 是一個有限的角色集合，表示參與業務流程的人；t 是一個有限的任務集合，表示網中的邏輯工作單元，必須完整執行，如申請、審核、會籤、投票等；w是一個有限的工作集合，表示角色在事務中的分工，如閲文、填表、批示等；d 是一個有限的轉發集合，表示任務完成後業務的流轉方向。

在一個mstc 網中，r 和t 是基本成分，稱為節點（node），w 和d 是由r 和t 構造出來的有向弧，稱為連接（connection）。

2.2 多mstc 網

定義 2（多mstc 網）一個六元組m＝（r，t；w，d；cn；dn）是一個多mstc 網，如果m 滿足以下的條件：

（1）n＝（r，t；w，d）是一個mstc 網，稱為m 的基網（basic-net）；

（2）cn 是一個有限的mstc 網集合；

（3）cn={n1，n2，…，nm}，ni 是一個mstc 網，m 為正整數且m≥1；

（4）dn 是n 和cn 之間的轉發的集合；

（5）dn ? (t × nk )∪ (nl × r)，1≤k≤m, 1≤l≤m；

（6） ( )dom dn ∪ cod(dn ) = r ∪t ∪ n1 ∪ n2 ∪.....∪ nm = r ∪t ∪cn 。

其中， ( ) { ( ) } dom dn = x | ?y：x，y ∈dn ， ( ) { ( ) } cod dn = y | ?x：x，y ∈dn 。

根據定義可知，n 和ni（1≤i≤m）都是m 的子網。dn ? (t × nk )∪ (nl × r)表明dn是n和cn 之間的轉發，稱為網間轉發（net-deliver）。網間轉發只能從n 的t 元素轉發到nk（即t×nk，也稱為網間轉出），或從nl 轉發到n 的r 元素（即nl×r，也稱為網間轉入）。( )dom dn ∪cod(dn ) = r ∪t ∪ n1 ∪ n2 ∪.....∪ nm = r ∪t ∪cn表示在多mstc網中不能有孤立的子網。

2.3 多mstc 網統

mstc 網的定義描述了網的靜態結構特徵，為了更好的描述網的動態運行狀態，需要對網的狀態加以描述，下面首先介紹幾個基本概念。

概念1（起始工作 start work）不依賴於任何轉發的結果就可以開始運行的工作稱為起始工作。mstc 網的運行必須從起始工作開始。一個mstc 網可能有多個起始工作，並且可以從任意一個或多個起始工作開始運行。

概念2（轉發條件 deliver condition）mstc 網中的轉發可能是無條件的，也可能是有條件的。有條件的轉發必須在條件計算結果為真值的前提下，才能執行轉發。轉發所依賴的條件稱為轉發條件。中國代本站為您代寫碩士論文。

概念3（分組 group）角色可異步地接收不同的轉發和辦理不同的工作，然而這些工作和轉發之間可能存在依賴關係。為了描述這種依賴關係，必須對這些轉發和工作進行區分，將有依賴關係的轉發和工作歸併在一起，稱為分組。

概念4（路徑 route）設n＝（r，t；w，d）是一個mstc 網，路徑p 是從節點n1 到節點nk 的序列<n1, n2, …,nk>，其中，<ni，ni+1>∈ w∪d，1≤i≤k-1。

概念5（循環 loop）循環是可被反覆執行的，並只保留最後一次執行信息的環形路徑。

概念6（關聯工作relate-work，關聯轉發relate-deliver、關聯任務relate-task、關聯角色relate-role）若n＝（r，t；w，d）是一個mstc 網，設r 是n 中的任一角色，t 是n 中的任一任務，則我們稱：

（1）rw(t) = {w| ?r : (r,t)∈w}為t的關聯工作，t為rw(t)的關聯任務；

（2）rd(t) = {d | ?r : (t, r)∈d}為t的關聯轉發，t為rd(t)的關聯任務；

（3）rw(r) = {w | ?t : (r,t)∈w}為r的關聯工作，r為rw(r)的關聯角色；

（4）rd(r) = {d | ?t : (t,r)∈d}為r的關聯轉發，r為rd(r)的關聯角色。

定義3（mstc 網系統）一個十元組σ＝（r，t；w，d；cn；dn ；cd，w0，g，l）構成mstc 網系統的充分必要條件是：

（1）m ＝（r，t；w，d；cn；dn）是一個多mstc 網；

（2）cd 是轉發條件的集合；

（3）w0 是起始工作的集合；

（4）g 是分組的集合；

（5）l 是循環的集合。

mstc 網系統比多mstc 網的定義增加了轉發條件、起始工作、分組和循環，能更好地描述真實系統。在不特殊説明的情況下，本文所説的mstc 網就是指mstc 網系統。

2.4 mstc 網系統的圖形表示

任務的圖符用一個矩形表示；工作的圖符為一個帶箭頭的直線，方向從角色指向任務，起始工作用帶空心箭頭的直線表示，而其他工作則為實心箭頭；轉發的圖符為也為一個帶箭頭的直線，方向從任務指向角色，條件轉發用帶空心箭頭的直線表示，而其他轉發則為實心箭頭；分組用標在直線上靠近角色端的數字表示；循環用雙箭頭表示（僅循環用為空心）。

3 mstc 網系統的調度方法研究

在一個具體的案例中，可能存在多個並行執行的任務，並且這些任務的執行時間和順序是完全依賴於多步任務協同網的拓撲結構及相關的轉發條件，因此需要工作流引擎對這些任務的執行進行調度。下面將詳細説明多步任務協同網中多任務的調度方法通常構建並運行一個多步任務協同網的步驟為:

(1) 構建多步任務協同網n＝（r，t；w，d）;

(2) 構建多步任務協同網系統σ＝（r，t；w，d；cn；dn ；cd，w0，g，l）;

(3) 構建調度所需的狀態集合, 包括五個狀態集合:

案例的狀態集合：si = { sir，siw，sif }，案例是多步任務協同網的一次執行，一個多步任務協同網系統可以被多次執行，每次執行都對應一個不同的案例.其中sir 就緒狀態表示案例等待執行的狀態; siw 在辦狀態：案例正在執行的狀態; sif 完成狀態：案例已經結束的狀態.

工作的狀態集合：sw = { swr，sww，swn，swf },其中swr 就緒狀態：工作等待角色辦理的狀態; sww 在辦狀態：工作正在被角色辦理的狀態; swn 否定狀態：工作因條件不滿足不能被角色辦理的狀態; swf 完成狀態：工作已經結束的狀態.

任務的狀態集合：st = { str，stw，stn，stf }，其中str 就緒狀態：任務等待角色辦理的狀態; stw 在辦狀態：任務正在被角色辦理的狀態; stn 否定狀態：任務因條件不滿足不能或不需要被角色辦理的狀態; stf 完成狀態：任務已經結束的狀態.

轉發的狀態集合：sd = { sdr，sdw，sdn，sdf}，其中sdr 就緒狀態：轉發等待被執行的狀態; sdw 待籤狀態：轉發等待被角色簽收的狀態; sdn 否定狀態：轉發因條件不滿足不能或不需要被角色簽收的狀態; sdf 完成狀態：轉發已經結束的狀態.

循環的狀態集合：sl = { s1r，s1w，slf }，其中s1r 就緒狀態：循環等待被執行的狀態; s1w工作狀態：循環正在被執行的狀態; slf 完成狀態：循環已經結束的狀態.

(4) 構建調度所需的調度方法

多步任務協同網系統中的調度方法包括啟動案例、終止案例、角色籤辦任務、角色退回任務、多步任務辦理、多步任務重辦、啟動循環和終止循環八個調度方法. 在多任務調度之前，案例和所有的工作、任務、轉發、循環都被初始化為就緒狀態。啟動案例是第一個被執行的調度，角色籤辦任務、角色退回任務、多步任務辦理、多步任務重辦、啟動循環和終止循環是根據多步任務協同網系統的流向，包括正向和逆向，由角色進行執行的，終止案例的調度是根據工作和轉發的狀態由系統自動執行的.令：setstatus(x) 表示設置對象x 的狀態，x可以為案例、任務、工作、轉發或循環；getstatus(x) 表示獲得對象x 的狀態，x 為案例、任務、工作、轉發或循環；setrole(x)表示設置對象所屬角色，x 為工作或轉發；getrole(x)表示獲得對象所屬角色，x 可以為工作或轉發；precondition(x)表示條件計算，結果為ture或false，x 為轉發；count(x)表示集合中對象的數目，x 為一個對象集合。

3.1 啟動案例的調度方法

一個多步任務協同網系統可以被多次執行，每次執行都對應一個不同的案例。

執行該調度方法之後，多步任務協同網系統就進入到運行狀態，此後各個元素將逐一轉變狀態直至案例結束。

3.2 終止案例的調度方法

該調度算法有多步任務協同網系統自動執行，即系統會根據需要執行該方法以檢查案例是否可以結束。

3.3 角色籤辦任務的調度方法

當角色的某組關聯轉發全部為否定或待籤且至少有一個為待籤時，該角色才能籤辦改組轉發以及相關的任務，同時同組的工作也會轉到在辦狀態。

3.4 角色退回任務的調度方法

當角色辦理工作時發現之前的工作存在問題時可以要求前驅角色重新辦理任務，此時該角色的工作將退回到就緒狀態，關聯轉發也會退回到就緒狀態，所需重辦的工作和任務則轉變為在辦狀態。

3.5 多步任務辦理的調度方法

當所有工作完成或否定且至少有一個完成的話，任務就辦理完成了。此時，關聯轉發根據設定的條件轉變為待籤或者否定。

3.6 任務重辦的調度方法

當工作未完成或者工作完成但還沒有簽收時，角色可以要求前驅角色重辦與之相關的工作，即退回已經籤辦的工作。

3.7 啟動循環的調度方法

3.8 終止循環的調度方法

4 案例簡析

設所示案例i 中有6 個角色（r1、r2、r3、r4、r5 和r6）和7 個任務（t1、t2、t3、t4、t5、t6、t7），其中任務t1、t5 和t7 是多步任務（由多個角色協同完成），工作w1_1、w1_2 和w_5 是啟動工作，轉發d1_1 和d1_2 是條件轉發，在r6 上定義了2 個分組，d2 和w6_2 為分組g1，d1_2 和w6_1 為分組g2，其它所有沒有定義分組的客户機默認為同一個分組，w2_1、d4、w3_1 和d3 是一個循環l。

4.1 案例i 的正向調度示例

(1)當案例i 啟動後，s(i) = siw，s(w1_1) = sww，s(w1_2) = sww，s(w5) = sww，s(t1) = stw，s(t2) = stw；

(2)由圖14 中可以看出，t1 由r1 和r5 同時負責，對應工作w1_1 和w5，t2 由r1 負責，對應工作w1_2；

(3)當w1_1 和w5 辦理完畢後，即s(w1_1) = swf，s(w5) = swf，則t1 完成，即s(t1) = stf，由於d1_1 和d1_2 是條件轉發，需要根據條件設置進行條件判斷，這裏假設p(d1_1) = true，p(d1_2) = false，則s(d1_1) = sdw，s(d1_2) = sdn；

(4)當w1_2 辦理完畢後，s(w1_2) = swf，s(t2) = stf，s(d2) = sdw；

(5)r2 沒有定義分組，默認所有轉發和工作為同一分組。由於d3 為僅循環用（啟動循環運行時才有效），這裏假設不啟動循環，所以r2 可以籤辦任務t1，籤辦後，s(d1_1) = sdf，s(w2_1) = sww，s(w2_2) = sww，s(t4) = stw，s(t5) = stw；

(6)r6 上定義了2 個分組，d2 和w6_2 為分組g1，d1_2 和w6_1 為分組g2。對於g1，r6籤辦任務t2 後，s(d2) = sdf，s(w6_2) = sww，s(t6) = stw。對於g2，由於s(d1_2) = sdn，所以s(w6_1) = swn；

(7)當w2_1 辦理完畢後，s(w2_1) = swf，s(t4) = stf，s(d4) = sdw；

(8)當w2_2 辦理完畢後，s(w2_2) = swf，由於s(w6_1) = swn，所以s(t5) = stf，s(d5_1) =sdw，s(d5_2) = sdw；

(9)當w6_2 辦理完畢後，s(w6_2) = swf，s(t6) = stf；

(10)r3 沒有定義分組，默認所有轉發和工作為同一分組。由於w3_1 為僅循環用，這裏假設不啟動循環，所以r3 籤辦任務t4 和t5 後，s(d4) = sdf，s(d5_1) = sdf，s(w3_2) = sww；

(11)r4 沒有定義分組，默認所有轉發和工作為同一分組。r4 籤辦任務t5 後，s(d5_2) = sdf，s(w4) = sww；

(12)當w3_2 和w4 辦理完畢後，s(w3_2) = swf，s(w4) = swf，s(t7) = stf，由於i 中沒有任何一個w 處於待辦狀態且沒有一個d 處於待籤狀態，所以案例i 結束，即s(i) = sif。

4.2 案例的逆向調度過程示例

(1)角色重辦任務

設案例i 正向調度到第（4）步，由於s(d1_1) = sdw，s(d1_2) = sdn，所以r5 可以重辦t1，r1 可以重辦t1 和t2。這裏設r1 重辦t1，重辦後，s(d1_1) = sdr，s(d1_2) = sdr，s(t1) = stw，s(w1_1) = sww。

(2) 角色退回任務

設案例i 正向調度到第（6）步，由於s(w2_1) = sww，s(w2_2) = sww，s(w6_1) = swn，s(w6_2) = sww，s(t4) = stw，s(t5) = stw，s(t6) = stw，所以r2 和r6 都可以退回任務。這裏設r6 退回分組g1 的籤辦的任務t2，則s(w6_2) = swr，s(d2) = sdw。可以看出，當r6 退回籤辦的t2 後，r1 還可以重辦w1_2，從而連續實現多步任務調度過程中的逆向。

4.3 案例的循環調度過程示例

設案例 i 正向調度到第（10）步，r3 啟動循環l，則s(l) = slw，s(w3_1) = sww，s(t3) = stw；當w3_1 辦理完畢後，s(w3_1) = swf，s(t3) = stf，s(d3) = sdw；這時，r2 可以籤辦任務t3，由於循環將路徑中工作、任務和轉發統一按照就緒狀態處理，而w2_2 不在循環中，所以籤辦後s(d3) = sdf，s(w2_1) = sww，s(t4) = stw；當w2_1 辦理完畢後，s(w2_1) = swf，s(t4) =stf，s(d4) = sdw；此時r3 如果終止循環，則s(l) = slf，循環結束，如果不終止循環，r3 可以接着辦理w3_1，則s(w3_1) = sww，s(t3) = stw，如此反覆執行直至循環終止。

5 結束語

本文以工作流過程模型mstc 網系統為基礎,研究了其主要的調度方法,最後以案例簡析來展示算法的有效性. mstc 網系統的建模元素主要有角色(r)、任務(t)、工作(w)、轉發(d)，這些建模元素擁有不同的狀態集合，在運行時通過不斷的改變他們所處的狀態最終實現預定的業務流程功能。mstc 網系統的調度算法是案例執行的規則，工作流引擎就是按照不同的調度算法對業務流程中的不同元素進行協同調度，從而實現業務流程的流轉運行。在現實工作流的執行過程中,任務的執行時間和順序是完全依賴於mstc 網的拓撲結構及相關的轉發條件，所以嚴密的調度邏輯對流程的正確執行至關重要。而本文所介紹的8 個調度方法可以全面的控制多步任務協同網的執行。從案例簡析中可以看到，mstc 網系統的調度算法不僅可以實現流程的正向調度，即正常的角色籤辦任務，還可以實現流程的逆向調度，如角色退回任務，並且可以很好的支持循環。

同時，由於多步任務協同網本身的演化，本文所介紹的調度算法可能還會進一步支持一些高級的結構，如子網，多實例等等。