資源約束多項目調度問題研究現狀與展望

彭武良, 黃 敏

(1.煙臺大學經濟管理學院,山東 煙臺 264005;2.東北大學信息科學與工程學院,流程工業綜合自動化國家重點實驗室,遼寧 沈陽 110819)

1 引 言

在全球市場競爭的壓力下,傳統單項目管理方法已經難以滿足企業創新和客戶化生產活動需要,多項目管理理論和方法逐步被人們所接納并成為頂尖的熱門問題之一[1].在項目管理實踐中,計劃調度率先發生并處于首要位置,它引領各種項目管理職能的實現,是項目得以實施和完成的前提及依據.半個多世紀以來,基于經典資源約束項目調度問題(resource constrained project scheduling problem,RCPSP)的模型衍生和算法設計一直是項目管理和運籌學領域的研究熱點,對單項目RCPSP 問題進行總體回顧和對RCPSP 特定問題分支進行綜述的文獻[2–6]不斷出現.然而,這些都是針對單項目調度的,迄今為止尚未出現針對多項目調度問題的綜述文獻.

現代項目管理理論將多項目管理劃分為戰略層,策略層和執行層三個層次[1].其中項目組合管理處于戰略層,其主要決策問題是項目投資和項目選擇問題.策略層的項目管理形式一般認為是項目群管理,它對一組項目進行統一協調管理,其核心決策問題是資源配置和粗能力計劃問題[7].而本文所專注的多項目調度問題則處于執行層,它致力于在內部任務邏輯約束和外部有限資源約束的條件下,合理安排任務的開始和完成時間,從而實現多項目總體目標的優化[8].多項目調度問題包含了單項目調度問題,其問題模型更為復雜,計算復雜度也更高.從上世紀末以來,隨著多項目管理技術的廣泛應用和計算機算法的不斷發展,以資源約束多項目調度問題(resource constrained multi-project scheduling problem,RCMPSP)為代表的多項目調度問題逐漸成為學術界的研究熱點,已經形成了兩個清晰的分支: 集中式多項目調度問題(centralized RCMPSP,CRCMPSP)和分散式多項目調度問題(decentralized RCMPSP,DRCMPSP).二者都需要在共享資源約束下對多個并行項目進行調度.但CRCMPSP 將多個獨立的項目組成一個大的項目,由一個多項目負責人基于全局信息對所有項目進行統一調度.而在DRCMPSP 中,每個項目由獨立的項目負責人自行調度,不同項目之間的信息不透明,需要通過某種機制進行共享資源競爭.由于DCRMPSP 問題的提出,使RCMPSP 的研究呈現出諸多新的特征.因此,有必要在現階段對其研究狀態進行系統的總結歸納,夯實進一步深入研究的基礎.本文專注于資源約束多項目調度問題的分析,突出多項目調度問題的特點,從各個維度對CRCMPSP和DRCMPSP 的研究現狀進行梳理,給出資源約束多項目調度問題的完整研究視圖.然后依據研究現狀,分析目前研究中存在的主要問題,指出未來的發展方向,為RCMPSP 的進一步深入研究和推廣應用提供參考.

2 集中式資源約束多項目調度問題

RCMPSP 的基本假設條件是項目之間不存在緊前關系,且不同項目的任務之間也不存在緊前關系.另外,研究人員通常假定多個項目是在一個集中環境下統一進行調度的.因此在DRCMPSP 問題出現之后,人們普遍將其稱為CRCMPSP 問題以示區分.與后來出現的DRCMPSP 相比,多個項目統一調度是CRCMPSP的最顯著特征.

2.1 問題描述

CRCMPSP 與RCPSP 問題相似, 項目內部活動之間存在著緊前關系約束和本地資源約束.因此, 很多RCPSP問題模型的衍生版本,如帶有活動可中斷,工期不確定或多執行模式等特征的RCPSP 問題,大都可以直接應用到CRCMPSP 中,本文不再詳述.CRCMPSP 與RCPSP 的主要不同之處在于: 1)多項目調度除了對每個單項目進行優化之外,更重要的是對多項目共同目標進行優化.2)每個項目除了有本地資源約束之外,更重要的是要在項目之間競爭共享資源.因此,在介紹CRCMPSP 的典型問題模型之后,將從目標函數和資源利用兩個方面對CRCMPSP 問題進行展開說明.

2.1.1 典型問題模型

CRCMPSP 管理多項目集合N,每個項目用p= 1,2,...,|N|表示,p ∈N.各個項目獨立,不存在緊前關系.每個單項目p均可以表示為有向無環圖Gp= (Vp,Ep),Vp為項目p的活動集合,每個活動pj ∈Vp用pj= 1,2,...,|Vp|表示.用Jp代表項目p的結束活動,即Jp=|Vp|.Ep為項目p中的緊前關系約束集合.若(pi,pj)∈Ep,則說明任務pi和pj之間存在緊前關系約束,要求活動pj必須在活動pi完成之后才能開始.活動pj的緊前任務集合表示為Epj.每個項目p有權重wp.全部N個項目共享K種可更新資源,其中第k種資源的供給量為Rk.活動pj對可更新資源k的需求量表示為rpjk.對于項目活動pj,其工期為dpj,開始時間和結束時間分別用spj和fpj表示.設At為多項目中在時間t上所有正在執行的多項目活動集合,典型CRCMPSP 的概念模型可以表示為[9]

