丁　超, 唐力偉, 鄧士杰

(軍械工程學(xué)院火炮工程系, 河北 石家莊 050000)

?

基于動態(tài)優(yōu)先級的測試任務(wù)搶占調(diào)度算法

丁超, 唐力偉, 鄧士杰

(軍械工程學(xué)院火炮工程系, 河北 石家莊 050000)

基于部隊(duì)現(xiàn)有裝備保障模式,難以滿足日趨復(fù)雜的測試需求,存在著測試效率偏低、測試周期過長的現(xiàn)象。因此綜合考慮任務(wù)的時間屬性和價值屬性,定量分析任務(wù)的執(zhí)行緊迫性、價值密度和資源負(fù)載均衡性等因素,提出了應(yīng)用于任務(wù)執(zhí)行初始時刻的動態(tài)優(yōu)先級分派策略(dynamicpriorityassignment,DPA)和任務(wù)執(zhí)行過程中的搶占調(diào)度策略(taskpreemption,TP),即基于動態(tài)優(yōu)先級的測試任務(wù)搶占調(diào)度算法(testtaskpreemptiveschedulingalgorithmbasedondynamicpriority,TTPSADP),實(shí)現(xiàn)了針對現(xiàn)有自動測試系統(tǒng)(automatictestsystem,ATS)價值收益、任務(wù)執(zhí)行成功率和資源負(fù)載均衡的綜合優(yōu)化。

自動測試系統(tǒng); 動態(tài)優(yōu)先級; 任務(wù)搶占; 調(diào)度算法

0　引　言

在部隊(duì)日常的裝備保障活動中,一旦面臨突發(fā)保障任務(wù),時間緊迫、任務(wù)繁重,基于部隊(duì)現(xiàn)有裝備保障模式難以滿足驟增的測試需求[1]。因此,依托現(xiàn)有測試資源,合理排序測試任務(wù),增強(qiáng)任務(wù)執(zhí)行的并行化水平,盡快恢復(fù)裝備的最佳作戰(zhàn)能力,探索針對測試任務(wù)的動態(tài)調(diào)度是部隊(duì)面臨的一項(xiàng)突出難題。

近年來,考慮任務(wù)調(diào)度的諸多影響因素,如價值屬性[2]、可調(diào)度性[3]、并行性[4]、柔性資源約束性[5]、最大保障時間[6]等,國內(nèi)外學(xué)者提出了許多調(diào)度算法,如基于優(yōu)先表的禁忌搜索算法[7]、任務(wù)優(yōu)化算法[8]、基于資源推拉的調(diào)度算法[9]、多目標(biāo)函數(shù)調(diào)度算法[10-12]、基于動態(tài)優(yōu)先級分派的調(diào)度算法[1]等。其中部分研究考慮的影響因素比較單一,偏重的應(yīng)用領(lǐng)域互有差異,限制了算法的應(yīng)用。

著眼于部隊(duì)裝備保障實(shí)際中,分析問題存在的深層次原因,概括為以下兩個方面:①測試任務(wù)價值屬性和時間屬性不對稱。過于追求時間屬性,保障緊迫性高的任務(wù)優(yōu)先執(zhí)行,提高任務(wù)執(zhí)行的成功率,但可能會導(dǎo)致部分高價值的任務(wù)不能盡早執(zhí)行,降低系統(tǒng)總的價值收益,推遲裝備原有作戰(zhàn)能力的恢復(fù);過于強(qiáng)調(diào)價值收益,可能會使部分低價值的任務(wù)因得不到執(zhí)行機(jī)會或被高價值任務(wù)搶占而錯過截止期,降低任務(wù)執(zhí)行的成功率,使裝備無法恢復(fù)到最佳作戰(zhàn)能力。②測試資源利用不均衡。在系統(tǒng)調(diào)用資源的過程中,測試能力強(qiáng)或排序靠前的資源往往會比能力弱或排序靠后的資源得到更多的調(diào)用機(jī)會,導(dǎo)致部分資源因頻繁調(diào)用產(chǎn)生不必要的損耗,降低其使用壽命,影響自動測試系統(tǒng)(automatictestsystem,ATS)的測試能力。

