航天測控網(wǎng)調(diào)度的混合構(gòu)造啟發(fā)式算法

劉建平, 李　晶, 張?zhí)祢?/p>

(西安衛(wèi)星測控中心宇航動力學(xué)國家重點實驗室, 陜西 西安 710043)

?

航天測控網(wǎng)調(diào)度的混合構(gòu)造啟發(fā)式算法

劉建平, 李晶, 張?zhí)祢?/p>

(西安衛(wèi)星測控中心宇航動力學(xué)國家重點實驗室, 陜西 西安 710043)

摘要：針對航天測控網(wǎng)調(diào)度問題,提出一種基于混合啟發(fā)式的解構(gòu)造算法。與其他構(gòu)造啟發(fā)式算法不同的是,本啟發(fā)式算法充分利用了我國航天測控網(wǎng)調(diào)度需求的特點,包括優(yōu)先級、任務(wù)之間時間間隔要求和一個需求包括多個相同任務(wù)要求等,綜合考慮了任務(wù)局部和需求全局,融合最大可用窗口價值規(guī)則和最早可用窗口集規(guī)則。其優(yōu)勢在于通過動態(tài)選擇構(gòu)造啟發(fā)式規(guī)則來提高求解質(zhì)量。最后,通過仿真實驗分析比較,該算法可以在不明顯增加計算時間的基礎(chǔ)上得到更高的初始解質(zhì)量。

關(guān)鍵詞：構(gòu)造啟發(fā)式; 航天測控網(wǎng)調(diào)度問題; 測控需求; 約束優(yōu)化問題; 時間間隔

0引言

隨著各航天大國對空間領(lǐng)域的高度重視,在軌衛(wèi)星的日益增加造成測控資源的高度緊張,航天測控網(wǎng)調(diào)度問題研究成為航天工業(yè)領(lǐng)域運籌學(xué)研究熱點之一[1]。航天測控網(wǎng)調(diào)度是航天測控網(wǎng)管理的核心任務(wù),主要負(fù)責(zé)協(xié)調(diào)測控設(shè)備與在軌衛(wèi)星(或即將發(fā)射衛(wèi)星)之間的通信分配。航天測控網(wǎng)調(diào)度問題是指在測控資源有限的情況下,如何為測控任務(wù)分配合理的測控資源和時間,以最大化地滿足所有測控需求[2]。在實際的航天測控網(wǎng)調(diào)度中,最終調(diào)度方案的形成一般分為3個階段:第一階段是初始解生成階段,就是利用某種或多種構(gòu)造啟發(fā)式規(guī)則快速生成滿足所有約束的無沖突初始分配結(jié)果;第二階段是優(yōu)化解生成階段,就是利用某種局部搜索算法或迭代修復(fù)規(guī)則在初始解的基礎(chǔ)上進(jìn)行改進(jìn),通常是以一定計算代價來獲得高質(zhì)量的解;第三階段是沖突消解階段,主要采用與用戶協(xié)商的機(jī)制進(jìn)行沖突任務(wù)約束松弛,也最大化地滿足各方需求的調(diào)度方案[3]。其中前兩個階段通常不需要人參與求解,因而往往合并為計算機(jī)自動調(diào)度階段[4]。本文的研究主要針對計算機(jī)自動調(diào)度階段的初始解生成。

