基于圖的廣度搜索的進(jìn)度生成機(jī)制

李小鵬，李存斌，龐南生

(華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，北京 102206)

1 引言

資源受限的項(xiàng)目調(diào)度問題(Resource-Constrained Project Scheduling Problem，RCPSP)在滿足資源約束和任務(wù)緊前關(guān)系約束的前提下追求項(xiàng)目工期最短，以最大化資源的利用率[1]。

精確算法、啟發(fā)式算法及元啟發(fā)式算法是RCPSP問題求解的基本算法：1)動態(tài)規(guī)劃法、0-1規(guī)劃法、分支定界法等是常見的精確算法，其中分支定界法效果最好，研究和應(yīng)用也最為廣泛[2]，精確算法雖然能夠求得問題的精確解，但RCPSP為NP-hard問題，對于任務(wù)數(shù)量較多的大型項(xiàng)目，精確算法很難在可接受的時(shí)間內(nèi)求得最優(yōu)解；2)啟發(fā)式算法則比較豐富，有基于優(yōu)先規(guī)則的啟發(fā)式算法、精簡分支定界法、基于整數(shù)規(guī)劃的啟發(fā)式算法、分離弧方法和局部搜索技術(shù)等[3]，基于任務(wù)優(yōu)先規(guī)則的啟發(fā)式算法具有邏輯直觀且易于理解、計(jì)算速度快等特點(diǎn)，可用于產(chǎn)生元啟發(fā)式算法所需的初始解，因此為多數(shù)商業(yè)項(xiàng)目管理軟件所采用[4]。3)元啟發(fā)式算法多采用智能搜索算法，通過對任務(wù)優(yōu)先級或者任務(wù)列表進(jìn)行編碼，在此基礎(chǔ)上進(jìn)行編碼尋優(yōu)，再通過傳統(tǒng)的并行或串行機(jī)制進(jìn)行解碼過程實(shí)現(xiàn)，目前研究過程中涉及較多的元啟發(fā)式算法有遺傳算法[5]、人工魚群[6]、人工免疫算法[7]、粒子群算法[8-9]、模擬退火算法[10]以及禁忌搜索算法[11]等。

基于優(yōu)先規(guī)則的啟發(fā)式算法由進(jìn)度生成機(jī)制(Schedule Generation Scheme, SGS)和優(yōu)先規(guī)則兩部分構(gòu)成。進(jìn)度生成機(jī)制能夠從零開始通過逐漸擴(kuò)展局部的任務(wù)計(jì)劃來生成一個完整可行的項(xiàng)目調(diào)度計(jì)劃；優(yōu)先規(guī)則對備選任務(wù)集合中的任務(wù)以一定的規(guī)則賦予優(yōu)先權(quán)，對優(yōu)先權(quán)最大的任務(wù)進(jìn)行調(diào)度[12]。

大多數(shù)學(xué)者在研究RCPSP問題的啟發(fā)式算法時(shí)，關(guān)注的焦點(diǎn)都是任務(wù)優(yōu)先規(guī)則。Cooper[13]最早提出了一些與網(wǎng)絡(luò)結(jié)構(gòu)中任務(wù)間緊前緊后關(guān)系相關(guān)的優(yōu)先規(guī)則，有最多緊后任務(wù)(Most Immediate Successor，MIS)、最多后續(xù)任務(wù)(Most Total Successors, MTS)和最大秩序權(quán)重(Greatest Rank Positional weight,GRPW)等；針對任務(wù)的資源占用量，Schirmer[14]提出了總資源需求(Total Resource Demand,TRD)和總資源稀缺度(Total Resource Scarcity,TRS),Klein[15]提出了最大資源需求(Greatest Resource Demand, GRD)等優(yōu)先規(guī)則算法。有些學(xué)者則根據(jù)調(diào)度方案的不同設(shè)計(jì)了不同的優(yōu)先規(guī)則，Kolisch[16]針對并行進(jìn)度生成機(jī)制提出了最壞自由時(shí)差(Worst Case Slack,WCS)、平均自由時(shí)差(Average Case Slack,ACS)等優(yōu)先規(guī)則；齊東海等[17]則提出了適用于并行機(jī)制的資源調(diào)度方法(Resource Schedule Method, RSM)和改進(jìn)資源調(diào)度方法(Improved Resource Schedule Method,IRSM)等。

