張家銘，劉 忠，石建邁，賀云岳

（國(guó)防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，湖南長(zhǎng)沙410073）

考慮發(fā)射失敗的多中心多衛(wèi)星發(fā)射任務(wù)協(xié)同規(guī)劃方法

張家銘，劉 忠，石建邁，賀云岳

（國(guó)防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，湖南長(zhǎng)沙410073）

在中國(guó)未來(lái)衛(wèi)星發(fā)射需求急劇增加和衛(wèi)星發(fā)射中心發(fā)射能力有限的情況下，為多顆衛(wèi)星協(xié)調(diào)發(fā)射中心和發(fā)射時(shí)間變得日趨困難。為解決大量衛(wèi)星發(fā)射任務(wù)的協(xié)同規(guī)劃問(wèn)題，以發(fā)射成本最少、發(fā)射失敗概率最低為優(yōu)化目標(biāo)，建立了多中心多衛(wèi)星發(fā)射任務(wù)協(xié)同優(yōu)化的多目標(biāo)混合整數(shù)規(guī)劃模型?；诜侵渑判虻亩嗄繕?biāo)優(yōu)化算法（nondominated sorting genetic algorithm II，NSGA-II）框架，設(shè)計(jì)了求解模型的多目標(biāo)進(jìn)化算法，提出了發(fā)射中心選擇的整數(shù)編碼方案，給出了基于啟發(fā)式搜索的發(fā)射時(shí)間規(guī)劃解碼算法，并設(shè)計(jì)了染色體質(zhì)量檢查與修正算法?；谥袊?guó)現(xiàn)有的4個(gè)衛(wèi)星發(fā)射中心和可能面臨的6類(lèi)發(fā)射任務(wù)，設(shè)計(jì)了包含10顆衛(wèi)星發(fā)射任務(wù)的小規(guī)模案例和30顆衛(wèi)星發(fā)射任務(wù)的大規(guī)模案例，對(duì)模型和算法進(jìn)行了仿真驗(yàn)證。實(shí)驗(yàn)結(jié)果表明該方法能有效解決多中心多發(fā)射任務(wù)協(xié)同規(guī)劃問(wèn)題。

衛(wèi)星發(fā)射；多目標(biāo)優(yōu)化；任務(wù)規(guī)劃；整數(shù)規(guī)劃

0 引 言

衛(wèi)星發(fā)射任務(wù)協(xié)同規(guī)劃是在滿足不同約束的條件下，為各種衛(wèi)星發(fā)射任務(wù)合理分配發(fā)射資源并安排發(fā)射時(shí)間，使得衛(wèi)星發(fā)射收益最大化（或損失最小化）的過(guò)程。文獻(xiàn)［1］指出，運(yùn)籌學(xué)方法早已運(yùn)用于研究包括衛(wèi)星發(fā)射任務(wù)規(guī)劃在內(nèi)的航天工業(yè)的諸多問(wèn)題，且取得了非常好的效果。根據(jù)衛(wèi)星發(fā)射傾角、運(yùn)行軌道、使用壽命等要求的不同，為衛(wèi)星發(fā)射任務(wù)選擇適合的衛(wèi)星發(fā)射中心至關(guān)重要，而科學(xué)合理的衛(wèi)星發(fā)射中心任務(wù)規(guī)劃策略不僅可以緩解日益顯現(xiàn)的發(fā)射場(chǎng)使用緊張的狀況，保障衛(wèi)星發(fā)射任務(wù)的順利進(jìn)行，更有助于提高我國(guó)衛(wèi)星發(fā)射產(chǎn)業(yè)的競(jìng)爭(zhēng)優(yōu)勢(shì)。隨著我國(guó)經(jīng)濟(jì)建設(shè)和社會(huì)發(fā)展對(duì)各類(lèi)衛(wèi)星需求的日益增長(zhǎng)，近年來(lái)我國(guó)加快了衛(wèi)星立項(xiàng)研制、發(fā)射和應(yīng)用的步伐，發(fā)射中心承擔(dān)的衛(wèi)星發(fā)射任務(wù)不斷增多。根據(jù)中國(guó)航天科技集團(tuán)公司介紹，到2020年，我國(guó)年均衛(wèi)星發(fā)射數(shù)量將達(dá)到30次左右，占全球發(fā)射數(shù)量30%。屆時(shí)，我國(guó)的衛(wèi)星發(fā)射中心將進(jìn)入新一輪高密度發(fā)射期［2］。如何在發(fā)射場(chǎng)數(shù)量有限的條件下，對(duì)發(fā)射任務(wù)進(jìn)行合理的規(guī)劃便成為提高整個(gè)衛(wèi)星發(fā)射系統(tǒng)容量和效率的一個(gè)關(guān)鍵所在。衛(wèi)星發(fā)射任務(wù)規(guī)劃不合理，將會(huì)造成發(fā)射任務(wù)的延誤和擁堵，甚至有可能造成不可挽回的損失。因此，有必要研究衛(wèi)星發(fā)射任務(wù)規(guī)劃問(wèn)題，尋找合理高效的規(guī)劃方案。

