劉盛銘， 馮書興

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

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

劉盛銘1， 馮書興2

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

(5)

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

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

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

2 求解流程

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

圖1 CPLEX Studio IDE

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

圖2 求解流程

對(duì)求解流程各步驟進(jìn)行如下說(shuō)明。

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

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

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

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

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

表1 約束條件的說(shuō)明

3 實(shí)例分析

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

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

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

表2 某航天試驗(yàn)項(xiàng)目的具體信息(局部)

圖4 解的變化情況

圖5 輸出結(jié)果

圖6 項(xiàng)目甘特圖

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

由圖5可知：按照CPLEX計(jì)算的活動(dòng)開始時(shí)間進(jìn)行安排，整個(gè)項(xiàng)目的完成時(shí)間是25 d。

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

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

4 結(jié)論

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

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

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

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

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

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

[6] 巴杰,伍書劍.航天型號(hào)多項(xiàng)目資源調(diào)度方法研究[J].宇航學(xué)報(bào),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

軍隊(duì)科研計(jì)劃項(xiàng)目

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

V57

A

10.3969/j.issn.1672-1497.2015.05.018