基于CPLEX的航天試驗項目管理應(yīng)用

劉盛銘， 馮書興

(1. 裝備學(xué)院研究生管理大隊， 北京 101416； 2. 裝備學(xué)院訓(xùn)練部， 北京 101416)

基于CPLEX的航天試驗項目管理應(yīng)用

劉盛銘1， 馮書興2

(1. 裝備學(xué)院研究生管理大隊， 北京 101416； 2. 裝備學(xué)院訓(xùn)練部， 北京 101416)

針對航天試驗項目管理中存在的多模式資源受限項目調(diào)度問題，首先通過建立數(shù)學(xué)模型進行了描述；然后基于CPLEX軟件平臺設(shè)計了求解流程，并采用優(yōu)化編程語言予以實現(xiàn)；最后通過實例分析驗證了求解方法的有效性，并將結(jié)果制成甘特圖，展現(xiàn)了整個項目的活動時間安排和資源消耗情況，為航天試驗人員進行項目管理和決策提供可靠依據(jù)。

航天試驗; 項目管理；資源受限項目調(diào)度

隨著我國綜合國力的提高，航天事業(yè)蓬勃發(fā)展，航天試驗項目規(guī)模大、綜合性強、不確定因素多的特點越來越突出。作為一項系統(tǒng)工程，航天試驗項目涉及人員、設(shè)備較多，跨越地域較廣，而且對項目活動執(zhí)行的實時性、準(zhǔn)確性和協(xié)同性要求較高，因此加強航天試驗項目管理就顯得尤為重要。

航天試驗項目管理是以航天試驗項目為對象的科學(xué)管理方法，通過對項目活動進行高效率計劃、組織、決策和控制，實現(xiàn)航天試驗項目全過程的動態(tài)管理和試驗項目目標(biāo)的優(yōu)化[1-2]。其中，項目調(diào)度作為項目管理中的一個重要內(nèi)容，近年來不僅受到了航天試驗部門的高度重視，而且還是學(xué)術(shù)研究的熱點?？祵幍萚3]研究了航天測控調(diào)度問題，通過建立0-1整數(shù)規(guī)劃模型并設(shè)計求解的優(yōu)化算法，進而取得問題的理想解，確保航天試驗項目順利完成；蘇青等[4]為解決資源約束下的航天多項目調(diào)度問題，針對建立的數(shù)學(xué)模型提出了一種啟發(fā)式算法，其結(jié)果能夠合理優(yōu)化多項目的資源分配。董學(xué)軍等[5]提出了航天發(fā)射多任務(wù)并行調(diào)度模型，設(shè)計了基于Agent的優(yōu)化算法進行求解；巴杰等[6]針對航天型號多項目調(diào)度中面臨的進度問題，提出了基于遺傳算法的一種求解方法。

以上研究針對航天試驗項目管理中不同類型的調(diào)度問題，其結(jié)果為本文工作提供了重要參考和借鑒，但這些研究沒有考慮到項目活動中可能存在多種執(zhí)行模式的情況。雖然研究中設(shè)計的各種算法在理論上具有較高參考價值，但對于一般項目管理人員，這些算法難以被直接應(yīng)用于實際工作之中?；诖耍P者針對航天試驗項目中的多模式資源受限項目調(diào)度問題，通過現(xiàn)有優(yōu)化軟件平臺設(shè)計簡單實用的求解流程，獲得調(diào)度問題的最終結(jié)果，以期為航天試驗項目管理人員提供參考和借鑒。

1 多模式資源受限項目調(diào)度

為了克服不確定因素的影響，參與航天試驗項目各個活動的試驗人員會針對項目進展準(zhǔn)備多種執(zhí)行方案，如果僅從活動出發(fā)選擇最優(yōu)方案，就可能加大整個項目的資源消耗，從而使試驗資源無法滿足后繼活動的使用要求。因此，試驗人員應(yīng)從項目全局所受到的資源約束出發(fā)，選擇各個活動合適的執(zhí)行方案，從而確保整個項目的順利完成。這就是航天試驗項目管理中的多模式資源受限項目調(diào)度問題(Multi-Mode Resource-Constrained Project Scheduling Problem，MMRCPSP)，它可用如下數(shù)學(xué)模型進行描述[7]：

