對地觀測衛(wèi)星動態(tài)任務(wù)調(diào)度優(yōu)化算法研究

陳 昊，趙 斐，白建東

(北京跟蹤與通信技術(shù)研究所，北京 100094)

0 引言

對地觀測衛(wèi)星任務(wù)規(guī)劃的目標(biāo)就是選擇需要觀測的目標(biāo)、確定觀測的衛(wèi)星遙感器、觀測開始時間和結(jié)束時間。對于多顆衛(wèi)星、多種遙感器和多個任務(wù)需求的情況下，如何充分分配衛(wèi)星資源、高效地完成任務(wù)和發(fā)揮對地觀測衛(wèi)星系統(tǒng)的能力，生成一個滿意的衛(wèi)星任務(wù)規(guī)劃方案，顯得非常重要。

國內(nèi)外對于衛(wèi)星對地觀測任務(wù)規(guī)劃問題已經(jīng)開展了較多研究。P.Wang等[1-2]建立了約束規(guī)劃模型，并比較了貪婪算法、動態(tài)規(guī)劃、約束規(guī)劃和局部搜索4種不同的求解策略；Han S M等[3-4]建立多目標(biāo)敏捷衛(wèi)星調(diào)度模型，并提出一種偏好的隨機(jī)遺傳算法求解該問題，研究了多種選擇策略和解碼策略；LI J F等[5]利用敏捷衛(wèi)星的高機(jī)動性優(yōu)勢，提出了一種針對區(qū)域目標(biāo)的最優(yōu)條帶劃分和觀測窗口計算方法；國內(nèi)以國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程團(tuán)隊為代表，在單星以及多星對地觀測的任務(wù)規(guī)劃問題上進(jìn)行了廣泛和深入的研究，取得了一系列的研究成果[6-14]。

但是，截止目前，國內(nèi)外對于衛(wèi)星對地觀測任務(wù)規(guī)劃問題的研究主要是針對靜態(tài)任務(wù)，即給定一定時間(通常為1天)進(jìn)行一次，在調(diào)度前衛(wèi)星觀測任務(wù)是預(yù)先提交確定的，規(guī)劃方案一經(jīng)生成便不再改變，方案提交給衛(wèi)星進(jìn)行執(zhí)行完成即可。然而這種情況在應(yīng)急任務(wù)時并不合適。此外，衛(wèi)星系統(tǒng)在運行過程中因為各種原因，導(dǎo)致當(dāng)前調(diào)度方案無法順利執(zhí)行下去，也需要對調(diào)度方案進(jìn)行動態(tài)調(diào)整。

本文針對衛(wèi)星任務(wù)規(guī)劃調(diào)度的動態(tài)調(diào)整需求，在每個動態(tài)調(diào)度決策點，將所有的任務(wù)劃分為已完成任務(wù)、已安排任務(wù)和新任務(wù)。首先對衛(wèi)星任務(wù)動態(tài)調(diào)度問題進(jìn)行統(tǒng)一描述，包括新任務(wù)的插入、已安排任務(wù)的取消、任務(wù)優(yōu)先級的變更、天氣條件的變化和衛(wèi)星資源狀態(tài)的變化描述為新任務(wù)的插入；其次以最大任務(wù)收益和最小任務(wù)擾動測度為目標(biāo)函數(shù)構(gòu)建完成任務(wù)動態(tài)調(diào)度優(yōu)化模型，設(shè)計可見時間窗口擁擠度和執(zhí)行時刻點重疊度2種啟發(fā)式因子，基于啟發(fā)式智能ISR-HA算法尋求最優(yōu)任務(wù)編排結(jié)果。

1 任務(wù)動態(tài)調(diào)度問題的統(tǒng)一描述

由于衛(wèi)星系統(tǒng)在運行過程中可能會遇到各種環(huán)境變化、任務(wù)擾動，導(dǎo)致當(dāng)前調(diào)度方案無法順利地執(zhí)行下去，需要對調(diào)度方案進(jìn)行動態(tài)調(diào)整。衛(wèi)星任務(wù)優(yōu)化調(diào)度技術(shù)路徑如圖1所示。

圖1 衛(wèi)星任務(wù)優(yōu)化調(diào)度技術(shù)路徑Fig.1 Technical approach to optimal sechduling of satellite mission

