邱冬陽(yáng)，卜慧蛟，王 帥，王功波，羅亞中?

（1.國(guó)防科學(xué)技術(shù)大學(xué)航天科學(xué)與工程學(xué)院，長(zhǎng)沙410073；2.載人航天總體研究論證中心，北京100094）

空間站運(yùn)營(yíng)在軌任務(wù)并行規(guī)劃技術(shù)研究

邱冬陽(yáng)1，卜慧蛟1，王 帥2，王功波2，羅亞中1?

（1.國(guó)防科學(xué)技術(shù)大學(xué)航天科學(xué)與工程學(xué)院，長(zhǎng)沙410073；2.載人航天總體研究論證中心，北京100094）

空間站運(yùn)營(yíng)任務(wù)規(guī)劃技術(shù)是空間站長(zhǎng)期穩(wěn)定運(yùn)營(yíng)的核心技術(shù)。面向我國(guó)空間站建設(shè)運(yùn)營(yíng)需求，對(duì)空間站運(yùn)營(yíng)任務(wù)層建模與規(guī)劃技術(shù)進(jìn)行了研究。針對(duì)任務(wù)層規(guī)劃任務(wù)類(lèi)型多樣、約束復(fù)雜及資源受限等問(wèn)題，基于約束滿足理論，建立了任務(wù)層規(guī)劃模型；同時(shí)針對(duì)任務(wù)層規(guī)劃問(wèn)題規(guī)模大、耦合性強(qiáng)及難于求解的特性，提出了一種任務(wù)層規(guī)劃問(wèn)題并行求解方法。仿真結(jié)果表明，本文提出的并行求解方法相較傳統(tǒng)的串行規(guī)劃算法加速比可達(dá)14.19，能有效快速求解空間站運(yùn)營(yíng)任務(wù)層規(guī)劃問(wèn)題。研究結(jié)論可為我國(guó)空間站運(yùn)營(yíng)相關(guān)規(guī)劃系統(tǒng)研制提供參考。

空間站；運(yùn)營(yíng)；任務(wù)規(guī)劃；并行計(jì)算

1 引言

從1971年4月19日，前蘇聯(lián)成功發(fā)射世界上第一個(gè)試驗(yàn)空間站“禮炮1號(hào)”至今，世界上已成功發(fā)射了十余座空間站［1］。經(jīng)過(guò)40余年的發(fā)展，美國(guó)、俄羅斯及歐洲等國(guó)相繼突破和掌握了一系列空間站核心工程技術(shù)，開(kāi)發(fā)了相應(yīng)的任務(wù)規(guī)劃系統(tǒng)并在空間站上得到了成功運(yùn)用。

2020年前后我國(guó)將建成并運(yùn)營(yíng)近地空間站［2］，目前我國(guó)的空間站工程正處于起步階段，開(kāi)展空間站運(yùn)營(yíng)在軌任務(wù)規(guī)劃技術(shù)研究、掌握相關(guān)技術(shù)，對(duì)空間站的長(zhǎng)期穩(wěn)定安全運(yùn)營(yíng)具有重要意義。

空間站運(yùn)營(yíng)在軌任務(wù)規(guī)劃不同于一般航天器任務(wù)規(guī)劃，其涵蓋的規(guī)劃對(duì)象和內(nèi)容更為廣泛，任務(wù)周期長(zhǎng)，規(guī)劃工作更繁重、難度更大。借鑒當(dāng)前國(guó)際上常用的空間站任務(wù)規(guī)劃層次劃分方法，可將我國(guó)空間站運(yùn)營(yíng)在軌任務(wù)規(guī)劃劃分為戰(zhàn)略、戰(zhàn)術(shù)、任務(wù)和執(zhí)行四個(gè)層次［3?4］。目前，國(guó)內(nèi)一些學(xué)者對(duì)空間站戰(zhàn)略、戰(zhàn)術(shù)及執(zhí)行層任務(wù)的建模與規(guī)劃技術(shù)進(jìn)行了研究［4?8］?？臻g站運(yùn)營(yíng)任務(wù)層規(guī)劃主要面向兩次載人飛船訪問(wèn)間隔時(shí)間內(nèi)的任務(wù)規(guī)劃，具有規(guī)劃任務(wù)種類(lèi)多樣、約束復(fù)雜及需求多樣的特性，目前的規(guī)劃模型和算法不能直接有效應(yīng)用于任務(wù)層規(guī)劃領(lǐng)域，還需進(jìn)一步研究任務(wù)層規(guī)劃的建模方法和規(guī)劃算法。