(1)

(2)

(3)

(4)

(5)

式中：ximt∈{0,1},為決策變量，其中t=1,2,…,T，

其中：式(1)為目標(biāo)函數(shù)，以最小化項目工期為目標(biāo)；式(2)限制活動i只能選擇1種執(zhí)行模式m和1個執(zhí)行開始時刻t；式(3)根據(jù)項目網(wǎng)絡(luò)結(jié)構(gòu)圖A限制活動執(zhí)行開始的時序關(guān)系；式(4)表示在每一時刻t，執(zhí)行中的各個活動可更新資源消耗量之和不會超過其資源總量；式(5)表示在每一時刻t，執(zhí)行中的各個活動不可更新資源消耗量之和不會超過其資源總量。

MMRCPSP是項目管理中的經(jīng)典問題[8-9]，在理論上屬于NP問題，求解困難。近年來，隨著計算機輔助決策技術(shù)在工業(yè)領(lǐng)域的廣泛應(yīng)用，航天試驗人員可借助運籌學(xué)優(yōu)化軟件求解項目調(diào)度問題，這不僅有助于試驗人員把更多精力和時間投入到具體的試驗活動中，而且有利于試驗人員合理安排試驗資源，提高整個試驗項目運行效率。

2 求解流程

CPLEX Studio IDE是一個運用優(yōu)化技術(shù)補充支持重要資源的軟件平臺[10]，如圖1所示。它利用CPLEX優(yōu)化引擎能迅速找到問題模型的解決方案，運行速度快，可以解決現(xiàn)實中許多大規(guī)模調(diào)度問題。

圖1 CPLEX Studio IDE

基于該軟件平臺，設(shè)計問題求解流程如圖2所示，并采用優(yōu)化編程語言(Optimization Programming Language，OPL)對航天試驗項目管理中的MMRCPSP進行建模。

圖2 求解流程

對求解流程各步驟進行如下說明。

2) 將式(1)中的三維決策變量ximt分解為2個interval類型決策變量xtask(iin Task)、xmode(kin Mode)。interval類型的決策變量是OPL為求解調(diào)度問題而引入的變量類型，它包括開始時間、結(jié)束時間等屬性。xtask(iin Task)意味著這是一個數(shù)組型變量，每一元素對應(yīng)著Task里的活動i。

3) 采用OPL的cumulFunction函數(shù)記錄可更新資源消耗量；采用int類型變量記錄不可更新資源消耗量。

4) 利用OPL建立目標(biāo)函數(shù)，如式(1)所示。

5) 式(2)-(5)約束條件采用OPL偽代碼進行表示，其說明如表1所示，相關(guān)符號定義可參考說明1)。

6) 采用OPL腳本語言，可以顯示優(yōu)化計算后的目標(biāo)函數(shù)值，決策變量xmode(kin Mode)被選中模式對應(yīng)的nid、nmid，以及xmode屬性中的開始時間。

表1 約束條件的說明

3 實例分析

為驗證以上求解流程的有效性，以某航天試驗項目為例進行分析。該項目包含52個活動，其網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示，其中：節(jié)點代表活動，活動1、52為虛節(jié)點；箭頭代表時序關(guān)系。該項目每個活動包含3種執(zhí)行模式，活動持續(xù)時間及各種資源的具體信息(局部)如表2所示。

該項目活動模式分配共有350種，盡管量大，但基于CPLEX的求解流程仍可計算出目標(biāo)函數(shù)結(jié)果。在求解的過程中，式(1)解的變化情況如圖4所示。迭代結(jié)束后，采用OPL腳本語言使其結(jié)果在腳本日志中輸出，如圖5所示。采用Project2010將圖5的輸出結(jié)果繪制成項目甘特圖，如圖6所示。

圖3 項目網(wǎng)絡(luò)結(jié)構(gòu)圖

表2 某航天試驗項目的具體信息(局部)

圖4 解的變化情況

圖5 輸出結(jié)果

圖6 項目甘特圖

由圖4可知：求解時間接近2 min，這在實際的項目管理中是可以接受的。

由圖5可知：按照CPLEX計算的活動開始時間進行安排，整個項目的完成時間是25 d。