其中Dp為每個項目的截止日期,fJp為項目p結束活動Jp的完成時間,即項目p的工期.若項目p不能在截止日期Dp內完成,需要付出拖期懲罰wp(fJp ?Dp).模型(1)最小化多項目拖期懲罰,約束條件(2)表示項目內部各活動之間的緊前關系約束,約束條件(3)限制了在任意時刻,多項目中的所有任務對每種資源的總需求不能超過其供應量.

2.1.2 CRCMPSP 的目標函數

非正規目標函數中包含了一些資源相關的目標函數, 如多項目資源水平, 魯棒性等[17,18].但因為CRCMPSP 網絡結構與單項目網絡相同,所以其目標函數形式也與單項目調度問題大同小異,限于篇幅,不再贅述.對于現金流優化的目標函數,若只計算各個活動的現金流,那么多項目調度與單項目調度也是相同的.而Chiu 等[19]的處理方式則深入考慮了多項目調度的特點,構建了一種新的現金流優化模型,即

其中NCFpj為活動pj完成時的凈現值,α為折扣率.CIFp為項目p完成時的現金流入.當項目拖期時,即fJp >Di,則Up=1,否則Up=0.Bp為項目提前完成時的單位時間獎勵,Pp為項目拖期完成時的單位時間懲罰.式中的第一項與單項目凈現值計算法方式相同,對每個活動計算折扣現金流并求和.式中第二項統計每個項目的凈現值,第三項為多項目提前獎勵,第四項為多項目拖期懲罰.該目標函數同時考慮了單項目和多項目的凈現值,并且加入了每個項目延期懲罰和提前獎勵,具有鮮明的多項目特征.

總之,與RCPSP 相比,CRCMPSP 問題的目標函數通常不是簡單的多項目總工期,往往需要考慮每個單項目的調度目標,對單項目調度目標進行加權.項目權重可以直接確定,如式(1).也可以通過不同項目的不同拖期懲罰,或不同凈現值來間接確定,如式(4).

2.1.3 CRCMPSP中的資源問題

CRCMPSP 的基本資源類型本質上與單項目RCPSP 相同,可分為三類: 可更新資源,不可更新資源和多重約束資源.在多項目調度問題中,又進一步分成共享資源和私有資源.但現有的研究通常只考慮研究價值比較高的共享可更新資源約束,僅有少數文獻考慮不可更新資源約束[20,21].近年來,CRCMPSP 基于資源利用的新進展主要體現在柔性資源利用和考慮資源轉移時間兩個方面.

在項目調度問題中,人力資源往往會被特殊對待.其原因是人具有學習能力,能夠在一個項目中勝任不同工種.這種能夠勝任不同工種的人力資源被定義為多技能資源或柔性資源.而考慮多技能資源約束的項目調度問題稱為柔性資源約束項目調度問題或多技能資源約束項目調度問題.Kazemipoor[16]對項目群調度進行研究,給出了一種多技能資源約束多項目調度問題,并提出了基于差分進化的求解算法.Chen 等[22]針對軟件開發多項目管理的需求,構建了一個多技能共享資源池,綜合考慮員工學習曲線,產品開發時間和成本,提出了一個多技能資源約束多項目調度問題,并采用快速非支配算法進行求解.事實上很多設備或加工中心也具有柔性,比如某種加工中心,既能用它進行車削加工,也能進行銑削加工,這個設備就可以被認為是柔性的[23].

另外,在多項目環境下,共享資源在項目之間乃至任務之間進行轉移時,往往會需要額外的時間和成本.考慮到這種情況,Krger[12]提出了帶有資源傳遞時間成本的多項目調度問題.若只考慮資源傳遞時間,需要在問題模型中增加如下約束條件,即

其中為項目m中的活動n作為資源傳輸方將資源k傳遞給項目p中的活動j所需的時間.為0-1 變量,=1 表示項目m中的活動n可以將資源k傳遞給項目p中的活動j,否則,=0.T為多項目工期.當=0 時,該式則構不成約束.

活動所需的資源不一定完全從緊前活動中獲取,在特定時刻,需要決策活動所需資源可有多種來源: 1)從共享資源池中選取閑置資源,不需要等待,可以提前到位.2)從緊前活動中獲取,需要等待.3)從其它活動中獲取,需要等待.其中2)和3)的情況都需要滿足式(5)的約束條件.Krger[20]深入研究了資源的多種轉移方式,最復雜的情形是一種資源的轉移會需要其它配套資源的占用,且同時產生資源轉移時間和轉移成本.

CRCMPSP 中多技能資源的使用與RCPSP 問題相同,而資源轉移則是多項目調度的一種典型應用場景,更能夠體現多項目調度的特點.因此,在調度目標和約束條件中考慮資源轉移是當前CRCMPSP 問題研究中一個比較活躍的方向[24].

2.2 CRCMPSP 的求解算法

