一種基于多約束關(guān)系的任務(wù)分解方法

霍永華,昌漢明，曹　毅

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所,河北 石家莊 050081；

2.西安電子科技大學(xué)，陜西 西安 710071;

3.總參信息化部石家莊地區(qū)軍事代表室，河北 石家莊 050000)

?

一種基于多約束關(guān)系的任務(wù)分解方法

霍永華1,昌漢明2，曹毅3

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所,河北 石家莊 050081；

2.西安電子科技大學(xué)，陜西 西安 710071;

3.總參信息化部石家莊地區(qū)軍事代表室，河北 石家莊 050000)

摘要：針對(duì)任務(wù)分解和分配的實(shí)時(shí)性和快速性，研究基于多約束關(guān)系的任務(wù)分解。首先對(duì)任務(wù)進(jìn)行初始化標(biāo)識(shí)，定義任務(wù)的唯一標(biāo)識(shí)、開始時(shí)間、生命周期及任務(wù)重要度。其次定義任務(wù)間的約束關(guān)系，包括同步、串行、父子關(guān)系以及同步下受時(shí)序和資源約束等，確定任務(wù)之間的相互聯(lián)系，為執(zhí)行任務(wù)分解做好準(zhǔn)備。然后，研究一種基于任務(wù)分解樹的算法：依據(jù)任務(wù)間約束關(guān)系通過(guò)任務(wù)分解樹的方法實(shí)現(xiàn)對(duì)任務(wù)的分解。最后附實(shí)例驗(yàn)證。

關(guān)鍵詞：任務(wù)重要度；同步關(guān)系；串行關(guān)系；父子關(guān)系；任務(wù)分解樹

0引言

針對(duì)抗震救災(zāi)壞境中宏觀任務(wù)的下達(dá)，任務(wù)的分解細(xì)化過(guò)程，研究一種任務(wù)的分解機(jī)制[1-3]。該機(jī)制首先依據(jù)任務(wù)的具體狀況定義任務(wù)的唯一標(biāo)識(shí)、開始時(shí)間、生命周期及任務(wù)重要度，實(shí)現(xiàn)對(duì)任務(wù)的初始化標(biāo)識(shí)。其次定義任務(wù)間的約束關(guān)系[4-6]，包括同步、串行、父子關(guān)系以及同步下受時(shí)序和資源約束等，確定任務(wù)之間的相互聯(lián)系，為執(zhí)行任務(wù)分解做好準(zhǔn)備。然后，研究一種基于任務(wù)分解樹的算法：建立一棵空的任務(wù)樹，將任務(wù)節(jié)點(diǎn)放入任務(wù)隊(duì)列中，依據(jù)任務(wù)間的約束關(guān)系從任務(wù)隊(duì)列中提取并放入任務(wù)樹的適當(dāng)位置，直至任務(wù)隊(duì)列為空，這樣最終依據(jù)任務(wù)間約束關(guān)系通過(guò)任務(wù)分解樹的方法實(shí)現(xiàn)對(duì)任務(wù)的分解。

1任務(wù)的四要素

任務(wù)可以分為復(fù)雜任務(wù)和簡(jiǎn)單子任務(wù)，為了更好地完成某個(gè)目標(biāo)，其對(duì)應(yīng)的任務(wù)應(yīng)該進(jìn)行分解和調(diào)度，以保障更好更快地完成。

定義每一個(gè)任務(wù)為一個(gè)四元組[7,8]G=(ID,Begin,Time,I)

① 其中ID代表每一個(gè)任務(wù)的名字，不同的任務(wù)具有不同的ID，且不可相同；

② Begin代表任務(wù)的開始時(shí)間，因?yàn)槿蝿?wù)的分解與調(diào)度中常有時(shí)序約束，所以要考慮不同任務(wù)的開始時(shí)間；

③ Time代表任務(wù)的持續(xù)時(shí)間；

④ I代表任務(wù)的重要度。所謂重要度指當(dāng)遇到突發(fā)情況時(shí)，每個(gè)節(jié)點(diǎn)的緊急情況可能各不相同，重要的節(jié)點(diǎn)應(yīng)優(yōu)先考慮處理，不同的任務(wù)可能具有不同的重要度。

2任務(wù)的關(guān)系約束

定義如下幾種關(guān)系約束：