目前，國(guó)內(nèi)外公開(kāi)發(fā)表的關(guān)于衛(wèi)星發(fā)射任務(wù)規(guī)劃的研究成果不多，在發(fā)表的極少數(shù)的相關(guān)研究成果中，文獻(xiàn)［3］提出了解決發(fā)射任務(wù)規(guī)劃的混合整數(shù)規(guī)劃模型（mixed-integer linear programming，MILP），用于解決地球同步轉(zhuǎn)移軌道（geostationary transfer orbit，GTO）衛(wèi)星和非地球同步轉(zhuǎn)移軌道（non-geostationary transfer orbit，non-GTO）衛(wèi)星的發(fā)射任務(wù)規(guī)劃問(wèn)題，取得了較好的效果。文獻(xiàn)［4］提出了航天器發(fā)射多任務(wù)并行規(guī)劃模型及算法，模擬不同方案的每次任務(wù)、每道工序的工作過(guò)程，結(jié)合算法尋找任務(wù)規(guī)劃的最優(yōu)方案，效果較好。文獻(xiàn)［5］闡述了衛(wèi)星發(fā)射失敗的嚴(yán)重后果，指出衛(wèi)星發(fā)射失敗后，不僅僅是重新補(bǔ)發(fā)那么簡(jiǎn)單，更嚴(yán)重的是錯(cuò)過(guò)了合適的衛(wèi)星發(fā)射窗口，整個(gè)衛(wèi)星發(fā)射計(jì)劃將會(huì)受影響。

盡管衛(wèi)星發(fā)射任務(wù)規(guī)劃研究成果不多，但作業(yè)車(chē)間調(diào)度問(wèn)題（job shop scheduling problem，JSP）［6－7］以及并行多機(jī)調(diào)度問(wèn)題早已成為研究熱點(diǎn)［8－10］，成像偵察衛(wèi)星和電子偵察衛(wèi)星任務(wù)規(guī)劃問(wèn)題也得到深入研究［11－13］，這些成果為本研究提供了參考。本文在對(duì)上述相關(guān)文獻(xiàn)的理解和借鑒基礎(chǔ)上，從衛(wèi)星發(fā)射任務(wù)規(guī)劃問(wèn)題的描述入手，建立了多中心多衛(wèi)星發(fā)射任務(wù)協(xié)同優(yōu)化的多目標(biāo)混合整數(shù)規(guī)劃模型，基于NSGA-II框架，設(shè)計(jì)了求解模型的多目標(biāo)進(jìn)化算法，并通過(guò)具體的仿真實(shí)驗(yàn)驗(yàn)證了模型的有效性。

1 問(wèn)題描述

在時(shí)間范圍［T，T＋Δt］內(nèi)有J（J＞1）個(gè)衛(wèi)星發(fā)射任務(wù)需要完成，可供使用的衛(wèi)星發(fā)射中心有I（I＞1）個(gè)，由于緯度等地理環(huán)境的不同，以及功能設(shè)計(jì)的差異，各衛(wèi)星發(fā)射中心在完成不同發(fā)射任務(wù)時(shí)的消耗時(shí)間和成本也不盡相同。因此，衛(wèi)星發(fā)射任務(wù)規(guī)劃問(wèn)題可以描述為，在滿足發(fā)射時(shí)間窗口要求和其他約束條件的同時(shí)，根據(jù)發(fā)射任務(wù)的用時(shí)變化特點(diǎn)，為發(fā)射任務(wù)安排合理的衛(wèi)星發(fā)射中心、發(fā)射時(shí)間及發(fā)射順序，以獲得最優(yōu)的規(guī)劃方案。

為便于研究，在不影響衛(wèi)星發(fā)射主要需求的前提下，進(jìn)行如下假設(shè)：

（1）對(duì)衛(wèi)星發(fā)射中心的假設(shè)。只考慮在同一時(shí)間段，每個(gè)衛(wèi)星發(fā)射中心只允許執(zhí)行一個(gè)發(fā)射任務(wù)。本文所指的發(fā)射時(shí)間是個(gè)廣義的概念，包含從運(yùn)載火箭及衛(wèi)星進(jìn)場(chǎng)，到航天器發(fā)射升空等階段所消耗的時(shí)間總和，且本文不考慮發(fā)射中心從發(fā)射場(chǎng)狀態(tài)恢復(fù)到滿足執(zhí)行下一發(fā)射任務(wù)的時(shí)間。

（2）對(duì)衛(wèi)星發(fā)射任務(wù)的假設(shè)。不考慮氣象條件對(duì)發(fā)射任務(wù)的影響，在給定的最早開(kāi)始時(shí)間到最遲完成時(shí)間區(qū)間內(nèi)，各個(gè)任務(wù)均能被執(zhí)行，不考慮任務(wù)推延的情況。

2 模型構(gòu)建

2.1 符號(hào)說(shuō)明

2.1.1 集合

I為衛(wèi)星發(fā)射中心集合，且i＝1，2，…，I；

J為待發(fā)射衛(wèi)星集合，且j＝1，2，…，J。

2.1.2 參數(shù)

tij：發(fā)射中心i發(fā)射衛(wèi)星j的消耗時(shí)間；

cij：發(fā)射中心i發(fā)射衛(wèi)星j的成本；

pij：發(fā)射中心i發(fā)射衛(wèi)星j的成功概率；

tj＿start：第j顆衛(wèi)星的最早發(fā)射時(shí)間；

t