進(jìn)度生成機(jī)制是大多數(shù)RCPSP啟發(fā)式算法的核心。根據(jù)擴(kuò)展方式的不用，SGS可以分為以任務(wù)為階段變量的串行進(jìn)度生成機(jī)制(Serial Schedule Generation Scheme，SSGS)和以時(shí)間為階段變量的并行進(jìn)度生成機(jī)制(Parallel Schedule Generation Scheme，PSGS)。Kolish[16]研究指出，SSGS生成的調(diào)度方案是積極調(diào)度計(jì)劃，而PSGS生成的調(diào)度方案是非延遲調(diào)度計(jì)劃。在進(jìn)一步研究中，學(xué)者們提出了一些更加靈活的進(jìn)度生成機(jī)制。李菲[19]研究了多回合算法，這種算法不同于傳統(tǒng)的單回合算法，可以生成多個調(diào)度方案，多優(yōu)先規(guī)則法(Multi-priority Rule Approach)是一種常見的多回合算法，根據(jù)不同的優(yōu)先規(guī)則生成多個調(diào)度方案；Li和Willis[20]提出了正向逆向調(diào)度法，該方法利用一種進(jìn)度生成機(jī)制，反復(fù)進(jìn)行正向和逆向排序，得到一組進(jìn)度計(jì)劃，Kolish和Hartmann[3]對各種算法進(jìn)行比較后表明，該算法可有效改進(jìn)解的質(zhì)量；邵浩等[21]針對帶有緩沖區(qū)的資源調(diào)度問題，提出了使用滾動時(shí)域策略的啟發(fā)式算法，使得調(diào)度過程中產(chǎn)生的費(fèi)用最?。会槍в谢顒又丿B的多模式資源受限項(xiàng)目調(diào)度問題，初梓豪等[22]和于靜等[23]通過對進(jìn)度生成機(jī)制的改進(jìn)，通過遺傳算法建立了新的進(jìn)度生成機(jī)制編碼模式；楊子蘭等[24]針對資源受限的指派問題，基于貪婪算法給出了一種啟發(fā)式算法，通過將問題分解為子問題集得到最優(yōu)解的集合。

綜上可見，學(xué)者們針對優(yōu)先規(guī)則做了大量的研究，但是很少有文獻(xiàn)針對進(jìn)度生成機(jī)制進(jìn)行創(chuàng)新，本文基于數(shù)據(jù)結(jié)構(gòu)中圖的廣度遍歷搜索原理，對傳統(tǒng)的進(jìn)度生成機(jī)制進(jìn)行了改進(jìn)，提出了一種考慮任務(wù)節(jié)點(diǎn)在AON圖中位置的基于圖的廣度搜索的新的進(jìn)度生成機(jī)制，并通過算例與傳統(tǒng)進(jìn)度生成機(jī)制進(jìn)行了比較，證明了新算法的性能。

2 新機(jī)制的提出

2.1 廣度優(yōu)先搜索

廣度優(yōu)先搜索是連通圖的一種遍歷策略，因?yàn)樗乃枷胧菑囊粋€頂點(diǎn)V0開始，輻射狀地優(yōu)先遍歷其周圍較廣的區(qū)域，故稱作廣度優(yōu)先遍歷或廣度優(yōu)先搜索，簡稱為廣度搜索。

圖的廣度優(yōu)先搜索是以圖的廣度優(yōu)先分層為基礎(chǔ)。圖的廣度優(yōu)先分層就是要識別出圖中每個節(jié)點(diǎn)屬于的層次，即給每個節(jié)點(diǎn)編一個層次號。但是，圖本身是非層次結(jié)構(gòu)，所以分層時(shí)，應(yīng)先確定一個參考點(diǎn)，將它的層次指定為起始層(第1層)，然后根據(jù)一定規(guī)則對所有節(jié)點(diǎn)進(jìn)行分層。圖的廣度優(yōu)先搜索從起始層開始，按照層次順序依次對各層節(jié)點(diǎn)進(jìn)行搜索。圖的廣度優(yōu)先分層及廣度優(yōu)先遍歷順序示意圖如圖1和圖2所示。

下面給出以節(jié)點(diǎn)v0為參考點(diǎn)的圖的廣度優(yōu)先搜索的一般步驟(這里用Level(v)表示結(jié)點(diǎn)v的廣度優(yōu)先分層的層號)：

步驟1選擇初始節(jié)點(diǎn)v0，令節(jié)點(diǎn)v0的層次Level(v0)=1；

