資源受限項(xiàng)目調(diào)度問(wèn)題的探討

劉 振

（中鐵第四勘察設(shè)計(jì)院集團(tuán)有限公司，430063，武漢∥高級(jí)工程師 ）

PERT（計(jì)劃評(píng)審技術(shù)）和CPM（關(guān)鍵路線法）作為項(xiàng)目管理非常有效的工具，被廣泛應(yīng)用于項(xiàng)目計(jì)劃和控制過(guò)程中。然而這兩種方法都是假設(shè)項(xiàng)目使用的資源是無(wú)限供給的。但在城市軌道交通項(xiàng)目的實(shí)際執(zhí)行過(guò)程中，可以使用的資源往往是受到一定限制的。如設(shè)備的訂貨、設(shè)備基礎(chǔ)和預(yù)埋件的施工等，本來(lái)是平行任務(wù)，但由于受供貨時(shí)間滯后、同型號(hào)不同廠家設(shè)備尺寸差異等影響，有些工序的開始時(shí)間只能向后推遲，待安排在前面的工序完成并且釋放資源后才能開始執(zhí)行。所以，根據(jù)PERT／CPM這兩種方法編制的計(jì)劃在資源受限的情況下一般不能夠得到保證。由此產(chǎn)生了資源受限項(xiàng)目調(diào)度問(wèn)題（Resource－Constrained Project Scheduling Problem，簡(jiǎn)為RCPSP）。該問(wèn)題在理論上屬于NP－h(huán)ard問(wèn)題［1］，即：項(xiàng)目中具有一系列相互關(guān)聯(lián)的任務(wù)，其中，每一個(gè)任務(wù)可以采用幾種模式完成，每一種模式以已知的工期和資源需求量為特征，在滿足緊前關(guān)系和資源約束條件下產(chǎn)生一種使其管理目標(biāo)為最優(yōu)的調(diào)度方案。

1 資源受限項(xiàng)目進(jìn)度問(wèn)題的描述

典型的資源受限項(xiàng)目進(jìn)度問(wèn)題可描述如下［2］：

在一個(gè)項(xiàng)目中，包括J項(xiàng)活動(dòng)，Pj為活動(dòng)j的緊前活動(dòng)集，j∈（1，2，…，J）；活動(dòng)j＝1與活動(dòng)j＝J為虛工作，即活動(dòng)1是唯一最早開始的活動(dòng)，活動(dòng)J是唯一最晚完成的活動(dòng)，均為不消耗資源且執(zhí)行時(shí)間為0的活動(dòng)。T為項(xiàng)目的合同工期。設(shè)活動(dòng)j的完成需要的第r種資源量為kjr，執(zhí)行時(shí)間為dj，第r種資源總量為常量Kr（r＝1，2，…，R），活動(dòng)j的完成時(shí)間為TFj，At為在t時(shí)間段內(nèi)正在進(jìn)行的活動(dòng)集合。典型的資源受限項(xiàng)目進(jìn)度問(wèn)題可建立如下數(shù)學(xué)模型：

式（1）是目標(biāo)函數(shù)，表示項(xiàng)目總工期最短；式（2）代表項(xiàng)目活動(dòng)間的緊前關(guān)系約束；式（3）代表每一階段的資源使用量不能超過(guò)其最大量。

2 資源受限項(xiàng)目調(diào)度問(wèn)題的分類

資源、任務(wù)和目標(biāo)函數(shù)三要素組成了資源受限項(xiàng)目調(diào)度問(wèn)題。資源的不同數(shù)量和類型，任務(wù)錯(cuò)綜復(fù)雜的約束條件，再加上度量不同指標(biāo)的目標(biāo)函數(shù)，形成了種類繁多的RCPSP問(wèn)題。通常采用文獻(xiàn)［3］三段式分類方法對(duì)資源受限的項(xiàng)目調(diào)度問(wèn)題進(jìn)行分類。該方法采用機(jī)器排序的分類形式，用三個(gè)參數(shù)α，β，γ來(lái)描述RCPSP的類型，得到了多數(shù)學(xué)者的認(rèn)同。以下簡(jiǎn)要介紹各段的含義。

1）段α描述問(wèn)題的資源屬性，包含3個(gè)參數(shù)：αl，α2，α3。

參數(shù)αl∈｛0，m｝描述了資源的種類，它可能是空，標(biāo)記為0，也可能是一種資源或者是m種資源，αl＝0或m；參數(shù)α2描述了資源種類的特性。

