時(shí)間約束下任務(wù)關(guān)鍵系統(tǒng)的可調(diào)度性分析

陳 瑩,邢建春,楊啟亮,,張孝鵬

(1.陸軍工程大學(xué) 國(guó)防工程學(xué)院,南京 210007; 2.南京大學(xué) 計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,南京 210093;3.酒泉衛(wèi)星發(fā)射中心,甘肅 酒泉 732750)

0 概述

任務(wù)關(guān)鍵系統(tǒng)(Mission Critical System,MCS)[1]是指在系統(tǒng)運(yùn)行過程中不能發(fā)生中斷或失效,否則將導(dǎo)致任務(wù)執(zhí)行失敗,造成嚴(yán)重的經(jīng)濟(jì)損失或人員傷亡的系統(tǒng)。如何在時(shí)間有限的情況下保證現(xiàn)有的關(guān)鍵任務(wù)持續(xù)、及時(shí)完成,己成為亟待解決的問題。時(shí)間約束下的任務(wù)關(guān)鍵系統(tǒng)的可運(yùn)行性分析,也就是確保有限時(shí)間約束內(nèi)能夠完成任務(wù)的觸發(fā)問題。因此,首先需要研究整個(gè)系統(tǒng)中所有活動(dòng)是否都為可調(diào)度的。

在工作流網(wǎng)系統(tǒng)中,如果任何2個(gè)變遷之間都不存在潛在的資源沖突,那么稱此工作流模型是可調(diào)度的。對(duì)于不可調(diào)度的活動(dòng),結(jié)合關(guān)鍵任務(wù)等級(jí),通過對(duì)活動(dòng)的時(shí)間約束進(jìn)行修正使得工作流模型變成可調(diào)度[2]。時(shí)間約束下的任務(wù)關(guān)鍵系統(tǒng)的調(diào)度性問題本質(zhì)上是一個(gè)非線性規(guī)劃問題[3]。

時(shí)間約束下工作流程的建模是其時(shí)間性能分析的前提,具有強(qiáng)大時(shí)間約束表達(dá)能力和數(shù)學(xué)基礎(chǔ)的時(shí)間約束Petri網(wǎng)(Timing Constraint Petri Net,TCPN)在建模方面得到了廣泛應(yīng)用。然而,TCPN強(qiáng)大的時(shí)間約束描述能力也使得可調(diào)度性的分析難度大大增加。因此,眾多學(xué)者從不同角度對(duì)其進(jìn)行了研究。文獻(xiàn)[1]提出了TCPN的概念,并給出了最基礎(chǔ)的調(diào)度驗(yàn)證的方法,很多學(xué)者的研究都基于此方法;文獻(xiàn)[2]提出了基于Petri網(wǎng)的時(shí)間約束工作流的可調(diào)度性驗(yàn)證算法;文獻(xiàn)[4]從結(jié)構(gòu)、時(shí)間、資源限制3個(gè)層面提出多工作流系統(tǒng)的原型,并進(jìn)一步給出多工作流網(wǎng)下的可調(diào)度性驗(yàn)證算法和修正策略;文獻(xiàn)[5]完善了TCPN的定義,并提出了TCPN時(shí)間可調(diào)度性判定定理;文獻(xiàn)[6]提出了4種基本工作流組件模型的簡(jiǎn)化規(guī)則和壓縮推理方法;文獻(xiàn)[7]對(duì)文獻(xiàn)[2]的驗(yàn)證算法進(jìn)行了改進(jìn),使得算法更加簡(jiǎn)潔,減小了時(shí)間復(fù)雜度;文獻(xiàn)[8]提出了擴(kuò)展的時(shí)間約束Petri網(wǎng)(w-TCPN)的定義,并結(jié)合w-TCPN的拓?fù)浣Y(jié)構(gòu),從模型和實(shí)例2個(gè)層次給出了w-TCPN可調(diào)度的判定定理,并描繪了時(shí)間約束的修正策略;文獻(xiàn)[9]提出了一種基于Parsec的并行計(jì)算工作流調(diào)度算法;文獻(xiàn)[10]進(jìn)行了基于集群拓?fù)浣Y(jié)構(gòu)的工作流調(diào)度研究;文獻(xiàn)[11]針對(duì)軍事網(wǎng)格應(yīng)用及工作流的特點(diǎn),給出一種基于網(wǎng)格工作流分割的調(diào)度算法;文獻(xiàn)[12]提出了一種基于多QoS目標(biāo)的工作流任務(wù)調(diào)度算法;文獻(xiàn)[13]對(duì)工作流進(jìn)行了建模與分析。

