劉 振

（中鐵第四勘察設計院集團有限公司，430063，武漢∥高級工程師 ）

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

1 資源受限項目進度問題的描述

典型的資源受限項目進度問題可描述如下［2］：

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

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

2 資源受限項目調度問題的分類

資源、任務和目標函數(shù)三要素組成了資源受限項目調度問題。資源的不同數(shù)量和類型，任務錯綜復雜的約束條件，再加上度量不同指標的目標函數(shù)，形成了種類繁多的RCPSP問題。通常采用文獻［3］三段式分類方法對資源受限的項目調度問題進行分類。該方法采用機器排序的分類形式，用三個參數(shù)α，β，γ來描述RCPSP的類型，得到了多數(shù)學者的認同。以下簡要介紹各段的含義。

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

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

按照文獻［4］和文獻［5］提出的資源分類法，可分為可更新資源（Renewable Resources）、不可更新資源（Nonrenewable Resources）和雙重資源（Doubly Constrained Resources）三種。可更新資源是指在每個時段獲得一定量的資源，這種資源的獲得和消耗是以每一階段為基礎的（如運碴汽車和施工人員等）；不可更新資源是指在整個工期內只能獲得一定量的資源（如原材料、能源等）；雙重資源是指資源的獲得和消耗既在工期的每一階段受限，又在整個工期的總量上受到限制（如掘進盾構機等）。雙重約束的資源分配問題可以被轉化為相應的可更新資源和不可更新資源來處理。

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

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

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

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

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

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

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

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

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

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

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

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

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

3 資源受限項目調度問題的求解方法

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

3.1 調度生產方案

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

3.1.1 串行調度方案

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

3.1.2 并行調度方案

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

3.1.3 兩種方案的比較

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

3.2 編碼與解碼

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

3.2.1 任務列表

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

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

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

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

此類方法事先選定若干條優(yōu)先規(guī)則構成優(yōu)先規(guī)則集，再從中依次隨機選擇J條規(guī)則構成優(yōu)先規(guī)則鏈表（一條編碼）。解碼規(guī)則既可以采用串行調度方案也可以采用并行調度方案。解碼過程如下：在調度第j項工作時，采用編碼中的第j條優(yōu)先規(guī)則計算當前可調度工作集中各工作的優(yōu)先權，并選擇優(yōu)先權最高的工作按照串行（并行）調度方案原則安排其開始時間，直至J項工作全部調度完畢。文獻［13］采用了此種編碼方式。

3.3 資源受限項目的求解步驟

基于智能算法的資源受限項目調度問題一般求解步驟：

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

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

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

第四步，確定適應度值的計算方式。第五步，確定算法終止規(guī)則。算法結構流程一般見圖1。

圖1 RCPSP智能算法一般結構流程

4 結語

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

［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］劉士新，王夢光，唐加福.一種求解資源受限工程調度問題的遺傳算法［J］.系統(tǒng)工程學報，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.