① 同步執(zhí)行任務(wù)集 P={T1，T2，T3}，即任務(wù)T1、T2、T3可以同步地執(zhí)行，主要是對(duì)于同層的節(jié)點(diǎn)，如圖1所示。

圖1　并行任務(wù)示意圖　圖2　串行任務(wù)示意圖

③ 父子關(guān)系任務(wù)集 F={T5，T6，T7}，即任務(wù)T5可以進(jìn)一步分解為T6、T7。表示T5是T6和T7的父節(jié)點(diǎn)，父子關(guān)系任務(wù)集中，父節(jié)點(diǎn)可能全面的包含子任務(wù)或是部分包含，全面包含指的是子任務(wù)全部完成，父任務(wù)才可執(zhí)行，用集合表示為：T={T5，A{T6，T7}}，如圖3所示。而部分包含指的是完成部分子任務(wù)后即可開始執(zhí)行父任務(wù)，用集合表示為T={T5，O{T6，T7}}，如圖4所示。用方框置于外側(cè)是表示這是一個(gè)任務(wù)分解模塊，T5是由T6和T7組成的。

圖3　全包含父子關(guān)系　　圖4　部分包含父子　示意圖　關(guān)系示意圖

綜合分析上述情況可以把任務(wù)分解表示在一個(gè)大的集合內(nèi)。

根據(jù)上述定義可以得出任務(wù)分解樹，如圖5所示。

圖5　任務(wù)分解樹示意圖

其中T1對(duì)T3有時(shí)序或資源方面的約束，在圖中用T1-3來(lái)表示這種約束關(guān)系。T3、T4、T5是串行執(zhí)行的。T6、T7全包含于T5。針對(duì)不同任務(wù)節(jié)點(diǎn)的重要度，可以對(duì)任務(wù)分解圖進(jìn)一步優(yōu)化，節(jié)點(diǎn)的重要度可以開始時(shí)由更高層級(jí)直接指定，若沒有指定，則依據(jù)節(jié)點(diǎn)重要性的算法來(lái)衡量。假設(shè)圖5中高層級(jí)指定了T3的重要度高于T2，則在出現(xiàn)緊急情況時(shí)優(yōu)先考慮T3。若沒有指定，以節(jié)點(diǎn)重要性的角度去考慮，T3節(jié)點(diǎn)的度數(shù)高于T2，所以T3重要度大于T2(以節(jié)點(diǎn)的度來(lái)衡量重要性)，根據(jù)以上兩種情況，可以把任務(wù)分解樹優(yōu)化。

3基于任務(wù)樹的任務(wù)分解

在進(jìn)行任務(wù)調(diào)度時(shí)，首先要考慮節(jié)點(diǎn)間的時(shí)序約束，其次當(dāng)在進(jìn)行任務(wù)調(diào)度出現(xiàn)緊急情況時(shí)，同層中左邊節(jié)點(diǎn)的重要度大于右邊，所以優(yōu)先處理左邊節(jié)點(diǎn)出現(xiàn)的情況，這種任務(wù)分解樹看上去直觀，且考慮的更加全面。

基于任務(wù)樹的任務(wù)分解算法[9,10]步驟如圖5所示。

步驟1：初始化任務(wù)樹節(jié)點(diǎn)置為空，把每項(xiàng)任務(wù)定義為任務(wù)樹中的節(jié)點(diǎn)，并把節(jié)點(diǎn)間的相互約束關(guān)系置于節(jié)點(diǎn)關(guān)系表中；

步驟2：為每個(gè)節(jié)點(diǎn)分配唯一的ID，初始化任務(wù)的開始時(shí)間Begin和預(yù)估執(zhí)行時(shí)間Time，根據(jù)需要判斷是否初始化重要度I，若需要?jiǎng)t給定相應(yīng)等級(jí)，否則置為空；

步驟3：設(shè)置一個(gè)隊(duì)列，把所有任務(wù)節(jié)點(diǎn)置于隊(duì)列中，首先輸出代表源節(jié)點(diǎn)的節(jié)點(diǎn)S；

步驟4：從隊(duì)列中依次輸出每個(gè)任務(wù)節(jié)點(diǎn)；