在前期針對(duì)任務(wù)層規(guī)劃算法的研究中，由于未充分考慮任務(wù)層規(guī)劃數(shù)據(jù)規(guī)模龐大的問(wèn)題，導(dǎo)致在使用傳統(tǒng)優(yōu)化算法求解時(shí)，計(jì)算效率低，計(jì)算資源占用量大，無(wú)法以合理的時(shí)間代價(jià)求得可行解。如何提高算法求解效率，是下一步亟待解決的關(guān)鍵問(wèn)題。

針對(duì)上述問(wèn)題，本文對(duì)空間站運(yùn)營(yíng)任務(wù)層規(guī)劃的建模與規(guī)劃技術(shù)展開(kāi)研究，構(gòu)建了面向工程實(shí)際的任務(wù)層規(guī)劃模型，同時(shí)借助并行計(jì)算技術(shù)，提出了能夠有效提高規(guī)劃效率的任務(wù)層規(guī)劃問(wèn)題并行求解方法。

2 任務(wù)層規(guī)劃模型

2.1 規(guī)劃問(wèn)題分析

空間站運(yùn)營(yíng)任務(wù)層規(guī)劃的規(guī)劃周期一般在6個(gè)月左右（1個(gè)任務(wù)周期）。主要依據(jù)戰(zhàn)術(shù)層規(guī)劃方案和當(dāng)前空間站運(yùn)營(yíng)狀態(tài)，結(jié)合任務(wù)設(shè)計(jì)者的目標(biāo)期望，在滿足空間站各項(xiàng)約束并保證其安全平穩(wěn)運(yùn)營(yíng)的前提下，制定某次載人飛行任務(wù)周期內(nèi)的在軌任務(wù)的編排方案，輸出以月為單位的在軌操作概要［4，9］。

空間站在軌任務(wù)規(guī)劃涉及到任務(wù)、活動(dòng)、設(shè)備和資源等多個(gè)要素。其任務(wù)通常由一個(gè)或多個(gè)活動(dòng)構(gòu)成，活動(dòng)按照其規(guī)定的次序，由航天員操作空間站站上設(shè)備及使用相關(guān)資源完成。相較于其它規(guī)劃層次，任務(wù)層規(guī)劃涉及到的在軌任務(wù)種類(lèi)更為多樣，除了常規(guī)的軌道姿態(tài)控制任務(wù)外，還包括空間站平臺(tái)管理維護(hù)、航天員操作、空間載荷應(yīng)用等，同時(shí)，任務(wù)層規(guī)劃具有更細(xì)的規(guī)劃粒度，其規(guī)劃周期內(nèi)包含幾百至上千個(gè)任務(wù)。

由于空間站運(yùn)營(yíng)所處特殊的內(nèi)外部環(huán)境，各項(xiàng)任務(wù)的執(zhí)行將受到空間站姿態(tài)、設(shè)備功耗、散熱、在軌資源（水、氧氣、氮?dú)獾龋┘疤斓赝ㄐ艛?shù)據(jù)窗口等約束的限制，一些任務(wù)的執(zhí)行還需考慮任務(wù)內(nèi)部活動(dòng)間的邏輯關(guān)系約束等。此外，空間站運(yùn)營(yíng)任務(wù)層規(guī)劃的顯著特點(diǎn)是在任務(wù)規(guī)劃周期內(nèi)長(zhǎng)期有航天員駐留，任務(wù)的安排還需考慮航天員的安全及生理作息規(guī)律的約束。

綜上，空間站運(yùn)營(yíng)任務(wù)層規(guī)劃問(wèn)題是一個(gè)規(guī)劃內(nèi)容多樣、約束復(fù)雜、耦合性強(qiáng)的大規(guī)模復(fù)雜系統(tǒng)規(guī)劃問(wèn)題。

2.2 規(guī)劃模型

空間站運(yùn)營(yíng)任務(wù)層規(guī)劃問(wèn)題是在各種約束限制下，有效調(diào)度在軌資源，合理安排每個(gè)活動(dòng)的執(zhí)行時(shí)間，本質(zhì)上是一個(gè)約束滿足問(wèn)題。本文在卜慧蛟等對(duì)空間站在軌任務(wù)規(guī)劃領(lǐng)域建模研究的基礎(chǔ)上［8］，建立了任務(wù)層規(guī)劃模型如式（1）：

其中，V為規(guī)劃變量集合，D為變量域集合，C為約束集合，F(xiàn)為目標(biāo)函數(shù)集合。

1）規(guī)劃變量集合

將規(guī)劃任務(wù)中第一個(gè)活動(dòng)的開(kāi)始時(shí)間作為規(guī)劃設(shè)計(jì)變量，如式（2）所示：