步驟2按照節(jié)點(diǎn)次序?qū)γ恳粋€節(jié)點(diǎn)v(v≠v0)分層，若存在v0到v的通路，則令：

Level(v)=1+MINu{Level(u)|是圖的邊}

否則令Level(v)=∞，直到所有節(jié)點(diǎn)都被分層。

步驟3從v0出發(fā)，按圖的廣度優(yōu)先分層的層次的大小次序訪問節(jié)點(diǎn)，即先訪問完第一層上節(jié)點(diǎn)，然后依次訪問所有第二層上節(jié)點(diǎn)，直到訪問完所有層次，同層上節(jié)點(diǎn)可按鄰接點(diǎn)次序或節(jié)點(diǎn)標(biāo)號大小次序訪問。

圖1 圖的廣度優(yōu)先分層示意圖

圖2 圖的廣度優(yōu)先遍歷順序示意圖

2.2 新機(jī)制的提出及定義

圖的廣度優(yōu)先搜索實(shí)現(xiàn)了對有向圖按照層次進(jìn)行遍歷，但是，進(jìn)度生成機(jī)制不僅要求對AON圖中的任務(wù)節(jié)點(diǎn)進(jìn)行遍歷，還要求在遍歷的過程中根據(jù)優(yōu)先規(guī)則進(jìn)行調(diào)度。因此，在圖的廣度搜索算法和傳統(tǒng)進(jìn)度生成機(jī)制的基礎(chǔ)上，本文提出了基于圖的廣度搜索算法的進(jìn)度生成機(jī)制(Schedule Generation Scheme Based on Breadth First Search of Graph，BSSGS)。

BSSGS不同于傳統(tǒng)的SSGS和PSGS算法。SSGS和PSGS在調(diào)度過程每一階段中動態(tài)生成任務(wù)集合，而BSSGS的任務(wù)集合生成及任務(wù)層次劃分則在調(diào)度前完成，任務(wù)調(diào)度在分層基礎(chǔ)上進(jìn)行。所以，將BSSGS機(jī)制分成兩個模塊：(1)分層模塊：根據(jù)AON圖結(jié)構(gòu)對任務(wù)節(jié)點(diǎn)進(jìn)行分層；(2)調(diào)度模塊：根據(jù)分層結(jié)果，按照優(yōu)先規(guī)則進(jìn)行調(diào)度。

在分層模塊中，以AON圖中的虛擬開始任務(wù)為初始節(jié)點(diǎn)(第1層)，以虛擬結(jié)束任務(wù)為最后一層，AON圖中任一任務(wù)節(jié)點(diǎn)均根據(jù)緊前緊后關(guān)系被分層，分層過程遵循以下原則：(1)任務(wù)節(jié)點(diǎn)的層次大于其緊前任務(wù)層次，且等于所有緊前任務(wù)的最大層次加一；(2)只有任務(wù)節(jié)點(diǎn)的所有緊前任務(wù)都已分層，才對該任務(wù)節(jié)點(diǎn)進(jìn)行分層；(3)任務(wù)節(jié)點(diǎn)分層唯一確定，且僅與AON圖網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)。

在BSSGS的分層過程中，根據(jù)動態(tài)任務(wù)分層情況定義三個互不相交的集合：

定義1已分層任務(wù)集合(Leveled set)，記為L，包括所有已經(jīng)分層的任務(wù)；

定義2當(dāng)前層任務(wù)集合(Current level set)，記為C，包括所有滿足分層條件，正在分層的任務(wù)；

定義3候選任務(wù)集合(Decision set)，記為D，D中包含所有尚未分層的任務(wù)中，其緊前任務(wù)都在已分層任務(wù)集合和當(dāng)前層任務(wù)集合中，并且至少有一個緊前任務(wù)在當(dāng)前層任務(wù)集合中的任務(wù)節(jié)點(diǎn)。即滿足以下關(guān)系的任務(wù)j：

D={j|{j?L∪C}∩{Pj∩C≠φ}

∩{Pj?(L∪C)}}

(1)

以圖3所示單項(xiàng)目中三個集合間關(guān)系示意圖為例，當(dāng)任務(wù)節(jié)點(diǎn)1、2、3進(jìn)入已分層任務(wù)集合時(shí)，可得到當(dāng)前層任務(wù)集合包含任務(wù)4、6，候選任務(wù)集合包含任務(wù)5、7。