航天測控網(wǎng)調(diào)度問題初始解生成算法一般包括兩個決策問題,即任務(wù)的選擇和可用窗口的選擇。任務(wù)的選擇一般都是基于任務(wù)優(yōu)先級規(guī)則(如果任務(wù)具有事先確定的優(yōu)先級)。而可用窗口的選擇目前主要有4種規(guī)則:一種是可用窗口開始時間最早最先分配規(guī)則,稱為“先到先服務(wù)”(first coming first serving,FCFS)或“先進(jìn)先出”(first in first out,FIFO)策略,將基于測控需求和可見信息生成的測控任務(wù)所對應(yīng)的時間窗口開始時間作為排序的標(biāo)準(zhǔn),進(jìn)行可用窗口的選擇[5];一種是可用窗口沖突最少最先分配規(guī)則,稱為“瓶頸避免”(bottleneck avoidance, BA),以沖突度來衡量每個可用的時間窗口,并以沖突度作為排序的標(biāo)準(zhǔn),進(jìn)行可用窗口的選擇[6];一種是可用窗口靈活度最小最先分配規(guī)則,以某種靈活度指標(biāo)來衡量每個可用的時間窗口,并以靈活度為排序的標(biāo)準(zhǔn),進(jìn)行可用窗口選擇[7-8]。一種是可用窗口價值最大最先分配規(guī)則,以某種價值指標(biāo)來綜合衡量每個可用的時間窗口,并以價值為排序的標(biāo)準(zhǔn),進(jìn)行可用窗口選擇[9-10]。

考慮到我國航天測控網(wǎng)調(diào)度需求特點,以上構(gòu)造啟發(fā)式算法很難適應(yīng)單個測控需求多時間關(guān)聯(lián)任務(wù)的表現(xiàn)形式,本文提出一種基于混合構(gòu)造啟發(fā)式規(guī)則的求解算法。該算法綜合考慮任務(wù)局部和測控需求整體,能夠在不明顯增加計算時間的基礎(chǔ)上得到更高質(zhì)量初始解。本文結(jié)構(gòu)如下:首先介紹當(dāng)前常用的4種構(gòu)造啟發(fā)式算法,給出統(tǒng)一的算法流程;接著分析我國航天測控網(wǎng)的調(diào)度需求;基于我國航天測控網(wǎng)調(diào)度特點,給出了基于COP的問題表示,并對4種構(gòu)造啟發(fā)式算法進(jìn)行適應(yīng)性調(diào)整;然后提出基于混合構(gòu)造啟發(fā)式的多星測控資源調(diào)度求解算法;最后給出仿真試驗。

14種構(gòu)造啟發(fā)式算法

前面提到了,4種構(gòu)造啟發(fā)式算法包括:基于可用窗口開始時間最早最先分配規(guī)則(FIFO)的構(gòu)造啟發(fā)式算法、基于可用窗口沖突最少最先分配規(guī)則(Min-Conflict)的構(gòu)造啟發(fā)式算法、基于可用窗口靈活度最小最先分配規(guī)則(Min-Flexibility)的構(gòu)造啟發(fā)式算法和基于可用窗口價值最大最先分配規(guī)則(Max-Value)的構(gòu)造啟發(fā)式算法。這4種構(gòu)造啟發(fā)式算法的一個共同特點就是利用可用窗口的排序準(zhǔn)則來覺得任務(wù)和可用窗口的選擇。其中前3種沒有考慮任務(wù)優(yōu)先級,第4種將任務(wù)優(yōu)先級融入到可用窗口的價值指標(biāo)中。圖1給出了4種構(gòu)造啟發(fā)式算法統(tǒng)一的算法流程。

圖1　4種構(gòu)造啟發(fā)式算法統(tǒng)一算法流程

首先根據(jù)測控需求和可見窗口信息生成可調(diào)度的可用窗口集合,并按照相應(yīng)的構(gòu)造啟發(fā)式規(guī)則對所有可用窗口集中的所有元素進(jìn)行排序;然后按照順序先后對任務(wù)分配資源,將先分配資源的任務(wù)所確定的資源及占用時間作為后續(xù)任務(wù)調(diào)度時必須遵守的硬約束,更新可用窗口集中合中受影響任務(wù)的可用時間信息,同時更新被調(diào)度任務(wù)對應(yīng)需求的滿足程度;重復(fù)分配資源的步驟,當(dāng)所有任務(wù)都已被操作(成功調(diào)度或由于沖突等原因調(diào)度失敗)或所有衛(wèi)星需求得到滿足時算法終止。

2我國航天測控網(wǎng)調(diào)度需求分析

