謝 芳 徐 哲 于 靜

(1.山東工商學(xué)院 金融學(xué)院 金融服務(wù)轉(zhuǎn)型升級(jí)協(xié)同創(chuàng)新中心,山東 煙臺(tái) 264005;2.北京航空航天大學(xué) 經(jīng)濟(jì)管理學(xué)院,北京 100191;3.天津理工大學(xué) 管理學(xué)院,天津 300384)

0 引言

資源受限項(xiàng)目調(diào)度問(wèn)題(Resource-constrained project scheduling problem,RCPSP)是指在有限的人員、機(jī)器設(shè)備等可更新資源和活動(dòng)間緊前關(guān)系的約束下,合理配置資源并確定各活動(dòng)的開(kāi)工時(shí)間,從而確保項(xiàng)目的一個(gè)或多個(gè)性能指標(biāo)最優(yōu)[1]。多模式資源受限項(xiàng)目調(diào)度問(wèn)題(Multi-mode RCPSP,MRCPSP)是RCPSP的推廣,項(xiàng)目中每個(gè)活動(dòng)都可能有多種執(zhí)行模式,每種模式對(duì)應(yīng)一個(gè)工期和可更新資源需求量的組合[2]。經(jīng)典的RCPSP和MRCPSP在建筑工程和軟件開(kāi)發(fā)等項(xiàng)目中具有很強(qiáng)的應(yīng)用背景,其優(yōu)點(diǎn)是能充分考慮到可更新資源可用量的限制和優(yōu)化配置問(wèn)題,故能在開(kāi)工前為項(xiàng)目管理者提供進(jìn)度計(jì)劃作為決策依據(jù),不足是并未考慮到實(shí)際項(xiàng)目調(diào)度中的各種不確定因素,如天氣變化、員工勞動(dòng)生產(chǎn)率變化引起得活動(dòng)工期不確定,機(jī)器設(shè)備故障維修、員工請(qǐng)假休假、工作場(chǎng)地因突發(fā)事件停工等導(dǎo)致的可更新資源可用量不確定[3]。因此,如何在不確定情形下有效利用不斷更新的項(xiàng)目數(shù)據(jù)為項(xiàng)目調(diào)度提供動(dòng)態(tài)決策依據(jù),對(duì)指導(dǎo)項(xiàng)目調(diào)度實(shí)踐具有重要意義。

目前,不確定環(huán)境下項(xiàng)目調(diào)度的主要研究方法可分為兩大類:隨機(jī)調(diào)度和魯棒調(diào)度[4]。隨機(jī)調(diào)度是將調(diào)度問(wèn)題視為多階段的決策問(wèn)題,在每個(gè)決策階段,不斷利用調(diào)度策略進(jìn)行決策直至項(xiàng)目完工。對(duì)于活動(dòng)工期不確定環(huán)境下RCPSP的隨機(jī)調(diào)度,學(xué)者們提出了多種靜態(tài)策略,即在項(xiàng)目開(kāi)工前就確定而在調(diào)度過(guò)程中不發(fā)生改變的策略?；谧钚〗杉母拍?Stork[5]分別研究了最早開(kāi)始策略、預(yù)選策略和線性預(yù)選策略,通過(guò)構(gòu)造不同的分支定界算法對(duì)策略之間的差異進(jìn)行了比較。Tsai和Gemmill[6]提出了基于資源的策略,該策略類似于并行調(diào)度生成機(jī)制,并設(shè)計(jì)了相應(yīng)的禁忌搜索算法。 Ballestín[7]以及 Ballestín 和 Leus[8]分別通過(guò)遺傳算法和貪婪隨機(jī)自適應(yīng)搜索過(guò)程研究最優(yōu)活動(dòng)列表策略。Ashtiani等[9]提出的預(yù)處理策略類似于最早開(kāi)始策略和基于資源的策略的結(jié)合,由活動(dòng)對(duì)集合和活動(dòng)列表構(gòu)成,通過(guò)活動(dòng)對(duì)集合添加一些額外的完成-開(kāi)始型緊前關(guān)系約束以解決資源沖突。Rostami等[10]對(duì)預(yù)處理策略進(jìn)行了推廣,除了添加完成-開(kāi)始型約束,還包括開(kāi)始-開(kāi)始型約束。與以上靜態(tài)策略不同的是,Li和Womer[11]研究的是動(dòng)態(tài)策略,該策略在項(xiàng)目執(zhí)行過(guò)程中依據(jù)實(shí)際進(jìn)展情況作出決策,設(shè)計(jì)了Rollout算法在各決策階段處不斷調(diào)用基于約束規(guī)劃的啟發(fā)式算法對(duì)各個(gè)可行活動(dòng)進(jìn)行近似評(píng)估。魯棒調(diào)度可分為主動(dòng)型調(diào)度和響應(yīng)型調(diào)度,主動(dòng)型調(diào)度力爭(zhēng)在項(xiàng)目開(kāi)工前就生成具有一定抗干擾能力的基線進(jìn)度計(jì)劃,在實(shí)際執(zhí)行時(shí)若進(jìn)度計(jì)劃被破壞,則需要調(diào)用響應(yīng)型調(diào)度對(duì)進(jìn)度計(jì)劃進(jìn)行修復(fù),使得實(shí)際進(jìn)度計(jì)劃與基線進(jìn)度計(jì)劃之間的偏差最小[12]。Davari和Demeulemeester[13]指出主動(dòng)型和響應(yīng)型調(diào)度之間的密切相關(guān)性,在工期不確定環(huán)境下構(gòu)建以基線進(jìn)度計(jì)劃的成本和所有偏離成本之和最小化為目標(biāo)的動(dòng)態(tài)規(guī)劃模型,為RCPSP提供主動(dòng)-響應(yīng)型調(diào)度策略。Lambrechts等[14-15]通過(guò)定義單位資源的平均失敗時(shí)間和恢復(fù)時(shí)間對(duì)不確定可更新資源可用量進(jìn)行描述,并設(shè)計(jì)了禁忌搜索算法獲得資源可用量不確定環(huán)境下RCPSP的基線進(jìn)度計(jì)劃和響應(yīng)型調(diào)度策略。在理論分析不確定資源中斷對(duì)活動(dòng)工期影響的基礎(chǔ)上,Lambrechts等[16]通過(guò)插入時(shí)間緩沖的方式構(gòu)造資源不確定環(huán)境下RCPSP的魯棒基線進(jìn)度計(jì)劃。