圖3 L、C、D三個任務(wù)集合關(guān)系示意圖

在分層基礎(chǔ)上，對任務(wù)節(jié)點(diǎn)根據(jù)優(yōu)先規(guī)則進(jìn)行調(diào)度，調(diào)度過程遵循以下規(guī)則：(1)進(jìn)度生成過程以層次為階段變量；(2)在每一階段內(nèi)，根據(jù)優(yōu)先規(guī)則對任務(wù)進(jìn)行調(diào)度，直到該層次任務(wù)集合所有任務(wù)都被調(diào)度；(3)在不同層次任務(wù)集合間，按照層次由小到大順序依次進(jìn)行調(diào)度。

在一個包含J個任務(wù)的單項(xiàng)目調(diào)度問題中，將J個任務(wù)分成n(n≤J)個不同的層次，對層次任務(wù)集合和階段變量定義如下：

定義4層次任務(wù)集合Ki(i=1,2,…,n)，集合Ki包含所有層次標(biāo)號為i的任務(wù)；

定義5階段變量g(g=1,2,…,n)，一個分為n個層次的項(xiàng)目共有n個階段

圖4 階段劃分及調(diào)度次序示意圖

以圖4所示單項(xiàng)目中調(diào)度的階段劃分和調(diào)度次序示意圖為例。該項(xiàng)目可分為5層，相應(yīng)分為5個階段，任務(wù)調(diào)度先在層內(nèi)進(jìn)行，后依次在層次間進(jìn)行。

2.3 新機(jī)制與傳統(tǒng)機(jī)制區(qū)別

BSSGS相較于傳統(tǒng)的SSGS和PSGS有以下幾點(diǎn)區(qū)別(表1)：

(1)BSSGS以層次為階段變量，而SSGS和PSGS分別以任務(wù)和時(shí)間為階段變量。在一個含有J個任務(wù)的單項(xiàng)目調(diào)度問題中，SSGS的階段數(shù)必然為J，BSSGS和PSGS則小于等于J。

(2)BSSGS生成的進(jìn)度計(jì)劃與SSGS相同，都是積極進(jìn)度計(jì)劃，也即生成的進(jìn)度計(jì)劃在滿足緊前緊后關(guān)系和資源約束的情況下，不可能左移任一任務(wù)的開始時(shí)間而不造成其他任務(wù)延遲。PSGS生成的進(jìn)度計(jì)劃則是非延遲進(jìn)度計(jì)劃。

(3)BSSGS的時(shí)間復(fù)雜度與SSGS和PSGS相同，都是O(J2,K)，程序運(yùn)行效率與傳統(tǒng)算法相同。

(4)對于目標(biāo)函數(shù)為常規(guī)目標(biāo)函數(shù)的資源受限問題來說，BSSGS的搜索空間和PSGS一樣都小于SSGS。

(5)BSSGS是在搜索出任務(wù)橫向?qū)哟侮P(guān)系基礎(chǔ)上，在同一層次內(nèi)部進(jìn)行的搜索，是橫向結(jié)構(gòu)關(guān)系和縱向的優(yōu)先規(guī)則結(jié)合的二維搜索。與BSSGS相似，PSGS則是以時(shí)間為橫向搜索出滿足約束的候選集合，在候選集合中按優(yōu)先規(guī)則進(jìn)行縱向搜索的二維搜索。SSGS不同于二者，是僅需滿足緊前緊后關(guān)系的一維搜索。

表1 BSSGS與傳統(tǒng)機(jī)制比較

3 BSSGS的算法實(shí)現(xiàn)

3.1 RCPSP基本模型

本文研究的內(nèi)容主要針對資源受限的單項(xiàng)目調(diào)度問題，故將涉及K種可更新資源和J個任務(wù)的目標(biāo)函數(shù)為項(xiàng)目工期最小化的的RCPSP問題模型描述如下：

mincJ

(2)

(3)

(4)

其中，j(j=1,2…,J)為任務(wù)序號,T為項(xiàng)目工期上限，t(t=1,2…,T)為時(shí)段序號，K為項(xiàng)目可更新資源種數(shù)，k(k=1,2…,T)為資源序號，pj為任務(wù)j的工期，Pj為任務(wù)j的緊前任務(wù)集合，sj為任務(wù)j的開始時(shí)間，At為時(shí)刻t處于工作狀態(tài)的任務(wù)集合，Rk為可更新資源k的供給量，rjk為任務(wù)j每期所需的可更新資源的數(shù)量。