雖然已經(jīng)有部分文獻(xiàn)比較明確地描述了我國航天測控網(wǎng)調(diào)度需求[11-13],但是本文首次從與幾個具有代表性的航天測控網(wǎng)調(diào)度需求對比的角度,來分析我國航天測控網(wǎng)調(diào)度需求的特點。有代表性的航天測控網(wǎng)調(diào)度需求分別是美國AFSCN[2]、ESA ESTRACK系統(tǒng)[14]、ESA GALILEO系統(tǒng)[15]和歐洲共享航天測控網(wǎng)絡(luò)(academic ground station network , AGSN)[16]。各國航天測控網(wǎng)調(diào)度需求的不同主要體現(xiàn)在任務(wù)需求和優(yōu)化目標(biāo)的不同形式,本文這里主要從任務(wù)形式的不同來進(jìn)行比較。

表1主要從7個方面進(jìn)行比較,包括任務(wù)提交形式、任務(wù)執(zhí)行時間、任務(wù)優(yōu)先級、關(guān)聯(lián)任務(wù)、任務(wù)間隔時間、任務(wù)可用窗口的升/降軌要求和任務(wù)冗余。從表1中可以清楚地看到我國航天測控網(wǎng)調(diào)度需求所具有的特點。這些特點大多數(shù)是因為我國航天測控網(wǎng)的幾何布局造成的,主要是中國大陸境內(nèi)測控站。

3基于COP的問題表示

將航天測控網(wǎng)調(diào)度問題描述為四元組,表示為

P=

(1)

式中，Reg表示所有衛(wèi)星用戶向測控網(wǎng)管中心提出的測控需求集合,包括具體的測控需求(指明了所用的設(shè)備和時間區(qū)間)、一般測控需求(日常管理的周期性需求),即Reg={r1,r2,…,rn}(ri表示第i個需求,n表示需求的數(shù)量)。參考文獻(xiàn)[9],測控需求r可以表示為

r={No,Sat,p,deviceset,Orbit,

(Rn,Fn)/N,Last,Min,Max}

(2)

其中,No表示需求編號;Sat表示需求對應(yīng)的衛(wèi)星編號;p表示需求的優(yōu)先級;deviceset表示可供完成此需求的測控設(shè)備集合,包括中繼測控設(shè)備、設(shè)備偏好次序、最少設(shè)備次數(shù)等;Orbit表示軌道類型,包括低/中/高軌;(Rn,Fn)是針對低軌類型衛(wèi)星來說,表示升軌次數(shù)和降軌次數(shù);N是針對中高軌衛(wèi)星來說,表示測控次數(shù);Last表示一次測控最短持續(xù)時間要求;Min表示兩次測控之間的最短測控間隔時間要求;Max表示兩次測控之間的最長測控間隔時間要求。

Sce表示航天測控網(wǎng)資源調(diào)度場景,主要由一個調(diào)度周期內(nèi)所有用于調(diào)度的可用時間窗口構(gòu)成,該時間窗口是衛(wèi)星與測控資源的可見弧段;即Sce=Sce1∨Sce2∨…∨Scen (Scei表示第i個測控需求率的所有可用弧段集合)。

表1　典型的航天測控網(wǎng)調(diào)度需求比較

C表示航天測控網(wǎng)資源調(diào)度問題所有約束集合,如衛(wèi)星約束、資源約束、時間窗口約束、關(guān)系約束等。約束的具體形式可以參考文獻(xiàn)[11],本文這里不再贅述。

由于zi=r(i,:)Xl,s+Ni (l{1,2,…,Nt}，s S)，Ni為QHN的第i個元素，此時βi(l,x)= ui(l,x)+ Ni，其中，ui(l,x)=r(i,:)Xl,s-r(i,:)X.在某一時刻，接收端信道狀態(tài)信息已知時，信道傳輸矩陣H已知，發(fā)射向量固定，接收端檢測時假設(shè)發(fā)端發(fā)射向量也是已知的，因此ui(l,x)可以近似看成一個常量.由于N服從高斯分布，可以推導(dǎo)出βi(l,x)也服從高斯分布，歸一化為：