j＿finish：第j顆衛(wèi)星的最遲發(fā)射時(shí)間；

Δtij：發(fā)射中心i發(fā)射衛(wèi)星j的準(zhǔn)備時(shí)間；

Ti：發(fā)射中心i的可用發(fā)射時(shí)間窗口，

2.1.3 決策變量

tj：衛(wèi)星j的發(fā)射時(shí)間；

xij：為0－1變量，第j個(gè)衛(wèi)星在第i個(gè)衛(wèi)星發(fā)射中心發(fā)射時(shí)值為1，否則值為0。

2.2 數(shù)學(xué)模型

2.2.1 優(yōu)化目標(biāo)

同其他任務(wù)規(guī)劃問(wèn)題的研究背景有所不同，本文研究的衛(wèi)星發(fā)射規(guī)劃屬于高投入、高風(fēng)險(xiǎn)的航天工程管理問(wèn)題，為提高發(fā)射任務(wù)可靠性，降低任務(wù)組織風(fēng)險(xiǎn)，衛(wèi)星發(fā)射任務(wù)的成本、時(shí)間和成功率等都是必須考慮的重要性能指標(biāo)。為此，本文構(gòu)建的0－1整數(shù)規(guī)劃模型考慮了發(fā)射成本和發(fā)射成功率兩個(gè)優(yōu)化目標(biāo)。

（1）總發(fā)射成本最小

由于衛(wèi)星發(fā)射中心的地理位置、交通狀況等的差異，導(dǎo)致不同類(lèi)型的衛(wèi)星在不同的發(fā)射中心發(fā)射，其發(fā)射成本也不盡相同。因此，衛(wèi)星發(fā)射任務(wù)隨規(guī)劃方案的不同而不同，在所有發(fā)射任務(wù)均能完成的前提下，應(yīng)盡量減少所有發(fā)射任務(wù)的發(fā)射成本，如式（1）所示。

（2）發(fā)射失敗概率最低

如前所述，衛(wèi)星發(fā)射屬于風(fēng)險(xiǎn)極高的產(chǎn)業(yè)，一次失敗不僅會(huì)造成巨大的經(jīng)濟(jì)損失，還可能導(dǎo)致一個(gè)國(guó)家的國(guó)際競(jìng)爭(zhēng)力和國(guó)家聲譽(yù)遭受難以挽回的影響。據(jù)統(tǒng)計(jì)，2004～2013年的10年間，全球共進(jìn)行了708次航天發(fā)射，其中共有36次發(fā)射失敗，發(fā)射失敗率為5.08%，失敗率雖然不算高，但失敗所造成的損失是驚人的［14－16］。僅以2010年12月5日俄羅斯的“質(zhì)子-M”火箭發(fā)射失敗為例，此次發(fā)射失敗直接經(jīng)濟(jì)損失高達(dá)4億美元，不僅如此，發(fā)射失敗完全打亂了俄羅斯的“全球?qū)Ш叫l(wèi)星系統(tǒng)”（GLONASS）的

2.2.2 約束條件

（1）每個(gè)衛(wèi)星的發(fā)射時(shí)間必須滿足衛(wèi)星發(fā)射時(shí)間窗口的要求，即發(fā)射時(shí)間必須在最早開(kāi)始時(shí)間和最晚完成時(shí)間區(qū)間內(nèi)，如式（3）所示。

（2）由于地球自轉(zhuǎn)和氣候等因素的影響，每個(gè)衛(wèi)星發(fā)射中心一年內(nèi)總有一定的時(shí)間段無(wú)法執(zhí)行衛(wèi)星發(fā)射任務(wù)，必須將發(fā)射任務(wù)安排在發(fā)射中心可用的發(fā)射時(shí)間段內(nèi)。因此，某一發(fā)射中心的可用發(fā)射時(shí)間窗口是若干可用時(shí)間段的集合，如式（4）所示。衛(wèi)星星座部署計(jì)劃，使俄羅斯擁有屬于自己的全球定位系統(tǒng)的夢(mèng)想不得不推遲實(shí)現(xiàn)［17］。因此，進(jìn)行衛(wèi)星發(fā)射任務(wù)規(guī)劃時(shí)應(yīng)當(dāng)全面掌握發(fā)射中心的衛(wèi)星發(fā)射記錄，特別是發(fā)射失敗的情況，在制定規(guī)劃方案時(shí)應(yīng)充分考慮和權(quán)衡失敗風(fēng)險(xiǎn)，應(yīng)盡量降低發(fā)射任務(wù)失敗的概率［18－19］，如式（2）所示。

（3）運(yùn)載火箭發(fā)射升空及進(jìn)入預(yù)定軌道過(guò)程中，分布在不同地域的測(cè)控站都在對(duì)其進(jìn)行實(shí)時(shí)監(jiān)控，為了避免幾個(gè)運(yùn)載火箭同時(shí)發(fā)射導(dǎo)致測(cè)控資源緊張，不允許幾個(gè)發(fā)射中心在同一時(shí)間進(jìn)行航天發(fā)射，如式（5）所示。