3.2 BSSGS步驟

對于含有J個任務(wù)的單項(xiàng)目用BSSGS進(jìn)行調(diào)度，共分為兩個模塊部分：分層模塊和任務(wù)調(diào)度模塊。

(1)分層模塊步驟如下：

步驟1初始化已分層任務(wù)集合L和當(dāng)前層任務(wù)集合C，令L=φ，C={1}，更新候選任務(wù)集合D,初始化當(dāng)前層號i=1。

步驟2對當(dāng)前層任務(wù)集合C中任務(wù)編號為層次i，并將C中任務(wù)賦予i層任務(wù)集合Ki，更新候選任務(wù)集合D。

步驟3判斷候選任務(wù)集合D是否為空集，如果D為空集，則分層結(jié)束，進(jìn)入項(xiàng)目調(diào)度模塊；否則，進(jìn)入步驟4。

步驟4將C中任務(wù)并入已分層任務(wù)集合L，將候選任務(wù)集合D中任務(wù)放入集合C，更新i。即：L=L∪C，C=D，i=i+1。返回步驟2。

(2)任務(wù)調(diào)度模塊步驟如下：

步驟1設(shè)定階段變量初值g=1。

步驟2根據(jù)階段變量g，確定該階段的層次任務(wù)集合Kg，根據(jù)優(yōu)先規(guī)則從Kg選擇一個任務(wù)j*，如果有兩個任務(wù)優(yōu)先次序相同，則選擇打破平局的補(bǔ)充規(guī)則(Tie-breaker)進(jìn)行選擇。

步驟3在符合緊前關(guān)系和資源約束條件下安排j*最早開始時(shí)間Sj*及所需資源rj*k。

由于任務(wù)j*要滿足緊前關(guān)系約束，因此j*的開始時(shí)間的下限為：

(5)

同時(shí)，該開始時(shí)間還要滿足資源約束條件，所以實(shí)際可行的開始時(shí)間Sj*為：

Sj*=min{t|(LB(Sj*)≤t≤LSj*)∧(rj*k≤Rk(τ)，?τ∈[t+pj*],?k)}

(6)

其中LSj*為任務(wù)j*根據(jù)項(xiàng)目時(shí)間上限T確定的最晚開始時(shí)間；Rk(t)為可更新資源k在時(shí)段t上的剩余供應(yīng)量。

步驟4更新各時(shí)段剩余資源Rk(t)。

對于可更新資源k，在分配j*后剩余資源供應(yīng)量(Residual availability)為：

(7)

步驟5將任務(wù)j*從層次Kg任務(wù)集合中刪除。

步驟6判斷Kg是否為空，如果為空則進(jìn)入步驟7；否則進(jìn)入步驟2。

步驟7判斷j*是否為最后一個任務(wù)J，如果是則結(jié)束調(diào)度；否則，令階段變量增加，即g=g+1，進(jìn)入步驟2。

3.3 BSSGS算法流程圖及偽代碼

BSSGS的算法流程圖如圖5所示：

圖5 BSSGS程序流程圖

BSSGS的偽代碼如下所示：

Procedure of improved serial schedule generation scheme based on Breadth First Search of Graph(BSSGS)

BEGIN

/*PART1*/

INIT: L:=φ; C:=1; i:=1，g：=1；

DO

Ki:=C;

UPDATE D;

L:=LC;

C:=D;

i:=i+1;

WHILE D=φ

/*PART2*/

DO

DO

SELECT j* from Kg;

/*according to some priority rule*/

Kg= j*/ Ki;

ASSIGN sj*；

/*as early as possilble*/

UPDATE Rk(t)；

WHILE Kg=φ

g++；

WHILE j*=J

END

4 新機(jī)制與傳統(tǒng)機(jī)制的實(shí)例對比分析

圖6展示了一個J=12的單項(xiàng)目調(diào)度AON圖，該項(xiàng)目只有一種可更新資源(K=1)，資源容量(R=5)，任務(wù)1和任務(wù)12為虛任務(wù)，表示項(xiàng)目的開始和結(jié)束，各任務(wù)的工期Pj和資源需求量rj均標(biāo)注在圖中。

圖6 某資源受限項(xiàng)目AON圖

