MSTC 網(wǎng)及調(diào)度算法小探

　　這是一篇關(guān)于mstc 網(wǎng)及調(diào)度算法小探的畢業(yè)論文提綱，歡迎瀏覽借鑒！

　　1 引言

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

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

　　也有人通過把已有的建模方法（如e-r 圖、面向?qū)ο蠓椒ǎ┡c有向圖模型相結(jié)合，以更有針對性地面向某些領(lǐng)域進行過程建模，如thomas allweyer 把epcm 與面向?qū)ο蟮膗ml 相結(jié)合，用于面向?qū)ο蟮臉I(yè)務(wù)過程建模。除了有向圖模型外，其它領(lǐng)域的工作流模型研究也取得了不少成果。如kacmar、carey 和alexaander 等人提出了基于活動樹（activity tree）的模型；范玉順、吳澄等提出一種基于協(xié)調(diào)理論和反饋機制的工作流建模方法，該方法擴展了傳統(tǒng)活動網(wǎng)絡(luò)模型；andreas geppert 等提出了代理/服務(wù)（broker/services）模型；winograd 和flores 在語言行為理論的基礎(chǔ)上提出了一種基于對話的工作流模型等。

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

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

　　本文第一節(jié)給出mstc 網(wǎng)的定義和相關(guān)概念，形式化的數(shù)學(xué)語義描述為進一步的深入研究提供基礎(chǔ)，直觀的圖形化描述為過程建模提供良好的圖形表示方法。第二節(jié)在建立了mstc 網(wǎng)中各建模元素的狀態(tài)集合的基礎(chǔ)上，對mstc 網(wǎng)的調(diào)度方法進行了深入研究。第三節(jié)通過案例解析詳細解釋了調(diào)度方法的調(diào)度過程。最后是小結(jié)。

　　2 mstc 網(wǎng)的定義和相關(guān)概念

　　2.1 mstc 網(wǎng)

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

　　（1）r ≠φ ；

　　（2）t ≠φ ；

　　（3）r ∩t =φ ；

　�。�4）w ? rt ；

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

　　mstc 網(wǎng)是一個由角色（role，r）、任務(wù)（task，t）、工作（work，w）和轉(zhuǎn)發(fā)（deliver，d）構(gòu)成的網(wǎng)絡(luò)。其中，r 是一個有限的角色集合，表示參與業(yè)務(wù)流程的人；t 是一個有限的任務(wù)集合，表示網(wǎng)中的邏輯工作單元，必須完整執(zhí)行，如申請、審核、會簽、投票等；w是一個有限的工作集合，表示角色在事務(wù)中的分工，如閱文、填表、批示等；d 是一個有限的轉(zhuǎn)發(fā)集合，表示任務(wù)完成后業(yè)務(wù)的流轉(zhuǎn)方向。

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

　　2.2 多mstc 網(wǎng)

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

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

　�。�2）cn 是一個有限的mstc 網(wǎng)集合；

　�。�3）cn={n1，n2，…，nm}，ni 是一個mstc 網(wǎng)，m 為正整數(shù)且m≥1；

　�。�4）dn 是n 和cn 之間的轉(zhuǎn)發(fā)的集合；

　�。�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 。

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

　　2.3 多mstc 網(wǎng)統(tǒng)

　　mstc 網(wǎng)的定義描述了網(wǎng)的靜態(tài)結(jié)構(gòu)特征，為了更好的描述網(wǎng)的動態(tài)運行狀態(tài)，需要對網(wǎng)的狀態(tài)加以描述，下面首先介紹幾個基本概念。

　　概念1（起始工作 start work）不依賴于任何轉(zhuǎn)發(fā)的結(jié)果就可以開始運行的工作稱為起始工作。mstc 網(wǎng)的運行必須從起始工作開始。一個mstc 網(wǎng)可能有多個起始工作，并且可以從任意一個或多個起始工作開始運行。

　　概念2（轉(zhuǎn)發(fā)條件 deliver condition）mstc 網(wǎng)中的轉(zhuǎn)發(fā)可能是無條件的，也可能是有條件的。有條件的轉(zhuǎn)發(fā)必須在條件計算結(jié)果為真值的前提下，才能執(zhí)行轉(zhuǎn)發(fā)。轉(zhuǎn)發(fā)所依賴的條件稱為轉(zhuǎn)發(fā)條件。中國代第一范文網(wǎng)為您代寫碩士論文。

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

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