Zhu等[17]最早對(duì)不確定MRCPSP的響應(yīng)型調(diào)度展開(kāi)研究,針對(duì)工期和資源等各類干擾,構(gòu)建問(wèn)題的混合整數(shù)線性規(guī)劃模型進(jìn)行求解。在活動(dòng)實(shí)際開(kāi)工時(shí)間不早于基線進(jìn)度計(jì)劃開(kāi)工時(shí)間的假設(shè)下,Deblaere等[18]設(shè)計(jì)了一系列精確算法以及禁忌搜索算法對(duì)不確定工期和資源破壞的MRCPSP進(jìn)度計(jì)劃進(jìn)行修復(fù)。李佳媛和何正文[19]考慮可更新資源可用量不確定的MRCPSP的主動(dòng)型調(diào)度,通過(guò)插入資源緩沖的方式最大化進(jìn)度計(jì)劃的魯棒性。Chakrabortty等[20]區(qū)分資源干擾發(fā)生前、干擾發(fā)生到資源恢復(fù)以及資源恢復(fù)后三個(gè)時(shí)段,構(gòu)建混合整數(shù)線性規(guī)劃模型以便MRCPSP的進(jìn)度計(jì)劃在發(fā)生資源中斷時(shí)可以調(diào)用。王艷婷等[21]研究活動(dòng)工期隨機(jī)中斷情況下MRCPSP的主動(dòng)型和響應(yīng)型調(diào)度的權(quán)衡問(wèn)題,以主動(dòng)型調(diào)度中資源占用成本與響應(yīng)型調(diào)度的調(diào)整成本之和的最小化為目標(biāo),在基線進(jìn)度計(jì)劃魯棒值合理設(shè)定的條件下獲得總成本最優(yōu)的調(diào)度方案。

基于以上綜述,目前的研究尚存在較大的局限性:(1)現(xiàn)有不確定環(huán)境下的隨機(jī)項(xiàng)目調(diào)度都是針對(duì)活動(dòng)工期的不確定,且主要集中于靜態(tài)策略的研究,雖然已有少量資源不確定的魯棒調(diào)度研究,但資源不確定環(huán)境下的隨機(jī)調(diào)度研究尚屬空白;(2)相較于不確定RCPSP的研究,由于活動(dòng)的多模式選擇將進(jìn)一步增加問(wèn)題的求解難度,導(dǎo)致不確定環(huán)境下MRCPSP的研究至今還很少。