（4）實(shí)際運(yùn)用中，導(dǎo)航衛(wèi)星系統(tǒng)、通信衛(wèi)星系統(tǒng)等大型的衛(wèi)星系統(tǒng)必須由多顆衛(wèi)星組網(wǎng)才能達(dá)到設(shè)計(jì)的功能，為逐步實(shí)現(xiàn)這些功能，某些單顆衛(wèi)星的發(fā)射順序是預(yù)先固定的。例如，我國(guó)的北斗衛(wèi)星導(dǎo)航系統(tǒng)的空間段包括5顆靜止軌道衛(wèi)星和30顆非靜止軌道衛(wèi)星，截止2013年10月25日，我國(guó)已經(jīng)先后將16顆北斗導(dǎo)航衛(wèi)星送入預(yù)定軌道，順利完成我國(guó)北斗導(dǎo)航的區(qū)域組網(wǎng)工作。這些衛(wèi)星的發(fā)射順序是按預(yù)定計(jì)劃而固定的。這類(lèi)有順序先后的約束關(guān)系如式（6）所示。

（5）從航天器及有效載荷進(jìn)場(chǎng)到衛(wèi)星發(fā)射的全套發(fā)射工序只能在同一個(gè)發(fā)射中心執(zhí)行，即每個(gè)衛(wèi)星發(fā)射任務(wù)只能由一個(gè)發(fā)射中心完成，如式（7）所示。

3 算法設(shè)計(jì)

本文研究的多中心多衛(wèi)星發(fā)射任務(wù)協(xié)同優(yōu)化問(wèn)題屬于多目標(biāo)優(yōu)化問(wèn)題，求解多目標(biāo)優(yōu)化問(wèn)題往往可以采用NSGA-II算法。本文借鑒標(biāo)準(zhǔn)NSGA-II算法的思想，針對(duì)多中心多衛(wèi)星發(fā)射任務(wù)規(guī)劃模型的特點(diǎn)進(jìn)行了算法設(shè)計(jì)。

3.1 編碼與解碼

結(jié)合問(wèn)題的特點(diǎn)，本文設(shè)計(jì)一種基于發(fā)射中心和發(fā)射任務(wù)的整數(shù)編碼方案，利用隨機(jī)生成的發(fā)射中心序號(hào)作為個(gè)體的編碼，染色體長(zhǎng)度為所有發(fā)射任務(wù)的數(shù)量J，每個(gè)基因位是［1，I］之間的隨機(jī)整數(shù)，其中I為衛(wèi)星發(fā)射中心的數(shù)量。例如，假設(shè)有4個(gè)衛(wèi)星發(fā)射中心承擔(dān)了10顆衛(wèi)星的發(fā)射任務(wù)，染色體編碼的長(zhǎng)度為任務(wù)數(shù)10，基因位序號(hào)代表任務(wù)的序號(hào)，每個(gè)基因位是［1，4］之間的隨機(jī)整數(shù)［9］。某染色體編碼如圖1所示。

圖1 染色體編碼結(jié)構(gòu)

采用這種編碼方法既簡(jiǎn)單、方便，又能保證每個(gè)染色體能快速解碼為一種發(fā)射任務(wù)規(guī)劃方案。如圖1所示，第1個(gè)基因位數(shù)值為3，表示第1個(gè)任務(wù)分配到第3個(gè)發(fā)射中心執(zhí)行；第2個(gè)基因位數(shù)值為4，表示第2個(gè)任務(wù)分配到第4個(gè)發(fā)射中心執(zhí)行，依次類(lèi)推，則可以得到一個(gè)初始的發(fā)射任務(wù)分配方案，如表1所示。

表1 發(fā)射任務(wù)初始分配方案

本文研究的衛(wèi)星發(fā)射任務(wù)規(guī)劃問(wèn)題包括兩個(gè)子問(wèn)題：發(fā)射中心分配和發(fā)射任務(wù)排序。剛生成的發(fā)射任務(wù)初始分配方案僅僅解決了每個(gè)發(fā)射任務(wù)在哪個(gè)發(fā)射中心進(jìn)行發(fā)射的問(wèn)題。接下來(lái)還需將各發(fā)射中心的任務(wù)進(jìn)行排序，決定各衛(wèi)星的發(fā)射時(shí)間及先后順序。屆時(shí)，發(fā)射任務(wù)規(guī)劃方案才算最終形成。為此，本文設(shè)計(jì)了基于發(fā)射最早開(kāi)始時(shí)間升序排列（earliest start time ascending order，ESTA）和基于發(fā)射最晚完成時(shí)間升序排列（latest finish time ascending order，LFTA）兩種任務(wù)排序規(guī)則。表2為10顆衛(wèi)星發(fā)射任務(wù)的最早開(kāi)始時(shí)間tj＿start和最晚完成時(shí)間tj＿finish計(jì)劃表。

表2 10顆衛(wèi)星發(fā)射任務(wù)的時(shí)間要求1）

以發(fā)射中心1的3個(gè)發(fā)射任務(wù)（任務(wù)4、任務(wù)6、任務(wù)7）為例來(lái)說(shuō)明兩種排序規(guī)則的具體操作。如表2所示，發(fā)射中心1的3個(gè)發(fā)射任務(wù)最早開(kāi)始時(shí)間分別為：55、40、50，若采用ESTA排列規(guī)則，則發(fā)射中心1的3個(gè)發(fā)射任務(wù)執(zhí)行順序?yàn)椋喝蝿?wù)6→任務(wù)7→任務(wù)4。發(fā)射中心1的3個(gè)發(fā)射任務(wù)最晚完成時(shí)間分別為：105、100、95，若采用LFTD排列規(guī)則，則發(fā)射中心1的3個(gè)發(fā)射任務(wù)執(zhí)行順序?yàn)椋喝蝿?wù)7→任務(wù)6→任務(wù)4。具體操作如圖2所示。表3為所有10個(gè)任務(wù)的執(zhí)行順序。