　　概念5（循環(huán) loop）循環(huán)是可被反復(fù)執(zhí)行的，并只保留最后一次執(zhí)行信息的環(huán)形路徑。

　　概念6（關(guān)聯(lián)工作relate-work，關(guān)聯(lián)轉(zhuǎn)發(fā)relate-deliver、關(guān)聯(lián)任務(wù)relate-task、關(guān)聯(lián)角色relate-role）若n＝（r，t；w，d）是一個mstc 網(wǎng)，設(shè)r 是n 中的任一角色，t 是n 中的任一任務(wù)，則我們稱：

　�。�1）rw(t) = {w| ?r : (r,t)∈w}為t的關(guān)聯(lián)工作，t為rw(t)的關(guān)聯(lián)任務(wù)；

　�。�2）rd(t) = {d | ?r : (t, r)∈d}為t的關(guān)聯(lián)轉(zhuǎn)發(fā)，t為rd(t)的關(guān)聯(lián)任務(wù)；

　�。�3）rw(r) = {w | ?t : (r,t)∈w}為r的關(guān)聯(lián)工作，r為rw(r)的關(guān)聯(lián)角色；

　　（4）rd(r) = {d | ?t : (t,r)∈d}為r的關(guān)聯(lián)轉(zhuǎn)發(fā)，r為rd(r)的關(guān)聯(lián)角色。

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

　�。�1）m ＝（r，t；w，d；cn；dn）是一個多mstc 網(wǎng)；

　�。�2）cd 是轉(zhuǎn)發(fā)條件的集合；

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

　�。�4）g 是分組的集合；

　�。�5）l 是循環(huán)的集合。

　　mstc 網(wǎng)系統(tǒng)比多mstc 網(wǎng)的定義增加了轉(zhuǎn)發(fā)條件、起始工作、分組和循環(huán)，能更好地描述真實系統(tǒng)。在不特殊說明的情況下，本文所說的mstc 網(wǎng)就是指mstc 網(wǎng)系統(tǒng)。

　　2.4 mstc 網(wǎng)系統(tǒng)的圖形表示

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

　　3 mstc 網(wǎng)系統(tǒng)的調(diào)度方法研究

　　在一個具體的案例中，可能存在多個并行執(zhí)行的任務(wù)，并且這些任務(wù)的執(zhí)行時間和順序是完全依賴于多步任務(wù)協(xié)同網(wǎng)的拓撲結(jié)構(gòu)及相關(guān)的轉(zhuǎn)發(fā)條件，因此需要工作流引擎對這些任務(wù)的執(zhí)行進行調(diào)度。下面將詳細說明多步任務(wù)協(xié)同網(wǎng)中多任務(wù)的調(diào)度方法通常構(gòu)建并運行一個多步任務(wù)協(xié)同網(wǎng)的步驟為:

　　(1) 構(gòu)建多步任務(wù)協(xié)同網(wǎng)n＝（r，t；w，d）;

　　(2) 構(gòu)建多步任務(wù)協(xié)同網(wǎng)系統(tǒng)σ＝（r，t；w，d；cn；dn ；cd，w0，g，l）;

　　(3) 構(gòu)建調(diào)度所需的狀態(tài)集合, 包括五個狀態(tài)集合:

　　案例的狀態(tài)集合：si = { sir，siw，sif }，案例是多步任務(wù)協(xié)同網(wǎng)的一次執(zhí)行，一個多步任務(wù)協(xié)同網(wǎng)系統(tǒng)可以被多次執(zhí)行，每次執(zhí)行都對應(yīng)一個不同的案例.其中sir 就緒狀態(tài)表示案例等待執(zhí)行的狀態(tài); siw 在辦狀態(tài)：案例正在執(zhí)行的狀態(tài); sif 完成狀態(tài)：案例已經(jīng)結(jié)束的狀態(tài).

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

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