本文以最小化項(xiàng)目的期望工期為目標(biāo),研究不確定可更新資源可用量環(huán)境下的多模式資源受限項(xiàng)目的隨機(jī)調(diào)度問(wèn)題(Stochastic scheduling of MRCPSP with uncertain resource availabilities,SMRCPSP-URA),主要的創(chuàng)新性工作有:(1)根據(jù)問(wèn)題特點(diǎn)建立由決策階段、狀態(tài)空間、決策空間、狀態(tài)轉(zhuǎn)移函數(shù)及目標(biāo)函數(shù)五部分構(gòu)成的馬爾可夫決策過(guò)程(Markov decision process,MDP)模型;(2)設(shè)計(jì)問(wèn)題的Rollout算法,基準(zhǔn)策略為動(dòng)態(tài)的活動(dòng)-模式優(yōu)先規(guī)則和改進(jìn)的串行調(diào)度生成機(jī)制(Serial schedule generation scheme,SSGS)相結(jié)合的啟發(fā)式算法,利用隨機(jī)資源可用量的蒙特卡洛仿真確定各時(shí)段資源可用量的樣本數(shù)據(jù),綜合評(píng)估后得到各決策階段處的最優(yōu)開(kāi)工活動(dòng)集合及其執(zhí)行模式;(3)通過(guò)算例的實(shí)驗(yàn)研究,系統(tǒng)分析與資源有關(guān)的問(wèn)題參數(shù)、隨機(jī)資源可用量的不確定參數(shù)以及不同優(yōu)先規(guī)則對(duì)問(wèn)題和Rollout算法求解效果和效率的影響,驗(yàn)證算法的有效性。

1 問(wèn)題描述

本文所研究項(xiàng)目共有n+2個(gè)活動(dòng),活動(dòng)0和n+1為虛活動(dòng),分別代表項(xiàng)目的開(kāi)始與結(jié)束,V={1,…,n}為項(xiàng)目所有的非虛活動(dòng),Pj代表活動(dòng)j的緊前活動(dòng)集合。任何非虛活動(dòng)j的執(zhí)行模式集合為Mj,其模式m∈Mj的工期為djm,dj=表示活動(dòng)j的最長(zhǎng)工期,T=表示所有活動(dòng)的最長(zhǎng)工期之和。項(xiàng)目執(zhí)行需要K種可更新資源,活動(dòng)j的執(zhí)行模式m對(duì)資源k的需求量為rjmk。活動(dòng)的執(zhí)行模式唯一,且活動(dòng)一旦開(kāi)工其執(zhí)行模式不再更改。可更新資源k的不確定可用量用隨機(jī)變量來(lái)表示,并且在t-1時(shí)刻可以確定資源k在t時(shí)段的可用量為Rkt,而無(wú)法確定t+1及其之后各時(shí)段的可用量。表示項(xiàng)目活動(dòng)的所有模式對(duì)資源k的最大需求量,假設(shè)≥LRk,即不會(huì)由于資源的隨機(jī)變化而造成整個(gè)項(xiàng)目的停工。不確定可更新資源可用量會(huì)導(dǎo)致正在進(jìn)行的活動(dòng)被迫發(fā)生中斷,本文考慮已開(kāi)工活動(dòng)僅在資源不足的時(shí)候允許被中斷,在資源可行時(shí),被中斷活動(dòng)可以繼續(xù)執(zhí)行,而無(wú)需重新開(kāi)始(preemptresume)[22]。

基于以上假設(shè),SMRCPSP-URA以最小化項(xiàng)目期望工期為目標(biāo),在滿足活動(dòng)間緊前關(guān)系、活動(dòng)的模式選擇、隨機(jī)可更新資源可用量和活動(dòng)可中斷的約束下,動(dòng)態(tài)決策開(kāi)工活動(dòng)及其執(zhí)行模式直至所有活動(dòng)均完工,最后得到項(xiàng)目調(diào)度的滿意解。

2 數(shù)學(xué)模型

馬爾可夫決策過(guò)程(MDP)是隨機(jī)環(huán)境下序貫決策問(wèn)題的常用建模方法[23-24],根據(jù)以上對(duì)本文研究的調(diào)度問(wèn)題的描述,建立如下的MDP模型,主要由五部分構(gòu)成。

2.1 決策階段

可更新資源可用量不可行的時(shí)刻或某種資源的未占用可用量增多的時(shí)刻(包括某活動(dòng)的完工時(shí)刻和某種資源的實(shí)際可用量增多的時(shí)刻)為決策時(shí)刻,例如,若某工程項(xiàng)目某天的施工人員不能滿足正在進(jìn)行的活動(dòng)對(duì)人員的需求,前一天有活動(dòng)完工,或者有新進(jìn)的施工人員,則該天為決策時(shí)刻。由此,總的決策階段的個(gè)數(shù)L≤T,決策階段i∈{0,…,L-1}的決策時(shí)刻記為ti。

2.2 狀態(tài)空間

