陳 昊，趙 斐，白建東

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

0 引言

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

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

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

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

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

由于衛(wèi)星系統(tǒng)在運(yùn)行過程中可能會(huì)遇到各種環(huán)境變化、任務(wù)擾動(dòng)，導(dǎo)致當(dāng)前調(diào)度方案無法順利地執(zhí)行下去，需要對(duì)調(diào)度方案進(jìn)行動(dòng)態(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

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

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

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

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

2.1 約束滿足問題

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

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

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

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

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

Td：表示動(dòng)態(tài)調(diào)度時(shí)刻點(diǎn)；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

約束條件如下：

(3)

(4)

(5)

(6)

(7)

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

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

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

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

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

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

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

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

3.1.1 可見時(shí)間窗口擁擠度

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

(8)

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

3.1.2 執(zhí)行時(shí)刻點(diǎn)重疊度

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

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

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

3.2.1 預(yù)處理

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

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

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

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

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

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

3.2.3 ISR-HA算法

ISR-HA算法步驟如下：

① 需要?jiǎng)討B(tài)插入的新任務(wù)集合NewTasks中共有N個(gè)任務(wù)，將N個(gè)任務(wù)降序排列。

② 令i= 1。

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

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

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

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

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

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

⑨ 循環(huán)處理Q中每個(gè)任務(wù)，若隊(duì)列為空則轉(zhuǎn)⑩，否則取出隊(duì)首元素j，若無沖突直接安排任務(wù)j成功，那么繼續(xù)處理下一個(gè)隊(duì)首元素；否則，找出與任務(wù)j沖突的最小權(quán)值任務(wù)集Δwj，若任務(wù)j的權(quán)值大于Δwj，那么任務(wù)j安排成功，并將與任務(wù)j沖突的任務(wù)加入Q中，繼續(xù)處理下一個(gè)隊(duì)首元素；否則刪除任務(wù)j，并將其加入任務(wù)集Delete，繼續(xù)處理下一個(gè)隊(duì)首任務(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í)行窗口下的情況)。由此可知，如果要將動(dòng)態(tài)任務(wù)k插入在資源r的執(zhí)行窗口1，則此時(shí)與任務(wù)4及任務(wù)5在資源r上的執(zhí)行時(shí)間窗口沖突，為了能夠?qū)?dòng)態(tài)任務(wù)k插入在資源r的執(zhí)行窗口1上，此時(shí)必須將任務(wù)4及任務(wù)5的執(zhí)行時(shí)間窗口在其可見時(shí)間窗口范圍內(nèi)移動(dòng)到對(duì)應(yīng)的虛線框內(nèi)的時(shí)間段。同樣，如果要將動(dòng)態(tài)任務(wù)k插入在資源r的執(zhí)行窗口2，則此時(shí)與任務(wù)1、任務(wù)2及任務(wù)3在資源r上的執(zhí)行時(shí)間窗口沖突，為了能夠?qū)?dòng)態(tài)任務(wù)k插入在資源r的執(zhí)行窗口2上，此時(shí)必須將任務(wù)1、任務(wù)2及任務(wù)3的執(zhí)行時(shí)間窗口在其可見時(shí)間窗口范圍內(nèi)移動(dòng)到對(duì)應(yīng)的虛線框內(nèi)的時(shí)間段。

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

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

4.2 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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