步驟5：輸出的節(jié)點(diǎn)是否需要進(jìn)一步分解，若是則符合父子約束關(guān)系，在任務(wù)分解樹中生成該節(jié)點(diǎn)的子節(jié)點(diǎn)，其層次為父節(jié)點(diǎn)加一，并由父節(jié)點(diǎn)指向子節(jié)點(diǎn)。若不是則跳轉(zhuǎn)到7；

步驟6：判斷父節(jié)點(diǎn)是全包含還是部分包含，若是全包含則所有子任務(wù)執(zhí)行完成才認(rèn)為父節(jié)點(diǎn)完成，是部分包含則部分子任務(wù)完成，父任務(wù)就認(rèn)為完成；

步驟7：以節(jié)點(diǎn)任務(wù)表中的約束判斷輸出的節(jié)點(diǎn)是否符合同步執(zhí)行約束，若是則任務(wù)分解樹中節(jié)點(diǎn)間層次相同并假設(shè)層次為n，且由n-1層節(jié)點(diǎn)同時(shí)指向它們。若不是則跳轉(zhuǎn)到步驟8；

步驟8：以節(jié)點(diǎn)任務(wù)表中的約束判斷輸出的節(jié)點(diǎn)是否符合串行執(zhí)行約束，若是則任務(wù)分解樹中任務(wù)節(jié)點(diǎn)的層次逐步遞增，且層次低的節(jié)點(diǎn)指向?qū)哟胃叩墓?jié)點(diǎn)，若不是則跳轉(zhuǎn)到步驟9；

步驟9：按節(jié)點(diǎn)重要性算法計(jì)算未置初值的任務(wù)節(jié)點(diǎn)的重要度，判斷是否需要優(yōu)化，若是則跳轉(zhuǎn)到步驟10，不是則跳轉(zhuǎn)到步驟11；

步驟10：同層中把沒有時(shí)序約束且重要度高的節(jié)點(diǎn)i(包括它的子節(jié)點(diǎn))不斷左移，直到其左側(cè)節(jié)點(diǎn)對(duì)i有約束則停止，所有節(jié)點(diǎn)優(yōu)化完跳到步驟11；

步驟11：重復(fù)執(zhí)行步驟3，直到隊(duì)列中節(jié)點(diǎn)為空，生成任務(wù)分解樹。

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

假設(shè)某次抗震救災(zāi)補(bǔ)給災(zāi)區(qū)運(yùn)輸車加油，由于搭建基地就只有一個(gè)，所以每個(gè)運(yùn)輸車按串行補(bǔ)給，總補(bǔ)給任務(wù)稱為S，假設(shè)有n輛運(yùn)輸車，表示為B1、B2…Bn則n輛車之間的關(guān)系為串行關(guān)系，也就是當(dāng)?shù)?輛車加油完畢后，第2輛車才能加油。

步驟1：對(duì)任務(wù)進(jìn)行初始化標(biāo)識(shí)，定義唯一標(biāo)識(shí)為S，任務(wù)分為兩類，即運(yùn)輸油A和加油B，開始時(shí)間為ts，生命周期為T，任務(wù)重要度為非常重要；

步驟2：定義任務(wù)間的約束關(guān)系，只有運(yùn)輸油到的情況下，才能加油。因此對(duì)運(yùn)輸油任務(wù)A對(duì)加油任務(wù)B有時(shí)序約束。在運(yùn)輸加油任務(wù)中，由于加油基地只有一個(gè)，所以只能一個(gè)一個(gè)進(jìn)行加油，因此加油任務(wù)A為同步關(guān)系；運(yùn)輸油任務(wù)B可以并行進(jìn)行；

步驟3：建立一棵空的任務(wù)樹S，將任務(wù)節(jié)點(diǎn)(任務(wù)A和任務(wù)B)放入任務(wù)隊(duì)列中，依據(jù)兩個(gè)任務(wù)間的約束關(guān)系(任務(wù)A對(duì)任務(wù)B有時(shí)序約束)，從任務(wù)隊(duì)列中提取并放入任務(wù)樹的適當(dāng)位置，任務(wù)分解樹如圖6所示。

圖6　抗震救災(zāi)運(yùn)輸車加油任務(wù)分解圖

5結(jié)束語(yǔ)