CRCMPSP 問題的求解算法可分為精確算法和近似算法兩類.最早對RCMPSP 問題的求解是從精確算法開始的,如0-1 規劃法[11]和整數規劃法[25,26]等.RCMPSP 是強NP-Hard 問題,采用精確算法無法在多項式時間內對RCMPSP 的實際問題進行求解,只能借助于近似算法.近似算法本質上都是確定項目活動的優先值,發生資源競爭時,優先值較高的那個(或那些)活動能夠率先被調度.近似算法一般都分為兩個階段: 第一個階段確定活動的優先值或優先級排序.第二個階段基于活動優先值生成調度計劃.

近似算法又分為兩種,一種是基于優先級規則的啟發式算法,一種是元啟發式算法或智能算法.二者的區別體現在第一個階段,基于優先級規則的啟發式算法采用某種啟發式規則進行計算確定每個活動的優先級值,而元啟發式算法致力于通過某種進化策略反復搜索得到最優的活動優先級排序.在近似算法的第二個階段, 多項目與單項目的調度計劃生成方法相同,主要包括串行調度生成算法(serial schedule generation scheme,SSGS)和并行調度生成算法(parallel schedule generation scheme,PSGS)[27].

既有的研究表明,SGSS 生成的是積極計劃,PGSS 生成的是非延遲計劃.非延遲計劃是積極計劃的子集, 有可能會錯過最優解.因此, 在RCPSP 中, 多數研究使用的是SGSS.但Chaurasia 等[28]通過測試發現,SSGS 適合于活動數目較少的小規模項目,而PSGS 則在大規模項目中效率更高.CRCMPSP 與RCPSP 調度計劃生成方法相同,但它包含了更多的活動,整體規模更大,因此PSGS 應該更具優勢.

2.2.1 基于優先級規則的啟發式算法

基于優先級規則的啟發式算法是CRCMPSP 的主要近似算法.CRCMPSP 的很多優先級規則源于單項目RCPSP,形式上非常接近,但在性能上則有差別.既有研究表明,很多在單項目調度中比較高效的優先級規則在多項目環境下則表現較差,如最短任務優先(shortest operation first,SOF)[29].

在形式上與單項目RCPSP 問題完全相同的優先級規則很多.典型的是以關鍵路徑時間為參數進行計算的優先級規則,如最小最晚完成時間MINLFT,最小最晚開始時間MINLST,最小最早開始時間MINEST,最小時差優先MINSLK 等都屬于這一類.還有基于活動工期優先級規則,如最短任務優先SOF,最長任務優先MOF 等.基于多項目網絡結構的優先級規則主要有最多后續任務MTS,最多緊后任務MCS.基于活動資源使用量構建的優先級規則主要有最小總工作量MINTWK,最大工作量MAXTWK 等[30].

還有一部分優先級規則針對了多項目調度的特點, 考慮活動隸屬不同項目的情況, 如最短項目優先SASP = Min CPLp+dpj, 最長項目優先LALP = Max CPLp+dpj, 其中CPLp為項目p的關鍵路徑長度.另外, 考慮到多項目網絡活動較多, 單一規則容易計算得出相同優先級值的多個活動, 所以人們提出采用兩種優先級規則組合計算活動優先值, 如最大工作量與最小最晚開始時間TWKLST =MAXTWK+MINLFT[14],最大工作量與最小最早開始時間TWKEST=MAXTWK+MINLFT[14].

很多文獻對各種優先級規則的性能進行測試分析,但因為調度目標和所選算例的不同,性能測試結果也不盡相同.Kurtulus 的測試結果表明MAXTWK 和SASP 是目標函數為平均項目延遲時的最佳算法[30].Lova 等[14]的測試支持了這個結論,但同時指出若以多項目工期為調度目標,則MINLFT 表現最好.在壽涌毅的隨機抽樣算法中,MINSLK 是最高效的優先級規則[31].Browning 等[29]選用了在不同網絡結構和資源強度的12 320 組多項目,對眾多優先級規則進行了系統的測試比較,其結論是MINWCS 和TWK-LST 性能表現最好.

2.2.2 元啟發式算法

元啟發式算法在搜索最優活動優先級排序的時候,通常不使用活動工期,活動資源和多項目網絡結構等信息.多數針對單項目RCPSP 問題的元啟發式算法均可直接應用在CRCMPSP 中.就編碼方式來說,在元啟發式算法中,針對單項目RCPSP 的典型編碼結構主要包括優先值編碼和活動列表編碼兩種.其中優先值編碼直接給出每個活動的優先值,而活動列表給出的是滿足緊前關系約束的活動優先級排序.這兩種編碼方式均可直接應用到CRCMPSP 中,且各種進化或搜索策略也非常接近[18,32,33].

多項目調度與單項目調度相比有其特殊性,其項目活動數目較多,且每個項目往往有自己的工期底線,拖期會產生懲罰.Goncalves 等[34]考慮了這種特殊性,在其所提出的遺傳算法中設計了一種新的編碼結構如圖1,其中n為活動數目,m為項目數.該編碼結構分為三段: 第一段用于確定每個活動的優先值,與單項目調度問題的處理方式相同.第二段考慮到多項目中活動比較多,因此采用設置延遲時間,控制在并行調度的每次迭代中,只選擇延遲時間較小的活動進行調度.第三段用于控制每個項目的發布時間.該算法基于PSGS 進行解碼,通過遺傳算法進化搜索最優解.文獻[35]考慮了多個項目優先級的不同,組合基于活動列表和項目優先級值進行編碼,采用SSGS 進行解碼,通過混合遺傳算法搜索多項目調度問題的最優解.