O表示優(yōu)化目標(biāo),最大限度地滿足航天測控網(wǎng)的測控需求。即

(3)

式中,p表示測控需求的優(yōu)先級;d表示單個測控需求的任務(wù)滿足率,例如某測控需求一天需要完成m個測控任務(wù),則d∈{0,1/m,2/m,…,(m-1)/m,1};優(yōu)化目標(biāo)O表示整個航天測控網(wǎng)的測控需求滿足率。

4構(gòu)造啟發(fā)式算法的適應(yīng)性調(diào)整

為了使4種常用的構(gòu)造啟發(fā)式算法能夠適應(yīng)我國航天測控網(wǎng)調(diào)度需求,需要對這4種算法進(jìn)行適應(yīng)性調(diào)整。圖2給出了調(diào)整后的統(tǒng)一算法流程,其中虛線框為適應(yīng)性調(diào)整的部分。可以看到,整個流程在兩個地方進(jìn)行了適應(yīng)性調(diào)整:一處是在構(gòu)造啟發(fā)式規(guī)則應(yīng)用可用窗口之前,增加了基于優(yōu)先級的任務(wù)選擇模塊,這主要是為了適應(yīng)任務(wù)優(yōu)先級的需求;另一處是在構(gòu)造啟發(fā)式規(guī)則應(yīng)用可用窗口之后,增加了可用窗口的升/降軌和時間間隔要求的判斷,這主要是為了適應(yīng)任務(wù)的升/降軌需求和任務(wù)間隔時間要求。

另外,由于以上4種常用構(gòu)造啟發(fā)式規(guī)則都是從單任務(wù)角度進(jìn)行逐個求解,而沒有從任務(wù)所屬的測控需求整體考慮。因此,為了適應(yīng)以測控需求為表現(xiàn)形式的相同多任務(wù)提交形式,也就是一個測控需求時段內(nèi)往往具有多個帶有時間間隔要求的相同任務(wù),本文提出了面向同一測控需求的最早可用窗口集優(yōu)先分配規(guī)則(First-Set)。First-Set定義如下:假設(shè)一個測控需求具有m個具有時間間隔要求的相同任務(wù),最短/最長時間間隔為Δmin/Δmax,其可見窗口集合為W。若存在同時滿足這m個任務(wù)的可用時間窗口集合為AWm(AWm?W),則First-Set就是AWm中具有第一個任務(wù)可見窗口開始時間最早的集合;若AWm為空集,可以繼續(xù)搜索同時滿足m-1個任務(wù)的可用時間窗口集合AWm-1,依次類推。

圖2　4種構(gòu)造啟發(fā)式算法調(diào)整后的統(tǒng)一算法流程

5基于混合構(gòu)造啟發(fā)式的求解算法

針對我國航天測控網(wǎng)調(diào)度需求特點,使構(gòu)造啟發(fā)式規(guī)則既能適應(yīng)傳統(tǒng)單任務(wù)提交形式又能適應(yīng)單個測控需求多任務(wù)的表現(xiàn)形式,綜合考慮任務(wù)局部和測控需求整體,本文這里提出了混合First-Set規(guī)則和Max-Value規(guī)則的構(gòu)造啟發(fā)式規(guī)則,縮寫為First-Set & Max-Value。其中First-Set規(guī)則側(cè)重于單個測控需求整體,而Max-Value側(cè)重于單個任務(wù)。圖3給出了求解算法流程。