近些年有關(guān)可調(diào)度性分析的研究,大部分都基于TCPN,沒有加入任何新元素,限制了可調(diào)度性分析的應(yīng)用范圍?；诖瞬蛔?本文通過引入任務(wù)關(guān)鍵系統(tǒng)這一元素,在時(shí)間約束著色Petri網(wǎng)(Timing Constraint Color Petri Net,TCCP-Net)中,提出一種任務(wù)關(guān)鍵系統(tǒng)的可調(diào)度性靜態(tài)分析、動(dòng)態(tài)分析及其修正策略。

1 TCCP-Net語義及相關(guān)概念

1.1 關(guān)鍵任務(wù)等級(jí)劃分

任務(wù)關(guān)鍵系統(tǒng)的時(shí)間約束驗(yàn)證有兩方面要求。一方面,整個(gè)工作流過程是在一定時(shí)間約束下進(jìn)行的,文中給出每一個(gè)庫所的時(shí)間約束最大值,即Vpmax。另一方面,將任務(wù)根據(jù)不同的重要程度分為不同的等級(jí),文中將其分為2個(gè)等級(jí)。

定義1關(guān)鍵系統(tǒng)中的任務(wù)分為關(guān)鍵任務(wù)和非關(guān)鍵任務(wù)。其中,關(guān)鍵任務(wù)是為完成最終任務(wù)必須要執(zhí)行的任務(wù),且每個(gè)工作流程中最少要有一個(gè)關(guān)鍵任務(wù)。

1.2 TCCP-Net定義

定義2時(shí)間約束著色Petri網(wǎng)(TCCP-Net)。一個(gè)時(shí)間約束著色Petri網(wǎng)是一個(gè)七元組:TCCP-Net=(P,T,F,M0,C,PT,D)。

1)P:描述系統(tǒng)庫所(Place)的有限集合;

2)T:變遷(Transition)的有限集合;

3)F:弧(Arc)的有限集合,滿足F?(P×T∪T×P);

4)M0:初始變量;

5)C:與每個(gè)庫所和變遷關(guān)聯(lián)的色彩集。具體地,庫所pi的色彩集為C(pi)={ai,1,ai,2,…,ai,ui},其中,ui=C(pi),i=1,2,…,n,變遷tj的色彩集為C(tj)={bj,1,bj,2,…,bj,vj},vj=C(tj),j=1,2,…,m;

6)PT是定義在庫所集和變遷集上的整數(shù)對(duì)PT(pj,tj)=[Vl(pt),Vc(pt)]的集合;

7)D是變遷的執(zhí)行延遲Vd(t)的集合。

1.3 TCCP-Net中時(shí)間參數(shù)的形式化定義

圖1為一個(gè)TCCP-Net的片段,Vl(pt)、Vc(pt)和Td(t)的單位為時(shí)間單元,如天(d)、小時(shí)(h)等。

圖1 TCCP-Net片段

結(jié)合圖1,將TCCP-Net中庫所和變遷的時(shí)間約束條件進(jìn)行說明,除此之外,為了下文討論方便,此處給出一些其他變量的定義和運(yùn)算公式。

1)[Vl(p1),Vc(p1)]和[Vl(p2),Vc(p2)]分別為庫所p1和p2上的局部時(shí)間約束值,表示庫所中的托肯對(duì)后續(xù)變遷的使能區(qū)間。假設(shè)托肯到達(dá)庫所p1的時(shí)間為V0,則在區(qū)間[V0+Vl(p1),V0+Vc(p1)]內(nèi)變遷t1被使能。

2)[Vl(t1),Vc(t1)]為變遷t1的局部時(shí)間約束值,表示t1的可觸發(fā)時(shí)間。假設(shè)變遷t1在V1時(shí)刻使能,那么其可觸發(fā)時(shí)間為[V1+Vl(t1),V1+Vc(t1)]。

3)Vd(t1)表示變遷t1完成觸發(fā)所需要的時(shí)間延遲。假設(shè)變遷t1的觸發(fā)時(shí)刻為V2,那么完成觸發(fā)的時(shí)刻為V2+Vd(t1)。