本文依據(jù)部隊(duì)裝備保障特點(diǎn),基于任務(wù)的價值屬性和時間屬性,綜合考慮影響任務(wù)執(zhí)行的多個關(guān)鍵因素,提出了面向任務(wù)執(zhí)行初始時刻的動態(tài)優(yōu)先級分派策略(dynamicpriorityassignment,DPA),保證任務(wù)執(zhí)行初始時刻的最優(yōu)調(diào)度;提出了面向任務(wù)執(zhí)行過程中的任務(wù)搶占調(diào)度策略(taskpreemption,TP),保證任務(wù)的平穩(wěn)執(zhí)行;最后基于以上策略,提出了面臨突發(fā)保障任務(wù)的基于動態(tài)優(yōu)先級的測試任務(wù)搶占調(diào)度算法(testtaskpreemptiveschedulingalgorithmbasedondynamicpriority,TTPSADP)，并進(jìn)行了實(shí)例驗(yàn)證。

1　測試任務(wù)描述

1.1任務(wù)數(shù)學(xué)描述

匯總ATS面臨的所有測試任務(wù)構(gòu)成集合Tasks={E1, E2,…, Ei,…, Em};任務(wù)Ei包含n(i)個待測點(diǎn)(即測試子任務(wù)),構(gòu)成子任務(wù)集合Ei={pi,1, pi,2, …, pi,j, …, pi,n(i)};每個子任務(wù)都具有7種屬性,如圖1所示。

圖1　測試任務(wù)調(diào)度甘特圖示例Fig.1　Test task scheduling Gantt chart

圖1中,Di為任務(wù)Ei的絕對截止期;ti,j為子任務(wù)pi,j的理論執(zhí)行時間;bi,j為pi,j的開始執(zhí)行時刻;di為Ei的最大保障時間,即相對截止期;oi,j為pi,j的預(yù)期結(jié)束時刻,且oi,j=bi,j+ti,j;wi,j為pi,j的測試價值,若pi,j在Di前完成,即oi,j≤Di,則wi,j=1,否則wi,j=0;fi,j為pi,j的空閑時間,且fi,j=Di-bi,j-ti,j,本文僅考慮等待子任務(wù)的空閑時間。

假設(shè)子任務(wù)執(zhí)行過程中的當(dāng)前時刻為T,根據(jù)子任務(wù)在該時刻的不同狀態(tài),將其劃分為以下3類:執(zhí)行子任務(wù),即正處在理論執(zhí)行時間ti,j里的子任務(wù)pi,j;完成子任務(wù),即已經(jīng)執(zhí)行完畢,執(zhí)行成功或失敗的pi,j;等待子任務(wù),即未獲得執(zhí)行機(jī)會而處于等待狀態(tài)的pi,j,其中動態(tài)價值密度和執(zhí)行緊迫性會隨著等待子任務(wù)等待時間的增加而逐漸增大。

針對測試任務(wù)的動態(tài)調(diào)度問題,作出以下4點(diǎn)假設(shè):①子任務(wù)在執(zhí)行過程中不能中斷;②子任務(wù)之間的切換時間很短,忽略不計;③子任務(wù)之間僅在資源占用上存在沖突,不存在其他關(guān)系;④單個測試資源在同一時刻只能匹配一個子任務(wù)pi,j,單個pi,j在同一時刻也只能匹配一種測試資源。

1.2測試資源匹配

