資源約束多項(xiàng)目調(diào)度問題研究現(xiàn)狀與展望

彭武良, 黃 敏

(1.煙臺(tái)大學(xué)經(jīng)濟(jì)管理學(xué)院,山東 煙臺(tái) 264005;2.東北大學(xué)信息科學(xué)與工程學(xué)院,流程工業(yè)綜合自動(dòng)化國家重點(diǎn)實(shí)驗(yàn)室,遼寧 沈陽 110819)

1 引 言

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

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

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

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

2.1 問題描述

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

2.1.1 典型問題模型

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

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

2.1.2 CRCMPSP 的目標(biāo)函數(shù)

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

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

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

2.1.3 CRCMPSP中的資源問題

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

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

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

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

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

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

2.2 CRCMPSP 的求解算法

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

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

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

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

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

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

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

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

2.2.2 元啟發(fā)式算法

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

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

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

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

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

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

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

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

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

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

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

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

2.5 CRCMPSP 問題庫

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

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

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

3.1 問題描述

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

3.1.1 資源處理方式

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

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

3.1.2 決策機(jī)制

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

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

3.1.3 問題模型

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

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

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

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

3.2 DRCMPSP的求解方法

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

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

3.2.1 基于市場(chǎng)的方法

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

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

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

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

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

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

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

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

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

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

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

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

3.3 DRCMPSP 問題庫

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

4 分析與展望

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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