決策階段i的狀態(tài)定義為Si={Ci,Ai,,γi},其中,Ci和Ai分別表示ti時(shí)的已完工活動(dòng)集合和正在進(jìn)行的活動(dòng)集合,為ti時(shí)確定的n維活動(dòng)執(zhí)行模式向量,為ti時(shí)已執(zhí)行的n維活動(dòng)工期向量,γi表示ti時(shí)實(shí)現(xiàn)的K行T列的資源可用量矩陣。初始狀態(tài)S0={?,?,,γ0},其中,和均為n維零向量,γ0為項(xiàng)目開(kāi)工時(shí)(0時(shí)刻)實(shí)現(xiàn)的資源可用量矩陣,第1列表示K種資源在第1時(shí)段的可用量,其余T-1列均為零向量。結(jié)束狀態(tài),其中為所有活動(dòng)的執(zhí)行模式向量,=(d1m1,…,dnmn)為所有活動(dòng)的實(shí)際工期向量,γL為項(xiàng)目結(jié)束前各時(shí)段的資源可用量矩陣。例如,某工程項(xiàng)目需要4種可更新資源,階段i的決策時(shí)刻為第10天,已完工活動(dòng)為活動(dòng)1、2和3,工期分別為0天、6天和2天,執(zhí)行模式分別為1,2和1,正在進(jìn)行的活動(dòng)為4和5,都已按照第2種執(zhí)行模式開(kāi)工2天,則Ci={1,2,3},Ai={4,5},(1,2,1,2,2,0,…,0),=(0,6,2,2,2,0,…,0),γi的前 4 行 10 列為已實(shí)現(xiàn)的所有資源在前10天的可用量。

2.3 決策空間

若Ui=VCi表示ti時(shí)未完工的活動(dòng)集合,則χ(Si)為ti時(shí)可以調(diào)度的活動(dòng)x及其所對(duì)應(yīng)的可行模式y(tǒng)所組成的二元向量(x,y)的集合:

該式表明階段i處,活動(dòng)x從集合UiAi中選擇,若活動(dòng)x的模式已確定,即ˉMi(x)≠0,則y=ˉMi(x);否則,y應(yīng)從模式集合Mx中選取。對(duì)于可開(kāi)工活動(dòng)x及其可行模式y(tǒng),一方面需要滿足緊前關(guān)系約束,活動(dòng)x的所有緊前活動(dòng)都已經(jīng)完工;另一方面需要滿足資源約束,活動(dòng)x對(duì)資源的需求量與正在進(jìn)行的活動(dòng)對(duì)資源的需求量之和不超過(guò)ti+1時(shí)段的資源可用量γi(k,ti+1)。χ(Si)的滿足資源約束的所有子集構(gòu)成決策階段i處的決策空間,每個(gè)可行子集對(duì)應(yīng)決策階段i處的可開(kāi)工活動(dòng)集合Xi和模式集合Yi,用(Xi,Yi)表示,則(Xi,Yi)?χ(Si)。

2.4 狀態(tài)轉(zhuǎn)移函數(shù)

若Yi為ti+1到ti+1時(shí)刻實(shí)現(xiàn)的K行ti+1-ti列的資源可用量矩陣,則定義SM(·)為狀態(tài)轉(zhuǎn)移函數(shù),即

可以看出,Si+1僅與階段i處的狀態(tài)Si、決策(Xi,Yi)以及矩陣Yi有關(guān),而與階段i之前的決策無(wú)關(guān),該性質(zhì)稱為馬爾可夫性。SM(·)的具體定義如下:

首先,更新Ai∪Xi中任意活動(dòng)j的已執(zhí)行工期(j)為與(ti,ti+1)之間的時(shí)間間隔之和,以及Xi中第l個(gè)活動(dòng)j的執(zhí)行模式(j)為Yi(l),由此,可以更新Ci+1為Ci與ti+1時(shí)Ai∪Xi中完工活動(dòng)集合的并集。然后,依據(jù)Yi更新資源從ti+2到ti+1+1時(shí)段的可用量。最后,若Ai∪XiCi+1中活動(dòng)對(duì)資源的需求量之和大于ti+1時(shí)的資源可用量,即資源不可行,則更新Ai+1為空集;否則,表明ti+1時(shí)資源可行且某種資源的未占用可用量增多,即Ci+1非空或者某種資源k在ti+1+1時(shí)段的可用量大于ti+1時(shí)段的可用量,則更新Ai+1為Ai∪Xi中排除Ci+1。

2.5 目標(biāo)函數(shù)

函數(shù)g(Si,Xi,Yi,Si+1)=ti+1-ti表示狀態(tài)Si時(shí)決策(Xi,Yi)到狀態(tài)Si+1所導(dǎo)致項(xiàng)目工期的增加量,則階段i所對(duì)應(yīng)目標(biāo)函數(shù)可表示為:

上式為從階段i開(kāi)始到階段L-1為止各階段項(xiàng)目工期的增加量之和的期望。在每個(gè)決策階段i處,隨機(jī)調(diào)度以(4)式的最小化為目標(biāo),以期獲得最優(yōu)開(kāi)工活動(dòng)和模式集合,根據(jù)貝爾曼遞歸函數(shù)(Bellman recursion function)[25]可得到:

表明最優(yōu)決策()是使得階段i所對(duì)應(yīng)項(xiàng)目工期的增加量和階段i+1所對(duì)應(yīng)目標(biāo)值之和的期望值最小的χ(Si)的子集。

綜合以上,基于MDP的SMRCPSP-URA的隨機(jī)調(diào)度過(guò)程如圖1所示:在資源不可行或某種資源的未占用可用量增多的時(shí)刻ti進(jìn)行決策,依據(jù)階段i處的狀態(tài)Si,以實(shí)現(xiàn)項(xiàng)目期望工期最小化為目標(biāo)得到(),開(kāi)工()后,

圖1 SMRCPSP-URA的隨機(jī)調(diào)度過(guò)程Figure 1 The stochastic scheduling process of SMRCPSP-URA

根據(jù)階段i與i+1之間實(shí)現(xiàn)的資源可用量矩陣Yi到達(dá)下一個(gè)決策狀態(tài)Si+1,決策過(guò)程不斷推進(jìn),直到所有活動(dòng)都完工,也就是到達(dá)結(jié)束狀態(tài)SL,則調(diào)度結(jié)束。

3 算法設(shè)計(jì)

眾所周知,以上的大規(guī)模MDP模型將面臨高維的狀態(tài)和決策空間,由此導(dǎo)致的“維數(shù)災(zāi)難”使得傳統(tǒng)的隨機(jī)動(dòng)態(tài)規(guī)劃算法很難得到(5)式的精確解,因此,需要針對(duì)問(wèn)題特點(diǎn)設(shè)計(jì)專門(mén)的近似動(dòng)態(tài)規(guī)劃算法尋求高質(zhì)量的近似解。Rollout是起源于動(dòng)態(tài)規(guī)劃的一種近似優(yōu)化方法,實(shí)質(zhì)是基準(zhǔn)策略的一個(gè)向前迭代的過(guò)程,其主要思想是在各決策階段處應(yīng)用基準(zhǔn)策略對(duì)目標(biāo)(4)進(jìn)行近似評(píng)估,該方法高效且易于操作,已被用于成功解決各類隨機(jī)調(diào)度問(wèn)題[11,26-27]。本節(jié)首先提出Rollout算法的基本框架,然后再詳細(xì)介紹算法中所采用的基準(zhǔn)策略,即基于動(dòng)態(tài)活動(dòng)-模式優(yōu)先規(guī)則和活動(dòng)可中斷SSGS的啟發(fā)式算法。

3.1 Rollout算法的框架

表1中展示了Rollout算法的基本框架。在初始化決策階段、決策時(shí)刻、初始狀態(tài)以及時(shí)間計(jì)數(shù)器t=0后,依據(jù)式(1)得到?jīng)Q策階段處可調(diào)度活動(dòng)及其模式集合χ(Si)。在該集合的元素個(gè)數(shù)|χ(Si)|非零且不唯一的情況下,對(duì)各時(shí)段的隨機(jī)資源可用量進(jìn)行蒙特卡洛仿真,具體做法如下:首先,根據(jù)隨機(jī)資源可用量的分布情況展開(kāi)隨機(jī)抽樣,抽樣次數(shù)為|Ω|,得到各類資源在各時(shí)段的可用量樣本集,然后,在資源可用量的確定性樣本和ti時(shí)開(kāi)工(Xi,Yi)的前提下,采用基準(zhǔn)策略對(duì)剩余未完工活動(dòng)進(jìn)行調(diào)度,直至項(xiàng)目結(jié)束,得到該資源樣本對(duì)應(yīng)的項(xiàng)目工期,最后,計(jì)算資源樣本集下項(xiàng)目工期的均值,得到ti時(shí)開(kāi)工(Xi,Yi)的項(xiàng)目期望工期。仿真是不確定情形下目標(biāo)值評(píng)估的常用方法,為了減少仿真次數(shù),縮短算法的運(yùn)行時(shí)間,在算法中設(shè)置(Xi,Yi)的元素個(gè)數(shù)為1,在滿足資源約束的條件下依次加入使得期望工期最小的活動(dòng)及其執(zhí)行模式,直至不能再加入為止,從而得到(,)后開(kāi)工。不斷更新決策階段,根據(jù)t+1時(shí)段的資源可用量更新決策時(shí)刻,并且依據(jù)式(3)更新決策狀態(tài),若Si=SL,則算法終止,否則,繼續(xù)進(jìn)行調(diào)度。

表1 Rollout算法的框架Table 1 The framework of Rollout algorithm

3.2 基準(zhǔn)策略

表2 算法中的活動(dòng)-模式優(yōu)先規(guī)則Table 2 Activity-mode priority rules of algorithm

表2 算法中的活動(dòng)-模式優(yōu)先規(guī)則Table 2 Activity-mode priority rules of algorithm