為保證抗震救災(zāi)環(huán)境下任務(wù)的執(zhí)行，提出了救災(zāi)網(wǎng)絡(luò)任務(wù)分解方法。文中提出的幾種約束關(guān)系，考慮到了任務(wù)和任務(wù)間，總?cè)蝿?wù)和子任務(wù)間的關(guān)系。而重要度的提出也是考慮到作戰(zhàn)任務(wù)的特殊性，所謂重要度是指任務(wù)節(jié)點(diǎn)分主次，當(dāng)出現(xiàn)緊急情況時(shí)優(yōu)先考慮重要度高的任務(wù)，這可以保證在救災(zāi)環(huán)境下作戰(zhàn)任務(wù)能最大限度地不受其他因素的影響。

參考文獻(xiàn)

[1]肖增良,樂(lè)曉波.基于與或依賴圖的多Agent系統(tǒng)任務(wù)分解算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2009，40(2):267-272.

[2]鐘琪.基于啟發(fā)式算法的任務(wù)分解策略[J].煤炭技術(shù)，2010,30(12)：25-29.

[3]秦娜,樂(lè)曉波,劉武.基于 Petri 網(wǎng)模型的 JSP 粒子群優(yōu)化調(diào)度[J].計(jì)算機(jī)應(yīng)用,2008,28(8):2167-2169.

[4]White J E.Mobile Agents In：Bradshaw，Jeffrey eds.Software Agents，Menlo Pork [M]. California:Press / The MIT Press，1996.

[5]Lange D B.Mobile Objects and Mobile agents：The Future of Distributed Computing[C]∥Proc of the European Conf on Object Oriented Programming’98.Brussels，1998:49-52.

[6]楊學(xué)會(huì),王精業(yè).基于任務(wù)分解的作戰(zhàn)仿真研究[J].系統(tǒng)仿真學(xué)報(bào),2006,18(10):18-21.

[7]劉波,羅軍舟.大規(guī)模網(wǎng)絡(luò)管理中的任務(wù)分解與調(diào)度[J].通信學(xué)報(bào),2010,42(6):48-51.

[8]劉波,羅軍舟.網(wǎng)絡(luò)管理中多agent的半在線調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展,2006，27(3)：65-72.

[9]王紅霞,劉治國(guó),潘成勝．分布式網(wǎng)絡(luò)管理中的任務(wù)管理與任務(wù)調(diào)度的研究[J]．沈陽(yáng)工業(yè)學(xué)院學(xué)報(bào)，2009,30(11):15-19.

[10]金黎黎,孔令富．協(xié)同設(shè)計(jì)環(huán)境中任務(wù)分解與調(diào)度的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，25(2)：22-25.

Task Decomposition Method Based on Multiple Constraint Relations

HUO Yong-hua1,CHANG Han-ming2,CAO Yi3

(1.The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China;

2.Xidian University,Xi’an Shaanxi 710071,China;

3.Military Representative Office of Information Technology Department of General Staff Headquarters Stationed in Shijiazhuang,

Shijiazhuang Hebei 050081,China)

Abstract：In view of timeliness and quickness of task decomposition,this paper studies the task decomposition based on multiple constraint relations.Firstly the initialization identifier is defined on task,including unique identification and start time and life cycle and importance of missions.Secondly the constraint relations between tasks are defined,including synchronous relations and serial relations,father and son relations,time and resource constraints in synchronization,the inter-relationship between tasks are determined for preparation for task decomposition.Lastly an algorithm based on task decomposition tree is studied,which uses task decomposition tree to implement task decomposition according to constraint relations between tasks.Finally this algorithm is verified by an instance.

Key words：importance of Missions;synchronous relations;serial relations;father and son relations;task decomposition tree

作者簡(jiǎn)介：霍永華(1977 —)，女，高級(jí)工程師，主要研究方向：通信網(wǎng)絡(luò)管理。昌漢明(1989— )，男，碩士研究生，主要研究方向：通信網(wǎng)絡(luò)管理。

基金項(xiàng)目：國(guó)防基礎(chǔ)科研計(jì)劃基金項(xiàng)目資助

收稿日期：2015-09-08

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1003-3114(2016)01-35-3

doi:10.3969/j.issn.1003-3114.2016.01.09

引用格式：霍永華,昌漢明，曹毅.一種基于多約束關(guān)系的任務(wù)分解方法[J].無(wú)線電通信技術(shù),2016,42(1):35-37.