4)[EVl(p),EVc(p)]為庫所p使能的時(shí)間區(qū)間,此區(qū)間是上文中托肯對(duì)后續(xù)變遷使能區(qū)間的交集。

5)[EVl(t),EVc(t)]為變遷t使能的時(shí)間區(qū)間。

6)[FVl(t),FVc(t)]為變遷t的可觸發(fā)時(shí)間區(qū)間。

7)[FVbegl(t),FVendc(t)]為變遷t觸發(fā)的最早開始時(shí)刻和最晚結(jié)束時(shí)刻。其中,FVendc(t)=EVc(p)。

8)Token(pn)j為第n個(gè)庫所中第j個(gè)托肯到達(dá)的時(shí)刻,并且每一個(gè)庫所托肯的到達(dá)時(shí)間Token(p)取決于庫所中最后一個(gè)托肯的到達(dá)時(shí)間。

由于變遷完成觸發(fā)還需要一定的時(shí)間延遲Vd(t),也就是說如果要求變遷能夠成功觸發(fā),需要滿足條件Vc(t)-Vl(t)≥Vd(t)。

變遷可調(diào)度性的驗(yàn)證問題,歸根結(jié)底是驗(yàn)證變遷觸發(fā)結(jié)束時(shí)刻值與出發(fā)開始時(shí)刻值之差是否滿足時(shí)間延遲的約束。因此,當(dāng)變遷的最晚觸發(fā)結(jié)束時(shí)刻的值FVendc(t)與最早觸發(fā)開始時(shí)刻的值FVbegl(t)的差值都不滿足時(shí)間延遲Vd(t)的約束,也即FVendc(t)-FVbegl(t)

規(guī)則1在TCCP-Net網(wǎng)的某一狀態(tài)標(biāo)識(shí)M下,如果變遷t滿足:

FVendc(t)-FVbel(t)≥Vd(t)

(1)

那么變遷t是可調(diào)度的。

定義3TCCP-Net網(wǎng)是可調(diào)度的,當(dāng)且僅當(dāng)網(wǎng)中每一個(gè)變遷都是可調(diào)度的。

定義4前驅(qū)庫所(precursor place)。如果有向弧從p連接到t,那么活動(dòng)t就稱為p的前驅(qū)庫所,即·p。帶有m個(gè)托肯的庫所如圖2所示。

圖2 帶有m個(gè)托肯的庫所

當(dāng)只有一個(gè)變遷時(shí),若要變遷t進(jìn)入觸發(fā)階段,則需要所有前驅(qū)庫所都處于使能階段,也就是說前驅(qū)庫所中的所有托肯都必須到達(dá),因此,FVbegl(t)和FVendc(t)的計(jì)算公式為:

FVbegl(t)=FVl(t)=EVl(t)+Vl(t)=

min{Token(·p1)m}+Vl(·p)+Vl(t)

(2)

FVendc(t)=EVc(t)=max{Token(·p1)1}+Vc(·p)

(3)

式(2)表示當(dāng)變遷t處于使能階段時(shí),需要經(jīng)過Vl(t)時(shí)間才能使得變遷t處于最早觸發(fā)時(shí)間階段,并且變遷t最早使能時(shí)間取決于最后一個(gè)托肯的到達(dá)時(shí)間;式(3)表示當(dāng)庫所處于觸發(fā)階段,變遷t處于使能階段時(shí),必須馬上被觸發(fā),否則庫所中的托肯將會(huì)丟失,從而導(dǎo)致變遷無法被觸發(fā),并且變遷t最晚使能時(shí)間取決于第一個(gè)托肯對(duì)其使能時(shí)間的最大值。

2 時(shí)間約束下的CTPN可調(diào)度性分析

工作流過程的可調(diào)度性分析一般分為靜態(tài)分析和動(dòng)態(tài)分析[14]。其中,靜態(tài)分析是指不考慮托肯到達(dá)庫所的時(shí)間,動(dòng)態(tài)分析又稱強(qiáng)可調(diào)度性分析,是指需關(guān)注不確定因素對(duì)工作流過程帶來的影響,其最大的影響因素就是托肯到達(dá)庫所的時(shí)間。

在實(shí)際的工作流過程中,只有資源(托肯)全部到達(dá),活動(dòng)(變遷)才能夠被觸發(fā),從而使得整個(gè)過程得以運(yùn)行。在分析工作流過程的可調(diào)度性時(shí),只有考慮到托肯的到達(dá)時(shí)間才具有實(shí)際意義。因此,文中只對(duì)可調(diào)度性進(jìn)行強(qiáng)可調(diào)度性分析。