類型 規(guī)則 極值 公式最晚結(jié)束時(shí)間(LFT) min LFTj活動(dòng)優(yōu)先規(guī)則 最晚開(kāi)始時(shí)間(LST) min LFTj-min m∈Mj{djm}最小總時(shí)差(MSLK) min LFTj-EFTj最短工期模式(SFM) min djm模式優(yōu)先規(guī)則K最小總資源需求(LTRU) min ∑k=1(rjmk×djm)

進(jìn)一步,考慮到資源緊缺引起的活動(dòng)中斷對(duì)進(jìn)度計(jì)劃的影響,對(duì)于活動(dòng)j及其模式m定義如下的中斷優(yōu)先值函數(shù):

上式函數(shù)s(j,m)中,MRSmin(j,m)∈[0,1]表示活動(dòng)j的模式m所需的所有資源在最早可能開(kāi)工時(shí)間ESTj和最遲完工時(shí)間LFTj區(qū)間內(nèi)資源強(qiáng)度的最小值。split為0-1變量,如果活動(dòng)j在ESTj開(kāi)工會(huì)發(fā)生中斷,則split=1,否則,split=0。δs為算法設(shè)定的活動(dòng)中斷參數(shù),若0＜MRSmin(j,m)≤δs,表明資源相對(duì)緊缺,則活動(dòng)j的中斷被鼓勵(lì),否則,資源相對(duì)充足,可以推遲活動(dòng)開(kāi)工時(shí)間而避免中斷。由于ESTj和LFTj是動(dòng)態(tài)變化的,所以,中斷優(yōu)先值也是動(dòng)態(tài)的。在標(biāo)準(zhǔn)化活動(dòng)-模式優(yōu)先值的基礎(chǔ)上再增加式(6)的中斷優(yōu)先值,則形成優(yōu)先規(guī)則 LFT-SFM-SPLIT,LST-SFM-SPLIT,MSLK-SFM-SPLIT,MSLK-LTRU-SPLIT。

表3 活動(dòng)可中斷SSGS的偽代碼Table 3 The pseudocode of SSGSwith activity interruption

4 計(jì)算實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證模型和算法的有效性,對(duì)PSLIB[30]標(biāo)準(zhǔn)算例庫(kù)中J30的MRCPSP算例改編后展開(kāi)計(jì)算實(shí)驗(yàn),各活動(dòng)的模式個(gè)數(shù)為3,資源種類為2。該算例集是目前庫(kù)中不確定MRCPSP調(diào)度研究測(cè)試的最大算例集,含有640個(gè)算例?？筛沦Y源系數(shù)(RF)反映活動(dòng)對(duì)各類可更新資源的需求狀況,取值為0.5和1;可更新資源強(qiáng)度(RS)用于表示活動(dòng)對(duì)每種資源的需要量與資源可用量之間的關(guān)系,取值為0.25、0.5、0.75和 1。 Rollout算法用 MATLAB R2018b編譯,在CPU主頻3.30 GHz,內(nèi)存為8 GB的個(gè)人計(jì)算機(jī)上運(yùn)行。

參考隨機(jī)活動(dòng)工期變量的設(shè)置方法,隨機(jī)資源可用量的均值為算例中可更新資源的可用量Rk,即E()=Rk,服從以下5種隨機(jī)分布[8-9]:

(1)U1:區(qū)間[LRk,2Rk-LRk]內(nèi)的均勻分布,方差為(Rk-LRk)2/3;

(2)U2:區(qū)間[(Rk+LRk)/2,(3Rk-LRk)/2]內(nèi)的均勻分布,方差為(Rk-LRk)2/12;

(3)Exp:指數(shù)分布,均值為Rk,方差為Rk2;

(4)B1:區(qū)間[LRk,2Rk-LRk]內(nèi)的貝塔分布,方差為(Rk-LRk)2/3;

(5)B2:區(qū)間[LRk,2Rk-LRk]內(nèi)的貝塔分布,方差為(Rk-LRk)2/12。

其中,分布U2和B2的方差最小,U1和B1的方差水平居中,分布Exp的方差最大;U1,U2和Exp是對(duì)稱分布,B1和B2是非對(duì)稱分布。分布B1或者B2的對(duì)應(yīng)參數(shù)值(α,β)的取值為α=β=1或者11/2。同時(shí),為了有效權(quán)衡算法求解質(zhì)量和效率之間的關(guān)系,參考Ballestín[7]的研究設(shè)定仿真次數(shù)|Ω|=10。

4.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)結(jié)果排除Rk＜LRk(即上述各隨機(jī)資源可用量分布區(qū)間的下界小于活動(dòng)最大資源需求量)的三個(gè)算例:j3033_9.mm,j3049_1.mm,j3049_2.mm。在隨機(jī)資源可用量的5種不同分布下,基于8種不同優(yōu)先規(guī)則的Rollout算法求解其余所有算例的項(xiàng)目工期、活動(dòng)的中斷次數(shù)和運(yùn)算時(shí)間如表4所示。