本文分析各類擾動對姿態(tài)機(jī)動時間的影響，結(jié)合星上實時狀態(tài)信息，把動態(tài)調(diào)度問題統(tǒng)一用插入任務(wù)的衛(wèi)星動態(tài)調(diào)度問題進(jìn)行描述，在每個動態(tài)調(diào)度決策點，將所有的任務(wù)劃分為3種類型：己完成任務(wù)、已安排任務(wù)和新任務(wù)，如圖2所示。已完成任務(wù)不需要再考慮；已安排任務(wù)表示在當(dāng)前調(diào)度方案中尚未執(zhí)行的任務(wù)；新任務(wù)指的是新到達(dá)任務(wù)或因不滿足約束條件而暫時沒有安排進(jìn)當(dāng)前調(diào)度方案的任務(wù)。任務(wù)動態(tài)調(diào)整指的是有新任務(wù)或者是已安排任務(wù)中，因約束條件改變導(dǎo)致無法按當(dāng)前調(diào)度方案執(zhí)行，或當(dāng)約束條件改變而導(dǎo)致某些任務(wù)無法按當(dāng)前調(diào)度方案執(zhí)行時，已安排任務(wù)就轉(zhuǎn)化為新任務(wù)。

圖2 動態(tài)調(diào)度任務(wù)的劃分Fig.2 Partition of dynamic sechduling tasks

可以把未安排任務(wù)看作是新任務(wù)集中的任務(wù)，并將取消的任務(wù)從已安排任務(wù)集中刪除；針對任務(wù)優(yōu)先級變化，如已安排任務(wù)的收益變低，或未安排任務(wù)收益變高，需將新任務(wù)集中的高收益任務(wù)插入到調(diào)度方案中，同時可將低收益任務(wù)從調(diào)度方案中調(diào)整出任務(wù)集；對天氣情況變化和衛(wèi)星資源變化，需要把這些因天氣條件不滿足暫無法執(zhí)行的任務(wù)從已安排任務(wù)集調(diào)整到新任務(wù)集中，必要時將后續(xù)優(yōu)先級低的任務(wù)從調(diào)度方案中調(diào)整出來。因此，動態(tài)調(diào)度調(diào)整問題中雖然擾動的類型不同，但本質(zhì)上都可以歸結(jié)為一類插入任務(wù)的動態(tài)調(diào)度問題。

2 衛(wèi)星任務(wù)動態(tài)調(diào)度優(yōu)化模型

2.1 約束滿足問題

在人工智能領(lǐng)域中有一個比較重要的問題就是約束滿足問題。一個約束滿足問題由3部分組成：① 變量集合；② 對應(yīng)變量所屬的值域；③ 求解過程中需要滿足的相關(guān)約束集合。

約束滿足問題的求解目標(biāo)是滿足各項約束條件的前提下，為在每個變量相應(yīng)的值域范圍內(nèi)取某一個特定的值。約束滿足問題的描述形式有多種，一種較為有代表性的定義是把約束滿足問題以一個三元組P=〈V,D,C〉來表示，其中：V為變量集，V={V1,V2,...,Vn}；D為定義域集，D={D1,D2,...,Dn}，其中Di為Vi的值域；C為約束關(guān)系集，C={C1,C2,...,Cm}，每個約束Cj與V的一個子集相關(guān)，即Cj≤Vsub，其中Vsub是約束中包含的變量，Vsub=Vj1×Vj2×...×Vjn；R是與變量相關(guān)的值域：R=Dj1×Dj2×...×Djn，即每個約束關(guān)系確定了它所涉及的變量定義域的笛卡兒積的一個子集；R>表示一個約束關(guān)系。

約束滿足問題的解是組合{〈V1,d1〉,〈V2,d2〉,...,〈Vn,dn〉}，該組合滿足所有相關(guān)的約束條件，其中di∈Di。

在優(yōu)化模型構(gòu)建前，首先對問題進(jìn)行假設(shè)，關(guān)注核心約束條件，實現(xiàn)模型約束條件的簡化，然后提出動態(tài)調(diào)度優(yōu)化的目標(biāo)函數(shù)與約束條件。多星任務(wù)動態(tài)調(diào)度問題涉及多顆衛(wèi)星，每顆衛(wèi)星都具有固定的運行狀態(tài)。同時，該問題也涉及多個地面觀測目標(biāo)，每個地面觀測目標(biāo)均有明確的經(jīng)緯度信息。受衛(wèi)星運行過程的限制，衛(wèi)星在一天內(nèi)通過地面觀測目標(biāo)的時間是有限的，此時間范圍稱為可見時間窗口?？捎脮r間窗相對于衛(wèi)星需要執(zhí)行的任務(wù)而言往往是不足的，所以，需要編排合理的衛(wèi)星調(diào)度執(zhí)行方案。

