基于不確定因素的最優(yōu)進(jìn)度計(jì)劃魯棒調(diào)度研究

1魯棒項(xiàng)目調(diào)度傳統(tǒng)的項(xiàng)目計(jì)劃研究通常在確定的環(huán)境下進(jìn)行，即假設(shè)活動(dòng)的服務(wù)年限、資源和其他參數(shù)。然而,實(shí)際的項(xiàng)目環(huán)境充滿了不確定性、干擾和風(fēng)險(xiǎn),基于確定環(huán)境和完全信息確定的最優(yōu)進(jìn)度計(jì)劃在執(zhí)行時(shí),可能會(huì)與預(yù)期產(chǎn)生較大的偏差,甚至變得不可行,導(dǎo)致項(xiàng)目進(jìn)度拖延、預(yù)算超支等問題。為了確保項(xiàng)目順利、平穩(wěn)地執(zhí)行,必須事先考慮好各種不確定性因素和評估相關(guān)風(fēng)險(xiǎn),并且在不確定事件發(fā)生后給予及時(shí)響應(yīng)。魯棒項(xiàng)目調(diào)度作為解決不確定環(huán)境下項(xiàng)目調(diào)度問題的有效方法,其目標(biāo)是產(chǎn)生一個(gè)具有較高的穩(wěn)定性、并具有一定吸收不確定因素能力的基線進(jìn)度計(jì)劃:以該計(jì)劃指導(dǎo)項(xiàng)目執(zhí)行,力求保證項(xiàng)目中的各活動(dòng)按時(shí)開始,以及項(xiàng)目按期完工;進(jìn)度計(jì)劃受到干擾后可以對其及時(shí)修復(fù),并確保干擾因素產(chǎn)生的不良后果盡可能小。魯棒項(xiàng)目調(diào)度可以從很大程度上解決困擾諸多項(xiàng)目的一個(gè)基本問題:無法按時(shí)、按預(yù)算、按預(yù)定規(guī)格交付項(xiàng)目。對于實(shí)際的項(xiàng)目管理而言,魯棒項(xiàng)目調(diào)度的優(yōu)勢是顯而易見的。魯棒項(xiàng)目調(diào)度減少了重計(jì)劃、重調(diào)度的頻率及其產(chǎn)生的成本,并且一個(gè)穩(wěn)定的進(jìn)度計(jì)劃可以令項(xiàng)目經(jīng)理能夠從容、準(zhǔn)確地與客戶、承包商進(jìn)行溝通與協(xié)調(diào),保證項(xiàng)目及時(shí)交付。魯棒項(xiàng)目調(diào)度研究在近十余年才逐漸興起,雖然之前也零星可見魯棒項(xiàng)目調(diào)度的研究成果出現(xiàn),但是,2004年和2005年,魯汶大學(xué)教授W.Herroelen和R.Leus合作發(fā)表了兩篇不確定環(huán)境下項(xiàng)目調(diào)度與魯棒項(xiàng)目調(diào)度的綜述文章,這可以看作魯棒項(xiàng)目調(diào)度研究的分水嶺。自此以后,大量的魯棒項(xiàng)目調(diào)度研究成果不斷涌現(xiàn)。2009年,魯汶大學(xué)教授E.Demeulemeester和W.Herroelen出版了合著《RobustProjectScheduling》,系統(tǒng)總結(jié)了當(dāng)時(shí)魯棒項(xiàng)目調(diào)度的研究成果,并對一些新的魯棒項(xiàng)目調(diào)度方法做了深入分析,標(biāo)志著魯棒項(xiàng)目調(diào)度的研究進(jìn)一步成熟。魯棒項(xiàng)目調(diào)度作為一個(gè)迅速發(fā)展的新領(lǐng)域,在上述幾篇綜述性文獻(xiàn)出現(xiàn)之后,新的研究成果不斷涌現(xiàn),有必要對這些成果進(jìn)一步歸納整理,以進(jìn)一步把握本領(lǐng)域的發(fā)展脈絡(luò)并為后續(xù)研究提供支持。因此,本文在闡述魯棒項(xiàng)目調(diào)度問題及其研究框架的基礎(chǔ)上,歸納總結(jié)進(jìn)度計(jì)劃魯棒性的種類,重點(diǎn)分析主動(dòng)型與響應(yīng)型項(xiàng)目調(diào)度的模型和算法在近幾年的研究進(jìn)展,最后指出魯棒項(xiàng)目調(diào)度未來的研究方向。2魯棒設(shè)計(jì)與研究分類2.1魯棒項(xiàng)目調(diào)度問題的概念模型魯棒項(xiàng)目調(diào)度問題衍生自資源受限項(xiàng)目調(diào)度問題(resource-constrainedprojectschedulingproblem,RCP-SP),RCPSP是jobshop調(diào)度問題的泛化,并且在最優(yōu)化問題中屬于強(qiáng)NP-hard?？紤]了不確定因素的魯棒項(xiàng)目調(diào)度求解更為困難,也屬于NP-hard?；镜聂敯繇?xiàng)目調(diào)度問題可以描述如下:1一個(gè)項(xiàng)目由節(jié)點(diǎn)式(activity-on-node,AoN)網(wǎng)絡(luò)G=(N,A)表示,其中N為節(jié)點(diǎn)的集合,表示活動(dòng),N={1,2,…,n};A為有向弧的集合,表示“完成-開始(FS)”型、零時(shí)滯的優(yōu)先關(guān)系。將各活動(dòng)從1到n拓?fù)渚幪?hào),其中活動(dòng)1和n是虛活動(dòng),分別代表項(xiàng)目的開始和結(jié)束。②每項(xiàng)活動(dòng)的工期為di(1≤i≤n)。項(xiàng)目執(zhí)行時(shí)需要K種可恢復(fù)的資源,K={1,2,…,k}。活動(dòng)i在執(zhí)行時(shí),每個(gè)時(shí)間段對資源k的需求量為rik.資源k在任一單位時(shí)間段的最大可獲得量為ak.虛活動(dòng)1和n的工期均為0且不需要任何資源。3在不確定項(xiàng)目環(huán)境下,上述的某個(gè)或某些參數(shù)可能成為不確定的量,分別表示為.④求解魯棒項(xiàng)目調(diào)度問題,就是在滿足優(yōu)先關(guān)系和資源約束的條件下,面對項(xiàng)目環(huán)境中的不確定性,為每個(gè)活動(dòng)確定開始時(shí)間,生成基線進(jìn)度計(jì)劃SB=(s1,s2,…,sn),最大化SB的魯棒性R(SB,ω)。魯棒項(xiàng)目調(diào)度問題的概念模型可以描述為subjectto式中,St表示時(shí)段t正在執(zhí)行的活動(dòng)集合,有;目標(biāo)函數(shù)(1)最大化SB的魯棒性;式(2)為優(yōu)先關(guān)系約束;式(3)為資源約束;式(4)定義了決策變量。鑒于此概念模型包含許多不確定參數(shù),無法直接求解。在對具體問題建模時(shí),應(yīng)根據(jù)需要采用不確定優(yōu)化方法建立具有明確意義的模型。對于魯棒項(xiàng)目調(diào)度問題的解決思路,Demeulemeester和Herroelen(2009)所提出的三階段方法已被眾多文獻(xiàn)廣為采納。第一階段:求解RCPSP,生成一個(gè)優(yōu)先關(guān)系和資源可行的基線進(jìn)度計(jì)劃;第二階段:利用主動(dòng)型項(xiàng)目調(diào)度,對基線進(jìn)度計(jì)劃進(jìn)行保護(hù),使其免受項(xiàng)目執(zhí)行中可能發(fā)生的各類不確定性干擾;第三階段:利用響應(yīng)型項(xiàng)目調(diào)度,對項(xiàng)目實(shí)際執(zhí)行時(shí)仍受到破壞的進(jìn)度計(jì)劃進(jìn)行修復(fù)。2.2魯棒項(xiàng)目調(diào)度的時(shí)機(jī)與不確定因素根據(jù)調(diào)度時(shí)機(jī)的不同,魯棒項(xiàng)目調(diào)度可以分為主動(dòng)型調(diào)度和響應(yīng)型調(diào)度［１，２］。主動(dòng)型調(diào)度是在項(xiàng)目執(zhí)行之前生成一個(gè)魯棒的基線進(jìn)度計(jì)劃,使其盡可能地對各類干擾因素不再敏感。針對項(xiàng)目執(zhí)行時(shí)仍會(huì)受到干擾、導(dǎo)致進(jìn)度計(jì)劃被破壞的情況,采用響應(yīng)型調(diào)度對其進(jìn)行修復(fù)。項(xiàng)目中的不確定因素可分為如下幾類:1時(shí)間的不確定性?；顒?dòng)的實(shí)際執(zhí)行時(shí)間或長于、或短于計(jì)劃時(shí)間;項(xiàng)目的交付日期可能會(huì)更改。2資源的不確定性。項(xiàng)目執(zhí)行時(shí),資源的可用量不確定,可能會(huì)出現(xiàn)資源短缺;物資供應(yīng)可能無法按時(shí)到達(dá)。3項(xiàng)目范圍的不確定性。有的活動(dòng)結(jié)束后可能會(huì)因?yàn)闆]有達(dá)到預(yù)定的里程碑而導(dǎo)致返工;因項(xiàng)目范圍的變更,新的活動(dòng)需要加入、原有的活動(dòng)沒有必要執(zhí)行。針對不同類別的魯棒項(xiàng)目調(diào)度,已有眾多有效的方法被提出。以項(xiàng)目調(diào)度的時(shí)機(jī)與不確定因素作為分類標(biāo)準(zhǔn),將魯棒項(xiàng)目調(diào)度的研究框架歸納為表1。其中,基于隨機(jī)規(guī)劃的方法已成為目前主流的處理手段,基于模糊理論、魯棒優(yōu)化的方法也逐漸受到重視。對于不確定因素的考慮,也逐漸從時(shí)間不確定性擴(kuò)展到資源、范圍等多種不確定性。眾多行之有效的精確或啟發(fā)式算法也不斷出現(xiàn)。隨機(jī)項(xiàng)目調(diào)度是處理時(shí)間不確定條件下項(xiàng)目調(diào)度的常用方法,它與魯棒項(xiàng)目調(diào)度有明顯區(qū)別,主要表現(xiàn)為:①隨機(jī)項(xiàng)目調(diào)度針對的不確定因素是時(shí)間不確定,它把調(diào)度問題看作一個(gè)多階段決策過程。魯棒項(xiàng)目調(diào)度研究的不確定因素并不局限于時(shí)間不確定。②隨機(jī)項(xiàng)目調(diào)度通常以優(yōu)化期望工期為目標(biāo)。魯棒項(xiàng)目調(diào)度以進(jìn)度計(jì)劃的魯棒性為優(yōu)化目標(biāo)。③隨機(jī)項(xiàng)目調(diào)度在項(xiàng)目執(zhí)行前不生成基線進(jìn)度計(jì)劃,而是隨著項(xiàng)目的推進(jìn),在每個(gè)決策階段,采用“調(diào)度策略”在滿足優(yōu)先關(guān)系與資源約束的條件下,確定可執(zhí)行的活動(dòng)集合,動(dòng)態(tài)產(chǎn)生進(jìn)度計(jì)劃。正是這個(gè)原因,隨機(jī)項(xiàng)目調(diào)度也經(jīng)常被稱為“完全響應(yīng)型調(diào)度”或“在線調(diào)度”。魯棒項(xiàng)目調(diào)度通常需要在項(xiàng)目執(zhí)行前生成一個(gè)魯棒的基線進(jìn)度計(jì)劃。3受不確定性影響的能力魯棒性一般是指當(dāng)系統(tǒng)存在不確定因素時(shí),系統(tǒng)仍然能夠保持正常工作的特性,即系統(tǒng)具有一定承受不確定性影響的能力。進(jìn)度計(jì)劃的魯棒性,即進(jìn)度計(jì)劃在執(zhí)行時(shí),具有一定承受不確定與干擾因素影響的能力。研究進(jìn)度計(jì)劃魯棒性有兩個(gè)角度:解的取值和目標(biāo)函數(shù)的取值。相應(yīng)地,已有研究中所涉及的項(xiàng)目魯棒性的評價(jià)指標(biāo)也分為:解的魯棒和質(zhì)量魯棒,以及上述兩者的復(fù)合。3.1期望估計(jì)模型解的魯棒,也稱為進(jìn)度計(jì)劃的穩(wěn)定性,衡量的是基線進(jìn)度計(jì)劃SB與實(shí)際執(zhí)行時(shí)的進(jìn)度SR的差異。Leus和Herroelen(2004)建議用計(jì)劃與實(shí)際的活動(dòng)開始時(shí)間的絕對差異的加權(quán)和來衡量解的魯棒。有式中,si表示活動(dòng)i在基線進(jìn)度計(jì)劃SB中的計(jì)劃開始時(shí)間;N為活動(dòng)編號(hào)集合,i∈N;Si為隨機(jī)變量,表示活動(dòng)i在實(shí)際進(jìn)度SR中的實(shí)際開始時(shí)間;權(quán)重wi代表活動(dòng)i在單位時(shí)間的懲罰成本,即活動(dòng)i的實(shí)際開始時(shí)間早于或晚于計(jì)劃開始時(shí)間一單位所產(chǎn)生的成本,wi≥0。該成本權(quán)重?cái)?shù)值大小反映了更改在預(yù)定的時(shí)間窗內(nèi)獲取資源的難易程度,或者準(zhǔn)時(shí)執(zhí)行活動(dòng)蹬重要性。在實(shí)際項(xiàng)目中,這一懲罰成本可能是相當(dāng)大的數(shù)值?；谑?5),在主動(dòng)型調(diào)度中最大化魯棒性,就等價(jià)于最小化活動(dòng)的計(jì)劃時(shí)間與實(shí)際開始時(shí)間差異的期望的加權(quán)和,即式中,E為期望值算子。上式通常也被稱為穩(wěn)法性成本目標(biāo)函數(shù)。Leus和Herroelen(2005)已經(jīng)證明,以上式為目標(biāo)函數(shù)的嗡題是NP-hard,因此,在大規(guī)模問題中用解析法求解上式中的期望值是不現(xiàn)實(shí)的,仿真方琺是常用的方法。也有研究用更容易計(jì)算的代理目標(biāo)函數(shù)衡量解的魯棒,如基于時(shí)差的解的魯棒指標(biāo)[9-11]。3.2用目標(biāo)函數(shù)計(jì)算質(zhì)量魯棒指的是基線進(jìn)度計(jì)劃對應(yīng)的目標(biāo)函數(shù)值對干擾因素不敏感。質(zhì)量魯棒的思想是構(gòu)造一個(gè)基線進(jìn)度計(jì)劃,當(dāng)干擾出現(xiàn)時(shí),該計(jì)劃對應(yīng)的目標(biāo)函數(shù)值不會(huì)惡化。質(zhì)量魯棒可以用目標(biāo)函數(shù)的期望值來衡量,如期望工期E[Cmax]。質(zhì)量魯棒還可以用所謂的“服務(wù)水平”(即,項(xiàng)目及時(shí)完工概率)來衡量,即maxP(Sn≤δn)。其中,Sn為代表項(xiàng)目完成的虛節(jié)點(diǎn)n的實(shí)際完成時(shí)間;δn為項(xiàng)目的截止日期。即使在不考慮資源約束的條件下,對該目標(biāo)函數(shù)進(jìn)行解析求解仍是非常困難的,這一問題是NP-hard。3.3復(fù)合魯棒性指標(biāo)如果同時(shí)考慮解的魯棒與質(zhì)量魯棒,可以引入復(fù)合魯棒性指標(biāo)。VandeVonder等(2008)［１２］采用雙目標(biāo)形式定義復(fù)合魯棒性指標(biāo),有上述目標(biāo)函數(shù)同時(shí)包含解的魯棒與質(zhì)量魯棒。如果無法先驗(yàn)獲知這一復(fù)合目標(biāo)函數(shù)F[·,·]的具體形式,并且兩個(gè)評價(jià)準(zhǔn)則的相對重要性也無法獲知,則無法用兩個(gè)準(zhǔn)則的線性組合來反映決策者的偏好。因此,解析方法難以對這一復(fù)合目標(biāo)函數(shù)進(jìn)行有效處理,仿真方法也就成為一種替代選擇。4不確定性調(diào)度主動(dòng)型調(diào)度(預(yù)應(yīng)式調(diào)度,前攝調(diào)度等)發(fā)生在在項(xiàng)目計(jì)劃階段,它通過分析各類不確定性因素對項(xiàng)目進(jìn)度計(jì)劃的影響,考慮各腫可能出現(xiàn)的干擾,建立對干擾不靈敏的進(jìn)度計(jì)劃,即魯棒的進(jìn)度計(jì)劃。主動(dòng)型調(diào)度是魯磅項(xiàng)目調(diào)度研究中相對成熟的一個(gè)領(lǐng)域。根據(jù)對不確定因素的處理方法不同,主動(dòng)型調(diào)度分濰:1基于確定型模型的主動(dòng)型調(diào)度,即不對未來情況進(jìn)行任何估計(jì),參數(shù)均取最可能值;2基于隨機(jī)或模糊模型的主動(dòng)型調(diào)度,即估計(jì)未來情況的概率(或可能性)與后果;3基于魯棒優(yōu)化模型的主動(dòng)型調(diào)度,即只估計(jì)可能的場景,不需要分布信息。隨機(jī)規(guī)劃與魯棒優(yōu)化作為兩大典型的不確定性優(yōu)化技術(shù),是處理不確定條件下魯棒項(xiàng)目調(diào)度的主流方法。隨機(jī)規(guī)劃基于概率模型用概率分布描述數(shù)據(jù)的不確定性,通常是以優(yōu)化系統(tǒng)的期望性能作濰目標(biāo)。魯棒優(yōu)化以獲得對參數(shù)不確定性不敏感的解為目標(biāo),通常優(yōu)化系統(tǒng)在最壞情況下的性能,從而保證產(chǎn)生的解在最壞情況發(fā)生時(shí)仍能良好執(zhí)行。因?yàn)轸敯魞?yōu)化是面向最壞情況的,導(dǎo)致該方法相對比較保守。如果可以獲得有關(guān)參數(shù)的確切概率分布信息,隨機(jī)規(guī)劃模型應(yīng)當(dāng)作為首選方法。當(dāng)然,隨機(jī)規(guī)劃模型也受困于“維災(zāi)難”,記算量按指數(shù)增加。如果無法獲得確切的概率分布信息,則魯棒優(yōu)化更為適用。4.1雙目標(biāo)資源受限項(xiàng)目調(diào)度模型的構(gòu)建基于確定型模型的主動(dòng)型調(diào)度假設(shè)完全信息與確定參數(shù),用確定型的優(yōu)化模型對問題建模。這類調(diào)度模型與常見的RCPSP的區(qū)別主要在于目標(biāo)函數(shù),這類模型主要以項(xiàng)目時(shí)差的函數(shù)作為魯棒性的衡量指標(biāo),通過最大化各類時(shí)差及其函數(shù),獲取魯棒的進(jìn)度計(jì)劃。其他方面與RCPSP基本類似,如模型中的時(shí)間、資源等參數(shù)都采用確定值,通常是貝照最可能值估計(jì)出來的,不對項(xiàng)目未來所面臨的干擾情況進(jìn)行估計(jì)。Al-Fawzan和Haouari(2005)將考慮資源約束的活動(dòng)的自由時(shí)差(FS)定義為:不影響其緊后活動(dòng)最早開始和不違背資源約束的條件下,該活動(dòng)的最早開始時(shí)間可以浮動(dòng)的時(shí)間。并將所有活動(dòng)自由時(shí)差之和作為進(jìn)度計(jì)劃的魯棒性指標(biāo)。由此建立了雙目標(biāo)資源受限項(xiàng)目調(diào)度模型,以最大化魯棒和最小化工期作為目標(biāo)函數(shù),使用禁忌搜索算法對問題求解,獲得有效的靳度計(jì)劃。從本質(zhì)上看,Al-Fawzan和Haouari的研究是建立在確定性環(huán)境中的,沒有對未來項(xiàng)目執(zhí)行時(shí)可能發(fā)生的情況進(jìn)行估計(jì),只是在RCPSP的解空間進(jìn)行搜索,找到其中魯棒性最高的進(jìn)度計(jì)劃。Abbasi等(2006)對Al-Fawzan和Haouari提出的雙目標(biāo)調(diào)度模型采用禁忌搜索算法進(jìn)行求解。Kobylanski和Kuchta(2007)對Al-Fawzan和Haouari所采用的魯棒性指標(biāo)提出了質(zhì)疑,指出該指標(biāo)不能全面描述進(jìn)度計(jì)劃的魯棒性,并通過反例說明了Al-Fawzan和Haouari的指標(biāo)對于某些項(xiàng)目調(diào)度問題的實(shí)例不能產(chǎn)生魯棒的進(jìn)度計(jì)劃?；诖?他們在綜合考慮解的魯棒和質(zhì)量魯棒的基礎(chǔ)上,提出了兩種改進(jìn)的魯棒性指標(biāo):①所有活動(dòng)自由時(shí)差中的最小值;②所有活動(dòng)自由時(shí)差與項(xiàng)目工期比值中的最小值。最大化魯棒性即最大化上述指標(biāo)?；诖_定型模型的主動(dòng)型調(diào)度的最大優(yōu)點(diǎn)在于,其生成的魯棒基線進(jìn)度計(jì)劃所對應(yīng)的項(xiàng)目工期,通常可以保證等于或非常接近于最短工期。然而,也正因?yàn)檫@點(diǎn),加之不對未來項(xiàng)目執(zhí)行期間的可能情況進(jìn)行預(yù)測,使得這類方法產(chǎn)生的進(jìn)度計(jì)劃的魯棒性表現(xiàn)較差,僅適用于不確定程度較低的項(xiàng)目環(huán)境。4.2不確定參數(shù)建模基于隨機(jī)或模糊模型的主動(dòng)型調(diào)度,克服了確定型模型的缺點(diǎn),利用隨機(jī)變量或模糊變量對不確定的參數(shù)(如活動(dòng)的工期、資源等)建模,從而產(chǎn)生魯棒性表現(xiàn)較好的進(jìn)度計(jì)劃。隨著基于隨機(jī)或模糊模型的主動(dòng)型調(diào)度研究的深入,這一方向的研究經(jīng)歷了無資源約束、有資源約束的階段,問題的難度不斷增加,現(xiàn)實(shí)相關(guān)性也逐步提高。(1)資源約束和進(jìn)度計(jì)劃作為最早的研究者之一,Herroelen和Leus(2004)假設(shè)不存在資源約束,在工期不確定條件下構(gòu)建魯棒的進(jìn)度計(jì)劃。他們以具有一定概率的干擾場景來表示工期面臨的不確定性,以式(6)為目標(biāo)函數(shù),建立數(shù)學(xué)規(guī)劃模型。他們的模型與網(wǎng)絡(luò)流模型具有一定相似性,因此設(shè)計(jì)了基于網(wǎng)絡(luò)流算法的精確解法。(2)主動(dòng)型調(diào)度可恢復(fù)資源不確定條件下的主動(dòng)型調(diào)度模型與方法,可按照是否使用歷史信息進(jìn)一步細(xì)分。在項(xiàng)目計(jì)劃階段,如果難以對項(xiàng)目執(zhí)行情況做出預(yù)測,可以使用代理魯棒目標(biāo)函數(shù)進(jìn)行調(diào)度;如果能夠較準(zhǔn)確預(yù)測未來事件或者能夠根據(jù)歷史信息統(tǒng)計(jì)出未來不確定事件發(fā)生的概率與后果,調(diào)度時(shí)就可以將這些信息考慮進(jìn)目標(biāo)函數(shù)。針對資源不確定性,Lambrechts等(2008)［２４］研究了資源供應(yīng)量隨機(jī)條件下的主動(dòng)型調(diào)度問題。作者采用式(5)作為魯棒性指標(biāo)。因?yàn)樵撝笜?biāo)難于用解析方法評價(jià),而仿真方法又相當(dāng)耗時(shí),所以作者提出了一個(gè)基于自由時(shí)差的效用函數(shù)作為代理目標(biāo)函數(shù):式中,i,j為活動(dòng)編號(hào),FSi為考慮資源約束的活動(dòng)i的自由時(shí)差,CIWi為活動(dòng)i的累積不穩(wěn)定權(quán)重,定義為,其中:wi表示活動(dòng)i的不穩(wěn)定權(quán)重,succi表示活動(dòng)i的直接與間接后繼活動(dòng)集合。作者使用CIWi的理由是,活動(dòng)i每延遲1個(gè)時(shí)間單位必然導(dǎo)致一個(gè)成本wi的產(chǎn)生,這一延遲同時(shí)也將導(dǎo)致活動(dòng)i的后繼活動(dòng)均延遲1個(gè)時(shí)間單位。基于上述代理函數(shù),作者采用禁忌搜索算法來生成一個(gè)魯棒的進(jìn)度計(jì)劃。(3)魯棒補(bǔ)償評估Wang(2004)基于模糊集理論研究產(chǎn)品開發(fā)項(xiàng)目調(diào)度,不確定的時(shí)間參數(shù)用模糊集表示。作者把最壞情況下具有最佳性能的進(jìn)度計(jì)劃定義為魯棒的進(jìn)度計(jì)劃,在預(yù)先定義好項(xiàng)目交付日期的條件下,最小化項(xiàng)目延期的可能性。張宏國等(2009)采用模糊集對不精確時(shí)間參數(shù)和資源不確定性進(jìn)行表示,同時(shí)考慮進(jìn)度計(jì)劃的質(zhì)量魯棒和解的魯棒性,定義了基于時(shí)差的魯棒性指標(biāo),并設(shè)計(jì)遺傳算法求解。王冰等(2011)采用模糊數(shù)描述不確定的活動(dòng)執(zhí)行時(shí)間和項(xiàng)目交貨期,建立了以最大化客戶滿意度和進(jìn)度計(jì)劃魯棒性為目標(biāo)的魯棒滿意項(xiàng)目調(diào)度模型,并用人工免疫算法求解。4.3魯棒優(yōu)化模型雖然在某些情況下對未來可能出現(xiàn)的不確定場景進(jìn)行預(yù)測是可行的,但難以估計(jì)這些事件發(fā)生的概率,這時(shí)概率模型就無法應(yīng)用。這種情況下,由于采用魯棒優(yōu)化方法處理不確定參數(shù)時(shí),主要是通過離散的場景集合或區(qū)間數(shù)對不確定參數(shù)建模,概率分布函數(shù)不需要決策者提供,使得魯棒優(yōu)化成為一種有效的解決手段。魯棒優(yōu)化以優(yōu)化最壞場景下的性能為目標(biāo),求出的進(jìn)度計(jì)劃即使在最壞情況發(fā)生時(shí)仍具有較好的表現(xiàn),從而保證了進(jìn)度計(jì)劃的魯棒性。針對工期不確定性,Yamashita(2007)研究了活動(dòng)時(shí)間不確定條件下的項(xiàng)目資源獲得成本問題(resourceavailabilitycostproblem,RACP),建立了兩個(gè)魯棒優(yōu)化模型:分別最小化RACP最大后悔值函數(shù)和最小化RACP均值-方差函數(shù)。針對RACP魯棒優(yōu)化模型的特點(diǎn),設(shè)計(jì)了分散搜索算法對問題求解。壽涌毅和王偉(2009)提出活動(dòng)工期不確定條件下的資源受限項(xiàng)目調(diào)度的魯棒優(yōu)化模型,并采用遺傳算法求解。實(shí)驗(yàn)結(jié)果表明,他們的方法獲得的進(jìn)度計(jì)劃能有效應(yīng)對任務(wù)工期不確定性導(dǎo)致的隨機(jī)差異,具有較強(qiáng)的魯棒性。Artigues等(2013)提出了AR-RCPSP問題(minimaxabsolute-regretrobustresource-constrainedprojectschedulingproblem),基于整數(shù)規(guī)劃求解各活動(dòng)的最早開始執(zhí)行策略(ES-policy),最小化所有場景下的最大絕對后悔值,求解出的進(jìn)度計(jì)劃在活動(dòng)工期出現(xiàn)最極端的情況下,仍能盡量接近最優(yōu)解。5響應(yīng)型資源受限項(xiàng)目調(diào)度算法雖然通過主動(dòng)型調(diào)度對基線進(jìn)度計(jì)劃進(jìn)行了充分保護(hù),但也不可能考慮到所有的干擾因素,項(xiàng)目執(zhí)行時(shí)仍然存在進(jìn)度計(jì)劃受到干擾的可能,即發(fā)生的干擾不能被基線進(jìn)度計(jì)劃完全“吸收”,這時(shí)就需要使用響應(yīng)型調(diào)度對進(jìn)度計(jì)劃進(jìn)行恢復(fù),以最小的代價(jià)盡快使項(xiàng)目進(jìn)度回到預(yù)定軌道。響應(yīng)型調(diào)度方法主要包括啟發(fā)式方法、干擾管理、約束規(guī)劃等。響應(yīng)型調(diào)度可以看作是在項(xiàng)目執(zhí)行過程中的一個(gè)多階段決策過程,采用多階段決策的方法求解。相比主動(dòng)型調(diào)度,響應(yīng)型調(diào)度的研究成果偏少。在時(shí)間不確定條件下,VandeVonder等(2007)提出了魯棒響應(yīng)型調(diào)度的啟發(fā)式規(guī)則,以及基于優(yōu)先規(guī)則的魯棒并行和魯棒串行進(jìn)度生成機(jī)制,用于修補(bǔ)活動(dòng)執(zhí)行時(shí)受到干擾的進(jìn)度計(jì)劃,使得基線進(jìn)度計(jì)劃與實(shí)際進(jìn)度的偏差最小化。以質(zhì)量魯棒和解的魯棒的復(fù)合函數(shù)作為目標(biāo)函數(shù),VandeVonder等(2007)通過實(shí)驗(yàn)評價(jià)了進(jìn)度計(jì)劃由于干擾受到破壞時(shí),4種響應(yīng)型資源受限項(xiàng)目調(diào)度算法的效果:①最優(yōu)的質(zhì)量魯棒算法:基于重調(diào)度,即在干擾發(fā)生的時(shí)刻,調(diào)用最優(yōu)算法完成重調(diào)度,再次生成一個(gè)最優(yōu)的進(jìn)度計(jì)劃。②質(zhì)量魯棒的啟發(fā)式方法:基于最早開始調(diào)度策略(earlystartpolicy)。③質(zhì)量魯棒的啟發(fā)式方法:基于活動(dòng)的優(yōu)先規(guī)則(Activity-basedpriorityrules)。④解的魯棒啟發(fā)式方法?；谧钚』崆?拖期成本,通過求解RCPSPWET問題(resource-constrainedearliness-tardinessprojectschedulingproblem)的最優(yōu)解獲得進(jìn)度計(jì)劃。Wang(2005)建立了項(xiàng)目調(diào)度對應(yīng)的動(dòng)態(tài)約束滿足問題(constraintsatisfactionproblem),項(xiàng)目交付日期作為必須滿足硬約束。該方法可以對以下干擾事件進(jìn)行處理:①活動(dòng)開始或結(jié)束時(shí)間發(fā)生變化;②活動(dòng)工期變化;③資源可用量變化;④時(shí)間約束的增刪。項(xiàng)目執(zhí)行時(shí),所有干擾事件對進(jìn)度計(jì)劃的影響都可以歸結(jié)為CSP中的約束的增加或刪除。分別用模擬退火和GA對受到干擾的進(jìn)度計(jì)劃進(jìn)行修補(bǔ),修補(bǔ)的目標(biāo)函數(shù)是最小化資源沖突成本。6魯棒項(xiàng)目進(jìn)度計(jì)劃魯棒項(xiàng)目調(diào)度未來的研究依然存在廣闊的發(fā)展空間,歸納為如下幾個(gè)方面:1在模型方面,建立面向多種不確定因素的魯棒項(xiàng)目調(diào)度模型。現(xiàn)有研究主要關(guān)注了時(shí)間或資源的不確定性［４９］,然而在實(shí)際項(xiàng)目中,還存在其他方面的不確定,如項(xiàng)目范圍變更(新活動(dòng)的加入或舊活動(dòng)的取消),活動(dòng)優(yōu)先關(guān)系不確定(活動(dòng)返工、迭代)等［５０］,需要進(jìn)一步探索新的模型與方法來處理這些問題。利用設(shè)計(jì)結(jié)構(gòu)矩陣或圖示評審技術(shù)來描述這些新的不確定性,將是一個(gè)非常值得探討的課題。此外,現(xiàn)有研究傾向于對各類不確定因素獨(dú)立研究,這顯然具有一定的局限性,如何在同時(shí)面臨多種不確定因素的條件下建立魯棒調(diào)度模型,需要進(jìn)一步深入研究。在魯棒項(xiàng)目調(diào)度模型中,不可避免地要對進(jìn)度計(jì)劃的魯棒性進(jìn)行評價(jià)?，F(xiàn)有的魯棒項(xiàng)目調(diào)度主要以最大化解的魯棒與質(zhì)量魯棒為主,其所用的魯棒性指標(biāo)大多數(shù)是關(guān)于時(shí)間的函數(shù),如基于時(shí)差、加權(quán)的活動(dòng)開始時(shí)間變動(dòng)或項(xiàng)目及時(shí)完工的概率［５１］。提出新的、有效的魯棒性指標(biāo),將會(huì)進(jìn)一步推進(jìn)魯棒項(xiàng)目調(diào)度的建模。②在算法方面,由于魯棒項(xiàng)目調(diào)度問題的復(fù)雜性很高,開發(fā)各類高效的精確或次最優(yōu)算法,仍然是非常值得關(guān)注的一個(gè)研究方向?，F(xiàn)有的主動(dòng)型/響應(yīng)型調(diào)度方法,很多都遵循Demeulemeester和Herroelen的三階段過程生成魯棒基線進(jìn)度計(jì)劃,有必要探索更為簡化的方法。Chtourou和Haouari(2008)提出了12種魯棒性指標(biāo),這些指標(biāo)都是以活動(dòng)的自由時(shí)差為基礎(chǔ)進(jìn)行計(jì)算的。為了獲取魯棒的項(xiàng)目進(jìn)度計(jì)劃,作者采用基于優(yōu)先規(guī)則的啟發(fā)式方法中的偏倚隨機(jī)抽樣多路算法進(jìn)行求解,求解過程分為兩個(gè)階段:第一階段采用偏倚隨機(jī)抽樣多路算法求解標(biāo)準(zhǔn)的RCPSP問題,將獲得的最優(yōu)工期加入第二階段的約束條件;第二階段以最大化魯棒性為目標(biāo)函數(shù),仍采用偏倚隨機(jī)抽樣多路算法求解,最終獲取到具有最小工期和最大魯棒的進(jìn)度計(jì)劃。針對時(shí)間的不確定性,有兩種提高進(jìn)度計(jì)劃魯棒性的方法得到了廣泛研究:魯棒資源分配和插入時(shí)間緩沖。魯棒資源分配主要依托“資源流網(wǎng)絡(luò)”來實(shí)現(xiàn)。資源流網(wǎng)絡(luò)描述了隨著項(xiàng)目的推進(jìn),每一單位資源在各活動(dòng)間的傳遞路線。給定一個(gè)進(jìn)度計(jì)劃,項(xiàng)目執(zhí)行時(shí)資源在活動(dòng)之間不同的流動(dòng)方式會(huì)對進(jìn)度計(jì)劃的魯棒性產(chǎn)生影響。魯棒資源分配方法就是為基線進(jìn)度計(jì)劃尋找一種巧妙的資源傳遞路線,使得該計(jì)劃在執(zhí)行時(shí)具有較好的魯棒性。Leus和Herroelen(2004)利用資源流網(wǎng)絡(luò)研究了活動(dòng)工期不確定條件下的魯棒資源分配問題,并采用分支定界算法進(jìn)行求解。將時(shí)間緩沖插入到進(jìn)度計(jì)劃中合適的位置,可以盡可能地阻止局部干擾蔓延到整個(gè)進(jìn)度計(jì)劃。插入時(shí)間緩沖有兩種策略:錦標(biāo)賽策略(即關(guān)鍵鏈法)和時(shí)刻表策略。關(guān)鍵鏈調(diào)度總是將活動(dòng)的開始時(shí)間盡可能早地開始。關(guān)鍵鏈調(diào)度是一種質(zhì)量魯棒的方法。時(shí)刻表策略不允許活動(dòng)的實(shí)際開始時(shí)間早于其基線進(jìn)度計(jì)劃中開始時(shí)間,如列車調(diào)度、航班調(diào)度。VandeVonder等(2008)在活動(dòng)工期隨機(jī)、項(xiàng)目工期給定的條件下,比較研究了多個(gè)以式(6)為目標(biāo)構(gòu)建魯棒項(xiàng)目進(jìn)度計(jì)劃的啟發(fā)式算法:RFDFF(resourceflowdependentfloatfactor)、VADE(virtualactivitydurationextension)、STC(startingtimecriticality)和禁忌搜索算法等。這些算法的思路,都是先利用分支定界算法獲得RCPSP的精確解(進(jìn)度計(jì)劃),然后用這些啟發(fā)式方法產(chǎn)生時(shí)間緩沖、并插入到項(xiàng)目進(jìn)度計(jì)劃中,從而獲得一個(gè)魯棒的進(jìn)度計(jì)劃。仿真實(shí)驗(yàn)結(jié)果表明,由于利用了活動(dòng)權(quán)重、工期的方差等多種信息輔助緩沖分配,基于時(shí)刻表策略的STC方法在幾種啟發(fā)式方法中表現(xiàn)最好。Tian等(2013)通過大量計(jì)算實(shí)驗(yàn)研究了不同調(diào)度策略對項(xiàng)目績效(平均工期、工期的標(biāo)準(zhǔn)差、及時(shí)完工概率和進(jìn)度穩(wěn)定性成本)的影響,其結(jié)果表明,對于較大規(guī)模的項(xiàng)目,采用錦標(biāo)賽策略和資源流網(wǎng)絡(luò)進(jìn)行調(diào)度會(huì)獲得較好結(jié)果。進(jìn)度計(jì)劃的魯棒性,通常是以犧牲項(xiàng)目工期為代價(jià)取得的,即進(jìn)度計(jì)劃的魯棒性越高,項(xiàng)目的計(jì)劃完工時(shí)間就會(huì)越長。VandeVonder等(2005)和VandeVonder等(2006)分別在無資源約束和有資源約束的條件下,比較了進(jìn)度計(jì)劃的魯棒性與工期的權(quán)衡關(guān)系。進(jìn)度計(jì)劃的魯棒性反映了解的魯棒,工期反映了質(zhì)量魯棒。VandeVonder等(2005)采用了三種基于時(shí)間緩沖的啟發(fā)式方法進(jìn)行權(quán)衡分析:關(guān)鍵鏈法、改進(jìn)的關(guān)鍵鏈法和ADFF(adaptedfloatfactormodel)。前兩種方法代表了解的魯棒,ADFF代表了質(zhì)量魯棒。研究表明,對于某些類型的項(xiàng)目網(wǎng)絡(luò),質(zhì)量魯棒與解的魯棒方法在平均表現(xiàn)上并沒有顯著差異;但多數(shù)情況下,解的魯棒方法產(chǎn)生魯棒性所用的代價(jià)更小,而且也會(huì)在一定程度上帶來質(zhì)量魯棒。針對資源受限項(xiàng)目,VandeVonder等(2006)首先設(shè)計(jì)了RFDFF啟發(fā)式方法,來最大化解的魯棒(即實(shí)際項(xiàng)目開始時(shí)間與計(jì)劃時(shí)間差異的加權(quán)和),該方法用一種巧妙的方法將合適的時(shí)間緩沖分散在進(jìn)度計(jì)劃的各處,并且用該方法插入緩沖后不會(huì)引起資源沖突,從而使得進(jìn)度計(jì)劃在面對干擾事件時(shí)仍能表現(xiàn)出一定程度上的穩(wěn)定性。作者將RFDFF與作為質(zhì)量魯棒代表的關(guān)鍵鏈方法進(jìn)行對比,通過仿真實(shí)驗(yàn),比較了進(jìn)度計(jì)劃的魯棒性與工期之間的權(quán)衡關(guān)系。雖然關(guān)鍵鏈方法旨在保護(hù)項(xiàng)目的工期,使其盡量按期完成,但仿真結(jié)果表明,在很多情況下關(guān)鍵鏈方法并非總是可以帶來質(zhì)量魯棒。VandeVonder等(2007)以質(zhì)量魯棒和解魯棒的復(fù)合目標(biāo)函數(shù),通過實(shí)驗(yàn)評價(jià)了3種主動(dòng)型資源受限項(xiàng)目調(diào)度算法的效果。這三種產(chǎn)生魯棒的基線進(jìn)度計(jì)劃的算法為:①產(chǎn)生質(zhì)量魯棒進(jìn)度計(jì)劃的精確算法:基于分支定界算法產(chǎn)生RCPSP問題的最優(yōu)解,然后在進(jìn)度計(jì)劃的后面加入時(shí)間緩沖。②產(chǎn)生質(zhì)量魯棒進(jìn)度計(jì)劃的近似最優(yōu)算法:基于優(yōu)先規(guī)則的啟發(fā)式算法,利用LateStartTime優(yōu)先規(guī)則,結(jié)合串行進(jìn)度生成機(jī)制,產(chǎn)生基線進(jìn)度計(jì)劃,然后在進(jìn)度計(jì)劃的后面加入時(shí)間緩沖。③產(chǎn)生解的魯棒進(jìn)度計(jì)劃的近似最優(yōu)算法:利用RFDFF算法產(chǎn)生時(shí)間緩沖,將緩沖加入到RCPSP問題最優(yōu)解對應(yīng)的進(jìn)度計(jì)劃中。實(shí)驗(yàn)表明,該方法綜合表現(xiàn)最好。Hazir等(2010)研究了工期不確定條件下,帶有工期拖延懲罰、提前獎(jiǎng)勵(lì)的離散時(shí)間-成本權(quán)衡問題。作者建立隨機(jī)規(guī)劃模型,在給定預(yù)算的條件下,求解最大化利潤和魯棒的進(jìn)度計(jì)劃。Jaskowski和Biruk(2011)將主動(dòng)型調(diào)度方法應(yīng)用于建筑項(xiàng)目,以式(6)為目標(biāo),基于仿真和數(shù)學(xué)規(guī)劃的方法,求解魯棒的進(jìn)度計(jì)劃。Deblaere等(2011)提出了一種新穎的主動(dòng)型調(diào)度方法,稱為“主動(dòng)型調(diào)度策略”,可以看作是魯棒調(diào)度與隨機(jī)調(diào)度在某種程度上結(jié)合。該主動(dòng)型調(diào)度策略利用隨機(jī)工期的分布信息,以進(jìn)度計(jì)劃魯棒性為目標(biāo),求解一個(gè)動(dòng)態(tài)的活動(dòng)執(zhí)行策略以及一個(gè)預(yù)測性的活動(dòng)開始時(shí)間向量。作者在求解過程中采用了基于仿真的下降算法和基于報(bào)童問題的方法。Lambrechts等(2008)提出了多種資源不確定條件下的主動(dòng)型調(diào)度方法:①基于CIW優(yōu)先規(guī)則的啟發(fā)式方法;②基于資源緩沖的方法(在生成進(jìn)度計(jì)劃時(shí),以小于最大資源獲得量的數(shù)值作為資源限制,將資源不確定性轉(zhuǎn)化為時(shí)間不確定性進(jìn)行處理);③基于時(shí)間緩沖的方法(該方法既可單獨(dú)使用,也可與資源緩沖法結(jié)合)。在不確定資源的分布信息是可以獲得的情況下,Lambrechts等(2011)基于概率論,用解析方法分析了意外的資源短缺這一干擾事件對活動(dòng)工期的影響,基于資源緩沖方法,將資源不確定性轉(zhuǎn)化為時(shí)間不確定性。在此基礎(chǔ)上,比較了幾種向進(jìn)度計(jì)劃插入時(shí)間緩沖以實(shí)現(xiàn)進(jìn)度計(jì)劃魯棒的方法:基于仿真的方法、基于代理目標(biāo)函數(shù)的方法和STC方法。項(xiàng)目時(shí)間-成本權(quán)衡是一類經(jīng)典的項(xiàng)目調(diào)度問題,魯棒優(yōu)化已在此類問題上出現(xiàn)了成功應(yīng)用。Cohen(2007)用區(qū)間數(shù)對不確定的工期和成本建模,基于魯棒優(yōu)化理論,建立線性時(shí)間成本權(quán)衡問題的魯棒優(yōu)化模型,獲取魯棒的進(jìn)度計(jì)劃執(zhí)行策略,使得面對不確定的工期的任何一個(gè)場景,都能保證項(xiàng)目按期完工。Hazir等(2011)假設(shè)活動(dòng)工期、活動(dòng)執(zhí)行模式是確定的,成本不確定。用區(qū)間數(shù)對成本的不確定性建模,基于Bertsimas和Sim(2003)的魯棒離散優(yōu)化框架,采用混合整數(shù)規(guī)劃對時(shí)間成本權(quán)衡中的“截止日期”問題建立了3個(gè)不同的優(yōu)化模型,并分別設(shè)計(jì)了基于Benders分解的精確算法和禁忌搜索啟發(fā)式算法進(jìn)行求解。Goh等(2010)基于Bertsimas和Sim的魯棒離散優(yōu)化框架,研究了工期不確定條件下的趕工問題,其目標(biāo)是最小化項(xiàng)目拖期懲罰成本+趕工成本的基礎(chǔ)上,并保證項(xiàng)目計(jì)劃的穩(wěn)定性。Deblaere等(2007)研究了工期不確定條件下的