與4種常見構(gòu)造啟發(fā)式算法的單一任務(wù)尺度不同,本算法混合了測控需求和任務(wù)兩種不同尺度,且一個測控需求包括多個優(yōu)先級相同或不同的任務(wù)。首先以優(yōu)先級為準(zhǔn)則依次選擇測控需求,再以該測控需求內(nèi)所包含的任務(wù)優(yōu)先級為準(zhǔn)則依次選擇任務(wù)。Max-Value規(guī)則運行一次僅得到一個調(diào)度任務(wù),而First-Set規(guī)則運行一次可以得到多個調(diào)度任務(wù)。當(dāng)完成一個測控需求分配時,通過比較兩者該測控需求滿足率,以較大者產(chǎn)生的調(diào)度任務(wù)作為本測控需求的已調(diào)度任務(wù)。這樣設(shè)計的優(yōu)勢在于,通過每一輪以測控需求滿足率為指標(biāo)動態(tài)選擇構(gòu)造啟發(fā)式規(guī)則,以融合First-Set規(guī)則和Max-Value規(guī)則的優(yōu)勢,提高整個求解質(zhì)量。當(dāng)然,從算法復(fù)雜性來看,由于混合了兩者規(guī)則,相對單一規(guī)則來說增加了計算成本,運行時間上應(yīng)該是兩個單一規(guī)則算法運行時間之和。

圖3　混合構(gòu)造啟發(fā)式算法流程

6仿真實例與結(jié)果分析

6.1仿真場景

假設(shè)航天測控網(wǎng)具有5個地面站9套設(shè)備,分別位于喀什(2套)、佳木斯(2套)、三亞(2套)、渭南(2套)和青島(1套),75顆在軌衛(wèi)星(包括4顆中高軌衛(wèi)星),其編號為1~75,每個衛(wèi)星測控任務(wù)需求如表2所示。

表2　每個衛(wèi)星測控任務(wù)需求

不失一般性,對于低軌衛(wèi)星來說,可見時間窗口一般為滿足任務(wù)最短持續(xù)時間要求的整個弧段;對于中高軌衛(wèi)星來說,由于可見弧段時間一般較長,為了提高弧段利用率,對每個長可見弧段進(jìn)行子弧段離散化處理,即每個子弧段時長為最短持續(xù)時間,時間間隔取1 min。仿真場景設(shè)計了3種不同規(guī)模的場景,分別是大、中和小規(guī)模場景,場景配置如表3所示。

6.2比較算法的設(shè)計

為了驗證本文提出的混合構(gòu)造啟發(fā)式算法的有效性,這里考慮了本文第4節(jié)給出的基于FIFO規(guī)則啟發(fā)式算法、基于Max-Value規(guī)則啟發(fā)式算法和基于First-Set規(guī)則啟發(fā)式算法。其中基于Max-Value規(guī)則啟發(fā)式算法采用文獻(xiàn)[10]的CHBR算法的弧段價值計算方法。這3種算法的選擇具有一定的代表性:FIFO啟發(fā)式反映在單個任務(wù)的可能開始時間上;Max-Value啟發(fā)式反映在涵蓋相鄰任務(wù)時間間隔要求的單任務(wù)價值上;First-Set啟發(fā)式則反映在具有多個時間關(guān)聯(lián)任務(wù)的測控需求上。

表3　3種場景配置

6.3仿真結(jié)果比較分析

為了更加客觀地反映各個算法的性能,這里以測控需求滿足度來衡量算法求解質(zhì)量,以計算時間來衡量算法計算成本。每個場景以需求優(yōu)先級的不同生成200個算例,每個算例在1~10間隨機(jī)生成所包含測控需求的優(yōu)先級。而且,每個場景設(shè)計了兩種時間間隔:一個最長時間間隔為8 h,一個最長時間間隔為10 h。表4是各算法在不同場景下的平均測控需求滿足度,表5是各算法在不同場景下的平均計算時間。

從求解質(zhì)量來看,First-Set & Max-Value啟發(fā)式最好,Max-Value次之,其次First-Set,FIFO最差。隨著最長時間間隔由10 h縮短為8 h,測控需求的時間間隔約束加強,雖然4個算法的求解質(zhì)量都有所下降,但是相比較次優(yōu)的Max-Value啟發(fā)式,有兩點發(fā)現(xiàn):一是First-Set & Max-Value啟發(fā)式的求解質(zhì)量從2%提高到6%;二是First-Set啟發(fā)式的求解質(zhì)量逐步逼近Max-Value啟發(fā)式。這兩點發(fā)現(xiàn)實際上也反映了First-Set & Max-Value啟發(fā)式綜合考慮任務(wù)局部和測控需求整體的優(yōu)勢所在。

