多模式資源受限項目調度問題的雙目標優化

顧 坤， 徐 哲

（北京航空航天大學經濟管理學院，北京 100191）

?

多模式資源受限項目調度問題的雙目標優化

顧 坤， 徐 哲

（北京航空航天大學經濟管理學院，北京 100191）

摘 要：除了追求項目工期最短，減少資源需求量波動也是項目管理者需要考慮的問題，但在實際項目執行時，追求較均衡的資源需求量則有可能導致項目延期，因此需要進行項目工期和資源均衡程度的權衡。綜合考慮資源的多樣性與活動的多執行模式，以項目工期和資源均衡為優化目標，建立多模式項目調度問題的雙目標優化模型。提出一種基于非支配排序遺傳算法的雙目標混合遺傳算法來求解問題的帕累托最優解，在算法中設計違背約束的懲罰方法和可行解的篩選過程。通過算例分析驗證模型與算法的有效性，并分析網絡參數和資源強度對帕累托解集的影響，說明求解帕累托解集的必要性，為項目管理者確定項目調度方案提供決策依據。

關鍵詞：資源受限項目調度；多模式；雙目標優化；資源均衡；遺傳算法

本文信息：顧 坤，徐 哲.多模式資源受限項目調度問題的雙目標優化［J］.石家莊鐵道大學學報：社會科學版，2016，10（1）：6－14.

項目調度是在滿足活動優先關系約束、資源約束及其它項目需求的基礎上，為項目中的每個活動確定開始時間，形成基線進度計劃，以滿足項目的某些績效指標（如最小化項目工期、均衡資源利用等）。經典的資源受限項目調度問題（Resource－Constrained Project Scheduling Problem，RCPSP）已經被證明是NP難問題，并得到了廣泛深入的研究［1］，其主要工作包括項目進度計劃的制定和資源的安排［2］，每個活動具有單一的工期和資源需求量。一般可以通過增加活動的資源使用量以縮短活動工期，從而形成不同的資源量與工期組合，這就產生了多模式資源受限項目調度問題（Multi－mode Resource－Constrained Project Scheduling Problem，MRCPSP）［3］，其中活動的每種執行模式對應特定的工期和資源需求量組合。目前，MRCPSP研究的主要是在資源及優先關系約束下，求解得到每個活動的執行模式和開始時間以使得項目工期最短［4］。

項目管理者在優化項目工期的同時，盡量避免造成可更新資源（如人力、大型機器、設備等）的需求量出現“高峰”和“低谷”。因此，有時還會要求項目在滿足活動優先關系和項目工期約束條件下，在一定時間內合理安排每個活動的開工時間，最小化資源使用量的變異，使資源高效均衡利用，即資源均衡問題（Resource Leveling Problem，RLP）。

在資源均衡問題中，多數研究假設不存在資源約束，文獻［5］和文獻［6］在不考慮資源約束及給定項目截止日期的情形下，最小化資源使用量與均值的方差；文獻［5］采用整數線性規劃求解RLP，但是求解時間較長；文獻［6］借助非連續動態規劃成功解決小規模RLP；文獻［7］研究存在截止期限的多模式資源受限項目調度資源均衡問題，提出一種基于分支定價的啟發式算法；文獻［8］提出了一個基于時間窗的分支定界算法，該算法的核心思想是巧妙枚舉活動的可行開始時間；與文獻［8］不同，文獻［9］的分支定界算法是建立在枚舉準穩進度計劃的基礎上。針對大規模問題，許多研究開始聚焦于啟發式算法，文獻［10］提出了一個基于優先權的啟發式算法和一個禁忌搜索算法；文獻［11］設計了基于種群的迭代貪婪搜索算法，并通過計算實驗證明其算法可以有效求解含有多達1000個活動的項目資源均衡問題；文獻［12］研究了通過活動分裂來實現資源均衡，并實現了一個求解資源均衡問題的遺傳算法。