其中，n是規(guī)劃任務(wù)數(shù)。

2）變量域集合

每個(gè)規(guī)劃變量的取值都在相應(yīng)任務(wù)的最早開(kāi)始時(shí)間和最晚結(jié)束時(shí)間范圍內(nèi)，如式（3）所示：

其中，EarStaTimei和LatEndTimei分別是第i個(gè)任務(wù)的最早開(kāi)始時(shí)間和最晚結(jié)束時(shí)間。

3）約束集合

（1）額定功率約束模型

某一時(shí)刻執(zhí)行活動(dòng)的總功率值不得超過(guò)空間站額定功率，如式（4）所示：

其中，t是當(dāng)前時(shí)刻，N是當(dāng)前時(shí)刻執(zhí)行活動(dòng)的個(gè)數(shù)，Mn是活動(dòng)Activityn在當(dāng)前時(shí)刻t執(zhí)行所需設(shè)備數(shù)，Power是設(shè)備運(yùn)行所需功率，W是空間站額定功率。

（2）額度通信帶寬約束模型

某一時(shí)刻執(zhí)行活動(dòng)的總需帶寬不得超過(guò)空間站額定通信帶寬，如式（5）所示：

其中，Bandwidth是活動(dòng)執(zhí)行所需通信帶寬，BD是空間站額定通信帶寬。

（3）在軌航天員人時(shí)約束模型

任務(wù)規(guī)劃時(shí)，保證活動(dòng)的執(zhí)行時(shí)間在航天員的工作時(shí)間內(nèi)，盡可能避免占用航天員休息時(shí)間，如式（6）所示：

其 中，Activityi.StartTime和Activityi.EndTime分別是航天員i參與執(zhí)行活動(dòng)的開(kāi)始時(shí)間 和結(jié)束時(shí)間， CrewiWorkTimeStart和

CrewiWorkTimeEnd是航天員每天工作開(kāi)始時(shí)間和工作結(jié)束時(shí)間。

（4）活動(dòng)間先驗(yàn)關(guān)系約束模型

多活動(dòng)任務(wù)的執(zhí)行需要滿足其活動(dòng)間的先驗(yàn)關(guān)系約束，這里定義了“先于（before）”、“同時(shí)（e?qual）”和“延后（after）”三種類(lèi)型，如式（7）所示：

其中，ActivityA是 ActivityB的先驗(yàn)活動(dòng)，TimeNode是時(shí)間節(jié)點(diǎn)，RaletionType是先驗(yàn)關(guān)系類(lèi)型。先驗(yàn)關(guān)系描述如圖1所示。

圖1 先驗(yàn)關(guān)系描述Fig.1 The description of precedence relationship

4）目標(biāo)函數(shù)集合

優(yōu)先級(jí)是評(píng)價(jià)任務(wù)重要性的一個(gè)重要指標(biāo)，在空間站運(yùn)營(yíng)過(guò)程中希望重要任務(wù)盡可能多的得到執(zhí)行，因此，將規(guī)劃方案中任務(wù)優(yōu)先級(jí)收益最大設(shè)定為目標(biāo)函數(shù)，如式（8）所示：

其中，U是規(guī)劃方案中任務(wù)總數(shù)。

3 任務(wù)層規(guī)劃問(wèn)題并行求解方法

智能優(yōu)化算法是求解規(guī)劃與調(diào)度問(wèn)題的有效方法。由于任務(wù)層規(guī)劃問(wèn)題具有變量規(guī)模大、約束復(fù)雜、搜索區(qū)間大等特性，在使用傳統(tǒng)智能優(yōu)化算法進(jìn)行優(yōu)化求解時(shí)，算法難于收斂，無(wú)法在合理的時(shí)間代價(jià)內(nèi)求得最優(yōu)解，只能在計(jì)算時(shí)間和規(guī)劃效果上進(jìn)行折衷。

并行計(jì)算（Parallel Computing）是指同時(shí)利用多種計(jì)算資源解決問(wèn)題的過(guò)程，在求解大規(guī)模復(fù)雜規(guī)劃問(wèn)題上具有顯著優(yōu)勢(shì)［10］。為了有效求解任務(wù)層規(guī)劃問(wèn)題，借助并行計(jì)算技術(shù)，提出一種任務(wù)層規(guī)劃問(wèn)題并行求解方法。

3.1 并行規(guī)劃策略

3.1.1 任務(wù)并行規(guī)劃

