李 琦 張靜文 王 帥

(西北工業(yè)大學(xué)管理學(xué)院 陜西 西安 710072)

面向?qū)ο蠹夹g(shù)實現(xiàn)求解RCPSP的遺傳算法

李 琦 張靜文 王 帥

(西北工業(yè)大學(xué)管理學(xué)院 陜西 西安 710072)

基于遺傳算法求解RCPSP(resource-constrained project scheduling problem)的算法框架，采用面向?qū)ο蟮募夹g(shù)抽象出算法運行中的五個類：活動類、項目網(wǎng)絡(luò)圖類、串行調(diào)度進程類、種群中的個體類及遺傳算法類?；趧討B(tài)數(shù)組表示項目網(wǎng)絡(luò)圖和活動之間的邏輯關(guān)系，并分析出每個類的基本屬性及操作函數(shù)，其次，探究出各個類之間的組合或依賴關(guān)系，從整體角度，設(shè)計出包含所有類的算法靜態(tài)結(jié)構(gòu)圖，清晰地展示了多個類之間復(fù)雜的數(shù)據(jù)互訪過程，進而實現(xiàn)了基于面向?qū)ο蠹夹g(shù)的遺傳算法求解RCPSP編碼，最后從理論上分析了采用面向?qū)ο蠹夹g(shù)的優(yōu)勢。研究表明，相對于傳統(tǒng)的面向過程的編程方式，基于面向?qū)ο蠹夹g(shù)實現(xiàn)求解RCPSP的遺傳算法使得代碼編寫工作量大大減少，程序的可讀性增強，且算法的運行效率有很大提高。

RCPSP 面向?qū)ο?遺傳算法 編碼

0 引 言

資源約束型項目調(diào)度問題RCPSP廣泛地存在于建筑工程、軟件開發(fā)、計算機行業(yè)(如操作系統(tǒng)中的資源管理、處理器的任務(wù)調(diào)度等)、飛機及輪船制造等單件或者小批量生產(chǎn)方式的企業(yè)中[1-2]?；顒觾H有一種執(zhí)行模式的RCPSP被稱作基本RCPSP[3]，它是項目調(diào)度問題PSP(project scheduling problems)中最經(jīng)典、也是最具代表性的模型，因此其求解算法也是求解其它類型PSP的基礎(chǔ)。求解基本RCPSP模型的算法分為兩大類：精確算法和啟發(fā)式算法。對大規(guī)模的項目，精確算法求解問題不現(xiàn)實，因此從實用角度，PSP求解中更廣泛地使用啟發(fā)式算法，包括啟發(fā)式算法和超啟發(fā)式算法，而超啟發(fā)式算法則主要體現(xiàn)為智能優(yōu)化算法，如遺傳算法GA、模擬退火、禁忌搜索、粒子群等[4-6]，還有將兩種啟發(fā)式算法相結(jié)合的混合智能優(yōu)化算法[7]。相比較而言，超啟發(fā)式算法在求解基本RCPSP中使用的更普遍且求解效果更好。

采用超啟發(fā)式算法求解RCPSP時，當(dāng)算法設(shè)計好之后，最關(guān)鍵的一個步驟是采用某種編程語言實現(xiàn)算法步驟。采用面向過程實現(xiàn)求解RCPSP及相關(guān)問題的過程太繁瑣，需要定義的變量太多，程序的可讀性差且編譯效率不高，基于此本文主要集中于算法的面向?qū)ο缶幊虒崿F(xiàn)問題。遺傳算法是求解RCPSP的最具代表性且被學(xué)者證明是對RCPSP具有最好效果的超啟發(fā)式智能優(yōu)化算法，因此本文以遺傳算法為依托，探究采用面向?qū)ο蠹夹g(shù)實現(xiàn)項目調(diào)度問題求解算法的核心技術(shù)。

1 遺傳算法求解基本RCPSP

1.1 算法框架

理論上，基本RCPSP模型是一類組合優(yōu)化問題，以項目工期最短為目標(biāo)函數(shù)，包括兩個約束條件：第一是最基本的活動之間的邏輯關(guān)系約束；第二是項目執(zhí)行過程中的可更新資源約束。模型的解是所有活動開始時間構(gòu)成的一個序列。通常，RCPSP模型借助一個有向五圈的項目網(wǎng)絡(luò)圖G=(V,E)來表達，其中V表示活動結(jié)合，E表示活動之間的優(yōu)先關(guān)系集合，且|V|=J和|E|=e。