按照文獻(xiàn)［4］和文獻(xiàn)［5］提出的資源分類法，可分為可更新資源（Renewable Resources）、不可更新資源（Nonrenewable Resources）和雙重資源（Doubly Constrained Resources）三種?？筛沦Y源是指在每個(gè)時(shí)段獲得一定量的資源，這種資源的獲得和消耗是以每一階段為基礎(chǔ)的（如運(yùn)碴汽車和施工人員等）；不可更新資源是指在整個(gè)工期內(nèi)只能獲得一定量的資源（如原材料、能源等）；雙重資源是指資源的獲得和消耗既在工期的每一階段受限，又在整個(gè)工期的總量上受到限制（如掘進(jìn)盾構(gòu)機(jī)等）。雙重約束的資源分配問(wèn)題可以被轉(zhuǎn)化為相應(yīng)的可更新資源和不可更新資源來(lái)處理。

α2∈｛0，1，T，1T，v｝，分別表示：資源類型（缺?。?，可更新資源，不可更新資源，雙重資源，部分可更新資源。

參數(shù)α3∈｛0，vα｝描述了資源的使用量，通常用來(lái)表達(dá)可更新資源。α3＝0，時(shí)，表示可更新資源使用量為常數(shù)；α3＝vα，表示可更新資源使用量為變量。

2）段β描述問(wèn)題的任務(wù)屬性，包含8個(gè)參數(shù)。

參數(shù)β1∈｛0，pmtn，pmtn－rep｝描述了任務(wù)在執(zhí)行時(shí)中斷的可能性。當(dāng)任務(wù)是不允許中斷時(shí)，β1＝0。β1＝pmtn，表示任務(wù)可以在執(zhí)行的過(guò)程中被中斷，然后在中斷點(diǎn)處繼續(xù)加工，任務(wù)中斷前后執(zhí)行的時(shí)間的總和與不中斷的執(zhí)行的時(shí)間是一樣的。此中斷稱為可續(xù)性中斷。β1＝pmtn－rep，表示任務(wù)在執(zhí)行過(guò)程中可被中斷，但不允許在中斷點(diǎn)處繼續(xù)執(zhí)行，必須從頭開始。此中斷被稱為重復(fù)性中斷。

參數(shù)β2∈｛0，cpm，min，gpr，prob｝描述了任務(wù)時(shí)序關(guān)系的約束特征，時(shí)序約束可以用一個(gè)網(wǎng)絡(luò)圖表示。

β2＝0時(shí)，表示任務(wù)相互獨(dú)立，即任務(wù)之間沒有時(shí)序約束。β2＝cpm，表示各任務(wù)之間是無(wú)延誤的完成－開始時(shí)序關(guān)系。β2＝min，表示各任務(wù)具有最小延誤時(shí)間的開始－開始，完成－開始，開始－完成，以及完成—完成的時(shí)序約束關(guān)系。β2＝gpr，表示任務(wù)間具有最小和最大延誤時(shí)間的廣義的時(shí)序約束關(guān)系。這里的最小延誤時(shí)間是指：只有在其緊前任務(wù)開始（完成）一段時(shí)間后該任務(wù)才能開始（完成）；最大延誤時(shí)間是指：任務(wù)應(yīng)該在另一任務(wù)開始（完成）后的某一時(shí)間內(nèi)開始（完成）。β2＝prob，表示任務(wù)的網(wǎng)絡(luò)圖具有一定的概率。

參數(shù)β3∈｛0，rj｝描述任務(wù)的準(zhǔn)備時(shí)間，分別表示：準(zhǔn)備時(shí)間為0，各任務(wù)需要不同的準(zhǔn)備時(shí)間。

參數(shù)β4∈｛0，cont，d｝描述任務(wù)的工期，分別表示：任務(wù)的工期為離散的整數(shù)，任務(wù)的工期為任意實(shí)數(shù)，所有的任務(wù)具有相同的工期。

參數(shù)β5∈｛0，δj，δn｝描述交貨期，分別表示：項(xiàng)目沒有底線約束，任務(wù)的交貨期，項(xiàng)目的交貨期。

參數(shù)β6∈｛0，vr，disc，cont｝描述資源需求的特性，Β6＝0時(shí)，表示任務(wù)在同一執(zhí)行模式下所需資源為常量。β6＝vr，表示任務(wù)在同一執(zhí)行模式下所需的資源是變量，β6＝disc，表示任務(wù)的資源需求量是任務(wù)工期的離散函數(shù)。β6＝cont，表示任務(wù)的資源需求量是任務(wù)工期的連續(xù)函數(shù)。