圖2 在發(fā)射中心1執(zhí)行的任務(wù)排序示意圖

編碼與解碼具體執(zhí)行步驟如下：

步驟1 設(shè)定染色體長(zhǎng)度，其長(zhǎng)度等于發(fā)射任務(wù)數(shù)。

步驟2 隨機(jī)生成一個(gè)［1，I］之間的正整數(shù)作為染色體基因位的值，并從左至右填滿到基因位。

步驟3 選取基因位值為i＝1，2，…，I的基因位序號(hào)數(shù)，構(gòu)成的集合便是第i個(gè)發(fā)射中心的執(zhí)行任務(wù)。

步驟4 采用ESTA（或LFTD）排列規(guī)則，為各發(fā)射中心的任務(wù)進(jìn)行執(zhí)行順序排序，生成初始規(guī)劃方案。

3.2 交叉策略

為使父代個(gè)體經(jīng)過(guò)操作后產(chǎn)生新個(gè)體，并在盡量避免染色體結(jié)構(gòu)被破壞的基礎(chǔ)上提高解空間的搜索效率［20］，本文設(shè)計(jì)如下交叉策略：

步驟1 隨機(jī)產(chǎn)生一個(gè)［1，J）區(qū)間內(nèi)的正整數(shù)r，在此基礎(chǔ)上再隨機(jī)產(chǎn)生互不相等的r個(gè)正整數(shù)。

步驟2 以上一步驟產(chǎn)生的整數(shù)r為依據(jù)，將兩個(gè)父代染色體中對(duì)應(yīng)位置的基因復(fù)制到兩個(gè)子代染色體對(duì)應(yīng)位置處，并且保持它們的順序和位置。

步驟3 將兩個(gè)父代染色體剩余的基因值依次復(fù)制到兩個(gè)子代染色體相應(yīng)位置中。

以父代染色體F1和F2為例，其染色體長(zhǎng)度為6，隨機(jī)產(chǎn)生［1，6）區(qū)間內(nèi)的一個(gè)正整數(shù)2，在此基礎(chǔ)上，再隨機(jī)生成［1，6）區(qū)間內(nèi)的兩個(gè)互不相等的正整數(shù)（2和5），將2和5作為交叉的位置序號(hào)，將父代染色體F1和F2中的相應(yīng)位置的基因值分別復(fù)制到子代染色體C1和C2相應(yīng)位置中，從而產(chǎn)生兩個(gè)新的個(gè)體C1和C2。如圖3所示。

圖3 染色體交叉操作示意圖

3.3 變異策略

本文采用互換、插入和逆序3種變異方法，通過(guò)隨機(jī)改變?nèi)旧w某些基因位的值，用較小的擾動(dòng)來(lái)產(chǎn)生新的個(gè)體，以增加種群多樣性［21］。具體執(zhí)行操作如圖4所示。

圖4 染色體變異操作示意圖

3.4 染色體質(zhì)量檢查及修正算法

在染色體編碼、交叉操作、變異操作過(guò)程中，會(huì)存在染色體不合格的情況，這不僅會(huì)影響種群質(zhì)量，甚至還可能導(dǎo)致得不到可行解。例如，在染色體編碼過(guò)程中，由于基因位是［1，I］之間的隨機(jī)整數(shù)，有可能遺漏某些數(shù)值，從而造成某些發(fā)射中心沒(méi)有分配到發(fā)射任務(wù)的情況。仍以4個(gè)衛(wèi)星發(fā)射中心承擔(dān)10顆衛(wèi)星的發(fā)射任務(wù)為例，某染色體如圖5所示。

圖5 不合格的染色體

可以看出，在產(chǎn)生［1，4］之間的隨機(jī)整數(shù)過(guò)程中，遺漏了整數(shù)4，即第4個(gè)發(fā)射中心沒(méi)有分配到發(fā)射任務(wù)，這顯然是一個(gè)不可行的分配方案，類(lèi)似情況在交叉操作和變異操作過(guò)程中同樣會(huì)出現(xiàn)。因此，必須設(shè)計(jì)一個(gè)算法，該算法具備對(duì)染色體質(zhì)量進(jìn)行實(shí)時(shí)檢查及修正的功能，確保種群質(zhì)量及運(yùn)算的順利進(jìn)行。

（1）染色體檢查策略

步驟1 生成一個(gè)1行I列的空矩陣，用于保存檢測(cè)序號(hào)。

步驟2 采用順序查找的方法，從染色體第一個(gè)基因位置開(kāi)始，依次將每個(gè)數(shù)值同給定的數(shù)值［1，2，…，I］進(jìn)行比較。首先查找數(shù)值1，若找到某基因位數(shù)值為1，則將空矩陣第一位賦值為1；若沒(méi)有查找到數(shù)值1，則在空矩陣第一位賦值0。