圖1 編碼結構Fig.1 Encoding of chromosome

近年來,國內學者對智能優化算法在CRCMPSP 的應用研究陸續出現,典型如遺傳算法[32,35],蟻群算法[36]和粒子群算法[37]等.另外, 人們嘗試將各種智能算法應用到CRCMPSP 多目標優化問題的求解中.如Rong 等[38]針對IT 產品開發項目的特點,構建了以成本,時間和技能增長為優化目標的三目標問題模型,并采用快速非支配遺傳算法對該問題進行求解.

總之,目前國內外在CRCMPSP 的元啟發式算法研究上與單項目RCPSP 相比還不夠系統.既有的研究通常參照RCPSP 的算法結構,然后針對多項目調度目標的特點,在編碼方式和其它算子上考慮多項目調度的特點.但CRCMPSP 的元啟發式算法研究未能像RCPSP 問題那樣形成廣泛推崇的典型編碼方式和搜索策略.

2.3 關鍵鏈方法在CRCMPSP 上的應用

關鍵鏈項目管理考慮了人的行為因素對項目進度計劃的影響,在項目管理中體現了科學和藝術的結合,被認為是項目管理技術的一個重要進展.近年來,關鍵鏈方法在CRCMPSP 上的應用研究開始出現[18,39].多項目關鍵鏈調度沿襲了單項目關鍵鏈調度的三種緩沖類型: 輸入緩沖,資源緩沖和項目緩沖.其中輸入緩沖的設置與單項目完全相同,且設置在單項目內部,項目緩沖設置在每個項目工期結束處.此外多項目調度還需要設置多項目共同的多項目緩沖,設置在多項目工期結束處.多項目調度中的資源緩沖則分為兩類: 一類是基于本地資源設置的內部資源緩沖.另一類是基于共享資源設置的能力緩沖,即項目間資源緩沖.出于簡化的考慮,通常并不設置全部所有類型的緩沖.在多項目關鍵鏈調度中,多項目緩沖和能力緩沖是多項目關鍵鏈調度區別于單項目關鍵鏈調度的兩個主要特征,應該著重予以考慮.李俊亭等[40]提出了一種考慮了多項目緩沖和能力緩沖的關鍵鏈多項目調度問題模型,以盡量去除活動的自由時間和減少資源在項目間轉移為目標進行優化,設計了基于優先級規則的啟發式算法.

關鍵鏈方法本身是一種樸素的管理思想,但對其優化調度則是一個復雜的難題.其原因在于各種緩沖區的嵌入會打亂原有的調度導致調度計劃不可行[41].在單項目的項目緩沖,輸入緩沖和資源緩沖的基礎上,多項目增加了項目之間的能力緩沖,進一步提升了優化調度的難度.因此在現有的研究中,都存在一定程度的簡化.比如在文獻[18,21]的研究中,僅僅考慮了項目緩沖和輸入緩沖,未考慮更為復雜的資源緩沖.文獻[40]突出了能力緩沖在多項目調度中的功能,將能力緩沖與關鍵活動合并,方便了資源沖突解決,但沒有說明輸入緩沖的處理辦法.

基于既有的文獻分析可見,目前的多項目關鍵鏈調度還處于探索階段,缺乏比較完善的優化調度路線,更缺乏嚴謹的形式化數學模型.總之,基于多項目的關鍵鏈管理方法還不完善[5].在這種情況下,如何突出能力緩沖的關鍵地位,對多項目關鍵鏈調度問題的模型和算法進行系統的研究,將是CRCMPSP 的一個重要發展方向.

2.4 多模式資源約束多項目調度問題

如果在CRCMPSP中,允許考慮項目活動可以按照不同的執行模式執行,則該問題就演變成了多模式資源約束多項目調度問題(multi-mode resource constrained multiple project scheduling problem, MRCMPSP).該問題是CRCMPSP 和MRCPSP(multi-mode resource constrained project scheduling problem)的結合,功能更為強大, 其優化調度的難度也相應較高.由于該問題的代表性和求解難度, MISTA 2013 挑戰賽中專門將其作為競賽題目,吸引了眾多算法參賽,包括很多啟發式算法和進化算法[42].Wauters 等對MISTA 2013 挑戰賽中MRCMPSP 的多種算法進行了分析和總結, 為后續研究奠定了基礎[42].在MISTA 2013 挑戰賽中,Asta 等[43]的蒙特卡羅超啟發式算法表現最好.其后,Asta 等對該算法進行了系統的完善,并對算法的關鍵環節, 比如蒙特卡羅樹, 超啟發式和更寬廣的鄰域搜索等進行了深入的討論.Geiger[44]應用多線程技術對原MISTA 2013 挑戰賽中排名第二的變鄰域搜索算法進行了改進,進一步提高了算法的性能.MISTA 2013挑戰賽中排名第三的算法是Toffolo 的整數規劃算法[45].

MRCMPSP 因其求解難度逐漸引起了算法研究領域的關注,但在既有的研究成果中,各種典型進化算法的研究還不夠充分.如何結合問題的特點,充分發揮各種進化策略的優勢,結合各種優先級規則,提高算法的求解效率和質量將是MRCMPSP 研究的一個熱點問題.