采用遺傳算法GA求解基本RCPSP時，在解的編碼、初始種群的產(chǎn)生、設(shè)置個體適應(yīng)值評價函數(shù)等方面，在選擇、交叉、變異等遺傳操作的實現(xiàn)上都有多種方式，對此本文都采用了最具代表性的方式來闡述[8-13]。遺傳算法的運行參數(shù)有：設(shè)Popsize表示種群規(guī)模(population size)、Pc表示交叉概率(crossover)、Pm表示變異概率(mutation)，Maxgen表示種群的最大進化代數(shù)。設(shè)k(k=1,2,…,Popsize)代表種群中的第k個個體，用T(k)表示個體k對應(yīng)的項目工期。

(1) 編碼和解碼

用優(yōu)先關(guān)系可行的活動序列進行編碼，這也是眾多超啟發(fā)式智能優(yōu)化算法求解RCPSP時最常用的編碼方式。由于簡潔直觀，這種編碼方式最具代表性，所以每個序列的長度為J(項目中包含的活動個數(shù))；基本RCPSP以項目工期最短為目標(biāo)，因此通常采用串行調(diào)度機制實現(xiàn)解碼過程，解碼后可獲得某個解對應(yīng)的目標(biāo)值─項目工期。

(2) 個體適應(yīng)值評價函數(shù)

基本RCPSP的目標(biāo)是項目工期(越小越好)，但在實現(xiàn)選擇操作時，適應(yīng)值大的個體有更高的概率進入下一代，所以個體的項目工期不能直接作為它的適應(yīng)值，需要基于個體的項目工期重新設(shè)計適應(yīng)值函數(shù)。本文用所有個體工期的和減去最小化項目工期，把原始目標(biāo)轉(zhuǎn)化為適應(yīng)值函數(shù)。

(3) 初始種群的產(chǎn)生

本文選擇隨機方式產(chǎn)生初始種群POP0。

1.2 遺傳進化過程

通過選擇、交叉和變異三種遺傳操作實現(xiàn)算法的進化過程，對于基本RCPSP模型，這三種操作具體如下：

(1) 選擇

本文遺傳算法實施輪盤賭選擇操作，對應(yīng)項目工期越小的個體適應(yīng)值越高，因此有更大的概率被選擇參與交叉等遺傳進化過程。

(2) 兩點交叉

交叉操作采用兩點交叉方式，記參與交叉的兩個個體分別為Mother(用M表示)和Father(用F表示)，交叉后產(chǎn)生的兩個后代分別為Daughter(用D表示)和Son(用S表示)。兩點交叉中，兩個交叉點的基因位置分別為r1和r2，且滿足 1

(3) 變異

變異操作時，對交叉獲得的每個個體，對每個基因位依變異概率Pm發(fā)生變異。具體為，對于序列中的某個活動，首先確定該活動所有緊前活動在序列中最右側(cè)的基因位置；其次，確定該活動的所有緊后活動在序列中最左側(cè)的基因位置，這兩個位置即確定了該活動變異時可行的位置區(qū)域。將需要變異的活動隨機地插入其可行區(qū)域內(nèi)的任意一個不同于當(dāng)前位置的基因位上。

2 面向?qū)ο蠹夹g(shù)的算法編程

對于規(guī)模較小和流程簡單的程序，編程者可以較容易地寫出面向過程(結(jié)構(gòu)化)的程序代碼，詳細地描述每一瞬時的數(shù)據(jù)結(jié)構(gòu)及其操作過程。然而，當(dāng)程序規(guī)模較大且復(fù)雜時，實現(xiàn)結(jié)構(gòu)化的程序編碼就非常繁瑣且冗長。而面向?qū)ο蟮姆治龊驮O(shè)計，注重從宏觀上考慮問題，把對問題論域和系統(tǒng)的認識抽象為規(guī)范的對象和對象之間的消息傳遞[14]。對象封裝了數(shù)據(jù)和操作，數(shù)據(jù)與操作緊密結(jié)合，對象互訪非常方便，這些都為使用面向?qū)ο笏枷虢鉀Q基本RCPSP提供了有利條件。