S：表示衛(wèi)星資源集合，即S={s1,s2,...,sn}；

Td：表示動態(tài)調(diào)度時刻點；

OriginTasks：表示原調(diào)度方案集合，即OriginTasks={t1,t2,...,tm}，其中ti表示原調(diào)度方案中第i個任務(wù)；

NewTasks：表示新任務(wù)集合，即NewTasks={t1,t2,...,tp}，其中ti表示新任務(wù)集中第i個任務(wù)；

Values：表示所有任務(wù)的價值集合，Values={v1,v2,...,vm+p}，其中任務(wù)數(shù)為m+p，即新任務(wù)與原調(diào)度方案任務(wù)數(shù)之和；

disturbi：布爾變量，表示任務(wù)ti是否受到擾動，是則為1，否則為0，其中ti∈OriginTasks；

tci：表示衛(wèi)星遙感器的相鄰任務(wù)間切換時間，即tci表示衛(wèi)星si的遙感器轉(zhuǎn)換時間，由于之前假設(shè)一個衛(wèi)星只攜帶一種傳感器，那么si∈S；

di：表示任務(wù)ti需要滿足的持續(xù)觀測時間，其中ti∈NewTasks∪OriginTasks；

ai：表示任務(wù)ti到達(dá)的時刻點，其中ti∈NewTasks∪OriginTasks；

ei：表示任務(wù)ti必須在此之前完成，即任務(wù)的完成截止期限，其中ti∈NewTasks∪OriginTasks；

tmini：表示衛(wèi)星si的遙感器最小開機(jī)時間；

tmaxi：表示衛(wèi)星si的遙感器最長開機(jī)時間。

2.2任務(wù)動態(tài)調(diào)度模型

衛(wèi)星動態(tài)調(diào)度問題可描述為：已知衛(wèi)星資源S，在動態(tài)調(diào)度決策時刻點Td，有一批新任務(wù)集NewTasks需要插入到原調(diào)度方案中OriginTasks。在滿足衛(wèi)星任務(wù)各種約束條件下，獲取盡量大的任務(wù)總價值，由于動態(tài)調(diào)度問題需要滿足時效性，所以應(yīng)保證盡量快地制定出新的調(diào)度方案，并保證新方案與原調(diào)度方案的差異性越小越好。

針對對地觀測衛(wèi)星在執(zhí)行初始調(diào)度方案的過程中經(jīng)常遇到各種突發(fā)事件的情況，分析導(dǎo)致動態(tài)調(diào)度的主要擾動因素以及主要的約束條件，并將其歸為一類復(fù)雜約束下的新任務(wù)插入問題，以最大化完成任務(wù)優(yōu)先級之和，并將對原調(diào)度計劃調(diào)整最小作為另一個目標(biāo)，建立了具有兩級優(yōu)化目標(biāo)的動態(tài)約束滿足問題模型。

衛(wèi)星對地觀測動態(tài)調(diào)度問題可以描述為七元組：

〈SimTime,S,Td,OriginTasks,Windows,Constraints,Values〉。

SimTime為整個仿真周期，SimTime=[tb,te]，tb表示仿真周期起始點，te表示仿真周期結(jié)束點。TimeWindows為所有任務(wù)的時間窗口集，即TimeWindows={tw1,tw2,...,twm+p}。Constraints表示任務(wù)所要滿足的所有約束集。

優(yōu)化目標(biāo)函數(shù)如下：

(1)

(2)

式(1)為第一級目標(biāo)，表示最大化完成任務(wù)總權(quán)值，反映了調(diào)度方案整體的收益。式(2)為第二級目標(biāo)，表示最小化受干擾的原計劃任務(wù)數(shù)目，反映了新任務(wù)對原調(diào)度方案的震蕩程度。

約束條件如下：

(3)

(4)

(5)

(6)

(7)

式(3)表示每個任務(wù)最多被某顆衛(wèi)星執(zhí)行一次， 如果任務(wù)i被成功安排在資源i的綠色部分，對于同一資源上和其他資源上的任何位置都不能再安排任務(wù)i。