此外，在多目標優化研究中，資源均衡也是優化的目標之一。文獻［13］研究了資源受限情況下資源均衡和凈現值雙目標優化問題，設計分支定界算法對多種資源進行優化；文獻［14］中，定義成本由活動不同模式產生的直接成本和與項目工期有關的間接成本兩部分組成，繼而研究了多模式資源受限下的離散時間／成本權衡問題（Multimode Resource Constrained Discrete Time／Cost Trade－off Problem，MRC－DTCTP），設計了遺傳算法對問題進行求解；文獻［15］在可更新資源和活動優先關系約束下研究了MRC－DTCTP，同時對項目工期、成本及資源均衡三個目標進行優化；文獻［16］和［17］都研究了模糊多目標“時間－成本－資源”優化問題，優化了時間、成本和資源均衡三個目標，使用模糊集理論對不確定的活動工期參數建模，分別采用NSGA－II算法和混合遺傳－粒子群算法來獲取基線進度計劃。

基于上述分析可以看出，對多模式資源受限項目調度問題的RLP研究較少，已有研究主要以可更新資源不受限或受限為基礎，較少考慮不可更新資源約束。成本作為一種特殊的不可更新資源，在實際項目開始之前，管理者往往對成本有大概的估計，即項目預算，因此需對項目成本進行單獨考慮。本文在綜合考慮可更新資源，不可更新資源以及總成本約束的條件下對多模式項目調度問題進行研究，同時優化項目工期和資源均衡水平。首先對所研究的問題進行數學描述，建立成本約束下的多模式資源受限項目調度問題的雙目標優化模型，然后，設計改進的雙目標混合遺傳算法并對算例進行求解，驗證模型與算法的有效性，最后通過算例實驗，給出深入的計算實驗分析與結果。

一、問題描述

本文采用節點式（activity－on－node，AON）項目網絡圖，活動有多種執行模式，不同模式對應不同的工期、成本及資源需求量組合，具體參數描述如表1。項目決策者綜合權衡項目工期和資源均衡程度，在滿足優先關系、可更新資源、不可更新資源及成本約束的條件下，以項目工期和資源正向偏差的最小化為目標，為每個活動選擇一個執行模式，安排各活動的開始時間，即求解多模式資源受限項目調度問題的帕累托最優集。

二、數學模型

本文所研究的調度問題有兩個優化目標：第一個目標是最小化項目工期，即最后一個活動的完工時間；第二個目標是可更新資源的均衡水平，該指標采用可更新資源每個時段的實際使用量與均值的正向偏差的加權和進行衡量，該目標值越小越好。例如，人力資源作為典型的可更新資源，項目管理者在規劃時應避免加班情況出現，而適當的閑暇相對可以接受，所以目標函數采用對正的偏差進行懲罰，更符合實際。

建立的項目調度模型如下：

式（1）表示最小化項目工期；式（2）表示資源均衡的目標函數，rk（t）是可更新資源k在時段的實際使用量；式（3）確保了每個活動在執行時只能采用一種執行模式；式（4）表示活動間的優先關系約束；式（5）意味著每種可更新資源在每個時段的需求量不能超過其可用量，其中At代表時段內正在進行的活動集合；式（6）表示不可更新資源的可用量有限；式（7）是項目成本約束；式（8）為活動模式選擇變量，活動j以模式m執行，則xjm＝1，否則xjm＝0。

表1 參數定義及說明

三、雙目標混合遺傳算法

本文研究多模式資源受限項目調度的雙目標優化問題，采用非支配排序遺傳算法NSGA－Ⅱ對上述模型進行求解。

本文設計的算法框架如圖1所示，首先，隨機產生可行解作為初始種群以保證初始解的優良性，然后，在確定了各種資源及成本的可用量條件下，對初始種群執行遺傳操作和非支配排序直到達到最大進化代數；最后，對所得解集進行篩選。

（一）解的編碼及解碼方式

在算法中，由滿足緊前關系的活動列表鏈和模式列表鏈相結合的方式對染色體進行編碼，活動列表鏈和模式列表鏈一一對應，如圖2，項目網絡中有6個活動，第一行表示染色體的活動執行順序，第二行為各活動對應的執行模式。依據串行調度生成機制對各個染色體進行解碼，在同時滿足可更新資源約束和緊前關系約束的條件下，確定各個活動的最早開工時間，生成可行的調度計劃，從而得到染色體所對應的兩個適應值：項目工期和可更新資源使用量正向偏差加權和。

圖1 雙目標混合遺傳算法流程圖

圖2 雙鏈染色體結構示意圖

（二）初始種群