參數(shù)β7∈｛0，mu，id｝描述任務(wù)的執(zhí)行模式，分別表示：?jiǎn)螆?zhí)行模式，多執(zhí)行模式，模式約束任務(wù)（此時(shí)任務(wù)集合被劃分為不相交的子集，每個(gè)子集中的所有任務(wù)必須以相同的模式來(lái)執(zhí)行）。

參數(shù)β7∈｛0，cj，per，sched｝描述數(shù)據(jù)流的性質(zhì)。β7＝0，表示空。β7＝cj，表示任務(wù)之間的資金流動(dòng)。，表示為靜態(tài)的資金流。，表示任務(wù)之間為正的資金流。β7＝per，表示特定的資金流。β7＝sched，表示既包含資金流又包含時(shí)間流。

3）段γ描述項(xiàng)目調(diào)度問(wèn)題的優(yōu)化目標(biāo)。優(yōu)化的目標(biāo)函數(shù)可分為兩類。一類為正則目標(biāo)函數(shù)，滿足以下兩個(gè)條件：①目標(biāo)函數(shù)是求最小值；②目標(biāo)函數(shù)是完工時(shí)間的單調(diào)非降函數(shù)，例如項(xiàng)目總工期最小、項(xiàng)目總成本最低或項(xiàng)目延誤最小等。另一類為非正則目標(biāo)函數(shù)，例如最大凈現(xiàn)值、提前完工費(fèi)用和誤工費(fèi)用最小等。下面介紹幾種目標(biāo)函數(shù)：γ＝Cmax，表示項(xiàng)目總工期最小。γ＝Tmax，表示項(xiàng)目誤工最小。γ＝nT，表示加權(quán)誤工任務(wù)數(shù)最小。γ＝npv，表示項(xiàng)目?jī)衄F(xiàn)值最大。由上述分類中可以看出，該問(wèn)題模型豐富，且多屬于NP－h(huán)ard問(wèn)題，但求解困難。從20世紀(jì)60年代初至今，資源受限項(xiàng)目調(diào)度問(wèn)題已吸引了大量學(xué)者的注意，有大量的研究成果從不同的角度研究了該問(wèn)題。總的來(lái)說(shuō)，求解該問(wèn)題的算法可分為精確算法與啟發(fā)式算法。智能算法為啟發(fā)式算法的一類分支。對(duì)于城市軌道交通動(dòng)輒上百億元的大項(xiàng)目，應(yīng)用此方法解決其調(diào)度問(wèn)題，具有明顯的優(yōu)勢(shì)。

3 資源受限項(xiàng)目調(diào)度問(wèn)題的求解方法

一般來(lái)講，RCPSP的求解關(guān)鍵要解決算法的表達(dá)形式，除了由算法本身所決定的進(jìn)化機(jī)制外，主要由調(diào)度生產(chǎn)方案、編碼方式和解碼規(guī)則、相鄰解的定義以及初始解的產(chǎn)生這幾個(gè)部分組成。而相鄰解的定義往往由編碼方式和解碼規(guī)則確定［6］；初始解一般是隨機(jī)生成或者根據(jù)特定的編碼方式結(jié)合一些優(yōu)先規(guī)則生成。

3.1 調(diào)度生產(chǎn)方案

調(diào)度產(chǎn)生方案可分為串行調(diào)度方案（SSS）和并行調(diào)度方案（PSS）。兩種方法都是對(duì)一個(gè)不完全計(jì)劃進(jìn)行擴(kuò)展，直至生成一個(gè)完全計(jì)劃。在工期的每個(gè)階段，調(diào)度生產(chǎn)方案都會(huì)形成一個(gè)可行工作集（滿足約束條件），然后根據(jù)某個(gè)優(yōu)先權(quán)規(guī)則從該集合中選取一個(gè)或多個(gè)活動(dòng)安排其進(jìn)度，并將其轉(zhuǎn)移到一個(gè)不完全計(jì)劃集合，直到所有活動(dòng)都安排完成為止。

3.1.1 串行調(diào)度方案

串行調(diào)度方案最早由文獻(xiàn)［7］提出。串行調(diào)度方案包括n（n＝1，…，J）個(gè)階段，每個(gè)階段都存在一個(gè)不完全計(jì)劃集合Sn和一個(gè)滿足緊前關(guān)系約束的可行工作集Dn。在每個(gè)階段，根據(jù)某個(gè)優(yōu)先規(guī)則在集合Dn中選擇一項(xiàng)工作，并指定該工作的開始時(shí)間為滿足緊前關(guān)系約束和資源約束的最早可行時(shí)間（如果有多個(gè)工作具有相同的優(yōu)先權(quán)，優(yōu)先安排編號(hào)小的工作），然后將該工作從集合Dn移動(dòng)到集合Sn中。當(dāng)當(dāng)前階段為n＝J時(shí)，所有的工作都從集合Dn移動(dòng)到集合Sn，Dn為空集。