仔細分析遺傳算法求解基本RCPSP的流程及其中的各個模塊，從中抽象出五個類(Class)，分別是活動類、網(wǎng)絡(luò)圖類、串行調(diào)度過程類、種群中的個體類及遺傳算法類。

2.1 活動類CActivity

在Aon(Activity-on-node)方式的項目活動網(wǎng)絡(luò)圖中，節(jié)點表示的活動可以抽象為一個活動類，命名為CActivity。CActivity類的基本屬性包括：代號id、工期duration，它對四種可更新資源的需求量分別為r1、r2、r3、r4。由于每個活動的緊前(或緊后)活動是哪些活動、且緊前(或緊后活動)的數(shù)目都不相同，因此定義CActiveArray是一種動態(tài)數(shù)組類型的數(shù)據(jù)。

CActivity類的基本屬性還包括它的活動的緊前活動集合pre_activities和緊后活動集合suc_activities，pre_activities和suc_activities的數(shù)據(jù)類型都是動態(tài)數(shù)組。

2.2 網(wǎng)絡(luò)圖類CAonDiagram

在大規(guī)模數(shù)值實驗中，通常要測試很多的算例，每個算例的網(wǎng)絡(luò)圖結(jié)構(gòu)和參數(shù)都不相同，因此將Aon項目活動網(wǎng)絡(luò)圖抽象為類CAonDiagram。不同的項目網(wǎng)絡(luò)圖中，活動的數(shù)目有差別，因此需要使用動態(tài)數(shù)組記錄網(wǎng)絡(luò)圖中的所有活動。使用CActiveArray動態(tài)數(shù)組來表示一個活動網(wǎng)絡(luò)中的所有活動。類CAonDiagram的基本屬性包括：動態(tài)數(shù)組activity_array，表示項目網(wǎng)絡(luò)中的所有活動，其中每個元素都是一個類CActivity(表示一個活動)；四種可更新資源的限量R1、R2、R3、R4。

2.3 種群中的個體類CSample

遺傳進化過程中，種群中包含多個個體，因此將個體對象抽象為類CSample。CSample的基本屬性包括：項目工期project_duration、適應(yīng)值fi。CSample類的對象表現(xiàn)形式為一個優(yōu)先關(guān)系可行的活動序列，同樣用動態(tài)數(shù)組表示。

2.4 串行調(diào)度過程CSerialSchedule

遺傳算法中，對種群中的每個個體的解碼操作都是在實施一次串行調(diào)度過程，因此串行調(diào)度過程是遺傳算法求解基本RCPSP中的一個核心的模塊，將其抽象為類CSerialSchedule。

CSerialSchedule的基本屬性包括：第一，網(wǎng)絡(luò)圖Aon，數(shù)據(jù)類型為CAonDiagram的變量，提供了串行調(diào)度過程中活動之間的邏輯關(guān)系(網(wǎng)絡(luò)圖的結(jié)構(gòu))；第二，串行調(diào)度過程中某個階段的合格活動集合En，數(shù)據(jù)類型為CActivityArray；第三，PSn，表示串行調(diào)度過程中某個階段的局部調(diào)度計劃集合，數(shù)據(jù)類型為CActivityArray；第四，priority，表示串行調(diào)度過程中活動的優(yōu)先值序列(一個個體)，數(shù)據(jù)類型為CIntegerArray。

2.5 遺傳進化過程GGeneticAlgorithm

將遺傳進化過程也抽象為類GGenetic-Algorithm，它的基本屬性包括：第一，max_gen表示遺傳算法的最大進化代數(shù)(為整性變量)；第二，Pc表示交叉概率；第三，Pm表示變異概率。種群由多個個體構(gòu)成，每個個體都是類型為CSample的對象，因此采用元素為CSample對象的動態(tài)數(shù)組CSampleArray表示種群。

2.6 五個類之間的互訪關(guān)系剖析

上述五個類之間的關(guān)系、每個類的基本屬性和操作函數(shù)總結(jié)于圖1中。在每個類對象的屬性或操作中，“-”表示私有成員變量或者私有成員函數(shù)(private)，“+”表示公有成員變量或者公有成員函數(shù)(public)，“#”表示受保護的成員變量或者受保護的成員函數(shù)(protected)。類CActivity與類CAonDiagram之間帶實心菱形的實線表示組合關(guān)系，菱形指向整體，即類CAonDiagram是整體，類CAonDiagram是部分；實線在類CActivity的一段標(biāo)注“n”，在實心菱形段標(biāo)注“1”，表示一個類CAonDiagram包含多個類CActivity，而且類CActivity不能離開類CAonDiagram而單獨存在；類CGeneticAlgorithm與CSerialSchedule之間帶箭頭的虛線表示依賴關(guān)系(Dependency)，箭頭指向被使用者，表示類CGeneticAlgorithm要依賴類CSerialSchedule(被使用的類)。