任務(wù)并行規(guī)劃，即根據(jù)問(wèn)題特性，找到其內(nèi)在的并行性，在此基礎(chǔ)上，將規(guī)劃任務(wù)分解成若干個(gè)相互獨(dú)立的子任務(wù)，同時(shí)對(duì)多個(gè)子任務(wù)進(jìn)行并行規(guī)劃，以提高計(jì)算效率［11］。

任務(wù)分解是任務(wù)并行規(guī)劃的核心，由2.1節(jié)知，任務(wù)層規(guī)劃主要考慮任務(wù)內(nèi)部活動(dòng)的先驗(yàn)關(guān)系約束，其各任務(wù)間具有相互獨(dú)立性。因此，可將整個(gè)任務(wù)周期，按照設(shè)計(jì)者的規(guī)劃需求，以特定的時(shí)間步長(zhǎng)，劃分成若干個(gè)子任務(wù)周期，同時(shí)對(duì)各子任務(wù)周期內(nèi)的在軌任務(wù)進(jìn)行規(guī)劃。

1）任務(wù)周期分解

任務(wù)層規(guī)劃的任務(wù)周期跨度為一個(gè)月至幾個(gè)月不等，為了充分利用并行計(jì)算資源，考慮將整個(gè)任務(wù)周期根據(jù)可調(diào)用的并行計(jì)算CPU數(shù)目進(jìn)行分解，子任務(wù)規(guī)劃周期如式（9）所示：

其中，Interval為子任務(wù)規(guī)劃時(shí)間，EndTerm和StartTerm分別為原任務(wù)周期的開(kāi)始時(shí)間和結(jié)束時(shí)間，n（CPU）為并行計(jì)算CPU數(shù)目。

由此得到n個(gè)子任務(wù)周期，其中第i個(gè)子任務(wù)周期的規(guī)劃時(shí)間區(qū)間為：

2）在軌任務(wù)并行規(guī)劃

根據(jù)各子任務(wù)周期的規(guī)劃時(shí)間區(qū)間，搜索在該區(qū)間執(zhí)行的在軌任務(wù)，構(gòu)成各子任務(wù)周期的規(guī)劃任務(wù)集合，將其分配給多個(gè)CPU進(jìn)行并行規(guī)劃，從而達(dá)到縮小算法搜索空間、減小求解問(wèn)題的規(guī)模的目的。

3.1.2 算法改進(jìn)

考慮任務(wù)層規(guī)劃問(wèn)題約束復(fù)雜，為提高算法收斂性能，結(jié)合遺傳算法，提出一種采用約束沖突修復(fù)策略的改進(jìn)遺傳算法，算法流程如圖2。

算法中，每個(gè)個(gè)體代表一個(gè)任務(wù)規(guī)劃方案，在初始化種群后，通過(guò)約束沖突修復(fù)策略，基于時(shí)間線，檢測(cè)方案的約束滿足情況，從有約束沖突的不可行初始解開(kāi)始，迭代性地進(jìn)行修復(fù)，以減少?zèng)_突數(shù)目，最后得到無(wú)沖突的可行解。

圖2 改進(jìn)遺傳算法流程圖Fig.2 Flow chart of improved GA

約束沖突修復(fù)流程：

Step 1：根據(jù)初始任務(wù)規(guī)劃方案，設(shè)定迭代開(kāi)始時(shí)間t＝t0，t0為子規(guī)劃周期的規(guī)劃開(kāi)始時(shí)刻，按設(shè)定的時(shí)間步長(zhǎng)Step對(duì)方案仿真推進(jìn)；

Step 2：判斷所有任務(wù)在當(dāng)前時(shí)刻t的執(zhí)行情況，根據(jù)執(zhí)行狀態(tài)，對(duì)相應(yīng)的資源進(jìn)行調(diào)度，從而獲得當(dāng)前時(shí)刻的執(zhí)行任務(wù)集合和資源集合；

Step 3：根據(jù)空間站約束條件，檢測(cè)當(dāng)前時(shí)刻任務(wù)方案的約束滿足情況；

Step 4：如果方案存在約束沖突，則在執(zhí)行任務(wù)集合中，根據(jù)規(guī)劃決策準(zhǔn)則，推遲或取消一個(gè)任務(wù)，放入未執(zhí)行任務(wù)集合中，同時(shí)在資源集合中釋放該任務(wù)占用的資源；反之則執(zhí)行Step 5；

Step 5：判斷當(dāng)前時(shí)刻是否小于該子規(guī)劃周期的規(guī)劃結(jié)束時(shí)間，若小于則執(zhí)行Step 2；反之迭代終止。

3.2 并行計(jì)算實(shí)現(xiàn)

3.2.1 并行環(huán)境分析