由圖6可知：各個活動所需要的資源消耗量與資源總量互不沖突，以第1種可更新資源r1為例，其最大資源量均未出現(xiàn)過度分配現(xiàn)象，這一結(jié)果驗證了求解流程是有效的。

若拖動圖6中任何一個活動條狀圖，使該活動的開始時間發(fā)生改變，則會導(dǎo)致資源發(fā)生沖突，因而驗證了25 d是整個項目在多模式資源受限條件下完成的最優(yōu)值。事實上，雖然Project2010具有調(diào)配資源功能，能在資源受限條件下對單模式的項目活動進行時間安排，但它無法解決MMRCPSP。而利用CPLEX Studio IDE對該問題進行求解，并將結(jié)果在Project2010中制成甘特圖，能夠清楚地展現(xiàn)整個項目的時間安排及每一類型的資源使用情況，從而為航天試驗人員進行項目管理決策提供可靠依據(jù)。

4 結(jié)論

為了在資源受限條件下合理調(diào)度航天試驗項目的各個活動，筆者研究了航天試驗項目管理中的多模式資源受限項目調(diào)度問題。實例分析結(jié)果表明：基于CPLEX軟件平臺設(shè)計的求解流程對處理此類問題是有效的，可為航天試驗項目管理提供參考和依據(jù)；采用優(yōu)化編程語言可方便地對此類問題進行建模和求解，這有助于試驗人員將更多的精力和時間投入到具體的試驗活動中，而無須過分關(guān)注求解問題的算法設(shè)計。

[1] 楊保華.神舟七號飛船項目管理[M].北京:航空工業(yè)出版社,2010:1.

[2] 張育林.航天發(fā)射項目管理[M].北京:國防工業(yè)出版社,2012:1-3.

[3] 康寧,武小悅.航天測控調(diào)度模型及其上界求解算法[J].系統(tǒng)工程理論與實踐,2010,30(9):1695.

[4] 蘇青,楊海成,敬石開,等.多資源約束下航天多項目調(diào)度的啟發(fā)式算法[J].中國空間科學(xué)技術(shù),2009(3):64-70,77.

[5] 董學(xué)軍,邢立寧,陳英武.航天器發(fā)射多任務(wù)并行調(diào)度模型及算法[J].系統(tǒng)工程與電子技術(shù),2013,35(7):1438-1444.

[6] 巴杰,伍書劍.航天型號多項目資源調(diào)度方法研究[J].宇航學(xué)報,2012,33(10):1552-1556.

[7] Erik D, Willy H. Project Scheduling: A Research Handbook [M].New York: Kluwer Academic Publishers, 2002:501-502.

[8] Van Peteghem V, Vanhoucke M. An Experimental Investigation of Metaheuristics for the Multi-mode Resource-constrained Project Scheduling Problem on New Dataset Instances [J]. European Journal of Operational Research, 2014, 235(1): 62-72.

[9] Jan W, Joanna J, Marek M, et al. Project Scheduling with Finite or Infinite Number of Activity Processing Modes: A Survey[J]. European Journal of Operational Research, 2011, 208:177-205.

[10] IBM. IBM ILOG CPLEX Optimization Studio[EB/OL].[2015-02-27]. http://www-01.ibm.com/software/integration/optimization/CPLEX-optimization-studio

(責(zé)任編輯: 尚彩娟)

Application with CPLEX for Project Management of Aerospace Test

LIU Sheng-ming1, FENG Shu-xing2

(1. Department of Graduate Management, Academy of Equipment, Beijing 101416, China； 2. Department of Training, Academy of Equipment, Beijing 101416, China)

Aiming at the multi-mode resource-constrained project scheduling problem in aerospace test project management, a mathematical model is firstly established to give a description. Then, based on CPLEX software, a computation flow is presented and implemented by optimized programming language. Finally, the effectiveness of computation flow is validated through analysis of examples and computation results are made into the Gantt chart to show the project schedule and resource consumption clearly, which provides a reliable basis for project management and decision-making for aerospace testing personnel.

aerospace test; project management; resource-constrained project scheduling

1672-1497(2015)05-0089-05

2015-08-15

軍隊科研計劃項目

劉盛銘(1986-)，男，博士研究生。

V57

A

10.3969/j.issn.1672-1497.2015.05.018