基于CPLEX的航天試驗項目管理應用

劉盛銘， 馮書興

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

基于CPLEX的航天試驗項目管理應用

劉盛銘1， 馮書興2

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

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

航天試驗; 項目管理；資源受限項目調度

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

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

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

1 多模式資源受限項目調度

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

(1)

(2)

(3)

(4)

(5)

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

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

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

2 求解流程

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

圖1 CPLEX Studio IDE

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

圖2 求解流程

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

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

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

4) 利用OPL建立目標函數，如式(1)所示。

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

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

表1 約束條件的說明

3 實例分析

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

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

圖3 項目網絡結構圖

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

圖4 解的變化情況

圖5 輸出結果

圖6 項目甘特圖

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

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

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

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

4 結論

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

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

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

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

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

[5] 董學軍,邢立寧,陳英武.航天器發射多任務并行調度模型及算法[J].系統工程與電子技術,2013,35(7):1438-1444.

[6] 巴杰,伍書劍.航天型號多項目資源調度方法研究[J].宇航學報,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

(責任編輯: 尚彩娟)

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