式(4)表示每個任務(wù)的執(zhí)行時間必須在可見時間窗口內(nèi)，且滿足相應(yīng)的持續(xù)時間。

式(5)表示為了保證任務(wù)的時效性，每個任務(wù)必須安排在其規(guī)定的截止時間之前，比如雖然任務(wù)i在資源1、資源2及資源3上均有2個不同的時間窗口，但考慮到任務(wù)的截至期限，實際上，任務(wù)在各個資源上的有效時間窗口均只有一個，各個資源上位于任務(wù)的截至期限之后的時間窗口均為無效時間窗口。

式(6)表示在同一個衛(wèi)星上相鄰的2個被安排任務(wù)，必須滿足相應(yīng)的轉(zhuǎn)換時間，以保證衛(wèi)星有足夠的時間完成姿態(tài)轉(zhuǎn)換。

式(7)表示一顆衛(wèi)星資源在同一時刻只能完成一個任務(wù)。

3 衛(wèi)星任務(wù)動態(tài)調(diào)度優(yōu)化算法

對地觀測衛(wèi)星動態(tài)調(diào)度問題實質(zhì)是在滿足各項約束條件的前提下，為各項任務(wù)合理分配衛(wèi)星資源以及確定執(zhí)行起止時間。雖然可以撤銷原方案，利用整體重新規(guī)劃調(diào)度的方法對所有的任務(wù)進(jìn)行新的分配，理論意義上能得到全局最優(yōu)解，但是這種方式?jīng)]有充分利用原調(diào)度方案的優(yōu)良特性，而且處理數(shù)據(jù)規(guī)模過大，無法滿足時效性要求，并且產(chǎn)生的新調(diào)度方案對原調(diào)度方案干擾過大，不利于后續(xù)工作的開展。本文基于對地觀測衛(wèi)星任務(wù)安排中2個關(guān)鍵過程，即可見時間窗口的選取和執(zhí)行時刻點的確定，給出了2種比較合理的啟發(fā)因子，并將其加入了設(shè)計的基于啟發(fā)式規(guī)則的ISR-HA算法。

3.1 啟發(fā)因子設(shè)計

3.1.1 可見時間窗口擁擠度

可見時間窗口擁擠度，是指當(dāng)將任務(wù)i安排在某個可見時間窗口后，對其他未安排新任務(wù)可能造成的干擾程度，以及對原調(diào)度方案中已安排任務(wù)干擾之和，計算公式如下：

(8)

式中，NT為新任務(wù)集中所有在衡量任務(wù)ti時還未安排的任務(wù)；OT為原調(diào)度方案任務(wù)集；λ為權(quán)衡對新任務(wù)和原任務(wù)干擾程度比重因子，根據(jù)需要進(jìn)行調(diào)整，本方案中取λ=3。

3.1.2 執(zhí)行時刻點重疊度

每個任務(wù)都需要確定它的執(zhí)行開始時刻和結(jié)束時刻，而每個任務(wù)的持續(xù)時間是一定的，那么只需要確定每個任務(wù)的開始時刻即可。若按照最早開始原則選擇，有些情況會導(dǎo)致有些任務(wù)無法執(zhí)行。如在同一個資源r上，若選擇最早開始原則安排任務(wù)j，那么若后續(xù)任務(wù)i在該資源上的時間窗口也比較靠前，則將無法分配時間段執(zhí)行觀測。若按圖3方式安排任務(wù)j，那么任務(wù)i和任務(wù)j均能得到安排。由此引入第二個啟發(fā)因子，即執(zhí)行時刻點重疊度。

圖3 按基于執(zhí)行時刻點重疊度插入任務(wù)Fig.3 Insert task based on overlap of execution time

3.2 啟發(fā)式ISR-HA算法設(shè)計

3.2.1 預(yù)處理

在預(yù)處理過程中，主要完成3大任務(wù)：

① 將動態(tài)調(diào)度時刻點以前的任務(wù)安排為已完成；② 刪除動態(tài)調(diào)度時刻點以前的任務(wù)時間窗口；③ 刪除不滿足任務(wù)觀測時長的時間窗口。

3.2.2 基于遺傳算法的初始調(diào)度方案

