彭武良, 黃 敏

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

1 引 言

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

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

2 集中式資源約束多項目調(diào)度問題

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

2.1 問題描述

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

2.1.1 典型問題模型

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

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

2.1.2 CRCMPSP 的目標函數(shù)

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

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

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

2.1.3 CRCMPSP中的資源問題

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

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

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

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

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

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

2.2 CRCMPSP 的求解算法

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

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

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

2.2.1 基于優(yōu)先級規(guī)則的啟發(fā)式算法

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

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

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

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

2.2.2 元啟發(fā)式算法

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

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

圖1 編碼結(jié)構(gòu)Fig.1 Encoding of chromosome

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

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

2.3 關(guān)鍵鏈方法在CRCMPSP 上的應用

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

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

基于既有的文獻分析可見,目前的多項目關(guān)鍵鏈調(diào)度還處于探索階段,缺乏比較完善的優(yōu)化調(diào)度路線,更缺乏嚴謹?shù)男问交瘮?shù)學模型.總之,基于多項目的關(guān)鍵鏈管理方法還不完善[5].在這種情況下,如何突出能力緩沖的關(guān)鍵地位,對多項目關(guān)鍵鏈調(diào)度問題的模型和算法進行系統(tǒng)的研究,將是CRCMPSP 的一個重要發(fā)展方向.

2.4 多模式資源約束多項目調(diào)度問題

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

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

2.5 CRCMPSP 問題庫

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

3 分散式資源約束多項目調(diào)度問題

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

3.1 問題描述

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

3.1.1 資源處理方式

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

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

3.1.2 決策機制

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

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

3.1.3 問題模型

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

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

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

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

3.2 DRCMPSP的求解方法

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

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

3.2.1 基于市場的方法

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

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

圖2 基于組合拍賣的多代理系統(tǒng)結(jié)構(gòu)Fig.2 Multi-agent system architecture based on combination auction

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

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

3.2.2 基于協(xié)商的方法

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

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

圖3 基于協(xié)商的多代理結(jié)構(gòu)Fig.3 Multi-agent system architecture based on negotiation

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

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

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

3.3 DRCMPSP 問題庫

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

4 分析與展望

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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