匯總ATS內(nèi)部所有可用測試資源構(gòu)成集合resource={r1, r2, …, rk, …, rl};resource中的資源全部為柔性資源(flexibleresource,FR)[13],即單個資源具備多種測試能力,滿足多樣化測試需求,如圖2所示。以數(shù)字萬用表為例,一套萬用表可以實(shí)現(xiàn)交/直流電壓、電流、電阻測量等多種測試功能。

圖2　子任務(wù)與資源匹配關(guān)系Fig.2　Relationship of sub-task and resource matching

子任務(wù)與資源匹配矩陣M(m,n)×l,描述子任務(wù)與資源之間的匹配關(guān)系

(1)

式中，e(i,j),k表示資源rk對子任務(wù)pi,j的匹配結(jié)果,如果rk滿足pi,j的測試需求,則e(i,j),k=1,否則e(i,j),k=0。

1.3任務(wù)調(diào)度模型

測試任務(wù)的有效執(zhí)行就是在保證任務(wù)執(zhí)行成功率的基礎(chǔ)上,均衡利用測試資源,安排高價值任務(wù)優(yōu)先執(zhí)行,實(shí)現(xiàn)任務(wù)執(zhí)行成功率、資源負(fù)載均衡和ATS價值收益的綜合優(yōu)化[14]。相比于日常的裝備保障活動,ATS在面臨突發(fā)保障任務(wù)時,要求在短時間內(nèi)針對眾多測試任務(wù)進(jìn)行合理調(diào)度,為此需要考慮諸多影響因素:

(1) 動態(tài)性。在測試過程中,被測對象和測試環(huán)境不斷變化,隨時可能有新的任務(wù)加入,保持現(xiàn)有任務(wù)序列依次排序新加入的測試任務(wù),可能會導(dǎo)致部分高價值任務(wù)無法盡快執(zhí)行,降低ATS的價值收益;而打亂現(xiàn)有序列重新排序需要動態(tài)考慮多種復(fù)雜因素。

(2) 優(yōu)先性。由于不同任務(wù)在測試過程中對恢復(fù)裝備原有作戰(zhàn)能力的影響程度不同,其執(zhí)行時的優(yōu)先級也會有差異;考慮到隨時可能加入的新任務(wù),依據(jù)優(yōu)先級針對所有任務(wù)進(jìn)行排序,在測試過程中容易引發(fā)混亂。

(3) 受限性。突發(fā)保障任務(wù)往往會在短時間內(nèi)帶來大量測試任務(wù),ATS的內(nèi)部資源難以同時滿足所有測試需求,需要在有限資源的約束下,通過對任務(wù)進(jìn)行排序依次調(diào)用所需資源。

測試任務(wù)調(diào)度模型為

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(2)表示測試任務(wù)執(zhí)行過程中價值收益的最大化,αi,j,k表示子任務(wù)pi,j與資源rk的匹配程度,如果rk滿足pi,j的需求,則αi,j,k=1,否則αi,j,k=0;若oi,j≤Di,則βi,j=1,否則βi,j=0。約束式(3)表示任意時刻的執(zhí)行子任務(wù)所匹配的資源數(shù)目不能超過系統(tǒng)內(nèi)部資源總量,其中St為任意時刻t正在執(zhí)行的子任務(wù)集合,ri,j,k為子任務(wù)pi,j所需的資源rk。約束式(4)表示單個子任務(wù)在執(zhí)行過程中最多能匹配一種資源。約束式(5)表示后續(xù)子任務(wù)pi,j只能在前序任務(wù)pi′,j′完成后才開始執(zhí)行。約束式(6)表示任務(wù)的理論執(zhí)行時間必須包含于最大保障時間內(nèi)。約束式(7)表示任務(wù)Ei的絕對截止期是由該任務(wù)中最早開始執(zhí)行的子任務(wù)開始時間bi,j和最大保障時間di決定的。約束式(8)表示子任務(wù)的預(yù)期結(jié)束時刻必須早于絕對截止期。

2　TTPSADP算法

2.1DPA策略

2.1.1DPA函數(shù)