分別利用SSGS、PSGS和BSSGS進(jìn)行調(diào)度，選定最短工期(Shortest Processing Time，SPT)為任務(wù)調(diào)度優(yōu)先規(guī)則，設(shè)定“任務(wù)編號較小”為打破平局的補(bǔ)充規(guī)則(Tie-breaker)。經(jīng)過計(jì)算，運(yùn)用SSGS得到的任務(wù)列表(Activity list)為：(1，8，11，2，5，10，3，6，4，7，9，12)，總工期(Total Processing Time，TPT)為25個單位時(shí)間，如圖7所示。運(yùn)用PSGS得到的任務(wù)列表為：(1，8，2，11，5，3，6，4，10，7，9，12)，總工期為20個單位時(shí)間，如圖8所示。運(yùn)用BSSGS得到的任務(wù)列表為：(1，8，2，3，6，11，5，4，10，7，9，12)，總工期為18個單位時(shí)間，如圖9所示。

圖7 基于SSGS及SPT的項(xiàng)目進(jìn)度計(jì)劃

圖8 基于PSGS及SPT的項(xiàng)目進(jìn)度計(jì)劃

圖9 基于BSSGS及SPT的項(xiàng)目進(jìn)度計(jì)劃

在該實(shí)例中，BSSGS較SSGS得到的總工期少7個單位時(shí)間，較PSGS得到的總工期少2個單位時(shí)間，調(diào)度計(jì)劃優(yōu)于傳統(tǒng)機(jī)制。下面結(jié)合該實(shí)例說明BSSGS較SSGS和PSGS的一些優(yōu)點(diǎn)。

(1)在任務(wù)調(diào)度過程中，BSSGS并未回避局部復(fù)雜網(wǎng)絡(luò)。

對比圖10、11、12中三種調(diào)度機(jī)制的任務(wù)調(diào)度次序，SSGS和PSGS在調(diào)度過程中回避了網(wǎng)絡(luò)結(jié)構(gòu)較為復(fù)雜的3、4、6、7部分，先沿簡單路線對8、11、2、5、10等任務(wù)節(jié)點(diǎn)進(jìn)行了調(diào)度，而BSSGS則很好解決了這一問題。

圖10 基于SSGS及SPT的各任務(wù)調(diào)度次序

圖11基于PSGS及SPT的各任務(wù)調(diào)度次序

圖12 基于BSSGS及SPT的各任務(wù)調(diào)度次序

在運(yùn)用SSGS和PSSGS進(jìn)行任務(wù)調(diào)度時(shí)，對于緊前任務(wù)較少的任務(wù)節(jié)點(diǎn)，只要僅有的緊前任務(wù)調(diào)度完成，該任務(wù)即可進(jìn)入待選集合，而對于緊前任務(wù)較多的任務(wù)節(jié)點(diǎn)，需要調(diào)度的緊前任務(wù)多，進(jìn)入待選集合的機(jī)會相對靠后，造成任務(wù)調(diào)度路線沿網(wǎng)絡(luò)中的簡單部分進(jìn)行，而回避了局部復(fù)雜網(wǎng)絡(luò)。造成方案可能只是優(yōu)先規(guī)則下的局部最優(yōu)而非全局最優(yōu)。BSSGS對局部復(fù)雜網(wǎng)絡(luò)強(qiáng)制分層，避免了這一問題。

(2)BSSGS避免了資源占有量特別大的靠后任務(wù)節(jié)點(diǎn)被提前安排造成的延遲。

分析圖8中的虛線部分任務(wù)5、10和3的調(diào)度，任務(wù)10資源占有量與資源容量相等，由于其被較前安排導(dǎo)致任務(wù)3不能利用任務(wù)5階段剩余的資源，導(dǎo)致了資源的浪費(fèi)和工期的延長。

在用傳統(tǒng)機(jī)制進(jìn)行調(diào)度時(shí)，某些與任務(wù)10一樣，位置靠后、資源占用量大、局部網(wǎng)絡(luò)結(jié)構(gòu)簡單并且優(yōu)先次序靠前的任務(wù)，往往會被較早安排。而當(dāng)其資源占有量特別大時(shí)，會隔斷其前后的剩余資源，導(dǎo)致資源的大量閑置和工期的延長。在用BSSGS進(jìn)行調(diào)度時(shí)，靠后任務(wù)靠后安排，減少了這一情況發(fā)生。