　　轉(zhuǎn)發(fā)的狀態(tài)集合：sd = { sdr，sdw，sdn，sdf}，其中sdr 就緒狀態(tài)：轉(zhuǎn)發(fā)等待被執(zhí)行的狀態(tài); sdw 待簽狀態(tài)：轉(zhuǎn)發(fā)等待被角色簽收的狀態(tài); sdn 否定狀態(tài)：轉(zhuǎn)發(fā)因條件不滿足不能或不需要被角色簽收的狀態(tài); sdf 完成狀態(tài)：轉(zhuǎn)發(fā)已經(jīng)結(jié)束的狀態(tài).

　　循環(huán)的狀態(tài)集合：sl = { s1r，s1w，slf }，其中s1r 就緒狀態(tài)：循環(huán)等待被執(zhí)行的狀態(tài); s1w工作狀態(tài)：循環(huán)正在被執(zhí)行的狀態(tài); slf 完成狀態(tài)：循環(huán)已經(jīng)結(jié)束的狀態(tài).

　　(4) 構(gòu)建調(diào)度所需的調(diào)度方法

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

　　3.1 啟動案例的調(diào)度方法

　　一個多步任務(wù)協(xié)同網(wǎng)系統(tǒng)可以被多次執(zhí)行，每次執(zhí)行都對應(yīng)一個不同的案例。

　　執(zhí)行該調(diào)度方法之后，多步任務(wù)協(xié)同網(wǎng)系統(tǒng)就進入到運行狀態(tài)，此后各個元素將逐一轉(zhuǎn)變狀態(tài)直至案例結(jié)束。

　　3.2 終止案例的調(diào)度方法

　　該調(diào)度算法有多步任務(wù)協(xié)同網(wǎng)系統(tǒng)自動執(zhí)行，即系統(tǒng)會根據(jù)需要執(zhí)行該方法以檢查案例是否可以結(jié)束。

　　3.3 角色簽辦任務(wù)的調(diào)度方法

　　當(dāng)角色的某組關(guān)聯(lián)轉(zhuǎn)發(fā)全部為否定或待簽且至少有一個為待簽時，該角色才能簽辦改組轉(zhuǎn)發(fā)以及相關(guān)的任務(wù)，同時同組的工作也會轉(zhuǎn)到在辦狀態(tài)。

　　3.4 角色退回任務(wù)的調(diào)度方法

　　當(dāng)角色辦理工作時發(fā)現(xiàn)之前的工作存在問題時可以要求前驅(qū)角色重新辦理任務(wù)，此時該角色的工作將退回到就緒狀態(tài)，關(guān)聯(lián)轉(zhuǎn)發(fā)也會退回到就緒狀態(tài)，所需重辦的工作和任務(wù)則轉(zhuǎn)變?yōu)樵谵k狀態(tài)。

　　3.5 多步任務(wù)辦理的調(diào)度方法

　　當(dāng)所有工作完成或否定且至少有一個完成的話，任務(wù)就辦理完成了。此時，關(guān)聯(lián)轉(zhuǎn)發(fā)根據(jù)設(shè)定的條件轉(zhuǎn)變?yōu)榇�簽或者否定�?/p>

　　3.6 任務(wù)重辦的調(diào)度方法

　　當(dāng)工作未完成或者工作完成但還沒有簽收時，角色可以要求前驅(qū)角色重辦與之相關(guān)的工作，即退回已經(jīng)簽辦的工作。

　　3.7 啟動循環(huán)的調(diào)度方法

　　3.8 終止循環(huán)的調(diào)度方法

　　4 案例簡析

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

　　4.1 案例i 的正向調(diào)度示例

　　(1)當(dāng)案例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 同時負責(zé)，對應(yīng)工作w1_1 和w5，t2 由r1 負責(zé)，對應(yīng)工作w1_2；

　　(3)當(dāng)w1_1 和w5 辦理完畢后，即s(w1_1) = swf，s(w5) = swf，則t1 完成，即s(t1) = stf，由于d1_1 和d1_2 是條件轉(zhuǎn)發(fā)，需要根據(jù)條件設(shè)置進行條件判斷，這里假設(shè)p(d1_1) = true，p(d1_2) = false，則s(d1_1) = sdw，s(d1_2) = sdn；

　　(4)當(dāng)w1_2 辦理完畢后，s(w1_2) = swf，s(t2) = stf，s(d2) = sdw；