2.5 CRCMPSP 問題庫

鑒于CRCMPSP 問題與單項目RCPSP 問題的相似性,很多學者在研究CRCMPSP 問題算法時,采用單項目RCPSP 問題庫(PSPLib)的單項目問題實例進行組合,形成多項目實例[19,34].文獻[14]基于多項目資源特征參數生成多項目調度問題實例,但沒有考慮到多項目網絡結構特征和項目權重.文獻[29]全面考慮多項目的各種特征參數,構建了一種全新的多項目問題庫.該問題庫包含了12 320 個問題,每個問題包含3 個項目,每個項目包含20 個活動,使用4 種共享資源,每個項目都采用設計結構矩陣表示.該問題庫公開在網絡上(http://sbuweb.tcu.edu/tbrowning/RCMPSPinstances.htm),是到目前為止針對CRCMPSP 問題研究最全面的公開問題庫.

3 分散式資源約束多項目調度問題

CRCMPSP 雖然也考慮了單項目的截止日期或項目之間的資源轉移,但仍然在很大程度上忽略了單個項目的自身訴求.實際上,在項目型組織結構下,單項目負責人對所負責的項目擁有很大的自主權,且多項目往往會在分布式環境下執行.針對這種情況,Confessore 等[46]在CRCMPSP 研究的基礎上,進一步提出了一種新的多項目調度形式—分散式資源約束多項目調度問題.DRCMPSP 呈現出顯著的新特點,且具有明確的實用背景.因此自提出以來,被引起廣泛關注,出現了很多對其進行介紹的文章[47?49].DRCMPSP 的最顯著特征是要求多項目中的每個項目各自獨立進行調度,其資源處理方式和調度過程與CRCMPSP 明顯不同.

3.1 問題描述

在目前的研究中,人們對DRCMPSP 的定性描述較多,形式化建模較少.本文從DRCMPSP 的資源處理方式和決策機制入手對其進行系統的分析,然后歸納出DRCMPSP 的優化問題模型.

3.1.1 資源處理方式

DRCMPSP 更加明確地界定了本地資源和全局資源,從資源從屬關系上把資源劃分為三種類型: 1)本地資源,僅供特定單項目使用的私有資源,不能被其它項目分享.2)全局共享資源,隸屬于所有多項目,屬于全局資源,在多項目執行期間,可以在任意時段分配給任意項目.3)全局專屬資源,隸屬于所有多項目,屬于全局資源,但每個單位資源一旦分配給某個項目,便只能在多項目周期內被該項目獨占.

雖然CRCMPSP 中也區分本地資源和全局資源,但在既有的研究中,都只關注共享資源,這通常也是集中式多項目執行的實際情況.但在DRCMPSP 中則不同,各個項目之間都有自己的本地資源,僅競爭有限的全局共享資源.文獻[50,51]對基于專屬資源利用的分散式多項目調度進行了研究,構建了問題模型并提出了相應的近似算法.但在目前大多數DRCMPSP 研究中,都沒有考慮全局專屬資源的情況.因此在后續對DRCMPSP 研究現狀的分析中,將只針對使用本地資源和全局共享資源的多項目場景.

3.1.2 決策機制

DRCMPSP 決策過程是一種分布式決策過程,其決策機制至少分為兩層: 1)本地決策.每個項目均由項目負責人自行調度,決策所需的信息是內部項目私有數據,不同項目負責人無法知曉其它項目的決策情況.2)全局決策.全局決策的目標是對共享資源在多個項目之間的使用進行分配.因為每個項目都單獨進行調度,在共享資源利用上會發生沖突.共享資源協調機制會根據多項目調度的總體目標,平衡共享資源在多個項目不同時段的使用情況.

Wang 等[47]按決策順序定義了三種決策模型: 1)從上向下,即先進行全局資源分配,然后進行本地決策.2)從下向上,也就是先進行本地決策,后進行全局決策.3)平等協商,各個項目自行調度,相互協商共享資源的使用.需要指出的是,在DRCMPSP 中,無論是按照從上到下還是從下到上的順序進行決策,都不可能一蹴而就,均需要反復迭代才能完成共享資源的最優分配.在平等協商模型中,若各個項目之間信息不透明,一對一或一對多進行協商對算法的復雜度要求太高.從目前的研究來看,主要以從上向下和從下向上兩種決策模型為主,二者均是典型的雙層計劃調度方式,也比較符合大多數多項目管理的實際情況.

3.1.3 問題模型

到目前為止,各種文獻中關于DRCMPSP 的描述還沒有形成一個統一框架.本文從DRCMPSP 的定義出發,基于DRCMPSP 的資源處理方式和決策機制,給出基本的DRCMPSP 問題的概念模型,該模型分為全局決策層式(6)～式(11)和本地決策層式(12)～式(16),即