3.1.2 并行調(diào)度方案

并行調(diào)度生成方案當(dāng)前有兩種算法：Kelley［7］和Brooks（Bedworth and Bailey）［8］。兩種算法有所區(qū)別。當(dāng)前沿用的主要是Brooks（Bedworth and Bailey）的方法。并行調(diào)度方案最多包括J個(gè)階段，每個(gè)階段對(duì)應(yīng)調(diào)度時(shí)間tn；在tn時(shí)間已完成的工作集合為Cn，在tn時(shí)間正在進(jìn)行的工作集合為An。同時(shí)，此時(shí)存在一個(gè)滿足緊前關(guān)系約束與資源約束并可以在tn時(shí)間開始的可行工作集Dn。與串行方案不同的是，并行調(diào)度方案的不完全計(jì)劃工作集由Cn與An兩個(gè)集合構(gòu)成。該方案從階段n到階段n＋1需要兩步：第一步，將tn＋1階段的時(shí)間設(shè)置為An集合中最早完工的工作的完成時(shí)間，然后將An集合內(nèi)完工時(shí)間等于tn＋1時(shí)間的工作，從An集合轉(zhuǎn)移到Cn集合，形成新的集合An＋1與Cn＋1，并計(jì)算剩余資源量，形成可行工作集Dn＋1。第二步，從Dn＋1集合中，按特定優(yōu)先規(guī)則，選擇一項(xiàng)工作（如果有多個(gè)工作具有相同的優(yōu)先權(quán)，優(yōu)先安排編號(hào)小的工作），將該工作開始時(shí)間安排在tn＋1時(shí)刻，并將其從Dn＋1集合中轉(zhuǎn)移到An＋1集合；然后不斷重復(fù)步驟二，直到Dn＋1集合為空。

3.1.3 兩種方案的比較

文獻(xiàn)［9］對(duì)這兩種調(diào)度生成方案進(jìn)行了比較和評(píng)價(jià)：當(dāng)無(wú)資源約束時(shí)，兩種調(diào)度方法都能生成最優(yōu)調(diào)度；串行調(diào)度方法生成的調(diào)度通常是積極的，而并行調(diào)度方法生成的是非延遲調(diào)度。對(duì)于兩種調(diào)度生成方案，并行調(diào)度生成方案搜索的解空間要比串行調(diào)度生成方案搜索的解空間?。ú⑿蟹桨傅膖n時(shí)刻總是等于上一階段正在工作集合中最早的完工時(shí)間），因此在某些情況下，可能搜索不到全局最優(yōu)解。Kolisch通過(guò)利用PSPLIB進(jìn)行研究發(fā)現(xiàn)；當(dāng)不考慮資源約束時(shí)，兩種方案都能夠產(chǎn)生最優(yōu)解；當(dāng)處理規(guī)模較大且有適當(dāng)資源限制的問(wèn)題時(shí)，串行方案比并行方案有較好的性能。

3.2 編碼與解碼

編碼方式和解碼規(guī)則，歸納起來(lái)可分為如下幾類［6］。

3.2.1 任務(wù)列表

此類方法通過(guò)串行調(diào)度方案生成一個(gè)工作鏈表，各工作在鏈表中的順序顯然是滿足緊前關(guān)系約束的。反之，如果給定一個(gè)滿足緊前關(guān)系的工作鏈表，那么應(yīng)用串行調(diào)度方案解碼可以生成一個(gè)可行調(diào)度計(jì)劃。但值得注意是，并行調(diào)度方案也適合這種方法的解碼［10］。文獻(xiàn)［11－18］采用了此類編碼與解碼方式。

3.2.2 優(yōu)先權(quán)系數(shù)向量

此類方法給定一個(gè)J維向量，向量中的第j個(gè)元素代表工作j的優(yōu)先權(quán)系數(shù)，那么針對(duì)該向量應(yīng)用串行（并行）調(diào)度方案解碼便可生成一個(gè)可行調(diào)度計(jì)劃。文獻(xiàn)［19－25］采用了此類編碼方式。

3.2.3 優(yōu)先規(guī)則鏈表