　　(5)r2 沒有定義分組，默認所有轉(zhuǎn)發(fā)和工作為同一分組。由于d3 為僅循環(huán)用（啟動循環(huán)運行時才有效），這里假設(shè)不啟動循環(huán)，所以r2 可以簽辦任務(wù)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簽辦任務(wù)t2 后，s(d2) = sdf，s(w6_2) = sww，s(t6) = stw。對于g2，由于s(d1_2) = sdn，所以s(w6_1) = swn；

　　(7)當(dāng)w2_1 辦理完畢后，s(w2_1) = swf，s(t4) = stf，s(d4) = sdw；

　　(8)當(dāng)w2_2 辦理完畢后，s(w2_2) = swf，由于s(w6_1) = swn，所以s(t5) = stf，s(d5_1) =sdw，s(d5_2) = sdw；

　　(9)當(dāng)w6_2 辦理完畢后，s(w6_2) = swf，s(t6) = stf；

　　(10)r3 沒有定義分組，默認所有轉(zhuǎn)發(fā)和工作為同一分組。由于w3_1 為僅循環(huán)用，這里假設(shè)不啟動循環(huán)，所以r3 簽辦任務(wù)t4 和t5 后，s(d4) = sdf，s(d5_1) = sdf，s(w3_2) = sww；

　　(11)r4 沒有定義分組，默認所有轉(zhuǎn)發(fā)和工作為同一分組。r4 簽辦任務(wù)t5 后，s(d5_2) = sdf，s(w4) = sww；

　　(12)當(dāng)w3_2 和w4 辦理完畢后，s(w3_2) = swf，s(w4) = swf，s(t7) = stf，由于i 中沒有任何一個w 處于待辦狀態(tài)且沒有一個d 處于待簽狀態(tài)，所以案例i 結(jié)束，即s(i) = sif。

　　4.2 案例的逆向調(diào)度過程示例

　　(1)角色重辦任務(wù)

　　設(shè)案例i 正向調(diào)度到第（4）步，由于s(d1_1) = sdw，s(d1_2) = sdn，所以r5 可以重辦t1，r1 可以重辦t1 和t2。這里設(shè)r1 重辦t1，重辦后，s(d1_1) = sdr，s(d1_2) = sdr，s(t1) = stw，s(w1_1) = sww。

　　(2) 角色退回任務(wù)

　　設(shè)案例i 正向調(diào)度到第（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 都可以退回任務(wù)。這里設(shè)r6 退回分組g1 的簽辦的任務(wù)t2，則s(w6_2) = swr，s(d2) = sdw。可以看出，當(dāng)r6 退回簽辦的t2 后，r1 還可以重辦w1_2，從而連續(xù)實現(xiàn)多步任務(wù)調(diào)度過程中的逆向。

　　4.3 案例的循環(huán)調(diào)度過程示例

　　設(shè)案例 i 正向調(diào)度到第（10）步，r3 啟動循環(huán)l，則s(l) = slw，s(w3_1) = sww，s(t3) = stw；當(dāng)w3_1 辦理完畢后，s(w3_1) = swf，s(t3) = stf，s(d3) = sdw；這時，r2 可以簽辦任務(wù)t3，由于循環(huán)將路徑中工作、任務(wù)和轉(zhuǎn)發(fā)統(tǒng)一按照就緒狀態(tài)處理，而w2_2 不在循環(huán)中，所以簽辦后s(d3) = sdf，s(w2_1) = sww，s(t4) = stw；當(dāng)w2_1 辦理完畢后，s(w2_1) = swf，s(t4) =stf，s(d4) = sdw；此時r3 如果終止循環(huán)，則s(l) = slf，循環(huán)結(jié)束，如果不終止循環(huán)，r3 可以接著辦理w3_1，則s(w3_1) = sww，s(t3) = stw，如此反復(fù)執(zhí)行直至循環(huán)終止。

　　5 結(jié)束語

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

　　同時，由于多步任務(wù)協(xié)同網(wǎng)本身的演化，本文所介紹的調(diào)度算法可能還會進一步支持一些高級的結(jié)構(gòu)，如子網(wǎng)，多實例等等。