當(dāng)前比較流行的并行計(jì)算環(huán)境可以分為三類(lèi)：共享式存儲(chǔ)、消息傳遞和數(shù)據(jù)并行［12］。由于數(shù)據(jù)并行環(huán)境僅適用于數(shù)據(jù)并行問(wèn)題，對(duì)于非數(shù)據(jù)并行類(lèi)的問(wèn)題，如果通過(guò)數(shù)據(jù)并行的方式來(lái)解決，一般難以取得較高的效率。結(jié)合求解問(wèn)題特性，并綜合考慮規(guī)劃算法基本框架及進(jìn)一步算法集成的單機(jī)運(yùn)行環(huán)境，主要采用共享式存儲(chǔ)和消息傳遞兩種并行環(huán)境實(shí)現(xiàn)并行計(jì)算。

OpenMP（Open Multi?Processing）和MPI（Mes?sage Passing Interface）是兩種并行計(jì)算環(huán)境的典型代表，均可調(diào)用高性能計(jì)算機(jī)自身的多核計(jì)算資源，即實(shí)現(xiàn)基于單機(jī)系統(tǒng)的并行計(jì)算，其主要特征分析見(jiàn)表1。

表1 并行計(jì)算環(huán)境主要特征Table 1 Main features of parallel computing environment

OpenMP實(shí)現(xiàn)簡(jiǎn)單，直接將原串行算法中具有并行性的部分進(jìn)行并行化，其創(chuàng)建的各線程間無(wú)需通信，節(jié)省了消息傳遞帶來(lái)的時(shí)間開(kāi)銷(xiāo)，是實(shí)現(xiàn)并行計(jì)算的理想方法［13］。但在實(shí)際算法并行改造過(guò)程中，由于任務(wù)層規(guī)劃問(wèn)題各變量間數(shù)據(jù)相關(guān)性強(qiáng)，其共享式存儲(chǔ)機(jī)制導(dǎo)致線程間極易出現(xiàn)內(nèi)存搶占現(xiàn)象，同時(shí)規(guī)劃算法中約束沖突修復(fù)策略本身所具有的串行特性導(dǎo)致算法無(wú)法有效運(yùn)用OpenMP進(jìn)行并行化改造。

MPI應(yīng)用較為復(fù)雜，需對(duì)原有串行算法進(jìn)行良好的并行結(jié)構(gòu)設(shè)計(jì)，但其可有效解決OpenMP并行實(shí)現(xiàn)過(guò)程中遇到的問(wèn)題，同時(shí)MPI具有良好的可擴(kuò)展性，可為下一步空間站運(yùn)營(yíng)任務(wù)規(guī)劃系統(tǒng)開(kāi)發(fā)大規(guī)模并行計(jì)算平臺(tái)奠定基礎(chǔ)。因此，采用MPI實(shí)現(xiàn)對(duì)任務(wù)層規(guī)劃問(wèn)題并行求解。

3.2.2 并行程序設(shè)計(jì)

1）MPI并行程序設(shè)計(jì)

MPI根據(jù)各進(jìn)程間執(zhí)行關(guān)系可分為主從式并行和對(duì)等式并行兩種并行模式，主從式并行即主進(jìn)程根據(jù)特定算法對(duì)問(wèn)題進(jìn)行分解后分配子任務(wù)到各從進(jìn)程，不擔(dān)任具體的運(yùn)算任務(wù)，接收各從進(jìn)程的計(jì)算結(jié)果；對(duì)等式并行模式即在任務(wù)分解后，主從進(jìn)程均分配得到子任務(wù)進(jìn)行規(guī)劃計(jì)算［11］。

基于3.1.1節(jié)提出的任務(wù)并行規(guī)劃方法，采用MPI對(duì)等并行模式及塊分配的任務(wù)分配策略（將總?cè)蝿?wù)連續(xù)分成若干個(gè)任務(wù)塊，每個(gè)處理器負(fù)責(zé)一個(gè)塊的計(jì)算），根據(jù)任務(wù)規(guī)劃需求，啟動(dòng)與子任務(wù)周期數(shù)相同個(gè)數(shù)的進(jìn)程，各進(jìn)程分配一個(gè)規(guī)劃任務(wù)，同時(shí)調(diào)用規(guī)劃算法對(duì)問(wèn)題進(jìn)行優(yōu)化求解，使各進(jìn)程間負(fù)載均衡，降低消息傳遞時(shí)間開(kāi)銷(xiāo)，以獲得最大的加速性能。并行規(guī)劃流程見(jiàn)圖3。

2）加速比分析

加速比（speedup）是衡量并行程序加速性能的重要指標(biāo)，其計(jì)算公式如式（11）所示：