考察表4可以看出:

(1)對(duì)于隨機(jī)資源可用量服從U2和Exp分布的項(xiàng)目調(diào)度問(wèn)題,Rollout算法中應(yīng)該選用的優(yōu)先規(guī)則顯然為L(zhǎng)STSFM,相較于其他優(yōu)先規(guī)則,LST-SFM得到的項(xiàng)目工期和活動(dòng)中斷次數(shù)都最小;隨機(jī)資源可用量服從U1和B2分布時(shí),優(yōu)先規(guī)則LFT-SFM對(duì)應(yīng)的項(xiàng)目工期最小,且活動(dòng)中斷次數(shù)(分別為5.73和1.74)與最小中斷次數(shù)(分別為5.58和1.63)之間的差別不大;隨機(jī)資源可用量服從隨機(jī)B1分布時(shí),優(yōu)先規(guī)則MSLK-SFM對(duì)應(yīng)最小的項(xiàng)目工期和幾乎最小的活動(dòng)中斷次數(shù)。這說(shuō)明基于不同優(yōu)先規(guī)則的Rollout算法在不確定資源可用量的不同情形下的求解效果不同,應(yīng)該根據(jù)隨機(jī)資源可用量的分布類型和方差大小選擇表現(xiàn)最優(yōu)的優(yōu)先規(guī)則求解。

(2)對(duì)于隨機(jī)資源可用量的5種分布,U2和B2兩種分布情況下Rollout算法所得解的項(xiàng)目工期、活動(dòng)中斷次數(shù)和算法運(yùn)算時(shí)間最小,U1和B1居中,分布Exp最大。研究結(jié)果表明:當(dāng)不確定資源可用量的方差逐漸增大時(shí),項(xiàng)目工期、活動(dòng)發(fā)生中斷的可能性以及調(diào)度問(wèn)題的求解難度也會(huì)逐漸增大。

(3)Rollout算法中,不考慮活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則(LFT-SFM,LST-SFM,MSLK-SFM,MSLK-LTRU)的求解效果和效率均優(yōu)于考慮活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則(LFT-SFMSPLIT,LST-SFM-SPLIT,MSLK-SFM-SPLIT,MSLK-LTRUSPLIT),這說(shuō)明應(yīng)該采用不考慮活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則來(lái)解決不確定資源可用量環(huán)境下的隨機(jī)項(xiàng)目調(diào)度問(wèn)題。

(4)對(duì)比LFT-SFM,LST-SFM,MSLK-SFM三種優(yōu)先規(guī)則,綜合考慮項(xiàng)目工期和活動(dòng)中斷次數(shù)兩方面指標(biāo),表現(xiàn)最差的為MSLK-LTRU,但是MSLK-LTRU在運(yùn)算時(shí)間方面具有優(yōu)勢(shì)。

前述所提到Buddhakulsomsiri和Kim[22]的研究結(jié)果表明,考慮活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則的求解效果要明顯優(yōu)于不考慮活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則,但是,從表4的分析結(jié)果(3)可以看出,對(duì)于本文所研究的SMRCPSP-URA而言卻并非如此。為了進(jìn)一步檢驗(yàn)活動(dòng)中斷優(yōu)先值對(duì)算法求解確定型與不確定型問(wèn)題效果之間是否存在顯著區(qū)別,對(duì)Rollout算法在采用與不采用活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則之間的項(xiàng)目工期數(shù)據(jù)進(jìn)行配對(duì)樣本T檢驗(yàn),分析結(jié)果見(jiàn)表5。假設(shè)兩組數(shù)據(jù)之間沒(méi)有顯著差異,并設(shè)置置信水平為99%,從表中顯著性水平p≈0.00可以看出,兩組數(shù)據(jù)之間存在顯著性差異,表明不考慮活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則可以顯著提高Rollout算法求解SMRCPSP-URA的績(jī)效。雖然優(yōu)先規(guī)則LFT-SFM,LST-SFM,MSLK-SFM的總體均值都要小于MSLKLTRU,但MSLK-LTRU的標(biāo)準(zhǔn)差最小,表明基于MSLK-LTRU的Rollout算法的表現(xiàn)更加穩(wěn)定。

表5 基于不同優(yōu)先規(guī)則的Rollout算法是否考慮中斷優(yōu)先值所對(duì)應(yīng)配對(duì)樣本的T檢驗(yàn)Table 5 Paired samp le T tests of Rollout algorithms based on priority rulesw ith and w ithout interruption priority value

4.3 參數(shù)分析

為了考察問(wèn)題參數(shù)對(duì)Rollout算法求解質(zhì)量和速度的影響,構(gòu)建如式(7)的線性回歸模型展開(kāi)分析。