在新任務(wù)動態(tài)插入之前，需要對原始任務(wù)集生成初始調(diào)度方案，在本文中使用遺傳算法(GA)對原始任務(wù)集生成初始調(diào)度方案。具體流程包括編碼設(shè)計—適應(yīng)度函數(shù)設(shè)計，由于遺傳算法比較成熟，本文不再贅述，需要強調(diào)的是：在編碼設(shè)計中本文采用“衛(wèi)星資源-時間窗次序編號”形式定義單個染色體，其示意如圖4所示。

圖4 動態(tài)調(diào)度遺傳算法編碼示意Fig.4 Diagram of genetic algorithm coding for dynamic sechduling

第1號任務(wù)分配給第4顆衛(wèi)星的第2個可見時間窗口，第2號任務(wù)分配給第5顆衛(wèi)星的第3個可見時間窗口，第3號任務(wù)分配給第1顆衛(wèi)星的第4個可見時間窗口，第5號任務(wù)分配給第2顆衛(wèi)星的第2個可見時間窗口。其中“0-0”表示第4號任務(wù)沒有對應(yīng)的衛(wèi)星資源進(jìn)行分配。

3.2.3 ISR-HA算法

ISR-HA算法步驟如下：

① 需要動態(tài)插入的新任務(wù)集合NewTasks中共有N個任務(wù)，將N個任務(wù)降序排列。

② 令i= 1。

③ 選擇NewTasks集合中第i個任務(wù)，計算任務(wù)i每個可見時間窗口的擁擠度，并按非降序原則排列。

④ 按排序后的可見時間窗口順序，依次考察每個可見時間窗口，計算該時間窗口內(nèi)每個時刻點的重疊度，并按非降序原則排列。依次考察排序后每個時刻點，嘗試無沖突的直接插空安排任務(wù)i，若成功，則轉(zhuǎn)③；否則，轉(zhuǎn)⑤。

⑤ 分別計算任務(wù)i插入到每個可選時刻點后，與任務(wù)i相沖突的已安排任務(wù)的數(shù)目。設(shè)任務(wù)i共有mi個可選時刻點，則得到任務(wù)i的任務(wù)沖突數(shù)向量ΔNi=[Δn1,Δn2,...,Δnmi]，并記錄相應(yīng)的任務(wù)沖突集，并按非降序排列ΔNi。

⑥ 依次從小到大考察ΔNi(為了保證對原調(diào)度方案擾動最小)，令k=1。

⑦ 選擇Δnk，若k>mi， 則轉(zhuǎn)⑧，否則將任務(wù)i安排到此時所選擇的時刻點，將此時與任務(wù)i沖突的所有任務(wù)集移位，移位的原則是在不刪除任何任務(wù)的前提下，將這些沖突任務(wù)重新安排。若成功，則轉(zhuǎn)③;否則，恢復(fù)任務(wù)i插入前的狀態(tài)，k=k+1，轉(zhuǎn)⑦。

⑧ 分別計算ΔNi中每個相應(yīng)任務(wù)沖突集的任務(wù)價值之和ΔWi=[Δw1,Δw2,...,Δwmi]，選擇ΔWi中價值和最小的Δwk(為了保證最大化收益總值)，如果任務(wù)i的權(quán)值小于等于Δwk，表示任務(wù)i不能替代相應(yīng)的沖突任務(wù)集，那么刪除任務(wù)i，并將其加入任務(wù)集Delete，轉(zhuǎn)③；否則，將相應(yīng)的任務(wù)沖突任務(wù)集加入優(yōu)先級隊列Q中(Q的排序準(zhǔn)則是按任務(wù)權(quán)值從小到大排序)。

⑨ 循環(huán)處理Q中每個任務(wù)，若隊列為空則轉(zhuǎn)⑩，否則取出隊首元素j，若無沖突直接安排任務(wù)j成功，那么繼續(xù)處理下一個隊首元素；否則，找出與任務(wù)j沖突的最小權(quán)值任務(wù)集Δwj，若任務(wù)j的權(quán)值大于Δwj，那么任務(wù)j安排成功，并將與任務(wù)j沖突的任務(wù)加入Q中，繼續(xù)處理下一個隊首元素；否則刪除任務(wù)j，并將其加入任務(wù)集Delete，繼續(xù)處理下一個隊首任務(wù)。

⑩ 若i≥N，轉(zhuǎn)；否則i=i+1， 轉(zhuǎn)③。