動態(tài)價值密度(dynamic value density, DVD)。在裝備保障活動中,ATS測試能力的實(shí)現(xiàn)依賴于任務(wù)的有效執(zhí)行,但由于不同任務(wù)的重要性不同,系統(tǒng)在執(zhí)行過程中的偏重也會有差異。為此考慮等待子任務(wù)的測試價值wi,j和空閑時間fi,j對其重要程度進(jìn)行量化:

(9)

執(zhí)行緊迫性(executive urgency, EU)。在針對子任務(wù)的調(diào)度過程中,不僅要實(shí)現(xiàn)ATS價值收益的最大化,更要保證任務(wù)執(zhí)行的成功率。借鑒傳統(tǒng)基于時間屬性的任務(wù)調(diào)度策略[15],考慮等待子任務(wù)的理論執(zhí)行時間ti,j與空閑時間fi,j評價任務(wù)的執(zhí)行緊迫性:

(10)

綜合考慮任務(wù)的DVD和EU,提出針對測試任務(wù)的動態(tài)優(yōu)先級分派函數(shù)DPA,實(shí)現(xiàn)ATS價值收益與任務(wù)執(zhí)行成功率的綜合優(yōu)化:

(11)

由式(9)和式(10)知,子任務(wù)pi,j的DVD和EU在任務(wù)執(zhí)行初始時刻最小,分別為wi,j/(Di-ti,j)和ti,j/Di;由式(11)知,pi,j的最小優(yōu)先級min DPAi,j(bi,j)=wi,j×ti,j/Di(Di-ti,j),即基本優(yōu)先級(basic priority, BP)僅與其固有屬性相關(guān)。

2.1.2負(fù)載均衡性

在任務(wù)與資源匹配過程中,考慮資源的負(fù)載均衡性(load balance, LB),就是在保證系統(tǒng)價值收益和任務(wù)執(zhí)行成功率的基礎(chǔ)上,依據(jù)匹配原則優(yōu)先將測試能力弱的資源與子任務(wù)進(jìn)行匹配。

匹配原則(match principle, MP)。首先統(tǒng)計資源的測試能力(test ability, TA),即一種測試資源可以滿足幾種任務(wù)需求,如式(12)所示;然后依據(jù)TA由小到大對資源進(jìn)行排序,針對TA相同的資源按照編號由小到大排序。

(12)

2.1.3DPA流程

假設(shè)初始時刻,ATS面臨的子任務(wù)均允許執(zhí)行,其動態(tài)優(yōu)先級分派流程DPA如下所示:

步驟 1依據(jù)BP對系統(tǒng)面臨的所有子任務(wù)pi,j進(jìn)行排序得到子任務(wù)集P3,優(yōu)先級最高的pi,j首先與資源進(jìn)行匹配。

步驟 2在對pi,j匹配的過程中,實(shí)時監(jiān)控每個匹配后子任務(wù)的結(jié)束時刻是否錯過了截止期,即oi,j≤Di;如果出現(xiàn)oi,j>Di的情況,進(jìn)入步驟3,否則進(jìn)入步驟4。

步驟 3遵循前移原則(move forward principle, MFP),對oi,j>Di的子任務(wù)pi,j前移,對在排序中位置發(fā)生變動的子任務(wù)重新進(jìn)行資源匹配,返回步驟2。

假設(shè)等待前移的子任務(wù)pi,j為pi′,j′的后序任務(wù),需要遵守的MFP原則為:①一般情況下,pi,j在排序中只能前移一個位置,即與pi′,j′互換位置;②當(dāng)pi′,j′與pi,j所需的資源沒有交集時,pi,j繼續(xù)前移,一直移動到與pi,j所需資源存在交集的第一個子任務(wù)前;③當(dāng)前移過程中出現(xiàn)死循環(huán)時,即pi,j前移后變?yōu)閜i′,j′前序任務(wù),pi,j滿足oi,j≤Di,但oi′,j′>Di′;此時pi′,j′需要前移到pi,j前面,pi′,j′滿足oi′,j′≤Di′,但oi,j>Di;針對該情況,pi,j繼續(xù)前移,跳出死循環(huán)。