(3)BSSGS對于“關(guān)鍵節(jié)點(diǎn)”及時(shí)進(jìn)行了調(diào)度。

從網(wǎng)絡(luò)圖中可以看到，任務(wù)3后續(xù)任務(wù)多且結(jié)構(gòu)復(fù)雜，是“關(guān)鍵節(jié)點(diǎn)”，對其及時(shí)調(diào)度能避免局部尋優(yōu)。對比圖7、8、9中任務(wù)3的位置，用BSSGS進(jìn)行調(diào)度時(shí)，任務(wù)3的及時(shí)安排，為后續(xù)任務(wù)的調(diào)度提供了條件。

對于AON網(wǎng)絡(luò)中某個直接或間接緊后任務(wù)較多，影響網(wǎng)絡(luò)節(jié)點(diǎn)較多的任務(wù)節(jié)點(diǎn)，我們將其稱為“關(guān)鍵節(jié)點(diǎn)”。在用傳統(tǒng)機(jī)制進(jìn)行調(diào)度時(shí)，某個關(guān)鍵節(jié)點(diǎn)可能會因?yàn)閮?yōu)先次序一直不滿足而遲遲得不到安排，導(dǎo)致后續(xù)優(yōu)先規(guī)則較大節(jié)點(diǎn)得不到安排，尋優(yōu)陷入局部尋優(yōu)。在用BSSGS進(jìn)行調(diào)度時(shí)，不僅考慮任務(wù)的優(yōu)先條件，也兼顧了任務(wù)所處的網(wǎng)絡(luò)位置，較好避免了這一問題。

5 算法分析

為檢驗(yàn)算法的性能，這里采用國際通用的PSPLIB問題庫對算法進(jìn)行測試[26]。運(yùn)用Progen案例生成器生成120組單項(xiàng)目調(diào)度問題，其中項(xiàng)目可更新資源種類K=1，資源量R=15，項(xiàng)目共有任務(wù)數(shù)J=32。分別采用SSGS、PSGS和BSSGS作為進(jìn)度生成機(jī)制，以最短工期(Shortest Processing Time，SPT)、最長工期(Longest Processing Time，LPT)、最大資源需求(Greatest Resource Demand，GRD)、最多緊后任務(wù)(Most Immediate Successors，MIS)和最多后續(xù)任務(wù)(Most Total Successors, MTS)、總資源需求(Total Resource Demand，TRD)為優(yōu)先規(guī)則對算例進(jìn)行調(diào)度，得到新機(jī)制在各優(yōu)先規(guī)則下的調(diào)度最優(yōu)方案分布如圖13-18所示，圖中黑色節(jié)點(diǎn)為新機(jī)制與傳統(tǒng)并行和串行機(jī)制相比工期較小的算例。

將新機(jī)制與傳統(tǒng)機(jī)制進(jìn)行對比，得到新機(jī)制(BSSGS)與串行機(jī)制(SSGS)、并行機(jī)制(PSGS)下各優(yōu)先規(guī)則的平均最短工期、資源利用率和最優(yōu)調(diào)度方案率等新機(jī)制性能結(jié)果如表2所示。從表2可以看出，新機(jī)制在LPT、SPT、MIS、MTS等與工期和任務(wù)相關(guān)的優(yōu)先規(guī)則下表現(xiàn)較優(yōu)，而在GRD、TRD等與資源相關(guān)的優(yōu)先規(guī)則下表現(xiàn)介于串行和并行機(jī)制之間。

表2 SSGS、PSGS和BSSGS算法效果比較

(1)平均最短工期比較

由表2可知，當(dāng)優(yōu)先規(guī)則為LPT、SPT、MIS和MTS時(shí)，用BSSGS得到平均工期均優(yōu)于傳統(tǒng)SSGS和PSGS，當(dāng)優(yōu)先規(guī)則為GRD和TRD時(shí)，用BSSGS得到的平均工期好于SSGS但較PSGS長；BSSGS在優(yōu)先規(guī)則為SPT、LPT、MTS和MIS時(shí)，表現(xiàn)較好，平均工期相比SSGS下降了5.12、2.7、3.17和1.63個單位，相比PSGS降低了1.24、1.77、1.47和0.25個單位；在優(yōu)先規(guī)則為GRD和TRD等與資源相關(guān)時(shí)，BSSGS較SSGS降低了0.52和0.91個單位，但高于PSGS分別2.88和1.79個單位?？梢夿SSGS算法在優(yōu)先規(guī)則為SPT、LPT、MIS和MIS時(shí)都較傳統(tǒng)算法性能更好，尤其適合于優(yōu)先規(guī)則SPT和MTS。

