李小鵬，李存斌，龐南生

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

1 引言

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

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

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

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

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

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

2 新機制的提出

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

廣度優(yōu)先搜索是連通圖的一種遍歷策略，因為它的思想是從一個頂點V0開始，輻射狀地優(yōu)先遍歷其周圍較廣的區(qū)域，故稱作廣度優(yōu)先遍歷或廣度優(yōu)先搜索，簡稱為廣度搜索。

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

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

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

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

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

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

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

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

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

2.2 新機制的提出及定義

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

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

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

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

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

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

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

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

∩{Pj?(L∪C)}}

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 RCPSP基本模型

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

mincJ

(2)

(3)

(4)

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

3.2 BSSGS步驟

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

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

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

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

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

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

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

步驟1設定階段變量初值g=1。

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

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

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

(5)

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

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

(6)

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

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

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

(7)

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

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

步驟7判斷j*是否為最后一個任務J，如果是則結(jié)束調(diào)度；否則，令階段變量增加，即g=g+1，進入步驟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 新機制與傳統(tǒng)機制的實例對比分析

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

圖6 某資源受限項目AON圖

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

圖7 基于SSGS及SPT的項目進度計劃

圖8 基于PSGS及SPT的項目進度計劃

圖9 基于BSSGS及SPT的項目進度計劃

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

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

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

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

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

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

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

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

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

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

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

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

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

5 算法分析

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

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

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

(1)平均最短工期比較

由表2可知，當優(yōu)先規(guī)則為LPT、SPT、MIS和MTS時，用BSSGS得到平均工期均優(yōu)于傳統(tǒng)SSGS和PSGS，當優(yōu)先規(guī)則為GRD和TRD時，用BSSGS得到的平均工期好于SSGS但較PSGS長；BSSGS在優(yōu)先規(guī)則為SPT、LPT、MTS和MIS時，表現(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)時，BSSGS較SSGS降低了0.52和0.91個單位，但高于PSGS分別2.88和1.79個單位。可見BSSGS算法在優(yōu)先規(guī)則為SPT、LPT、MIS和MIS時都較傳統(tǒng)算法性能更好，尤其適合于優(yōu)先規(guī)則SPT和MTS。

(2)資源利用率比較

平均工期僅從時間方面表征了算法的優(yōu)劣，資源利用率同樣也是項目調(diào)度算法追求的最優(yōu)目標之一，從表2可知，除了優(yōu)先規(guī)則為GRD和TRD時，BSSGS平均資源利用率較PSGS較低外，其他情況均優(yōu)于傳統(tǒng)算法；優(yōu)先規(guī)則為LPT、SPT和MTS時，資源利用率明顯高于傳統(tǒng)算法，相較SSGS增加了3.3%、5.9%和3.7%，相較PSGS增加了2.1%、1.9%和1.85%；優(yōu)先規(guī)則為MIS時，BSSGS相較SSGS和PSGS分別增長了2%和0.25%?？梢姡珺SSGS在優(yōu)先規(guī)則為SPT、LPT、MTS和MIS都較傳統(tǒng)算法節(jié)約資源，當優(yōu)先規(guī)則為SPT、LPT和MTS時表現(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)計圖，其中對BSSGS獲得最短工期的算例進行了標注。統(tǒng)計可知，當優(yōu)先規(guī)則為LPT、SPT、MTS和MIS時，用BSSGS得到最優(yōu)調(diào)度方案概率均大于傳統(tǒng)SSGS和PSGS，當優(yōu)先規(guī)則為GRD和TRD時，用BSSGS得到最短工期的概率小于SSGS和PSGS；BSSGS在優(yōu)先規(guī)則為LPT時獲得較優(yōu)方案的概率比SSGS和PSGS大20%和30%，在優(yōu)先規(guī)則為SPT時獲得較優(yōu)方案的概率比SSGS和PSGS大38%和28%，在優(yōu)先規(guī)則為MIS時獲得較優(yōu)方案的概率比SSGS和PSGS大28%和26%，在優(yōu)先規(guī)則為MTS時獲得較優(yōu)方案的概率比SSGS和PSGS大19%和11%。可見，不同機制和優(yōu)先規(guī)則下最短工期概率的表現(xiàn)與平均最短工期和資源利用率并不完全一致，MIS在BSSGS機制下平均工期并非最優(yōu)，但得到最短工期的概率卻比較大。

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

6 結(jié)語

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