其中，Ts和Tp分別為程序串行和并行的計(jì)算時(shí)間。

（1）串行計(jì)算時(shí)間

串行計(jì)算即在空間站全任務(wù)周期下開(kāi)展的規(guī)劃計(jì)算，其規(guī)劃時(shí)間的計(jì)算公式如式（12）所示：

其中，tpretreatment為規(guī)劃信息讀取，任務(wù)分配等規(guī)劃預(yù)處理操作時(shí)間開(kāi)銷(xiāo)，tmissionplan為任務(wù)規(guī)劃時(shí)間開(kāi)銷(xiāo)。

規(guī)劃時(shí)間主要取決于算法計(jì)算時(shí)間，設(shè)Gmax為遺傳算法最大進(jìn)化代數(shù)，Psize為種群規(guī)模，為一次迭代計(jì)算的平均時(shí)間，則規(guī)劃時(shí)間如式（13）所示：

由于算法采用了基于時(shí)間迭代的約束沖突修復(fù)策略，在迭代時(shí)間步長(zhǎng)一定的情況下，其規(guī)劃時(shí)間受任務(wù)周期和規(guī)劃任務(wù)數(shù)的影響。

（2）并行計(jì)算時(shí)間

通過(guò)并行程序設(shè)計(jì)，知各進(jìn)程間無(wú)通信時(shí)間開(kāi)銷(xiāo)，根據(jù)3.1節(jié)的并行規(guī)劃策略，對(duì)任務(wù)周期進(jìn)行分解后，其各子任務(wù)周期的規(guī)劃時(shí)間區(qū)間和規(guī)劃任務(wù)數(shù)均近似為原來(lái)的1/n（CPU）。各子規(guī)劃周期同時(shí)計(jì)算，則并行計(jì)算時(shí)間如式（14）所示：

加速比為：

當(dāng)tmissionplan》tpretreatment時(shí)，S≈n2（CPU），即最大加速比可近似達(dá)到并行計(jì)算CPU數(shù)目的平方。

圖3 并行規(guī)劃流程Fig.3 Parallel planning process

4 算例仿真及結(jié)果分析

4.1 問(wèn)題配置

以我國(guó)空間站運(yùn)營(yíng)為背景，設(shè)定任務(wù)周期為2023年9月1日—2023年12月31日，駐留2人。參考國(guó)際空間站運(yùn)營(yíng)需求，需規(guī)劃的任務(wù)包含空間站例行維護(hù)維修、空間生物技術(shù)實(shí)驗(yàn)、醫(yī)學(xué)生物學(xué)研究及觀測(cè)科學(xué)研究等，共9大類(lèi)，3127項(xiàng)子任務(wù)，其任務(wù)分布如圖4所示。表2展示了一個(gè)典型的任務(wù)模型描述實(shí)例。

圖4 任務(wù)分布Fig.4 Distribution of mission

表2 任務(wù)模型描述Table 2 Description of mission model

任務(wù)的優(yōu)先級(jí)共分為5級(jí)，其中1、2級(jí)任務(wù)為保證航天員安全駐留和空間站正常運(yùn)營(yíng)的關(guān)鍵任務(wù)，必須執(zhí)行；3到5級(jí)任務(wù)主要為空間應(yīng)用類(lèi)任務(wù)，在空間站資源受限的情況下，希望該類(lèi)任務(wù)盡可能多的完成，以提高空間站的運(yùn)營(yíng)收益。本文以任務(wù)優(yōu)先級(jí)作為規(guī)劃決策準(zhǔn)則，即當(dāng)發(fā)生約束沖突時(shí)，優(yōu)先保證優(yōu)先級(jí)較高的任務(wù)執(zhí)行。

表3給出了在軌航天員信息。這里定義航天員休息事件的優(yōu)先級(jí)為3，優(yōu)先級(jí)大于3的任務(wù)可以占用航天員休息時(shí)間，以保證空間站交會(huì)對(duì)接、加注及艙外實(shí)驗(yàn)等重要任務(wù)的執(zhí)行。

表3 在軌航天員信息Table 3 On?orbit astronaut information

設(shè)定空間站額定功率為3200 W，額定通信帶寬為600 Mbps。規(guī)劃算法參數(shù)及并行環(huán)境配置分別見(jiàn)表4和表5。

表4 算法參數(shù)配置Table 4 Algorithm parameter configuration

表5 并行環(huán)境配置Table 5 Parallel environment configuration

4.2 結(jié)果分析