步驟3 重復(fù)步驟2，直到檢測(cè)完基因位最后一位，此時(shí)，若空矩陣各元素均為1，則說(shuō)明各基因位數(shù)值涵蓋了給定的［1，2，…，I］之間的所有隨機(jī)整數(shù)，即每個(gè)發(fā)射中心均分配到了發(fā)射任務(wù)；若空矩陣中第i位元素為0，則說(shuō)明基因位數(shù)值中缺少了數(shù)值i，即第i個(gè)發(fā)射中心沒(méi)有分配到任務(wù)。檢查結(jié)束。

（2）染色體修正策略

對(duì)于檢查不合格的染色體，必須對(duì)其進(jìn)行及時(shí)修正，本文采取的方法是將檢測(cè)出來(lái)缺少的數(shù)值i換入不合格染色體，換出的數(shù)值為基因位中出現(xiàn)次數(shù)最多的值，而具體的交換位置選擇在其第一次出現(xiàn)的位置。

如圖6所示，F(xiàn)1染色體基因位中缺少數(shù)值4，而數(shù)值2出現(xiàn)的次數(shù)又最多。根據(jù)上述修正策略，將數(shù)值4換入，將數(shù)值2換出，而換出位置選在數(shù)值2第一次出現(xiàn)的位置。修正后的F2染色體確保了基因位數(shù)值的完整，可以保證后續(xù)計(jì)算順利進(jìn)行。假如存在不合格染色體的幾個(gè)基因位數(shù)值出現(xiàn)次數(shù)一樣多的情況，則將其都確定為換出數(shù)值，且換出位置都為其第一次出現(xiàn)的位置。

圖6 不合格染色體的修正

3.5 算法流程

本文借鑒了標(biāo)準(zhǔn)的NSGA-II算法思想，并結(jié)合多中心多衛(wèi)星發(fā)射任務(wù)協(xié)同優(yōu)化的特點(diǎn)，進(jìn)行了調(diào)整及改進(jìn)，具體計(jì)算流程如圖7所示。

圖7 算法流程圖

4 實(shí)驗(yàn)計(jì)算及結(jié)果分析

實(shí)驗(yàn)計(jì)算機(jī)配置為Intel（R）Core2 6400＠2.13GHz，內(nèi)存為2.00GB，操作系統(tǒng)為Windows XP，編程環(huán)境為Matlab R2012a。

4.1 實(shí)驗(yàn)1

4.1.1 實(shí)驗(yàn)數(shù)據(jù)說(shuō)明

實(shí)驗(yàn)1設(shè)置為小規(guī)模問(wèn)題，即10顆衛(wèi)星發(fā)射任務(wù)在4個(gè)發(fā)射中心進(jìn)行發(fā)射。

每顆衛(wèi)星的最早允許發(fā)射時(shí)間和最遲要求發(fā)射時(shí)間如表2所示。

各發(fā)射中心的發(fā)射執(zhí)行時(shí)間和發(fā)射成本如表4所示。各衛(wèi)星發(fā)射中心自成立并投入使用以來(lái)，發(fā)射各類(lèi)衛(wèi)星的成功概率可通過(guò)歷史數(shù)據(jù)查詢得知，不妨設(shè)10個(gè)發(fā)射任務(wù)包含6種類(lèi)型的衛(wèi)星。即，任務(wù)1、任務(wù)4屬于第一種類(lèi)型；任務(wù)2、任務(wù)8屬于第二種類(lèi)型；任務(wù)7屬于第三種類(lèi)型；任務(wù)10屬于第四種類(lèi)型；任務(wù)3、任務(wù)5、任務(wù)6屬于第五種類(lèi)型；任務(wù)9屬于第六種類(lèi)型。6種類(lèi)型衛(wèi)星的發(fā)射成功率如表5所示。各個(gè)衛(wèi)星發(fā)射中心一年內(nèi)總有一段時(shí)間無(wú)法執(zhí)行衛(wèi)星發(fā)射任務(wù)，設(shè)各中心可用發(fā)射時(shí)間窗口如表6所示。

表4 10個(gè)任務(wù)的發(fā)射執(zhí)行時(shí)間及發(fā)射成本

表5 4個(gè)衛(wèi)星發(fā)射中心發(fā)射6類(lèi)衛(wèi)星的成功率

表6 4個(gè)衛(wèi)星發(fā)射中心的可用發(fā)射時(shí)間窗口

4.1.2 實(shí)驗(yàn)結(jié)果分析

取初始種群規(guī)模為50，最大迭代次數(shù)為100，交叉概率為0.8，變異概率為0.6，遺傳算法搜索得到所有衛(wèi)星發(fā)射任務(wù)完成的最短時(shí)間是147天，發(fā)射任務(wù)最優(yōu)分配方案及目標(biāo)值如表7所示，即發(fā)射中心1執(zhí)行2個(gè)發(fā)射任務(wù)（任務(wù)7、任務(wù)8），發(fā)射中心2執(zhí)行3個(gè)發(fā)射任務(wù)（任務(wù)5、任務(wù)6、任務(wù)9），發(fā)射中心3執(zhí)行1個(gè)發(fā)射任務(wù)（任務(wù)1），發(fā)射中心4執(zhí)行4個(gè)發(fā)射任務(wù)（任務(wù)2、任務(wù)3、任務(wù)4、任務(wù)10），且所有任務(wù)執(zhí)行費(fèi)用和為20 860萬(wàn)元，所有任務(wù)的失敗概率和為0.889。