此類方法事先選定若干條優(yōu)先規(guī)則構(gòu)成優(yōu)先規(guī)則集，再?gòu)闹幸来坞S機(jī)選擇J條規(guī)則構(gòu)成優(yōu)先規(guī)則鏈表（一條編碼）。解碼規(guī)則既可以采用串行調(diào)度方案也可以采用并行調(diào)度方案。解碼過(guò)程如下：在調(diào)度第j項(xiàng)工作時(shí)，采用編碼中的第j條優(yōu)先規(guī)則計(jì)算當(dāng)前可調(diào)度工作集中各工作的優(yōu)先權(quán)，并選擇優(yōu)先權(quán)最高的工作按照串行（并行）調(diào)度方案原則安排其開始時(shí)間，直至J項(xiàng)工作全部調(diào)度完畢。文獻(xiàn)［13］采用了此種編碼方式。

3.3 資源受限項(xiàng)目的求解步驟

基于智能算法的資源受限項(xiàng)目調(diào)度問(wèn)題一般求解步驟：

第一步，確定編碼方式與解碼規(guī)則。這一步包括了兩個(gè)方面：一是確定RCPSP與算法的映射，即編碼方式，主要有上述介紹的三種；二是確定解碼規(guī)則，包括進(jìn)度生成計(jì)劃。

第二步，確定初始化方法。一般是隨機(jī)生成或者根據(jù)特定的編碼方式結(jié)合一些優(yōu)先規(guī)則生成。

第三步，確定算法的進(jìn)化機(jī)制。主要與算法本身特性相關(guān)，即迭代尋優(yōu)。

第四步，確定適應(yīng)度值的計(jì)算方式。第五步，確定算法終止規(guī)則。算法結(jié)構(gòu)流程一般見圖1。

圖1 RCPSP智能算法一般結(jié)構(gòu)流程

4 結(jié)語(yǔ)

資源受限項(xiàng)目調(diào)度問(wèn)題廣泛存在于城市軌道交通工程領(lǐng)域以及其他重點(diǎn)、大規(guī)模建設(shè)項(xiàng)目。本文主要回顧了該問(wèn)題在其項(xiàng)目管理環(huán)節(jié)中的呈現(xiàn)方式和基本分類，并對(duì)建模、調(diào)度生產(chǎn)方案、編碼方式和解碼規(guī)則加以詳細(xì)闡述；重點(diǎn)介紹應(yīng)用智能算法求解資源受限數(shù)學(xué)模型的關(guān)鍵步驟和一般求解過(guò)程。

［1］Blazewica J，Lenstra J K，Rinnooy Kan.Scheduling projects to resource constraints：classification and complexity ［J］.Discrete Applied Mathematics，1983，5：11.

［2］Kolisch R.Serial and Parallel Resource－constrained Project Scheduling Methods Revisited：Theory and Computation［J］.European Journal of Operational Research，1996，90（2）：320.

［3］Herroelen W，Demeulemeester E，De Reyck B，A classification scheme for project scheduling.Project Scheduling：Recent Models，Algorithms and Applications［M］.Boston／London／DordrechtL：Kluwer Academic Publishers，1999：1.

［4］Slowinski R.Two approaches to problems of resource allocation among project activities：A Comparative Study［J］.Journal of the Operational Research Society，1980（31）：711.

［5］Weglarz J.Project scheduling with discrete and continuous resources［J］.IEEE Transactions on Systems，Man and Cybernetics 1979，9，644－650.

［6］劉士新，王夢(mèng)光，唐加福.一種求解資源受限工程調(diào)度問(wèn)題的遺傳算法［J］.系統(tǒng)工程學(xué)報(bào)，2002，17（1）：1.

［7］Kelley J E.The critical path method：resources planning and scheduling［C］∥Muth，Thompson，eds.Industrial Scheduling.New Jersey：Prentice－Hall，Englewood Cliffs，1963：347.

［8］Bedworth D D，Bailey JE.Integrated production control systems－management，Analysis，Design［M］.New York：Wiley，1982.

［9］Kolisch R.Serial and parallel resource－constrained project scheduling methods revisited：theory and computation［J］.European Journal of Operational Research，1996，90（2）：320.

［10］Alcaraz J，Maroto C.A robust genetic algorithm for resource allocation in project scheduling［J］.Annals of Operations Research，2001，102（1）：83.

［11］Hartmann S.A competitive genetic algorithm for resourceconstrained project scheduling［J］.Naval Research Logistics，1998，45（7）：733.

［12］Leon V J，Ramamoorthy B.Strength and adaptability of problem－space based neighborhoods for resource－constrained scheduling［J］.OR Spektrum，1995，17（23）：173.

［13］Ozdamar L.A genetic algorithm approach to a general category project scheduling problem［J］.IEEE Trans on Syst，Man and Cyber，1999，29（1）：44.