(2)資源利用率比較

平均工期僅從時(shí)間方面表征了算法的優(yōu)劣，資源利用率同樣也是項(xiàng)目調(diào)度算法追求的最優(yōu)目標(biāo)之一，從表2可知，除了優(yōu)先規(guī)則為GRD和TRD時(shí)，BSSGS平均資源利用率較PSGS較低外，其他情況均優(yōu)于傳統(tǒng)算法；優(yōu)先規(guī)則為LPT、SPT和MTS時(shí)，資源利用率明顯高于傳統(tǒng)算法，相較SSGS增加了3.3%、5.9%和3.7%，相較PSGS增加了2.1%、1.9%和1.85%；優(yōu)先規(guī)則為MIS時(shí)，BSSGS相較SSGS和PSGS分別增長了2%和0.25%?？梢姡珺SSGS在優(yōu)先規(guī)則為SPT、LPT、MTS和MIS都較傳統(tǒng)算法節(jié)約資源，當(dāng)優(yōu)先規(guī)則為SPT、LPT和MTS時(shí)表現(xiàn)更好。

(3)最優(yōu)調(diào)度方案率比較

定義所有算例中不同的算法獲得最短工期的概率為最優(yōu)調(diào)度方案率，最優(yōu)調(diào)度方案率可表征算法獲得最優(yōu)調(diào)度方案的能力。圖13為六種優(yōu)先規(guī)則下用SSGS、PSGS和BSSGS算法獲得的算例最短工期統(tǒng)計(jì)圖，其中對BSSGS獲得最短工期的算例進(jìn)行了標(biāo)注。統(tǒng)計(jì)可知，當(dāng)優(yōu)先規(guī)則為LPT、SPT、MTS和MIS時(shí)，用BSSGS得到最優(yōu)調(diào)度方案概率均大于傳統(tǒng)SSGS和PSGS，當(dāng)優(yōu)先規(guī)則為GRD和TRD時(shí)，用BSSGS得到最短工期的概率小于SSGS和PSGS；BSSGS在優(yōu)先規(guī)則為LPT時(shí)獲得較優(yōu)方案的概率比SSGS和PSGS大20%和30%，在優(yōu)先規(guī)則為SPT時(shí)獲得較優(yōu)方案的概率比SSGS和PSGS大38%和28%，在優(yōu)先規(guī)則為MIS時(shí)獲得較優(yōu)方案的概率比SSGS和PSGS大28%和26%，在優(yōu)先規(guī)則為MTS時(shí)獲得較優(yōu)方案的概率比SSGS和PSGS大19%和11%?？梢姡煌瑱C(jī)制和優(yōu)先規(guī)則下最短工期概率的表現(xiàn)與平均最短工期和資源利用率并不完全一致，MIS在BSSGS機(jī)制下平均工期并非最優(yōu)，但得到最短工期的概率卻比較大。

圖13 不同優(yōu)先規(guī)則下的最短工期統(tǒng)計(jì)圖

6 結(jié)語

本文基于圖的廣度優(yōu)先搜索算法，提出了一種以層次為階段變量的新的進(jìn)度生成機(jī)制，并結(jié)合案例對該新機(jī)制進(jìn)行了分析。對新機(jī)制(BSSGS)進(jìn)行理論和算例分析，得到結(jié)論如下：1)新機(jī)制考慮了AON圖本身的網(wǎng)絡(luò)結(jié)構(gòu)，兼顧了任務(wù)在網(wǎng)絡(luò)圖中的位置因素，在調(diào)度過程中對于局部復(fù)雜網(wǎng)絡(luò)不回避，對關(guān)鍵節(jié)點(diǎn)及時(shí)調(diào)度，避免了局部尋優(yōu)；2)運(yùn)用PSPLIB問題庫對算法性能進(jìn)行測試，結(jié)果顯示在LPT、SPT、MTS和MIS等優(yōu)先規(guī)則時(shí)時(shí)算法在平均最短工期、平均資源利用率及最優(yōu)調(diào)度方案率等方面優(yōu)于串行和并行進(jìn)度生成機(jī)制，且在與優(yōu)先規(guī)則為SPT和MTS時(shí)算法性能突出。