其中，關(guān)鍵步驟④任務(wù)直接插入過程的流程如圖5所示。

圖5 任務(wù)直接插入流程Fig.5 Direct task insertion flow chart

其中步驟⑦任務(wù)移位插入過程示意如圖6所示(插入任務(wù)k在不同執(zhí)行窗口下的情況)。由此可知，如果要將動態(tài)任務(wù)k插入在資源r的執(zhí)行窗口1，則此時與任務(wù)4及任務(wù)5在資源r上的執(zhí)行時間窗口沖突，為了能夠?qū)討B(tài)任務(wù)k插入在資源r的執(zhí)行窗口1上，此時必須將任務(wù)4及任務(wù)5的執(zhí)行時間窗口在其可見時間窗口范圍內(nèi)移動到對應(yīng)的虛線框內(nèi)的時間段。同樣，如果要將動態(tài)任務(wù)k插入在資源r的執(zhí)行窗口2，則此時與任務(wù)1、任務(wù)2及任務(wù)3在資源r上的執(zhí)行時間窗口沖突，為了能夠?qū)討B(tài)任務(wù)k插入在資源r的執(zhí)行窗口2上，此時必須將任務(wù)1、任務(wù)2及任務(wù)3的執(zhí)行時間窗口在其可見時間窗口范圍內(nèi)移動到對應(yīng)的虛線框內(nèi)的時間段。

圖6 任務(wù)移位過程圖Fig.6 Task shift process diagram

綜上，ISR-HA算法流程如圖7所示。

圖7 ISR-HA算法流程Fig.7 ISR-HA algorithm flow chart

4 仿真實驗

本次仿真實驗環(huán)境為Core i7-8550 @1.8 GHz CPU，8 GB RAM，Windows 10，64位操作系統(tǒng)的筆記本電腦。設(shè)置仿真實驗的 5顆衛(wèi)星軌道參數(shù)，以及初始任務(wù)、新任務(wù)等相關(guān)基本參數(shù)，最后通過 Matlab R2016a 仿真對比驗證所提出算法的有效性。

4.1仿真參數(shù)設(shè)置

實驗的初始調(diào)度任務(wù)集數(shù)為150個，經(jīng)度范圍[76°E，131°E]，緯度范圍[17°N，45°N]內(nèi)隨機(jī)生成的點目標(biāo)任務(wù);動態(tài)任務(wù)集數(shù)為200個，經(jīng)度范圍[80°E，120°E]， 緯度范圍[20°N，42°N]內(nèi)隨機(jī)生成的點目標(biāo)任務(wù)。實驗通過衛(wèi)星工具包(STK)生成相應(yīng)的衛(wèi)星觀測任務(wù)集，動態(tài)任務(wù)集的經(jīng)緯度范圍更集中，有利于增加與原任務(wù)集的時間沖突度。仿真實驗總調(diào)度周期設(shè)置為24 h(2020年5月15日0:00-24:00)，動態(tài)調(diào)度時刻點設(shè)置為2020年5月15日6:00。

仿真實驗衛(wèi)星軌道基本參數(shù)設(shè)置如表1所示。

表1 仿真實驗衛(wèi)星軌道基本參數(shù)表Tab.1 Basic paramaters of simulation experimental satellite orbit

4.2 仿真實驗及結(jié)果分析

通過前一節(jié)設(shè)置的任務(wù)觀測集數(shù)據(jù)和衛(wèi)星軌道參數(shù)即可獲得每個觀測任務(wù)的衛(wèi)星過境窗口來進(jìn)行衛(wèi)星觀測任務(wù)的調(diào)度。由于反應(yīng)式調(diào)度基于初始預(yù)調(diào)度進(jìn)行重新調(diào)度，仿真實驗首先采用GA對初始任務(wù)集生成初始預(yù)調(diào)度方案，生成的初始調(diào)度方案如表2所示。

表2 仿真實驗初始調(diào)度方案(部分)Tab.2 Initial schedule scheme of simulation experiment (partial) 單位：s

為了驗證啟發(fā)因子本身設(shè)計的有效性，本文從2種設(shè)計的算法中分別加入和不加入啟發(fā)因子2種情況進(jìn)行對比，為了方便對以下實驗結(jié)果管理，做以下名稱替換：

(a) 表示未加任何啟發(fā)式策略的改進(jìn)迭代法；