步驟 4任務(wù)與資源匹配完成,生成子任務(wù)集P7,開始執(zhí)行任務(wù)。

2.2TP策略

2.2.1執(zhí)行顛簸與避免

在測試任務(wù)的執(zhí)行過程中,隨著任務(wù)執(zhí)行時間的推移以及新任務(wù)的不斷加入,可能出現(xiàn)兩個或多個子任務(wù)由于動態(tài)優(yōu)先級交替上升導(dǎo)致子任務(wù)之間反復(fù)搶占,即反復(fù)變化子任務(wù)在排序中的位置,稱為任務(wù)執(zhí)行的顛簸現(xiàn)象(task executive bump, TEB)[16]。

測試子任務(wù)之間的相互搶占會優(yōu)化子任務(wù)的執(zhí)行序列,提高測試效率,但需要消耗系統(tǒng)內(nèi)部資源;而任務(wù)執(zhí)行顛簸是一種過于頻繁的任務(wù)間搶占,會額外消耗系統(tǒng)大量資源和時間,反而會降低測試效率。為避免可能出現(xiàn)的TEB現(xiàn)象,設(shè)置任務(wù)搶占閾值,避免優(yōu)先級相差不大的子任務(wù)之間相互搶占,減少ATS資源的不必要損耗。子任務(wù)搶占閾值的設(shè)定主要有以下兩種方式:①設(shè)定閾值系數(shù)C(C≥1),針對前序子任務(wù)pi′,j′和后序子任務(wù)pi,j,其優(yōu)先級分別為DPAi′,j′和DPAi,j,只有當(dāng)DPAi,j>C×DPAi′,j′時,子任務(wù)pi,j才允許搶占;②設(shè)定閾值增量ΔI(ΔI>0),只有DPAi,j>DPAi′,j′+ΔI時,子任務(wù)pi,j才允許搶占。

不論是閾值系數(shù)C還是閾值增量ΔI,其設(shè)定的準(zhǔn)確性都需要通過大量的實(shí)際測試來驗(yàn)證。

2.2.2TP流程

假設(shè)子任務(wù)與資源匹配完成后,任務(wù)進(jìn)入執(zhí)行階段。經(jīng)過時間T,新的測試任務(wù)加入現(xiàn)有保障活動中,由于ATS對新加入的任務(wù)和等待子任務(wù)動態(tài)優(yōu)先級的計算、比較需要一定時間,所以推遲適當(dāng)時間到時刻Td,保證系統(tǒng)重新排序新加入的任務(wù)和等待子任務(wù),實(shí)現(xiàn)任務(wù)的平穩(wěn)執(zhí)行。推遲時間Td的設(shè)定相似于任務(wù)搶占閾值的設(shè)定,設(shè)定推遲系數(shù)Cd(Cd≥1)或者推遲增量ΔT,推遲時間分別是Td=Cd×T或者Td=T+ΔT,如圖1所示。測試任務(wù)搶占調(diào)度流程TP如下所示:

步驟 1提取時刻Td后的所有等待子任務(wù),將其與新加入的任務(wù)組成新的子任務(wù)集P5;

步驟 2計算、比較P5中所有子任務(wù)的動態(tài)優(yōu)先級,按照優(yōu)先級由大到小的順序進(jìn)行排序組成一個新的子任務(wù)集P6,優(yōu)先級最高的子任務(wù)首先與資源進(jìn)行匹配;

步驟 3～步驟5轉(zhuǎn)入DPA策略中的步驟2～步驟4。

2.3算法流程