由于任務(wù)周期跨度為4個(gè)月，因此考慮將任務(wù)周期分解成4個(gè)子任務(wù)周期，同時(shí)調(diào)用4個(gè)CPU進(jìn)行并行計(jì)算。表6和圖5分別給出了并行計(jì)算的加速效果和并行計(jì)算時(shí)CPU使用情況。

表6 CPU并行程序加速效果Table 6 Speed?up of CPU parallel program

圖5 CPU使用情況Fig.5 CPU usage

根據(jù)3.2.2節(jié)的加速比分析，當(dāng)n（CPU）＝4時(shí)，其理想加速比S≈16，但在實(shí)際規(guī)劃過(guò)程中由于受到規(guī)劃預(yù)處理等操作時(shí)間開(kāi)銷(xiāo)的影響，實(shí)際加速比達(dá)到了14.19。由此可知，本文提出的并行規(guī)劃策略可有效快速求解任務(wù)層規(guī)劃問(wèn)題。

任務(wù)層規(guī)劃獲得的是以月為單位的空間站每天的執(zhí)行任務(wù)列表，但不精確到任務(wù)具體執(zhí)行時(shí)刻。由于任務(wù)數(shù)據(jù)量過(guò)大，表7以航天員 A在2023年9月1日的執(zhí)行任務(wù)列表為例展示了典型的任務(wù)層規(guī)劃結(jié)果方案。

表7 2023年9月1日任務(wù)列表（航天員A）Table 7 2023?09?01 mission list（Astronaut A）

規(guī)劃結(jié)果方案均滿足空間站各項(xiàng)約束要求。圖6展示了不同優(yōu)先級(jí)任務(wù)的完成情況如，其中優(yōu)先級(jí)1、2級(jí)的任務(wù)完成率達(dá)100%，保證了在軌航天員安全駐留及空間站平臺(tái)的正常運(yùn)行；3到5級(jí)任務(wù)的完成率分別達(dá)到92%、99%和73%，實(shí)現(xiàn)了較高的空間應(yīng)用收益，其任務(wù)未執(zhí)行的主要原因是航天員工作人時(shí)、電能、設(shè)備及帶寬等資源不滿足任務(wù)的執(zhí)行需求?？臻g站工程總體將根據(jù)任務(wù)層規(guī)劃得到的任務(wù)初步執(zhí)行方案及工程目標(biāo)，對(duì)未執(zhí)行任務(wù)需求進(jìn)行調(diào)整，最終確定滿足工程要求的任務(wù)執(zhí)行方案。

圖6 不同優(yōu)先級(jí)任務(wù)的完成情況Fig.6 The completion of different priority missions

5 結(jié)論

經(jīng)驗(yàn)證本文建立的規(guī)劃模型，能有效描述多類(lèi)型任務(wù)、復(fù)雜約束以及多樣化需求的空間站運(yùn)營(yíng)任務(wù)層規(guī)劃問(wèn)題，提出的基于MPI并行計(jì)算的任務(wù)層規(guī)劃問(wèn)題并行求解方法能夠充分利用計(jì)算資源，獲得良好的運(yùn)行加速比，快速求得問(wèn)題可行解，可為我國(guó)研制空間站運(yùn)營(yíng)相關(guān)規(guī)劃系統(tǒng)提供參考。

（

）

［1］Popov A.Mission planning on the International Space Station program concepts and systems［C］//IEEE Aerospace confer?ence，2003：3427?3434.

［2］周建平.我國(guó)空間站工程總體構(gòu)想［J］.載人航天，2013，19（2）：1?10.Zhou Jianping.Chinese space station project overall vision［J］.Manned spaceflight，2013，19（2）：1?10.（in Chinese）.

［3］羅亞中，林鯤鵬，唐國(guó)金.空間站運(yùn)營(yíng)任務(wù)規(guī)劃技術(shù)評(píng)述［J］.載人航天，2012，18（2）：7?13.Luo Yazhong，Lin Kunpeng，Tang Guojin.Review on space station operation mission planning technology［J］.Manned spaceflight，2013，18（2）：7?13.（in Chinese）

［4］朱閱訸.空間站運(yùn)營(yíng)在軌事件與貨運(yùn)補(bǔ)給規(guī)劃方法研究［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2015.Zhu Yehe.Study on Space Station Operation On?Board Events and Cargo Supplying Planning Approach［D］.Changsha：Na?tional University of Defiance Technology，2014.（in Chinese）

［5］李志海，侯永青，嚴(yán)厚民，等.空間站長(zhǎng)期運(yùn)營(yíng)任務(wù)規(guī)劃建模初步研究［J］.載人航天，2013，19（5）：52?58.Li Zhihai，Hou Yongqing，Yan Houmin，et al.Preliminary modeling study on long?term operation mission planning of space station［J］.Manned spaceflight，2013，19（5）：52?58.（in Chinese）