圖8為多目標(biāo)（目標(biāo)1：發(fā)射成本最少，目標(biāo)2：發(fā)射失敗概率最低）Pareto解分級(jí)示意圖，圖中列出了4個(gè)不同迭代次數(shù)所得到的非支配解分級(jí)情況。如圖8所示，隨著迭代次數(shù)的增加，第1級(jí)非支配解呈現(xiàn)出趨向全局最優(yōu)的趨勢(shì)。

表7 任務(wù)最優(yōu)分配方案及目標(biāo)值

圖8 非支配解分級(jí)示意圖

圖9為發(fā)射任務(wù)規(guī)劃甘特圖，圖中縱坐標(biāo)代表發(fā)射中心，橫坐標(biāo)代表發(fā)射時(shí)間，網(wǎng)狀底紋方塊代表某發(fā)射中心不可用時(shí)間段，淺灰色方塊表示發(fā)射任務(wù)，方塊的長(zhǎng)度表示占用時(shí)間的多少。

圖9 10顆衛(wèi)星的發(fā)射任務(wù)規(guī)劃甘特圖

4.2 實(shí)驗(yàn)2

實(shí)驗(yàn)2設(shè)置為大規(guī)模問(wèn)題，即30個(gè)衛(wèi)星發(fā)射任務(wù)在4個(gè)衛(wèi)星發(fā)射中心執(zhí)行的規(guī)劃問(wèn)題。對(duì)于大規(guī)模問(wèn)題，本文模型及算法依然可行。設(shè)遺傳算法基本參數(shù)設(shè)置同實(shí)驗(yàn)1，搜索得到所有衛(wèi)星發(fā)射任務(wù)完成的最短時(shí)間是268天，發(fā)射任務(wù)規(guī)劃甘特圖如圖10所示。

圖10 30顆衛(wèi)星的發(fā)射任務(wù)規(guī)劃甘特圖

5 結(jié) 論

本文針對(duì)衛(wèi)星發(fā)射任務(wù)規(guī)劃問(wèn)題構(gòu)建了數(shù)學(xué)模型，并結(jié)合問(wèn)題的具體特點(diǎn)，設(shè)計(jì)了多層編碼的遺傳算法進(jìn)行問(wèn)題求解，并對(duì)10顆衛(wèi)星、30顆衛(wèi)星在4發(fā)射中心發(fā)射這兩種不同規(guī)模的算例進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果顯示，本文的模型和算法能得到滿意的規(guī)劃方案。下一步，將在發(fā)射任務(wù)動(dòng)態(tài)到達(dá)和算法設(shè)計(jì)方面進(jìn)行深入研究。

［1］Fliege J，Kaparis K，Khosravi B.Operations research in thespace industry［J］.European Journal of Operational Research，2012，217（2）：233－240.

［2］Zhu Z Y.In 2012the global satellite industry increased to MYM189billion Chinese spacecraft manufacturing surpass the European and Russia［J］.Chinese Economic Weekly，2013（20）：70－71.（朱梓燁.2012年全球衛(wèi)星產(chǎn)業(yè)增至1895億美元中國(guó)航天器制造超歐洲俄羅斯［J］.中國(guó)經(jīng)濟(jì)周刊，2013（20）：70－71.）

［3］Brandimarte P.Scheduling satellite launch missions：an MILP approach［J］.Journal of Scheduling，2013，16（1）：29－45.

［4］Dong X J，Xing L N.Scheduling model and algorithm of parallel multitask on spacecraft launch［J］.Systems Engineering and E-lectronics，2013，35（7）：1438－1444.（董學(xué)軍，邢立寧.航天器發(fā)射多任務(wù)并行規(guī)劃模型及算法［J］.系統(tǒng)工程與電子技術(shù)，2013，35（7）：1438－1444.）

［5］Gavish B，Kalvenes J.Dynamic policies for optimal LEO satellite launches［J］.Production and Operations Management Society，2004，13（4）：386－397.

［6］Debra J，Peter B，Krishna R.A practical approach to job-shop scheduling problems［J］.Robotics and Automation，1993，9（1）：1－13.

［7］Arash M，Kamyar S，Mahdi H.Solving flexible job shop scheduling with multi objective approach［J］.International Journal of Industrial Engineering ＆Production Research，2010，21（4）：197－209.

［8］Kettimuthu R，Subramani V，Srinivasan S，et al.Selective preemption strategies for parallel job scheduling［J］.International Journal of High Performance Computing and Networking，2005，3（2）：122－152.

［9］Liu Z X.Research of particle swarm optimization algorithm for parallel machine scheduling problem［J］.Machinery Design ＆Manufacture，2010（10）：68－70.（劉志雄.并行機(jī)調(diào)度問(wèn)題粒子群優(yōu)化研究［J］.機(jī)械設(shè)計(jì)與制造，2010（10）：68－70.）

［10］Brandimarte P.Exploiting process plan fiexibility in production scheduling：a multi-objective approach［J］.European Journal of Operational Research，1999，114（1）：59－71.