(b) 表示加了時間窗口擁擠度，以及基于重疊度的開始執(zhí)行時間啟發(fā)因子的改進(jìn)迭代法；

(c) 表示沒有加入任何啟發(fā)因子的ISR-HA算法；

(d) 表示在直接插入過程、移位插入過程和替換插入過程中均加入了兩種啟發(fā)因子的ISR-HA算法。

通過設(shè)置動態(tài)任務(wù)集的個數(shù)(10、20、100和200)來對上述各個算法分組仿真，為避免少數(shù)實驗的隨機(jī)性造成的影響，本文將每種算法迭代 10 次，得到的衛(wèi)星調(diào)度結(jié)果如表3所示。

表3 各算法動態(tài)插入任務(wù)規(guī)劃仿真實驗結(jié)果表Tab.3 Simuliation experiment result of dynamic insertion of algorithms into a task planning

以任務(wù)收益和擾動測度作為最后對比的參考結(jié)果，具體結(jié)果如圖8所示。

圖8 4種算法任務(wù)調(diào)度收益對比Fig.8 Comparision of task scheduling benefits among four algorithms

由圖8可以看出，當(dāng)動態(tài)任務(wù)集個數(shù)較少時(個數(shù)為10和20)，緊急任務(wù)集與已安排任務(wù)集沖突度較小，4種算法都能完成已安排任務(wù)和動態(tài)任務(wù)集，無觀測收益上的差別；當(dāng)動態(tài)任務(wù)集個數(shù)較多時(個數(shù)為100和200)，緊急任務(wù)集與已安排任務(wù)集沖突度較大，ISR-HA算法的觀測收益要高于II-HA算法的觀測收益，其中ISR-HA比II-HA平均收益提高5.8%，并且加入2種啟發(fā)式因子的算法與不加啟發(fā)式因子的算法對比，明顯有觀測收益上的提高，其中II-HA和ISR-HA的平均收益分別增加5.2%和9.5%，證明了本研究2種啟發(fā)因子的有效性。4種算法任務(wù)擾動測度對比如圖9所示。

圖9 4種算法任務(wù)擾動測度對比Fig.9 Comparision of task disturbance measures among four algorithms

由圖9可以看出，當(dāng)動態(tài)任務(wù)集個數(shù)較少時(個數(shù)為10和20)，緊急任務(wù)集與已安排任務(wù)集沖突度較小，4種算法都能完成已安排任務(wù)和動態(tài)任務(wù)集，在任務(wù)擾動測度上無明顯區(qū)別；當(dāng)動態(tài)任務(wù)集個數(shù)較多時(個數(shù)為100和200)，緊急任務(wù)集與已安排任務(wù)集沖突度較大，II-HA算法的擾動測度起初低于ISR-HA算法的擾動測度，但隨著沖突度的增加，II-HA算法的擾動測度迅速增加并遠(yuǎn)遠(yuǎn)超過ISR-HA算法的擾動測度，另外加入2種啟發(fā)式因子的算法與不加啟發(fā)式因子的算法對比，明顯有擾動測度上的降低，其中II-HA和ISR-HA的平均擾動測度下降34%和34.4%，證明了本研究2種啟發(fā)因子的有效性。

5 結(jié)束語

衛(wèi)星對地觀測任務(wù)規(guī)劃問題已經(jīng)被證明是NP-Hard問題。本文針對衛(wèi)星任務(wù)規(guī)劃調(diào)度的動態(tài)調(diào)整需求，將所有的任務(wù)劃分為已完成任務(wù)、已安排任務(wù)和新任務(wù)。第一步，對衛(wèi)星任務(wù)動態(tài)調(diào)度問題進(jìn)行統(tǒng)一描述，包括新任務(wù)的插入、已安排任務(wù)的取消、任務(wù)優(yōu)先級的變更、天氣條件的變化和衛(wèi)星資源狀態(tài)的變化描述為新任務(wù)的插入；第二步，以最大任務(wù)收益和最小任務(wù)擾動測度為目標(biāo)函數(shù)構(gòu)建完成任務(wù)動態(tài)調(diào)度優(yōu)化模型，設(shè)計可見時間窗口擁擠度和執(zhí)行時刻點重疊度2種啟發(fā)式因子；最后，提出基于啟發(fā)式智能ISR-HA算法尋求最優(yōu)任務(wù)編排結(jié)果。