［6］林鯤鵬.空間站長(zhǎng)期運(yùn)營(yíng)總體任務(wù)規(guī)劃與仿真方法［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2014.Lin Kunpeng.Overall Mission Planning and Simulation Ap?proaches for Space Station Long?duration Operations［D］.Changsha：National University of Defiance Technology，2014.（in Chinese）

［7］Bu H J，Zhang J，Luo Y Z，et al.Multi?objective optimiza?tion of space station short?term mission planning［J］.SCI?ENCE CHINA Technological Sciences.2015，58（12）：2169?2185.

［8］卜慧蛟，張進(jìn)，羅亞中，等.基于本體理論的空間站短期任務(wù)規(guī)劃領(lǐng)域建模研究［J］.載人航天，2016，22（2）：191?201.Bu Huijiao，Zhang Jin，Luo Yazhong，et al.Modeling of Space Station Short?Term Mission Planning Domain Based on Ontology Theory［J］.Manned spaceflight，2016，22（2）：191?201.（in Chinese）

［9］林鯤鵬.空間站運(yùn)營(yíng)總體任務(wù)規(guī)劃技術(shù)研究［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2010.Lin Kunpeng.Study on Space Station Operation Mission Plan?ning Technology［D］.Changsha：National University of Defi?ance Technology，2010.（in Chinese）

［10］陳國(guó)良，孫廣中，徐云，等.并行計(jì)算的一體化研究現(xiàn)狀與發(fā)展趨勢(shì)［J］.科學(xué)通報(bào)，2009，54（8）：1043～1049.Chen G L，Sun G Z，Xu Y，et al.Integrated research of par?allel computing：Status and future［J］.Chinese Sci Bull，2009，54（11）：1845?1853.（in Chinese）

［11］安竹林，基于MPI的并行遺傳算法研究［D］.合肥：合肥工業(yè)大學(xué)，2006.An Zhulin.Research on Parallel Genetic Algorithms Based on MPI［D］.Hefei：Hefei University of Technology，2006.（in Chinese）

［12］都志輝.高性能計(jì)算并行編程技術(shù)—MPI并行程序設(shè)計(jì)［M］.北京：清華大學(xué)出版社，2001：7?9.Du Zhihui.Parallel Programming technology for High Per?formance Computing?MPI parallel programming［M］.Beijing：Tsinghua University Press，2001：7?9（in Chinese）

［13］陳樹(shù)敏，羅俊博，陳青.并行計(jì)算技術(shù)的幾種實(shí)現(xiàn)方式研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2015，25（9）：174?181.Chen Shumin，Luo Junbo，Chen Qing.Research on ways of parallel computing technology［J］.Computer Technology and Development，2015，25（9）：174?181.（in Chinese）

Research on Parallel Planning Technology for On?Board Mission Planning of Space Station Operation

QIU Dongyang1，BU Huijiao1，WANG Shuai2，WANG Gongbo2，LUO Yazhong1?
（1.College of Aerospace Science and Engineering，National University of Defense Technology，Changsha 410073，China；2.Manned Space System Research Center，Beijing 100094，China）

Mission planning of the space station operation is a key technology to keep the long?term steady on?orbit operation of a space station.In terms of the operation requirements of China's space station（CSS），the modeling and planning methods of the space station pre?increment planning were studied.The pre?increment planning model，combining the theory of constraint satisfaction，was es?tablished to deal with issues such as multi?type missions，complex constraints，limited resources et al.Considering the features including the great?scale of problems，strong coupling，and solving diffi?culties，a parallel planning method was proposed.The simulation results showed that the speed?up ratio of the parallel planning method was 14.58 as compared with the traditional serial algorithm，which could effectively solve the problem.The implication of the current research conclusion may provide references for the development of CSS operation system.

space station；operation；mission planning；parallel computing

V423.7

A

1674?5825（2016）06?0680?07

2016?05?30；

2016?10?25

湖南省自然科學(xué)基金（2015JJ3020）；國(guó)防科學(xué)技術(shù)大學(xué)科研計(jì)劃（JC14?01?05）；載人航天預(yù)先研究項(xiàng)目（010103）

邱冬陽(yáng)（1991－），女，碩士研究生，研究方向?yàn)榭臻g站運(yùn)營(yíng)任務(wù)規(guī)劃。E?mail：gfkdqiu＠163.com

?通訊作者：羅亞中（1979－），男，博士，教授，研究方向?yàn)檩d人航天任務(wù)規(guī)劃。E?mail：luoyz＠nudt.edu.cn