隨機抽取滿足緊前關系約束的活動列表和模式列表組成個體，計算其不可更新資源使用量及成本，如果滿足約束，則將該個體放入初始種群，直至初始種群規模達到pop。

（三）遺傳算子

1.選擇算子

通過非支配排序，得到各個染色體的位次和擁擠距離，根據偏序關系定義對種群進行選擇操作，即如果兩個個體的非支配排序不同，取位次較小的個體；如果兩個個體在同一級，取周圍較不擁擠的個體。

對于每個個體p都設有以下兩個參數np和sp。其中np為在種群中支配個體p的個體的數量，sp為被個體p所支配的解個體的集合。據此對種群中的個體進行非支配排序，從而將種群劃分為N個互不相交的非支配邊界集｛F1，F2，…，FN｝。若p∈Fa，則個體p的位次為a；對同一個位次的個體按目標函數進行升序排列，計算p的擁擠距離，有

式中，Or（p＋1）和Or（p－1）分別為與p的目標函數值相鄰的兩個個體所對應的目標函數值，Omaxr和Ominr分別為屬于Fa的所有個體的第r個目標函數的最大值和最小值。

每次遺傳迭代后，將子代種群與父代合并，新種群大小為2pop，按上述方法選取靠前的pop個個體。

2.交叉和變異

在遺傳操作中，親代染色體都有一定概率發生交叉，交叉由兩條鏈分別進行，其中活動列表鏈采取兩點交叉，模式列表鏈采取單點交叉。

子代個體以一定概率發生變異，對于活動列表的變異，在滿足優先關系的前提下，交換選定活動j和活動j＋1的位置；對于模式列表的變異，隨機選定一個活動，將其執行模式隨機改變。

（四）目標函數值的懲罰

通過遺傳操作之后，需要對子代種群的可行性進行判斷，如果子代個體超出了不可更新資源約束或成本上界，則應減少其進入下一代遺傳的概率。設F（1）j、F（2）j分別為個體j解碼后得到的兩個目標函數值，選取懲罰函數為

式中，F（1）′j為懲罰后的工期值，F（2）′j是對資源均衡函數進行懲罰所得值，即在個體j已有均衡函數值的基礎上增加該代種群均衡函數均值的十分之一。

（五）最終解的篩選

當種群進化到最大代數后，遺傳操作停止，對所得近似解集進行篩選，剔除違背不可更新資源和成本約束的不可行解，得到最終可行解。

四、算法測試

本文實例根據文獻［14］進行改編，項目網絡圖如圖3所示，項目中共包含8個活動，其中活動0和活動7是虛活動，表示項目的開始和結束；活動1至6為實活動，每個活動有2種模式，各模式由活動工期、可更新資源需求量、不可更新資源需求量以及活動的直接成本組成。假設項目的執行只需要一種可更新資源以及一種不可更新資源，可更新資源可用量Rr＝6，不可更新資源可用量Ru＝15，項目預算C＝215，單位時間的間接成本a＝1。

圖3 示例項目的AON網絡圖

采用Matlab實現本文的雙目標混合遺傳算法。設置參數如下：種群規模pop＝200，最大進化代數分別為1、5、10、100，染色體交叉概率0.9，活動列表和模式列表的變異概率均為0.1。

取算法結束時所得100代的2個解作為帕累托最優解，以此作為比較基準，所對應的目標函數值向量分別為［8，2.625］和［9，1.556］。從多樣性看，如圖4所示，當進化代數為1時，得到2個近似解，所對應的目標函數值向量集合為｛［9，2］和［11，1.828］｝。當進化代數為5時，得到2個近似解，所對應的目標函數值向量集合為｛［8，2.625］和［9，1.778］｝，其中包括一個帕累托最優解。從收斂性看，當進化代數為10時，得到全部帕累托最優解集，從第10代至算法結束，最優解集保持穩定。各代對應近似解的調度計劃見圖5。

圖4 種群進化所得解集與帕累托最優集的比較

從計算結果上看，與單目標MRCPSP模型相比，多目標問題會獲得多個帕累托最優解，為項目管理者提供了更多決策空間，并且，每個最優解對應多個調度方案，體現了解的差異性和多樣性。按文獻［2］的模型和算法，僅以工期最短為目標對本算例求解，得到最優項目工期為8。但是，在實際項目管理中，如果項目更偏向于對資源的均衡利用，管理者也可能會采用工期較長、資源更均衡的調度方案。