在回歸模型中有4個(gè)解釋變量,x1表示可更新資源系數(shù)RF;x2表示可更新資源強(qiáng)度RS;x3表示不確定資源可用量的方差;x4表示SMRCPSP-URA對(duì)應(yīng)的確定型問(wèn)題項(xiàng)目工期上界與下界之間的相對(duì)偏差,代表確定型問(wèn)題求解的難易程度,偏差大表示求解難度大,偏差小表示求解容易。因變量y分別代表基于不考慮活動(dòng)中斷的優(yōu)先規(guī)則(LFT-SFM,LST-SFM,MSLK-SFM,MSLK-LTRU)的Rollout算法求解的項(xiàng)目工期、活動(dòng)中斷次數(shù)和運(yùn)算時(shí)間?；貧w分析的結(jié)果如表6所示,括號(hào)中的數(shù)字代表系數(shù)估計(jì)值的標(biāo)準(zhǔn)誤差,以上四種因素在5%的顯著性水平下的t檢驗(yàn)均顯著,F檢驗(yàn)的p值均為0,衡量指標(biāo)項(xiàng)目工期、活動(dòng)中斷次數(shù)和運(yùn)算時(shí)間用這四種因素表示的擬合度R2均超過(guò)60%,表明三種衡量指標(biāo)都可以較好的用這四種因素來(lái)表示。

表6 線性回歸分析的結(jié)果Table 6 Results of linear regression analysis

以上統(tǒng)計(jì)檢驗(yàn)的結(jié)果表明:(1)活動(dòng)對(duì)可更新資源的需求越大(RF越大),以及不確定資源可用量的變化波動(dòng)越大越會(huì)影響Rollout算法的求解質(zhì)量,同時(shí)也會(huì)降低算法的求解效率;(2)可更新資源的供應(yīng)越充足(RS越大)則越有可能有效提升Rollout算法的求解質(zhì)量和效率;(3)采用Rollout算法求解SMRCPSP-URA的求解質(zhì)量會(huì)隨著其對(duì)應(yīng)確定型問(wèn)題求解難度的增大而表現(xiàn)出明顯的優(yōu)勢(shì),但會(huì)導(dǎo)致活動(dòng)中斷次數(shù)增大和算法運(yùn)算時(shí)間的增加。

5 結(jié)論

本文研究的隨機(jī)調(diào)度問(wèn)題同時(shí)考慮了可更新資源可用量的不確定性、活動(dòng)執(zhí)行模式的多樣性和資源不確定導(dǎo)致的活動(dòng)可中斷性,將不確定可更新資源的可用量建模為隨機(jī)變量,以最小化項(xiàng)目的期望工期為目標(biāo)建立了調(diào)度問(wèn)題的MDP模型,定義可更新資源可用量不可行的時(shí)刻或某種資源的未占用可用量增多的時(shí)刻為決策時(shí)刻,設(shè)計(jì)了基于動(dòng)態(tài)活動(dòng)-模式優(yōu)先規(guī)則和活動(dòng)可中斷SSGS的Rollout算法對(duì)問(wèn)題求解,項(xiàng)目管理者可在決策階段處根據(jù)選定的執(zhí)行模式開(kāi)工相應(yīng)的活動(dòng)直至項(xiàng)目完工。通過(guò)大量的算例實(shí)驗(yàn)研究,我們得出以下結(jié)論:(1)不確定可更新資源可用量的變化波動(dòng)越大,則項(xiàng)目工期、活動(dòng)中斷次數(shù)以及問(wèn)題的求解難度也會(huì)越大;(2)不考慮活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則對(duì)隨機(jī)問(wèn)題的求解效果要優(yōu)于考慮活動(dòng)中斷優(yōu)先值的優(yōu)先規(guī)則;(3)本文所設(shè)計(jì)的Rollout算法對(duì)于解決可更新資源需求小、可更新資源供應(yīng)充足以及相應(yīng)的確定型問(wèn)題求解難度大的算例的效果更好。

本文所研究的SMRCPSP-URA考慮了活動(dòng)工期的不確定和活動(dòng)多執(zhí)行模式,但尚未考慮資源不確定和項(xiàng)目調(diào)度多目標(biāo)等因素,雖然問(wèn)題會(huì)變得更加復(fù)雜,但具有更重要的現(xiàn)實(shí)應(yīng)用背景,有待進(jìn)一步拓展。本文的Rollout算法以優(yōu)先規(guī)則和調(diào)度生成機(jī)制相結(jié)合的啟發(fā)式算法作為基準(zhǔn)策略,簡(jiǎn)便且易于操作,另外,智能優(yōu)化算法也是解決大規(guī)模問(wèn)題的有效途徑,未來(lái)我們將探索更加高效的智能算法作為基準(zhǔn)策略以進(jìn)一步提升Rollout算法的求解性能。