基于DPA策略和TP策略,實(shí)現(xiàn)了ATS針對裝備保障活動的平穩(wěn)執(zhí)行,保證測試任務(wù)的最優(yōu)調(diào)度。綜合兩類策略的具體流程,提出了TTPSADP流程，如圖3所示。其中,灰色方框表示DPA策略,白色方框表示TP策略。

圖3　TTPSADP算法流程Fig.3　TTPSADP algorithm flow

3　實(shí)例驗(yàn)證

基于文獻(xiàn)[6]中針對裝備的測試實(shí)例,相關(guān)數(shù)據(jù)如表1所示,驗(yàn)證TTPSADP算法的可行性。假設(shè)任務(wù)執(zhí)行的初始時刻,只有任務(wù)E1和E2加入,經(jīng)過時間T=6后,E3加入測試任務(wù)序列。

表1　測試任務(wù)實(shí)例相關(guān)數(shù)據(jù)

3.1DPA策略

步驟 1計算初始階段測試任務(wù)E1和E2中所有子任務(wù)的基本優(yōu)先級BP,如表2所示;以子任務(wù)p1,1為例,計算其基本優(yōu)先級:

0.50×6/[30×(30-6)]=0.004 2

(13)

經(jīng)過比較后排序,得到子任務(wù)集P3={p2,1, p1,2, p1,1, p2,4, p2,2, p2,3, p1,3, p1,4},對P3中子任務(wù)進(jìn)行資源匹配,如表2所示。

步驟 2實(shí)時監(jiān)控匹配過程中的子任務(wù)pi,j,全部滿足oi,j≤Di,進(jìn)入步驟3。

步驟 3任務(wù)與資源匹配完成,生成子任務(wù)集P7={p2,1, p1,2, p1,1, p2,4, p2,2, p2,3, p1,3, p1,4},開始執(zhí)行任務(wù),如圖4所示。

表2　測試任務(wù)計算數(shù)據(jù)

圖4　初始階段測試任務(wù)調(diào)度甘特圖Fig.4　Testing task scheduling Gantt chart in the initial phase

3.2TP策略

步驟 1設(shè)定推遲增量ΔT=2,則Td=T+ΔT=8;提取時刻Td后的等待子任務(wù),與新加入的E3組成子任務(wù)集P5={p1,4,p1,3,p2,3,p3,1,p3,2,p3,3,p3,4}。

步驟 2計算P5中所有子任務(wù)的動態(tài)優(yōu)先級DPA,如表2所示;以子任務(wù)p1,3為例,計算其動態(tài)優(yōu)先級:

(0.90×16)/[(40-20)×(40-20-16)]=0.180 0

(14)

依據(jù)計算結(jié)果對子任務(wù)排序得到子任務(wù)集P6={p3,2,p3,1,p2,3,p3,3,p3,4,p1,3,p1,4}。

步驟 3實(shí)時監(jiān)控匹配過程中子任務(wù)pi,j,發(fā)現(xiàn)p1,4的o1,4>D1。

步驟 4基于MFP原則前移子任務(wù)p1,4,更新子任務(wù)集P6={p3,2,p3,1,p1,4,p2,3,p3,3,p3,4,p1,3},新序列中的子任務(wù)全部滿足oi,j≤Di,對P6中子任務(wù)進(jìn)行資源匹配,如表2所示。

步驟 5任務(wù)與資源匹配完成,更新子任務(wù)集P7={p2,1,p1,2,p1,1,p2,4,p2,2,p3,2,p3,1,p1,4,p2,3,p3,3,p3,4,p1,3},其中p1,1已經(jīng)完成,p2,1,p1,2,p2,4,p2,2正在執(zhí)行;執(zhí)行后續(xù)任務(wù),如圖5所示。

圖5　執(zhí)行階段測試任務(wù)搶占甘特圖Fig.5　Testing task preemption Gantt chart in the execution phase

4　結(jié)　論