五、實驗分析

本節通過對隨機生成的算例集合進行分析，驗證算法的有效性。由項目調度問題算例生成器Progen2.0軟件生成具有不同結構的活動網絡，通過對每個算例的參數進行定義生成本文所需要的算例集合。采用資源強度（RS）測度資源稀缺程度，RS越小，表示資源越稀缺；采用網絡復雜度（NC）測度活動網絡的復雜程度，NC越大，表示活動間約束越多。實驗參數設置見表2，指定活動個數N取3個不同的值，NC取2個不同的值，RS取4個不同的值，每種參數組合隨機產生10個算例，從而得到個算例。算法通過Matlab編程實現，實驗參數設置如下：最大進化代數設為50代；種群個數為40；交叉概率為0.8，變異概率為0.1。

圖5 各代對應最優解的活動調度示例

表2 實驗參數設置

（一）考察網絡參數、資源強度對帕累托解個數的影響

對240個算例進行求解，根據活動個數N的取值進行統計歸類，計算帕累托解個數的均值，繪制圖6。考察圖6，可以得出以下結論：①當N增大時，解的個數隨之增大，說明活動數多的項目調度問題具有更多的帕累托解；②NC從1.5到1.8變化時，解的個數略有減少，這說明對于網絡復雜度低的項目，帕累托解的數量會越多；③當RS變化時，解的個數變化沒有明顯的規律性，這是因為，隨著資源強度的RS增大，項目工期會縮短，由此產生新的解，但是，如果新解的資源均衡指標值優于之前的解，則將淘汰一個或多個已有解，因此，解的個數沒有一致的變動趨勢。

圖6 不同參數下所得帕累托解個數的均值

（二）考察資源強度對帕累托解集的影響

在上節中討論了網絡參數對帕累托解數量的影響，發現網絡活動數量（N）越多，網絡復雜度（NC）越低的項目，帕累托解的數量會越多，因此本部分選取N＝30、NC＝1.5的情形考察資源強度RS對帕累托解集的影響。圖7和圖8均給出了算例實驗中NC＝1.5、N＝30組的帕累托解集隨RS變化的散點圖。考察圖7可以看出，當資源強度（RS）增大時，優化目標值更優，這說明資源供應越充足，可以同時獲得工期短，資源均衡水平高的調度計劃，有效地實現了優化調度的目的。考察圖8可以看出，資源強度（RS）依次取1、0.7、0.5、0.3時，帕累托解集逐步向外圍移動，且移動幅度有擴大的趨勢。即當資源供應充足時，RS的適度減少（RS值從1減小到0.7），對優化結果的影響較小；而當資源供應緊張時，此時減小RS （RS值從0.5減小到0.3）會使工期和資源均衡度水平明顯變差。

圖7 NC＝1.5、N＝30時優化結果隨RS變化散點圖

圖8 NC＝1.5、N＝30時，優化結果隨RS變化散點圖

六、結論

綜合考慮資源的多樣性與活動的多執行模式，同時優化項目工期和資源均衡水平，建立了多模式項目調度問題的雙目標優化模型。設計了一種基于非支配排序遺傳算法的雙目標混合遺傳算法求解帕累托最優解，通過算例分析驗證模型與算法的有效性，并測試分析了網絡參數及資源強度對帕累托解集的影響。研究發現，活動數量多、網絡復雜度較低的項目可以獲得更多的帕累托解，即項目決策者有更大的選擇空間；當資源供應充足時，可以同時獲得工期短，資源均衡水平高的調度計劃，有效實現優化調度的目的，而當資源供應緊張時，工期和資源均衡水平的優化結果會明顯變差。

參考文獻：

［1］李明.項目人力資源調度研究綜述［J］.石家莊鐵道大學學報：社會科學版，2015，9（1）：54－60.

［2］頊志芬，王春想.基于項目組合管理理論的研發項目管理流程研究［J］.石家莊鐵道大學學報：社會科學版，2013，7（1）：1－4.

［3］Mori M，Tseng C C.A genetic algorithm for multimode resource constrained project scheduling problem ［J］.European Journal of Operational Research，1997，100（1）：134－141.