圖1 遺傳算法求解基本RCPSP模型的靜態(tài)結(jié)構(gòu)圖

3 面向?qū)ο蠹夹g(shù)的優(yōu)勢分析

如果考慮遺傳算法的通用框架，算法流程并不復(fù)雜。但是遺傳算法復(fù)雜性體現(xiàn)在所求解的特定問題上，比如采用遺傳算法求解RCPSP的實現(xiàn)過程就比較復(fù)雜，而這種復(fù)雜性源自RCPSP模型本身的復(fù)雜性(具有NP-hard特征的組合優(yōu)化問題)。當(dāng)然，采用面向過程的編碼也可以實現(xiàn)遺傳算法求解RCPSP。但是需要定義的變量非常多，編寫代碼的工作量很大，而采用面向?qū)ο蠹夹g(shù)編程將使代碼編寫量大大減少。

以項目網(wǎng)絡(luò)圖的表示為例，基于面向?qū)ο蟮念惐硎揪W(wǎng)絡(luò)圖且采用動態(tài)數(shù)組存儲活動網(wǎng)絡(luò)圖的復(fù)雜度為O{J+e}；在面向過程的程序中，存儲網(wǎng)絡(luò)圖通常采用鄰接矩陣(復(fù)雜度為O{J2})或鄰接表(復(fù)雜度為O{J+e})的形式，盡管采用鄰接表的復(fù)雜度與動態(tài)數(shù)組存儲網(wǎng)絡(luò)圖的復(fù)雜度相同，但是鄰接表的定義和訪問操作需要使用指針，計算和編程都較麻煩[15]。最關(guān)鍵的是，網(wǎng)絡(luò)圖的存儲方式直接決定了求解RCPSP時，遺傳進化過程中數(shù)據(jù)訪問操作的效率。因為種群中的每個個體都是一個優(yōu)先關(guān)系可行的活動序列(本質(zhì)是項目網(wǎng)絡(luò)圖)，并且對每個個體的編碼、解碼、交叉及變異操作都是對網(wǎng)絡(luò)圖的結(jié)構(gòu)和數(shù)據(jù)的一次訪問過程。因此網(wǎng)絡(luò)圖的編碼表示和存儲方式直接決定了遺傳算法求解RCPSP的運行效率。

相對傳統(tǒng)的面向過程的的編程方式，面向?qū)ο蟮募夹g(shù)實現(xiàn)求解RCPSP的遺傳算法，代碼編寫工作量減少，程序的可讀性增強，其優(yōu)勢是非常明顯的。而且，對于越復(fù)雜的組合優(yōu)化問題，采用遺傳算法求解時，面向?qū)ο蠹夹g(shù)實現(xiàn)編程的優(yōu)勢比面向過程的方式優(yōu)勢體現(xiàn)得更明顯。

4 結(jié) 語

本文采用面向?qū)ο蟮念惐硎净顒?、網(wǎng)絡(luò)圖、串行調(diào)度過程、種群中的個體及遺傳算法，定義了每個類的基本屬性和操作函數(shù)，類之間的關(guān)系，開發(fā)了基于面向?qū)ο蠹夹g(shù)實現(xiàn)遺傳算法的代碼，進一步從理論上分析了采用面向?qū)ο蠹夹g(shù)的優(yōu)勢。本文研究工作對采用面向?qū)ο蠹夹g(shù)實現(xiàn)更多復(fù)雜的智能優(yōu)化算法求解組合優(yōu)化問題提供了理論框架?；綬CPSP問題僅考慮可更新資源限量，本文后續(xù)將研究不可更新資源和雙重約束資源約束下項目進度計劃方面的面向?qū)ο髮崿F(xiàn)技術(shù)。

[1] Hall Nicholas G.Projecr management: recent developments and research opportunities[J].Journal of Systems Science and Systems Engineering,2012,21(2):129-143.