綜合考慮測試任務(wù)的DVD、EU和資源LB等影響因素,提出了TTPSADP:在任務(wù)執(zhí)行的初始階段依托DPA實(shí)現(xiàn)了任務(wù)的最優(yōu)排序,在任務(wù)搶占階段依托TP實(shí)現(xiàn)了任務(wù)間執(zhí)行順序的合理搶占,在保證任務(wù)執(zhí)行成功率的基礎(chǔ)上,實(shí)現(xiàn)了ATS價值收益和內(nèi)部資源均衡利用的綜合優(yōu)化。

[1] Xia J L, Chen H, Yang B. A real-time tasks scheduling algorithm based on dynamic priority[J].ChineseJournalofCompu-ters, 2012, 35(12): 2685-2695. (夏家莉, 陳輝, 楊兵. 一種動態(tài)優(yōu)先級實(shí)時任務(wù)調(diào)度算法[J].計算機(jī)學(xué)報, 2012, 35(12): 2685-2695.)

[2] Burus A, Prasad D, Bondavalli A, et al. The meaning and role of value in scheduling flexible real-time system[J].JournalofSystemsArchitecture, 2000, 46(4): 305-325.

[3] Balbastre P, Ripoll I, Crespo A. Minimum deadline calculation for periodic real-time tasks in dynamic priority systems[J].IEEETrans.onComputers, 2008, 57(1): 96-109.

[4] Liang X, Li X S, Yu J S. Research on the task schedule algorithm based on the GA[J].JournalofElectronicMeasurementandInstrument,2009,23(2):19-24.(梁旭,李行善,于勁松.基于遺傳算法的并行測試調(diào)度算法研究[J].電子測量與儀器學(xué)報,2009,23(2): 19-24.)

[5] Huang M M,Luo R G． Study on flexible-resource-constrained product development project scheduling[J].JournalofIndustrialEngineering/EngineeringManagement, 2010, 24(4): 143-148. (黃敏鎂, 羅榮桂. 柔性資源約束下的產(chǎn)品開發(fā)項(xiàng)目優(yōu)化調(diào)度研究[J]. 管理工程學(xué)報, 2010, 24(4): 143-148.)

[6] Wan M, Zhang F M, Fan X G. Two novel algorithm for equipment maintenance task scheduling in wartime[J].SystemsEngineeringandElectronics,2012,34(1):107-110.(萬明,張鳳鳴,樊曉光.戰(zhàn)時裝備維修任務(wù)調(diào)度的兩種新算法[J].系統(tǒng)工程與電子技術(shù),2012,34(1):107-110.)

[7] Bellenguez-Morineau O. Methods to solve multi-skill project scheduling problem[J].AQuarterlyJournalofOperationResearch, 2008, 6(1): 85-88.

[8] Wang Z Y, Yan X Q, Zhu Y, et al. An optimal method on dynamic maintenance task scheduling with subject taken into account[J].ActaArmamentarii,2009,30(2):252-256.(王正元,嚴(yán)小琴,朱昱,等.一種考慮專業(yè)的動態(tài)維修任務(wù)調(diào)度的優(yōu)化方法[J].兵工學(xué)報,2009,30(2):252-256.)

[9] Xu C J, Li A P, Liu X M. Multi-project scheduling algorithm based on resource push-pull technology[J].ComputerIntegratedManufacturingSystems, 2010, 16(6): 1246-1254. (徐賜軍, 李愛平, 劉雪梅. 基于資源推拉技術(shù)的多項(xiàng)目調(diào)度算法[J]. 計算機(jī)集成制造系統(tǒng), 2010, 16(6): 1246-1254.)

[10] Ben A M, Sassi M, Gossa M. Simultaneous scheduling of production and maintenance tasks in the job shop[J].InternationalJournalofProductionResearch, 2011, 49(13): 3891-3918.

[11] Safari E, Sadjadi S J. A hybrid method for flow shops scheduling with condition-based maintenance constraint and machines breakdown[J].ExpertSystemswithApplication, 2011, 38(3): 2020-2029.