表4　各算法在不同場景下的平均測控需求滿足度

表5　各算法在不同場景下的平均計算時間　s

從計算成本來看,由于本文所給出的算法都是調(diào)度問題初始解構(gòu)造的貪婪算法,每一步任務(wù)的選擇和可用弧段的選擇都是根據(jù)啟發(fā)式規(guī)則確定的,直至所剩任務(wù)沒有可以弧段為止。因此在算法運行過程中,未調(diào)度集合隨時間變化都應(yīng)是線性遞減,直至算法結(jié)束。不同的是,各個算法進(jìn)行每一步可用弧段選擇時進(jìn)行的計算復(fù)雜度是不同的,從仿真結(jié)果來看,FIFO由于僅僅進(jìn)行簡單排序,因而計算量最少;First-Set由于要先確定AW窗口集,再排序,因而次之;Max-Value由于需要先確定每個可用弧段的價值而需要更多計算量;First-Set & Max-Value即要先確定AW窗口集又要確定每個可用弧段的價值,因此計算量最大。

7結(jié)論

針對我國航天測控網(wǎng)調(diào)度需求特點,提出一種混合構(gòu)造啟發(fā)式的測控網(wǎng)調(diào)度問題求解算法。算法綜合考慮任務(wù)局部和測控需求整體,融合了First-Set規(guī)則和Max-Value規(guī)則的構(gòu)造啟發(fā)式規(guī)則,通過以測控需求滿足率為指標(biāo)動態(tài)選擇構(gòu)造啟發(fā)式規(guī)則來提高求解質(zhì)量。通過仿真實驗分析比較驗證了該算法可以在不明顯增加計算時間的基礎(chǔ)上得到更高的初始解質(zhì)量。本文雖然對航天測控網(wǎng)調(diào)度的混合構(gòu)造啟發(fā)式算法進(jìn)行了一個很好的嘗試,但是由于混合的方式還比較簡單而造成計算代價較大。下一步將繼續(xù)深入研究這種混合構(gòu)造啟發(fā)式算法,提高兩者構(gòu)造啟發(fā)式規(guī)則的耦合程度,如在可用窗口集的選擇依據(jù)上引入Max-Value規(guī)則等,進(jìn)一步改善計算成本。

參考文獻(xiàn)：

[1] Jorg F, Konstantinos K, Banafsheh K. Operations research in the space industry[J].EuropeanJournalofOperationalResearch, 2012, 217(2): 233-240.

[2] Barbulescu L, Howe A, Whitley D. AFSCN scheduling: how the problem and solution have evolved[J].MathematicalandComputerModelling, 2006, 43(9/10):1023-1037.

[3] Stottler D. Satellite communication scheduling, optimization, and deconfliction using artificial intelligence techniques[C]∥Proc.oftheInfotech@Aerospace,2010.

[4] Schalck S M. Automating satellite range scheduling[D]. Dayton: Air Force Institute of Technology, 1993.

[5] Barbulescu L, Watson J P, Whitley L D, et al. Scheduling space-ground communications for the air force satellite control network[J].JournalofScheduling, 2004, 7(1): 7-34.

[6] Stottler R, Mahan K, Jensen R. Bottleneck avoidance techniques for automated satellite communication scheduling[C]∥Proc.oftheInfotech@Aerospace, 2011.

[7] Gooley T. Automating the satellite range scheduling process[D]. Dayton: Air Force Institute of Technology, 1993.

[8] Chen L J, Wu X Y, Li Y F. Scheduling algorithm for relaying satellite based on temporal flexibility[J].AeronauticalComputingTechnique,2006,36(4):48-51.(陳理江,武小悅,李云峰.基于時間靈活度的中繼衛(wèi)星調(diào)度算法[J].航空計算技術(shù),2006,36(4):48-51.)