其中式(6)為多項目目標函數,基于單項目調度結果及其權重wp計算.式(7)為全局共享資源約束,要求每種資源k在每個時刻t分配給各個項目的資源量不能超過該資源的總量,其中G為全局共享資源集合,為全局共享資源k的供應量,為在t時刻分配給項目p的共享資源k的數量.式(8)為全局專屬資源約束,要求分配給所有項目的全局專屬資源量之和不能超過該資源的總量.其中D為全局專屬資源集合,為全局專屬資源k的供應量,為分配給項目p的全局專屬資源數量.等式約束(9)中,的取值為單項目調度層每個項目p的調度結果.式(10)為每個項目的取值,仍然依賴于單項目調度層每個項目p的調度結果,其中Apt意義同前,為項目p在t時刻正在執行的活動集合.為活動j對全局共享資源k的需求,k∈G.等式(11)為每個項目的取值,依賴于單項目調度層每個項目p的調度結果,為活動j對全局專屬資源k的需求,?k∈D.

在本地決策層,式(12)為單項目調度目標函數.式(13)為單項目p中活動的緊前關系約束,spj為項目p中活動j的開始時間,Epj為該活動的緊前活動集合,fi為其某個緊前活動i的完成時間.式(14)為項目p的全局共享資源約束.式(15)為項目p的全局專屬資源約束.式(16)為項目i的本地資源約束,L為本地資源集合,為本地資源k的供應量,為活動j對本地資源的需求量.

在全局決策層,DRCMPSP 的目標函數與CRCMPSP 一致,可以使用CRCMPSP 的各種目標函數.而本地決策層本質上一個是個單項目RCPSP 問題,區別在于其全局共享資源的供應量在項目周期的各個時段是不同的.單項目之間在本地決策時獨立,但本地決策依賴于全局決策的共享資源分配方案,全局決策依賴于本地決策的單項目目標和共享資源需求.

3.2 DRCMPSP的求解方法

在DRCMPSP 中,本地決策的單項目調度問題和全局決策的資源分配問題都是NP-Hard 的問題.其中應用各種近似算法求解本地層的單項目RCPSP 問題已不再是DRCMPSP 的主要矛盾.DRCMPSP 問題求解算法的難點是解決全局共享資源的最優分配問題, 其原因在于全局共享資源競爭的情況更為復雜, 需要同時確定每單位資源在每個時段的分配情況.若在多項目中有全局共享資源集合G, 資源k的供應量為在整個項目周期內,會有個單位時間資源需要分配.若從上向下分配這些資源,在全局層無法確切知曉每個單項目在哪些時段需要的資源量.反之,若從下向上競爭這些資源,在本地決策層無法知曉其它項目是不是也在特定時段需要這些資源.因此,求解DRCMPSP 無法像CRCMPSP 一樣只要確定活動的優先級即可生成完整的多項目調度計劃,它必須采取多階段反復迭代的方式才能實現全局共享資源的分配.

可見,與CRCMPSP 相比,DRCMPSP 算法的瓶頸體現在全局共享資源的分配(或競爭)上,既有的DRCMPSP 研究大都聚焦于此[46,49,52?54].從目前的研究來看,DRCMPSP 共享資源沖突解決的各種方法差別很大,總體來看大致有兩種思路: 基于市場的方法(market-based approach)和基于協商的方法(negotiation-based approach).通常二者均基于多代理系統(multi-agent system,MAS)實現.

3.2.1 基于市場的方法

基于市場的方法可以被認為是一種從下向上的決策過程,其出發點是各個項目競爭共享資源,緊缺共享資源在緊缺時段的價格會被抬升,從而引導自行調度的各個項目在成本的壓力下進行變通,通過調整活動的執行時間改變全局共享資源的占用時段,最終達到解決資源沖突的目的.通常采用多代理的方式實現,為每個項目設置一個代理作為競拍者,負責單項目調度,并在每一輪競標時發出競標書.競標書中含有對資源的報價,以及在每個時段對共享資源的需求量.為共享資源設置代理作為拍賣人,致力于在每一輪以最高的價格將資源拍賣出去.這種方法類似于自由市場的拍賣過程,因此基于市場的方法也稱為基于組合拍賣的方法.

Confessore 等[46]為每個項目設置一個代理(競拍者)負責該項目的調度并參與共享資源的競標.為共享資源設置一個代理(拍賣者)執行組合拍賣算法,決定每輪競標的勝出者.通過計算實驗,證明該算法可以解決最多5 個項目每個項目8 個任務的小規模DRCMPSP 問題.Confessore 等[52]進一步完善了算法的流程,并將基于市場的方法與基于優先級規則的算法進行了比較,驗證了算法的有效性.目前基于組合拍賣方法的DRCMPSP 在思路上是相同的,但處理細節上往往區別很大.其中Confessore[52],Ara′uzo[53]和王磊等[54]的處理方式相對比較接近.本文以文獻[52]的算法結構為基礎說明基于組合拍賣的DRCMPSP 問題求解過程,如圖2.

圖2 基于組合拍賣的多代理系統結構Fig.2 Multi-agent system architecture based on combination auction

拍賣者將全局共享資源在每個時段的單位供應量作為拍賣品.每個單位資源在每個時間單位均為一個獨立的拍賣品.這樣,對于每種資源k,?k ∈G,在多項目工期T內,會產生種拍賣品.首先設定資源拍賣價格,通知競拍者.每個競拍者在工期,本地資源和全局資源的約束下,以某種單項目目標進行單項目調度.調度完成之后,將報價,對共享資源在每個時段的需求和調度結果傳遞給拍賣者.拍賣者以總價最高為目標進行組合拍賣,約束條件是每個拍賣品只分配給一個競拍者.若所有競拍者均勝出,則算法結束.否則,調整資源價格,要求失利者重新調度.待所有失利者重新調度完畢,再次與勝出者重新競標.拍賣者組織進行新一輪的組合拍賣,直到所有競拍者勝出.最后根據每個競拍者的調度結果,計算多項目總體目標.