[12] Hsu C J, Yang S J, Yang D L. Due-date assignment and optimal maintenance activity scheduling problem with linear deteriorating jobs[J].JournalofMarineScienceandTechnology, 2011, 19(1): 97-100.

[13] Lü X Z, Chen L, Yin J, et al. Maintenance task scheduling model considering rest time and its solving algorithm[J].ActaArmamentarii,2014,35(12):2116-2123.(呂學(xué)志,陳樂,尹健,等.考慮休息的維修任務(wù)調(diào)度模型及其求解算法[J].兵工學(xué)報,2014,35(12):2116-2123.)

[14] Wang X, Yan J L. Evaluation function-based dynamic collaboration task scheduling algorithm[J].JournalofHuazhongUniversityofScienceandTechnology(NaturalScienceEdition), 2011, 39(10): 46-49. (王璇, 顏景龍. 基于評價函數(shù)的動態(tài)協(xié)同任務(wù)調(diào)度算法[J]. 華中科技大學(xué)學(xué)報(自然科學(xué)版), 2011, 39(10): 46-49.)

[15] Zhu Y, Song J S, Wang Z Y. Scheduling model of the battle equipment maintenance task based on the most support time[J].SystemsEngineeringandElectronics, 2007, 29(11): 1900-1903. (朱昱, 宋建社, 王正元. 一種基于最大保障時間的戰(zhàn)時裝備維修任務(wù)調(diào)度[J]. 系統(tǒng)工程與電子技術(shù), 2007, 29(11): 1900-1903.)

[16] Jin H, Wang H A, Wang Q, et al. An improved least-slack-first scheduling algorithm[J].JournalofSoftware, 2004, 15(8): 1116-1123. (金宏, 王宏安, 王強(qiáng), 等. 改進(jìn)的最小空閑時間優(yōu)先調(diào)度算法[J]. 軟件學(xué)報, 2004, 15(8): 1116-1123.)

Testtaskpreemptiveschedulingalgorithmbasedondynamicpriority

DINGChao,TANGLi-wei,DENGShi-jie

(Department of Artillery Engineering, College of Ordinance Engineering, Shijiazhuang 050000, China)

Thereisaphenomenonoflowtestefficiencyandlongcycleundertheexistingequipmenttestmodelinthearmy,whichishardtosatisfytheincreasinglycomplextestrequirements.Consideringthetimeandvalueattributesandqualitativeanalysisofthetaskexecutionurgency,valuedensityandresourceloadbalancing,thetacticsofdynamicpriorityassignment(DPA)andtaskpreemption(TP),whichisusedinthebeginningoftaskexecution,arestudiedtoachievethecomprehensiveoptimizationofthevaluegains,taskexecutionsuccessrateandresourceloadbalancingoftheautomatictestsystem(ATS),namelythetesttaskpreemptiveschedulingalgorithmbasedondynamicpriority(TTPSADP).

automatictestsystem(ATS);dynamicpriority(DP);taskpreemption(TP);schedulingalgorithm

2015-11-04；

2016-01-11；網(wǎng)絡(luò)優(yōu)先出版日期：2016-05-12。

TP316

ADOI:10.3969/j.issn.1001-506X.2016.09.16

丁超(1990-),男,博士研究生,主要研究方向?yàn)樽詣訙y試系統(tǒng)設(shè)計與應(yīng)用。

E-mail:duncan1119@163.com

唐力偉(1961-),男,教授,博士,主要研究方向?yàn)樽詣訙y試系統(tǒng)、機(jī)械測試及性能檢測與故障診斷。

E-mail:tom5157@163.com

鄧士杰(1982-),男,講師,博士,主要研究方向?yàn)楣收显\斷及自動測試系統(tǒng)。

E-mail:13700317750@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160512.0908.004.html