[2] 劉士新.項目優(yōu)化調(diào)度理論與方法[M].北京:機械工業(yè)出版社,2007:56-70.

[3] 張靜文.項目調(diào)度優(yōu)化模型與方法的拓展[M].陜西西安:西安交通大學(xué)出版社,2015:2-3.

[4] Leus S,Chen A T,Yang C H.A GA-based fuzzy optimal model for construction time-cost trade-off[J].International Journal of Project Management,2001,19(1):47-58.

[5] Hapke M,Jaszkiewicz A,Roman S.Pareto simulated annealing for fuzzy multi-objective combinatorial optimization[J].Journal of Heuristics,2000,6(3):329-345.

[6] Tsai Y W,Gemmill D D.Using tabu search to schedule activities of stochastic resource-constrained projects[J].European Journal of Operational Research,1998,111(1):129-141.

[7] Ahsan M K,Tsao D.A heuristic search algorithm for solving resource-constrained project scheduling problems[J].Asia-pacific Journal of Operational Research,2003,20(2):143-160.

[8] 王宏,林丹,李敏強.一種求解資源受限項目調(diào)度問題的自適應(yīng)遺傳算法[J].系統(tǒng)工程,2005,23(12):99-102.

[9] 楊利宏,楊東.基于遺傳算法的資源約束型項目調(diào)度優(yōu)化[J].管理科學(xué),2008,21(4):60-68.

[10] Liu S,Wang M.An object-oriented methodology for solving the RCPSPs with heuristics and metaheuristics[J].Production Planning & Control:The Management of Operations,2010,11(5):434-442.

[11] 王宏,林丹,李敏強.一種求解多目標(biāo)資源受限項目調(diào)度的遺傳算法[J].計算機工程與應(yīng)用,2008,44(7):1-4.

[12] Bianco L,Caramia M.An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations[J].European Journal of Operational Research,2012,219(1):73-85.

[13] Hartmann S.Project Scheduling with Multiple Modes:A Genetic Algorithm[J].Annals of Operations Research,2001,102(1/4):111-135.

[14] 譚浩強.C++面向?qū)ο蟪绦蛟O(shè)計[M].北京:清華大學(xué)出版社,2006:37-66.

[15] 張靜文,周杉.面向?qū)ο蠹夹g(shù)實現(xiàn)活動網(wǎng)絡(luò)圖及關(guān)鍵路徑算法[J].計算機工程與應(yīng)用,2016,52(4):234-237.

REALIZATIONOFGENETICALGORITHMFORSOLVINGRCPSPBASEDONOBJECT-ORIENTEDTECHNIQUE

Li Qi Zhang Jingwen Wang Shuai

(SchoolofManagement,NorthwesternPolytechnicalUniversity,Xi’an710072,Shaanxi,China)

The framework of resource-constrained project scheduling problem(RCPSP)was solved based on genetic algorithm, an object-oriented(OO, in short) class was adopted to represent activities, project network diagrams, serial scheduling process, individuals in the population and genetic algorithms. And dynamic arrays were used to denote the project network graphs and the logical precedence relationships among activities. The basic properties and the operation function of each class were defined. Next, the combination or dependency relationship of each class was explored in this paper. And the static structure diagram of the algorithm which contains all classes from a whole perspective was designed, which clearly showed the complex process of data exchange between multiple classes. Then, the codes of the genetic algorithm were developed by means of an OO technique. Finally, the advantages of OO technology were analyzed theoretically. Compared with the traditional process-oriented programming, the research shows the genetic algorithm based on OO technology to solve RCPSP makes the code writing workload greatly reduced. The readability of the program is enhanced and the running efficiency of the algorithm is improved greatly.

RCPSP Object-oriented Genetic algorithm Coding

TP3

A

10.3969/j.issn.1000-386x.2017.09.001

2016-11-11。中國博士后科學(xué)基金項目(2015M580875，2016T90947)；航空科學(xué)基金項目(2015ZG53080)；陜西省科學(xué)基金項目(2015JM7368，2014P23)；西北工業(yè)大學(xué)研究生創(chuàng)意創(chuàng)新種子基金項目(Z2016177，Z2017055)。李琦，碩士生，主研領(lǐng)域：項目調(diào)度優(yōu)化。張靜文，教授。王帥，碩士生。