類似的研究還有文獻[55–60]等.現有的基于市場的方法都采用MAS 的架構,在全局決策層采用組合拍賣的方式實施價格引導.由于組合拍賣問題本身就是一個NP-Hard 問題,所以針對大規模DRCMPSP 問題設計高效的組合拍賣算法將是未來的一個主要研究方向.

3.2.2 基于協商的方法

與基于市場的方法類似,基于協商的方法也多采用MAS 實現.通常在本地決策層為每個項目設置項目代理,在全局決策層為共享資源設置協調代理(中介代理).在基于市場的方法中,單輪競爭的勝出者只是暫時的勝利,在后續輪次中還需要繼續參與競爭.而在基于協商的方法中,一旦某個項目勝出,則直接獲得共享資源的使用權,不再參與競爭.

由于DRCMPSP 問題本身的復雜性,在既有的研究中,協商的方法也不盡相同.但一般都在全局決策層設置協調代理,在本地決策層為每個項目設置項目代理.協調代理負責共享資源分配方案,其對資源的分配是強制性的,項目代理必須執行.其典型結構如圖3.

圖3 基于協商的多代理結構Fig.3 Multi-agent system architecture based on negotiation

Homberger[62]進一步提出了一種基于進化算法的中介代理機制,思路是通過進化算法搜索最優或近優的項目訂單列表(項目對共享資源的需求).項目代理使用屬于自己的項目訂單進行調度產生可行的項目調度計劃,并提交調度結果給協調代理,實驗結果表明,計算效率明顯得到提升.Homberger 的方法強化了協調代理的權利,是一種統一協調的方法[61,62].在文獻[63]中,通過多個Agent 之間交換附加信息的手段提高算法收斂速度和求解質量.但在DRCMPSP 中應該公開什么哪些信息尚無定論,需要根據具體應用場景而定.文獻[64]提出了一種帶有單邊支付的自動協商方法,引導項目代理通過支付一定的成本贏得其它代理對其資源要求的認可,但項目代理需要事先生成基于多種調度計劃以供協商時選擇.

資源分配是一個協商的過程,也是各個項目代理之間進行博弈的過程[65].Wauters 等[66]以多項目總工期最短為目標,將分散博弈引入中介代理進行全局共享資源分配,中介代理管理項目訂單列表和項目代理提交的調度信息,通過項目訂單列表和每個項目的活動列表,對全局共享資源進行分配.這種方法的問題求解速度很快,但它假定每個項目代理的詳細調度信息對中介代理是透明的.李飛飛等[67]以多項目總延期成本為優化目標,設計了多回合序貫博弈談判機制,基于多項目總體目標決定每個回合的勝出者.勝出者退出,失利者基于剩余資源繼續調度并參與博弈.與Homberger 的方法相比,在基于博弈的協調過程中,各個項目代理會提供多種調度方案,每種方案對多項目(隱含其它項目)和本身有不同的收益.項目代理之間基于某種協議進行博弈,勝出者退出,失利者需要重新調度.

與基于市場的方法相比,基于協商的方法的特點有二: 1)在基于協商的方法中,項目代理與中介代理按照某種協議進行協調直接進行共享資源分配,而不是通過抬高共享資源價格進行間接引導.2)基于協商的方法為了方便全局層決策或與其它項目協商,通常會要求單項目公開一定的私有信息.如何在資源競爭時確定勝出者取決于DRCMPSP 的多項目調度目標函數.而如何確定私有信息的公開程度,則需要在算法效率和實際需求之間進行權衡.

3.3 DRCMPSP 問題庫

很多DRCMPSP 研究通過項目實例或基于單項目調度算例組合形成DRCMPSP 問題實例, 但這不利于不同算法的性能比較.為此, Homberger 構建了一個包含140 個實例的DRCMPSP 問題庫并在網絡上公開(http://www.mpsplib.com)[61].多項目實例中分別包含了2,5,10 和20 個單項目實例,共享資源分別包括1,2,3 和4 種.單項目實例來源于單項目問題庫PSPLib(http://www.om-db.wi.tum.de/psplib)[68].該問題庫從2007年公開以來,引起了廣泛關注,截止到目前已發布了140 余種算法和測試結果.

4 分析與展望

從被提出的時間順序和成熟度來看,單項目RCPSP 最早,之后是CRCMPSP 和DRCMPSP.三者存在著包含和被包含關系,但不存在著替代的關系.三者的總體比較如表1.CRCMPSP 和DRCMPSP 均包含多個單項目RCPSP 實例.CRCMPSP 可將多個項目合并形成一個超級項目網絡,而DRCMPSP 則維持各個單項目的獨立決策.CRCMPSP 通常只關注多項目總體目標,而DRCMPSP 則同時優化多項目和單項目.單項目RCPSP 和CRCMPSP 都只由一個負責人決策,而DRCMPSP 則由多個單項目負責人和多項目總負責人協同決策完成.所關注的資源,算法和所使用的問題庫也各不相同.

表1 典型項目調度問題的比較Table 1 Comparison of classic project scheduling problem

如前所述,單項目RCPSP,CRCMPSP 和DRCMPSP 的歷史積淀不同,因此其成熟度也各不相同.其中最成熟的單項目RCPSP發展路線圖可成為后兩者的直接參考.尤其是CRCMPSP 問題,未來的發展必然會隨著單項目RCPSP 的發展而發展,主要體現在兩個方面:

1)CRCMPSP 問題模型的研究.與單項目RCPSP 相同,CRCMPSP 的問題模型可以基于目標函數,資源處理方式和活動執行方式等方面進行擴展.而在目標函數和約束條件中考慮資源轉移的多種情形能夠體現多項目調度的特點,是實現多項目調度問題理論與應用契合的關鍵,因此有必要對其進行更深入的研究.另外,綜合考慮項目緩沖,輸入緩沖,單項目內部的資源緩沖和多項目之間的能力緩沖,構建多項目關鍵鏈調度的優化問題模型,仍然是目前該領域的一個研究難點.