2.1 可調(diào)度性分析方法

通過規(guī)則1可知,變遷的可調(diào)度性取決于變遷和前驅(qū)庫所的時(shí)間約束。從圖3可以看出,只有并行路徑的庫所需要大于一個(gè)的托肯數(shù)。換句話說,只有并行路徑存在變遷擁有多個(gè)前驅(qū)庫所的情況。但根據(jù)結(jié)構(gòu)可知,其他路徑是并行路徑的一個(gè)特殊情況,因此,只需分析并行路徑中多個(gè)前驅(qū)庫所的情況即可。

圖3 變遷路徑的基本結(jié)構(gòu)

定理1在TCCP-Net網(wǎng)的某一狀態(tài)標(biāo)識(shí)M下,具有n個(gè)前驅(qū)庫所的變遷強(qiáng)可調(diào)度性充要條件為:

min{Token(·pi)1}-max{Token(·pi)m}+

minVc(·p)-maxVl(·p)-Vl(t)≥Vd(t)

(4)

其中,1≤i≤n。

證明

由于:

FVbegl(t)= max{min{Token(·pi)m}+

Vl(·p)}+Vl(t)

其中,1≤i≤n。

FVendc(t)= min{max{Token(·pi)1}+

Vc(·p)}

其中,1≤i≤n,帶入式(1)可得:

min{ max{Token(·pi)1}+Vc(·p)}-

max{min{Token(·pi)m}+

Vl(·p)}+Vl(t)≥Vd(t)

也即:

min{ max{Token(·pi)1}}-

max{min{Token(·pi)m}+minVc(·p)-

maxVl(·p)-Vl(t)≥Vd(t)

其中,1≤i≤n,式(4)得證。

綜上所述,工作流過程的可調(diào)度性分析的基本思路為:根據(jù)已知時(shí)間約束,計(jì)算變遷t觸發(fā)最早開始時(shí)刻FVbegl(t)和最晚結(jié)束時(shí)刻FVendc(t)的值,然后比較FVendc(t)-FVbegl(t)≥Vd(t)是否成立。若成立,則可判斷t是強(qiáng)可調(diào)度的;若不成立,則應(yīng)對(duì)變遷及其前驅(qū)庫所的時(shí)間約束進(jìn)行修正,從而使得變遷為強(qiáng)可調(diào)度的。

2.2 時(shí)間約束修正策略與算法

工作流過程的可調(diào)度分析不僅要驗(yàn)證工作流中的變遷是否可調(diào)度,還要對(duì)不可調(diào)度的變遷進(jìn)行修正,使得整個(gè)工作流網(wǎng)都為可調(diào)度的。由式(4)可知,影響變遷可調(diào)度性的元素有4種:庫所使能時(shí)間上限,庫所使能時(shí)間下限,變遷可觸發(fā)時(shí)間下限和變遷完成觸發(fā)所需的時(shí)間延遲。其中,時(shí)間延遲是固定值,無法進(jìn)行修改。那么,如果要使得式(4)成立,根據(jù)對(duì)工作流過程的總的時(shí)間約束值Vpmax,可首先減小變遷可觸發(fā)時(shí)間下限值;若仍不成立且V≤Vpmax,則可減小庫所使能時(shí)間下限值并增加庫所使能時(shí)間上限值;最后,若式(4)仍不成立且V≥Vpmax,則根據(jù)關(guān)鍵任務(wù)的等級(jí)程度對(duì)其進(jìn)行取消執(zhí)行。假設(shè)工作流時(shí)間約束為Vpmax,當(dāng)V≤Vpmax時(shí),具體步驟如下:

步驟1減小Vl(t)的值,如果Vl(t)≥0且式(4)成立,轉(zhuǎn)入步驟4,否則轉(zhuǎn)入步驟2。

步驟2減小Vl(·p)的值,如果Vl(·p)≥0且式(4)成立,轉(zhuǎn)入步驟4,否則轉(zhuǎn)入步驟3。

步驟3尋找變遷t的直接前驅(qū)庫所·p,增加Vc(·p)的值,當(dāng)式(4)成立,但V(·p)>V(·pmax)時(shí),若活動(dòng)t為非關(guān)鍵任務(wù),則可直接取消執(zhí)行任務(wù)t;若活動(dòng)t為關(guān)鍵任務(wù),則增大Tmax的值,直到式(4)成立。

步驟4結(jié)束。

3 案例分析

圖4為某港岸基保障信息系統(tǒng)流程,碼頭一般設(shè)置有食品供應(yīng)中心、供水中心、供電中心、供暖中心等岸基保障設(shè)施,所以艦艇靠岸駐泊后,岸基保障部門通過這些保障設(shè)施為其補(bǔ)給水、電、氣、食品以及軍械、彈藥等物資[15],其工作流程如圖4所示。其中:p1表示準(zhǔn)備提交申請(qǐng);p2表示準(zhǔn)備進(jìn)行審核;p3表示完成審核,準(zhǔn)備部門批準(zhǔn);p4表示完成批準(zhǔn),準(zhǔn)備配備食品;p5表示完成批準(zhǔn),準(zhǔn)備配備水電;p6表示準(zhǔn)備調(diào)用貨車;p7表示準(zhǔn)備調(diào)配保障人員;p8表示食品裝配完畢,待運(yùn)輸;p9表示水電準(zhǔn)備完畢,待配送;p10表示食品輸送完畢,待確認(rèn);p11表示水電配送完畢,待確認(rèn);p12表示水電配送完畢,待確認(rèn);t1表示提交申請(qǐng);t2表示部門進(jìn)行審核;t3表示部門批準(zhǔn);t4表示配備需供應(yīng)的食品;t5表示配備需供應(yīng)的水電;t6表示將貨車調(diào)到食品供應(yīng)站;t7表示調(diào)用保障人員;t8表示用貨車運(yùn)輸食品;t9表示保障人員進(jìn)行水電配送;t10表示確認(rèn)任務(wù)完成。

圖4 案例工作流程

案例工作流程時(shí)間約束集PT如表1所示,其時(shí)間單位為min。

表1 案例工作流程時(shí)間約束集

一只艦艇靠岸駐泊后,假設(shè)庫所p中有2個(gè)托肯,到達(dá)庫所的時(shí)間區(qū)間分別為:Token(p)1=[1,3]和Token(p)2=[2,5],且t4～t9為關(guān)鍵任務(wù),t1～t3、t10為非關(guān)鍵任務(wù)。運(yùn)用第2節(jié)所述的工作流過程,可調(diào)度性驗(yàn)證方法對(duì)案例進(jìn)行驗(yàn)證的過程如下:

1)對(duì)活動(dòng)t1進(jìn)行驗(yàn)證,其最早觸發(fā)開始時(shí)間值與最晚觸發(fā)結(jié)束時(shí)間值分別為:

FVbegl(t1)= min{Token(·p1)2}+Vl(·p1)+

Vl(t1)=4

FVendc(t1)= max{Token(·p1)1}+

Vc(·p1)=5

由于FVendc(t1)-FVbegl(t1)=1<5,對(duì)活動(dòng)t1的時(shí)間約束進(jìn)行修正:

(1)減小Vl(t1)的值至0,則FVendc(t1)-FVbegl(t1)=2<5,活動(dòng)仍不可調(diào)度約束。此時(shí),活動(dòng)t1新的時(shí)間約束為[0,2]。

(2)減小Vl(·p1)的值至0,則FVendc(t1)-FVbegl(t1)=3<5,活動(dòng)仍不可調(diào)度約束。此時(shí),庫所p1新的時(shí)間約束為[0,2]。

(3)若要使得FVendc(t1)-FVbegl(t1)≥5,FVbegl(t1)的最小值為2,那么就需要增加FVendc(t1)的值,由上述分析可知增加Vc(·p1)的值為4時(shí),不等式成立。此時(shí)庫所p1新的時(shí)間約束為[0,4]。但由已知條件可知,V(p1)max=3,并且活動(dòng)t1為非關(guān)鍵任務(wù),因此,可選擇不執(zhí)行活動(dòng)t1,直接執(zhí)行活動(dòng)t2。

2)對(duì)活動(dòng)t2進(jìn)行驗(yàn)證:

FVbegl(t2)= min{Token(·p2)2}+

Vl(·p2)+Vl(t2)=3

FVendc(t2)= max{Token(·p2)1}+

Vc(·p2)=8

由于FVendc(t2)-FVbegl(t2)=6>5,因此活動(dòng)t2為可調(diào)度的。

3)對(duì)活動(dòng)t3進(jìn)行驗(yàn)證:

FVbegl(t3)= min{Token(·p3)2}+Vl(·p3)+

Vl(t3)=9

FVendc(t3)= max{Token(·p3)1}+

Vc(·p3)=15

由于FVendc(t3)-FVbegl(t3)=6<7,因此對(duì)活動(dòng)t3的時(shí)間約束進(jìn)行修正:

(1)減小Vl(t3)的值至0,則FVendc(t3)-FVbegl(t3)=7,可調(diào)度。

(2)活動(dòng)t3新的時(shí)間約束為[0,3],活動(dòng)t3新的最早觸發(fā)開始時(shí)間值與最晚觸發(fā)結(jié)束時(shí)間值分別為:

Vl(·p3)+Vl(t3)=8

4)對(duì)活動(dòng)t4進(jìn)行驗(yàn)證:

FVbegl(t4)= min{Token(·p4)2}+

Vl(·p4)+Vl(t4)=18

FVendc(t4)= max{Token(·p4)1}+

Vc(·p4)=25

由于FVendc(t4)-FVbegl(t4)=7≥5,因此活動(dòng)t4為可調(diào)度的。

5)對(duì)活動(dòng)t5進(jìn)行驗(yàn)證:

FVbegl(t5)= min{Token(·p5)2}+

Vl(·p5)+Vl(t5)=28

FVendc(t5)= max{Token(·p5)1}+

Vc(·p5)=34

由于FVendc(t5)-FVbegl(t5)=6>4,因此活動(dòng)t5為可調(diào)度的。

6)對(duì)活動(dòng)t6進(jìn)行驗(yàn)證:

FVbegl(t6)= min{Token(·p6)2}+

Vl(·p6)+Vl(t6)=37

FVendc(t6)= max{Token(·p6)1}+

Vc(·p6)=42

由于FVendc(t6)-FVbegl(t6)=5≥4,因此活動(dòng)t6為可調(diào)度的。

7)對(duì)活動(dòng)t7進(jìn)行驗(yàn)證:

FVbegl(t7)= min{Token(·p7)2}+

Vl(·p7)+Vl(t7)=42

FVendc(t7)= max{Token(·p7)1}+

Vc(·p7)=50

由于FVendc(t7)-FVbegl(t7)=8≥7,因此活動(dòng)t7為可調(diào)度的。

8)對(duì)活動(dòng)t8進(jìn)行驗(yàn)證:

FVbegl(t8)= min{Token(·p8)2}+Vl(·p8)+

Vl(t8)=54

FVendc(t8)=max{Token(·p8)1}+Vc(·p8)=62

由于FVendc(t8)-FVbegl(t8)=6≥5,因此活動(dòng)t8為可調(diào)度的。

9)對(duì)活動(dòng)t9進(jìn)行驗(yàn)證:

FVbegl(t9)= min{Token(·p9)2}+Vl(·p9)+

Vl(t9)=62

FVendc(t9)= max{Token(·p9)1}+

Vc(·p9)=71

由于FVendc(t9)-FVbegl(t9)=9≥5,因此活動(dòng)t9為可調(diào)度的。

10)對(duì)活動(dòng)t10進(jìn)行驗(yàn)證:

FVbegl(t10)= min{Token(·p10)2}+

Vl(·p10)+Vl(t10)=70

FVendc(t10)= max{Token(·p10)1}+

Vc(·p10)=78

由于FVendc(t10)-FVbegl(t10)=8≥7,因此活動(dòng)t10為可調(diào)度的。

11)驗(yàn)證算法結(jié)束。

對(duì)不可調(diào)度的活動(dòng)進(jìn)行修正后的時(shí)間約束值如表2所示。其中“/”表示無數(shù)據(jù)。

表2 修正后的時(shí)間約束值

4 結(jié)束語

為了更好地解決時(shí)間約束下工作流過程的可調(diào)度性分析這一問題,本文引入了時(shí)間約束Petri網(wǎng),將工作流中的活動(dòng)分為關(guān)鍵任務(wù)和非關(guān)鍵任務(wù),提出了可調(diào)度性分析的判別方法,并且對(duì)于不可調(diào)度的活動(dòng)進(jìn)行時(shí)間約束修正,從而使得整個(gè)工作流滿足可調(diào)度性。分析結(jié)果表明,該方法不僅增強(qiáng)了工作流運(yùn)行的準(zhǔn)確性,還大幅提高了其運(yùn)行效率。