［4］Sprecher A，Hartmann S，Drexl A.An exact algorithm for project scheduling with multiple modes［J］.OR Spektrum，1997，19（3）：195－203.

［5］K.A H，E.B J.Integrated project task and manpower scheduling［J］.IIE Transactions.1997，29（9）：711－717.

［6］Coughlan E T，Lübbecke M E，Schulz J.A branchand－price algorithm for multi－mode resource leveling ［M］.Experimental Algorithms.Springer Berlin Heidelberg，2010：226－238.

［7］Neumann K，Zimmermann J.Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints［J］.European Journal of Operational Research，2000，127（2）：425－443.

［8］Gather T，Zimmermann J，Bartels J H.Exact methods for the resource leveling problem［J］.Journal of Scheduling，2011，14（6）：557－569.

［9］Neumann K，Zimmermann J.Resource levelling for projects with schedule－dependent time windows［J］.European Journal of Operational Research，1999，117 （3）：591－605.

［10］Ballestín F.When it is worthwhile to work with the stochastic RCPSP［J］.Journal of Scheduling，2007，10（3）：153－166.

［11］Hossein Hashemi Doulabi S，Seifi A，Shariat S Y.Efficient hybrid genetic algorithm for resource leveling via activity splitting［J］.Journal of Construction Engineering and Management，2010，137（2）：137－146.

［12］Neumann K，Zimmermann J.Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints［J］.European Journal of Operational Research，2000，127（2）：425－443.

［13］Peng W L，Wang C G.A multi－mode resource－constrained discrete time－cost tradeoff problem and its genetic algorithm based solution［J］.International Journal of Project Management，2009，27（6）：600－609.

［14］Ghoddousi P，Eshtehardian E，Jooybanpour S，et al.Multi－mode resource－constrained discrete time－costresource optimization in project scheduling using nondominated sorting genetic algorithm［J］.Automation in construction，2013，30：216－227.

［15］Zahraie B，Tavakolan M.Stochastic time－cost－resource utilization optimization using non－dominated sorting genetic algorithm and discrete fuzzy sets［J］.Journal of Construction Engineering and Manage－ment，2009，135（11）：1162－1171.

［16］Ashuri B，Tavakolan M.Fuzzy enabled hybrid genetic algorithm–particle swarm optimization approach to solve TCRO problems in construction project planning［J］.Journal of Construction Engineering and Management，2011，138（9）：1065－1074.

［17］Drezet L E，Billaut J C.A project scheduling problem with labor constraints and time－dependent activities requirements［J］.International Journal of Production Economics.2008，112（1）：217－225.

Bi－objective Optimization for the Multi－mode Resource－constrained Project Scheduling Problem

GU Kun，XU Zhe
（School of Economics and Management，Beihang University，Beijing，100191，China）

Abstract：In addition to the pursuit of the shortest project duration，reducing the fluctuation of resources demand is the problem mostly needed to be considered by project managers as well.During the actual implement of the project，the arrangement of a relatively balanced resources demand will probably lead to the delay of projects，thus the duration of project and the equilibrium level of resources need to be balanced.Concerning the diversity of resources and the verified execution mode of activities，aiming at the optimization of project duration and resource leveling，an optimized model of multimode project scheduling problem should be established.A double objective hybrid genetic algorithm is proposed based on the non－dominated sorting genetic algorithm to get the Pareto optimal solution of the problem.In the algorithm，the methods of punishment for violating the constraints and the filtering of feasible solution will be designed.The validity of the mode and algorithm will be testified by case operators，and case test will be carried out to analyze the influence of network parameters and resource intensity on Pareto solution sets，thus the necessity of solving the Pareto solution sets will be explained，which will provide the decision making basis for the project managers to determine the scheduling program for project.

Key words：resource－constrained project scheduling，multi－mode，bi－objective optimization，resources leveling，genetic algorithms

基金項目：國家自然科學基金（71271019，71571005）；河北省社會科學基金（HB14GL023）；河北省高等學校科學技術研究項目（QN2014035）。

作者簡介：顧 坤（1990－），男，碩士研究生，研究方向：項目管理與調度。

收稿日期：2015－11－09

文章編號：2095－0365（2016）01－0006－09

中圖分類號：N945

文獻標識碼：A

DOI：10.13319／j.cnki.sjztddxxbskb.2016.01.02