2)CRCMPSP 求解算法的研究.與單項目RCPSP 問題相比,CRCMPSP 問題求解難度更高,需要借助于近似算法.在目前的CRCMPSP 近似算法中,基于優先級規則的啟發式算法研究相對較多.而元啟發式算法,或結合智能算法和優先級規則的混合算法在CRMPSP 中的應用研究還不夠深入.多項目的關鍵鏈調度因為涉及額外的緩沖設置操作,對算法的設計提出了更高的要求.因此,基于最新的智能算法進行改進,設計更加高效的求解算法,必然是未來的一個重要研究方向.

對于DRCMPSP 而言,雖然人們近年來對其進行了很多研究,但當前的成熟度還比較低,具有更加開闊的研究空間,主要表現在以下幾個方面:

1)雖然人們提出了幾種典型的DRCMPSP 求解策略,但到目前為止,大部分求解算法都還只能求解小規模DRCMPSP 問題.因此,研究DRCMPSP 問題的高效求解算法是DRCMPSP 的首要發展趨勢.

2)既有的算法中,能夠在本地決策層應用單項目RCPSP 方法進行單項目調度,但在全局決策層的共享資源分配上,無論是啟發式規則還是智能算法的應用研究都還非常欠缺.因此作者認為,在共享資源分配上實現基于優先級規則或智能算法的近似算法研究,具有廣闊的研究前景.

3)在共享資源分配(或競爭)上,目前的主流算法比如基于市場的方法和基于協商的方法,提升空間都還很大.比如在基于市場的方法中,所使用的組合拍賣方法本身就是一個復雜的NP-Hard 問題,其價格調整策略也有很多種,如何設計和評價并選擇適合于DRCMPSP 問題本身的組合拍賣算法,目前還沒有統一的框架.在基于協商的方法中,如何面對多項目調度目標設定協商規則,或如何設計高效的博弈方法,都還需要進一步深入研究.

4)另外,在DRCMPSP 中,單項目通常只在競爭共享資源時與全局決策層代理或其它項目發生關系.但既有研究表明,適度公開單項目的私有信息,會明顯加快算法的求解速度.而如何在保持DRCMPSP 問題本質特征的基礎上,確定公開單項目私有信息的程度,還需要進行測試和進一步的界定.

總體來看,DRCMPSP 無論在問題模型還是在調度方法上,均與既有的RCPSP 和CRCMPSP 問題有了明顯的不同,是近年來多項目調度問題研究的一個重要進展.它具有明顯的分層機制,單項目層按照單項目目標獨立調度,并在多項目層面向多項目總體目標進行協調,在分布式多項目管理中具有非常好的實際應用前景.在求解算法上,除了能夠利用CRCMPSP 的既有算法之外,多代理技術,博弈論和組合拍賣算法等均有充分的理論發揮空間.因此,對DRCMPSP 的深入研究將是多項目調度問題的一個重要研究主題和主要發展趨勢.

5 結束語

項目管理是一個非常活躍的研究領域,項目調度作為項目管理的核心內容,也得到了業界和學術界的廣泛關注.但現今項目規模越來越大,項目數目越來越多,僅僅依靠傳統的單項目計劃方法往往不能滿足現代多項目管理實踐的要求.因此,人們從執行層到策略層對資源約束多項目調度問題進行了深入的研究,提出了很多理論模型和求解算法.盡管多項目調度問題從上個世紀六十年代就已經被提出,但到目前為止,還缺乏對既有研究的深入分析和系統總結.

本文對多項目調度問題的兩個分支CRCMPSP 問題和DRCMPSP 問題進行了界定,然后分別對兩種問題的數學模型和求解算法進行了梳理,給出兩個問題研究現狀的總體視圖.在此基礎上,對單項目RCPSP,CRCMPSP 和DRCMPSP 問題進行系統比較,指出多項目調度問題研究目前存在的問題和未來發展方向.通過本文的研究,希望能夠為多項目調度理論的深入研究提供更加直接的參考,為多項目調度理論體系的進一步發展完善提供助力.