[9] Ling X D, Wu X Y, Liu Q. Requirement-oriented TT&C scheduling algorithm[J].SystemsEngineeringandElectronics, 2009, 31(7):1661-1666.(凌曉冬,武小悅,劉琦.面向需求的航天測控資源調(diào)度算法[J].系統(tǒng)工程與電子技術(shù), 2009,31(7):1661-1666.)

[10]Chen F. Research on genetic algorithm for multi-satellite TT&C scheduling problem[D].Changsha:National University of Defense Technology,2010.(陳峰.多星測控調(diào)度問題的遺傳算法研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2010.)

[11]Ling X D, Wu X Y, Liu B, et al. Study on the CSP model of satellite TT&C resource scheduling[J].SystemsEngineeringandElectronics,2012,34(11):2275-2279.(凌曉冬,武小悅,劉冰,等.衛(wèi)星測控資源調(diào)度CSP模型研究[J].2012,34(11):2275-2279.)

[12]Chen F, Wu X Y. Space and ground TT&C resource integrated scheduling model[J].JournalofAstronautics, 2010, 31(5): 1405-1412.(陳峰,武小悅.天地測控資源一體化調(diào)度模型[J].宇航學(xué)報,2010,31(5):1405-1412.)

[13]Kang N. Research on genetic algorithm for multi-satellite TT&C scheduling problem[D]. Changsha: National University of Defense Technology,2011.(康寧.航天測控優(yōu)化調(diào)度模型及其拉格朗日松弛[D].長沙:國防科學(xué)技術(shù)大學(xué),2011.)

[14]Damiani S, Dreihahn H, Noll J, et al. Automated allocation of ESA ground station network services[C]∥Proc.oftheInternationalWorkshoponPlanningandSchedulingforSpace,2006:1-10.

[15]Marinelli F, Rossi F, Nocella S, et al. A Lagrangian heuristic for satellite range scheduling with resource constraints[J].Computers&OperationsResearch,2005,38(11):1572-1583.

[16]Schmidt M, Schilling K. A scheduling system with redundant scheduling capabilities for ground station networks[C]∥Proc.oftheInternationalWorkshoponPlanningandSchedulingforSpace, 2009: 1-6.

劉建平(1975-),男,高級工程師,博士,主要研究方向為航天任務(wù)智能規(guī)劃與優(yōu)化調(diào)度。

E-mail:ljpnudt@sina.com

李晶(1963-),女,研究員,博士,主要研究方向為航天任務(wù)智能規(guī)劃與優(yōu)化調(diào)度。

E-mail:carol_lee_0727@sina.com

張?zhí)祢?1988-),女,工程師,博士研究生,主要研究方向為航天任務(wù)智能規(guī)劃與優(yōu)化調(diào)度。

E-mail:tiantian880407@163.com

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

Hybrid constructive heuristics of space measurement and

control network scheduling problem

LIU Jian-ping, LI Jing, ZHANG Tian-jiao

(StateKeyLaboratoryofAstronauticDynamics,Xi’anSatelliteControlCentre,Xi’an710043,China)

Abstract:For the space measurement and control network scheduling problem, a hybrid constructive heuristics is proposed. Different from existing constructive heuristics, this heuristics takes advantage of characteristics of space measurement and control network scheduling requirements, including priorities, temporal intervals and multiple same tasks in one requirement. Considering both local tasks and the complete requirement, it integrates the maximum valued available task window rule with the first available task window set rule. Its advantage is to improve the solution quality by means of dynamic choice of the two rules. Finally,through simulation cases and computational results analysis,it is found that this hybrid constructive heuristics can improve the solution quality and increase less computation cost.

Keywords:constructive heuristics; space measurement and control network scheduling problem; tracking, telemetry and command (TT&C) requirement; constraint optimization problem (COP); temporal interval

作者簡介：

中圖分類號：TP 18

文獻(xiàn)標(biāo)志碼：A

DOI:10.3969/j.issn.1001-506X.2015.07.16

基金項目：青年創(chuàng)新基金(GFZX04060103-02)資助課題

收稿日期：2014-07-08；修回日期：2014-11-01；網(wǎng)絡(luò)優(yōu)先出版日期：2014-11-19。