［11］Wang P，Reinelt G，Gao P.A model，a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation［J］.Computers ＆Industrial Engineering，2011，61（2）：322－335.

［12］Lema?tre M，Verfaillie G，Jouhaud F，et al.Selecting and scheduling observations of agile satellites［J］.Aerospace Science and Technology，2002，6（5）：367－381.

［13］Nowakovski J，Schw?rzler W，Triesch E.Using the generalized assignment problem in scheduling the ROSAT space telescope［J］.European Journal of Operational Research，1999，112（3）：531－541.

［14］Yang G.The global space activity review in 2008［J］.Chinese Space，2009（2）：32－39.（陽(yáng)光.2008年全球航天活動(dòng)回顧［J］.中國(guó)航天，2009（2）：32－39.）

［15］Yang G.The global space activity review in 2011（I）［J］.Chinese Space，2012（2）：14－21.（陽(yáng)光.2011年全球航天活動(dòng)回顧（上）［J］.中國(guó)航天，2012（2）：14－21.）

［16］Xu Y X.Statistical analysis of spacecraft launching all over the world in 2013［J］.Space International，2014（2）：7－10.（徐映霞.2013年世界航天器發(fā)射統(tǒng)計(jì)分析［J］.國(guó)際太空，2014（2）：7－10.）

［17］Bo Y.The Russian navigation satellite launching failure leads to delay new round satellite constellation deployment time［J］.Space International，2011（1）：1－11.（博引.俄羅斯導(dǎo)航衛(wèi)星發(fā)射失敗新一輪完整衛(wèi)星星座部署時(shí)間推遲［J］.國(guó)際太空，2011（1）：1－11.）

［18］Leslie O，Alysse R，Richard L.Simultaneously determining the mix of space launch vehicles and the assignment of satellites to rockets［J］.European Journal of Operational Research，2006，172（3）：747－760.

［19］Farhan A，He L S，Kamranb A，et al.Hyper heuristic approach for design and optimization of satellite launch vehicle［J］.Chinese Journal of Aeronautics，2011，24（2）：150－163.

［20］Gao L，Zhang G H，Wang X J，et al.The flexible job shop scheduling intelligent algorithm and its application［M］.Wuhan：Huazhong University of Science and Technology Press，2012.（高亮，張國(guó)輝，王曉娟，等.柔性作業(yè)車(chē)間調(diào)度智能算法及其應(yīng)用［M］.武漢：華中科技大學(xué)出版社，2012.）

［21］Zhang G H，Gao L.Improved genetic algorithm for the flexible job-shop scheduling problem［J］.Journal of Mechanical Engineering，2009，45（7）：145－151.（張國(guó)輝，高亮.改進(jìn)遺傳算法求解柔性作業(yè)車(chē)間規(guī)劃問(wèn)題［J］.機(jī)械工程學(xué)報(bào)，2009，45（7）：145－151.）

Schedule of multiple satellite launch missions in multiple launch centers considering failures

ZHANG Jia-ming，LIU Zhong，SHI Jian-mai，HE Yun-yue
（Science and Technology on Information Systems Engineering Laboratory，National University of Defense Technology，Changsha 410073，China）

It becomes more difficult to schedule launch centers and launch time for multiple satellites in China，with the increase of satellites launch demand and the limited capability of launch centers.A mixed-integer programming model of optimizing multiple launch missions in multiple launch centers is set up，aiming at the least cost and the lowest failure probability.Based on the non-dominated sorting genetic algorithm II（NSGA-II）frame，a multiple objects evolution algorithm is designed and an integer coding method is put forward.A decoding algorithm for launch time scheduling based on the heuristic search is also proposed，and an algorithm to examine and revise the quality of chromosomes is designed.Finally，a small-scale case study with 10missions and a large-scale case study with 30missions are conducted to validate the model and algorithms，basing on the exiting 4satellites launch centers and probable 6types of launch missions.The results indicate the efficiency of the method.

satellite launching；multi-objective optimization；mission planning；integer programming

TP 391

A

10.3969／j.issn.1001-506X.2015.08.14

張家銘（1982－），男，博士研究生，主要研究方向?yàn)槿蝿?wù)規(guī)劃、設(shè)施選址、計(jì)劃系統(tǒng)技術(shù)。

E-mail：zjm08091018＠163.com

劉 忠（1968－），男，教授，博士研究生導(dǎo)師，博士，主要研究方向?yàn)閺?fù)雜人機(jī)組織、指揮控制組織、組織行為過(guò)程、組織效能。

E-mail：phillipliu＠263.net

石建邁（1980－），男，講師，博士，主要研究方向?yàn)槿蝿?wù)規(guī)劃、設(shè)施選址、閉環(huán)供應(yīng)鏈。

E-mail：jianmaishi＠gmail.com

賀云岳（1991－），男，碩士研究生，主要研究方向?yàn)槿蝿?wù)規(guī)劃、設(shè)施選址、閉環(huán)供應(yīng)鏈。

E-mail：heyunyue09＠163.com

1001－506X201508－1803－07

網(wǎng)址：www.sys－ele.com

2014－08－15；

2014－12－07；網(wǎng)絡(luò)優(yōu)先出版日期：2015－03－17。

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

國(guó)家自然科學(xué)基金（70771109，71201169）資助課題