金敏力，馮玉強(qiáng)

(1.哈爾濱工業(yè)大學(xué) 管理學(xué)院，黑龍江 哈爾濱 150001;2.沈陽理工大學(xué) 教務(wù)處，遼寧 沈陽 110159)

關(guān)鍵鏈項目優(yōu)化調(diào)度問題模型以資源約束項目調(diào)度問題模型為基礎(chǔ)，因此求解資源約束項目調(diào)度問題是關(guān)鍵鏈項目管理的前提，設(shè)計合理的算法產(chǎn)生基準(zhǔn)計劃是關(guān)鍵鏈項目優(yōu)化調(diào)度的基礎(chǔ)［1］。目前關(guān)于關(guān)鍵鏈項目調(diào)度的基準(zhǔn)計劃生成的算法主要有兩大方面:即基于優(yōu)先規(guī)則的啟發(fā)式算法生成基準(zhǔn)計劃和基于智能優(yōu)化算法生成基準(zhǔn)計劃。由于不同優(yōu)先規(guī)則的啟發(fā)式算法在求解關(guān)鍵鏈項目調(diào)度問題時計算結(jié)果有很大差異［2－4］。因此，對不同的關(guān)鍵鏈項目調(diào)度問題需事前判斷采用哪種優(yōu)先規(guī)則［5］。近幾十年來，人們設(shè)計了各種智能仿生算法，這些算法均是模仿自然規(guī)律而設(shè)計的問題求解模型，這些算法與經(jīng)典的數(shù)學(xué)規(guī)劃方法截然不同，試圖通過模擬自然生態(tài)系統(tǒng)的演化機(jī)制求解復(fù)雜問題，如遺傳算法、模擬退火算法、群智能算法(如蟻群、魚群、蜂群和鳥群等)、神經(jīng)網(wǎng)絡(luò)計算方法和人工免疫算法等。這些智能算法為許多復(fù)雜的組合優(yōu)化問題求解提供了切實可行的解決方案［6］。資源約束項目調(diào)度問題本身是一類 NP－h(huán)ard［2－3］問題，求解困難，而資源約束關(guān)鍵鏈項目調(diào)度問題相比較于資源約束項目調(diào)度問題，模型更復(fù)雜，求解更困難，因此，利用智能優(yōu)化算法進(jìn)行優(yōu)化求解是切實可行的方向。本文在前人研究的基礎(chǔ)上，為單模式關(guān)鍵鏈項目調(diào)度問題的基準(zhǔn)計劃的產(chǎn)生設(shè)計一種遺傳算法，并對算法的結(jié)構(gòu)、編解碼規(guī)則、遺傳操作及初始種群的產(chǎn)生進(jìn)行詳細(xì)說明，通過仿真試驗進(jìn)行驗證，并與最新的不同算法的計算結(jié)果進(jìn)行比較。

1 模型構(gòu)建

生成基準(zhǔn)計劃是產(chǎn)生最終關(guān)鍵鏈的中間步驟，因為關(guān)鍵鏈的基準(zhǔn)計劃采用固定活動工期，不考慮緩沖區(qū)，只受可更新資源約束，因此可參照資源約束項目調(diào)度問題建立基準(zhǔn)計劃的優(yōu)化模型。單執(zhí)行模式資源受限項目調(diào)度問題(SRCPSP)，假設(shè)每一個任務(wù)只有一種執(zhí)行模式;每一個任務(wù)占用一定的資源，而整個項目的總資源有限，資源量均為整數(shù);項目中各個任務(wù)的開始時間和結(jié)束時間均為非負(fù)整數(shù)，且任務(wù)之間存在緊前關(guān)系;每個任務(wù)都有確定的執(zhí)行時間，其值為非負(fù)整數(shù);用一個有向無環(huán)圖G=(V，A)(其中V代表任務(wù)節(jié)點(diǎn)的集合，A代表任務(wù)間前后約束的有向邊的集合)來表示項目計劃。該問題的優(yōu)化目標(biāo)是在資源約束條件下，考慮前后約束關(guān)系，實現(xiàn)項目持續(xù)時間最短。

SRCPSP問題可用以下數(shù)學(xué)語言描述:

式中:STi為活動i的開始時間;Di為活動i的持續(xù)時間;Si為在活動i之后的所有活動的集合;rik為活動i需要資源k的數(shù)量;At為t時刻正在執(zhí)行的任務(wù)的集合;K為資源類型的數(shù)量。任務(wù)1和任務(wù)n是虛工序，標(biāo)識項目的開始時間和結(jié)束時間。目標(biāo)是最小化項目的持續(xù)時間，即最小化STn。式(1)是最小化項目時間，式(2)滿足任務(wù)的時間約束，式(3)滿足每種資源的約束，式(4)保證項目時間非負(fù)。

SRCPSP問題的求解，理論上可通過數(shù)學(xué)方法求得最優(yōu)解，但由于資源約束項目調(diào)度問題屬于NP－h(huán)ard問題，當(dāng)任務(wù)數(shù)量和復(fù)雜度達(dá)到一定程度時，精確求解變得不現(xiàn)實。因此，啟發(fā)式求解的方法適用于這種問題，這類方法給出相對簡單的調(diào)度規(guī)則來尋找滿意的解，而不一定是最優(yōu)的解。文中提出的求解單執(zhí)行模式項目調(diào)度問題的遺傳算法，實質(zhì)上包含兩個部分:(a)根據(jù)項目的前后約束關(guān)系，產(chǎn)生一個可行的調(diào)度方案;(b)根據(jù)資源情況，逐個向后移動任務(wù)開始時間，最終確定滿足資源約束條件的各個任務(wù)的開始時間。其中初始種群任務(wù)的優(yōu)先權(quán)是根據(jù)隨機(jī)產(chǎn)生的與任務(wù)總數(shù)相同的整數(shù)，根據(jù)串行調(diào)度的原理對每一個優(yōu)先權(quán)情況下的任務(wù)進(jìn)行調(diào)度，使其滿足時間約束條件和資源約束條件，再采用遺傳算法進(jìn)化項目的調(diào)度。

2 遺傳算法設(shè)計

利用遺傳算法求解關(guān)鍵鏈項目調(diào)度問題，是將每一個項目調(diào)度計劃編碼成一個染色體，通過交叉、變異、選擇操作(由于選擇操作采用最優(yōu)保持和輪盤賭方法，染色體的性能始終向最優(yōu)解的方向進(jìn)化)，最終得到最優(yōu)的調(diào)度計劃或次優(yōu)的調(diào)度計劃［7］。傳統(tǒng)的輪盤賭方法雖然能較好地選擇出適應(yīng)值較高的個體，但適應(yīng)值較高的個體只是被選擇的概率較高，而不能肯定被復(fù)制到下一代，因此為較好地保留局部最優(yōu)的個體，采用最優(yōu)保留的策略使進(jìn)化持續(xù)不斷地進(jìn)行?；谧顑?yōu)保留和輪盤賭相結(jié)合的方式，文中的新遺傳算法是在每一代種群中選擇相對于種群規(guī)模的一定比例的最優(yōu)個體直接進(jìn)入到下一代中，這樣既有利于最優(yōu)個體的保留，也不破壞種群的多樣性，更利于產(chǎn)生更優(yōu)秀的個體。通過父代和子代相互競爭的策略，在選擇過程中，子代與父代有相同的權(quán)利在輪盤賭過程中被復(fù)制到下一代。文中采用的求解單執(zhí)行模式項目調(diào)度問題遺傳算法的流程為:首先設(shè)置算法參數(shù)，定義一個結(jié)構(gòu)數(shù)組，用于存放項目信息，包括緊前任務(wù)關(guān)系、緊后任務(wù)關(guān)系、資源占用量、任務(wù)優(yōu)先權(quán)、任務(wù)工期等;然后計算每個任務(wù)的內(nèi)度，并存放到結(jié)構(gòu)數(shù)組中;再基于優(yōu)先權(quán)生成初始種群，進(jìn)入到循環(huán)體中，進(jìn)行交叉、變異、選擇操作;最后對個體進(jìn)行選擇，直到得到滿意的結(jié)果為止。

2.1 制定編碼解碼規(guī)則

本文采用基于優(yōu)先權(quán)的編碼規(guī)則，再利用串行調(diào)度進(jìn)行解碼?；趦?yōu)先權(quán)的編碼是用位置表示一個活動的ID，基因的值用來表示活動的優(yōu)先權(quán)，有較高優(yōu)先權(quán)的任務(wù)優(yōu)先進(jìn)入計劃。基因的值是［1，n］之間惟一的整數(shù)，其中n與任務(wù)數(shù)相同，且每個任務(wù)的優(yōu)先權(quán)都不相同。編碼方法是通過基因位置確定任務(wù)的ID，通過基因值確定任務(wù)的優(yōu)先權(quán)。

編碼過程的關(guān)鍵在于拓?fù)渑判?，拓?fù)渑判驅(qū)τ谝粋€給定的有向圖G=(V，A)，一個拓?fù)渑判蚴且粋€所有節(jié)點(diǎn)的線性次序，對于任意有向邊(u，v)∈A，u在該次序中先于v出現(xiàn)。每一個拓?fù)渑判驊?yīng)對應(yīng)與項目任務(wù)數(shù)一樣多的位置，從拓?fù)渑判虻谝粋€位置開始，從左到右，依次添加拓?fù)渑判?，對?yīng)于某個位置，可能有多個任務(wù)進(jìn)行競爭，具有最高優(yōu)先權(quán)的任務(wù)贏得這個位置。用向量PS存儲不完全拓?fù)渑判?，初始化PS=1。將所有任務(wù)分為三種狀態(tài):已排序任務(wù)、合格任務(wù)和自由任務(wù)。確定了合格任務(wù)，就可根據(jù)每個合格任務(wù)的優(yōu)先權(quán)確定進(jìn)入拓?fù)渑判虻娜蝿?wù)，再更新合格任務(wù)集合，不斷循環(huán)，直到所有任務(wù)都進(jìn)入拓?fù)渑判驗橹埂?/p>

合格任務(wù)的確定可通過內(nèi)度的概念得以解決，用Din表示任務(wù)的內(nèi)度，其大小就是這個任務(wù)的父任務(wù)的數(shù)量。再引入割集的概念，其實質(zhì)是某一時間節(jié)點(diǎn)符合條件的邊的集合，用CUT表示。CUTi表示t時刻的割集，PSt表示t時刻的拓?fù)渑判?，V表示所有任務(wù)的集合，任務(wù)i∈PSt，任務(wù)j∈V － PSt，則 CUTt={(i，j)|i∈PSt，j∈V － PSt}表示時t刻的割集。對于給定的任務(wù)j∈V－PSt，如割集中傳入任務(wù)j的邊的數(shù)量等于內(nèi)度，那么這個任務(wù)j是合格任務(wù)。如圖1所示，給出一個項目的網(wǎng)絡(luò)圖作為例子。

圖1 部分拓?fù)渑判?、割集和合格任?wù)

當(dāng)時刻為4時，部分拓?fù)渑判騊S4={1，3，2，6}，此刻的割集為 CUTt={(6，10)，(3，7)，(1，4)，(1，5)}。由于任務(wù)10的內(nèi)度為2，而僅有一條屬于割集的邊傳入該任務(wù)，因此任務(wù)10不是合格任務(wù)，而是自由任務(wù)。由于任務(wù)4、5、7的內(nèi)度均為1，而傳入這些任務(wù)的邊均在割集中，因此任務(wù)4、5、7均是合格任務(wù)。以此類推，可得到這個項目在該優(yōu)先權(quán)下的拓?fù)渑判?，如圖2所示。

圖2 完整拓?fù)渑判?/p>

由于每一個拓?fù)渑判驘o法反映出個體的優(yōu)劣，因此需要采用解碼來衡量個體的情況。文中采用串行調(diào)度的方式對每一個染色體進(jìn)行解碼。首先根據(jù)任務(wù)之間的緊前關(guān)系約束，確定任務(wù)j=PS(i)的最早可能開始時間，再計算這個時刻所有資源的占用量，如果資源剩余量滿足任務(wù)的j要求，則可確定任務(wù)j的開始時間，否則時間往后移動一個單位，再判斷資源的剩余量是否滿足要求;隨著任務(wù)的完工，可更新資源會被釋放，因此必然存在某個時刻的資源是可行的。按照這種方法確定每一個任務(wù)的開始時間和結(jié)束時間，其中最后任務(wù)的結(jié)束時間即為整個項目的時間。

2.2 遺傳算子與適值函數(shù)

遺傳算法主要通過遺傳算子實現(xiàn)向目標(biāo)解方向進(jìn)化，遺傳算子主要有三部分組成:交叉算子、變異算子和選擇算子;其中交叉算子實現(xiàn)在廣度空間上的搜索，變異算子有利于深度搜索，選擇算子使解向更好的方向發(fā)展。

(1)交叉算子設(shè)計

本文的編碼實際上是［1，n］的整數(shù)排列，這個排列發(fā)生改變，個體也隨之改變，理論上據(jù)這些整數(shù)的所有排列方式就可計算出所有的可行解。用雜交方法隨機(jī)地從父代1中選擇若干個基因位置，將這些基因的值遺傳給子代中相應(yīng)的位置，子代中空缺的位置由父代2由左到右依次填補(bǔ)完整，如圖3所示。

圖3 交叉操作執(zhí)行過程

(2)變異算子設(shè)計

本文變異算子的主要目的是搜索當(dāng)前解的鄰域來尋找更好的解，既深度搜索。隨機(jī)在父代中找到兩個位置，交換這兩個位置的基因值，產(chǎn)生新的個體，如圖4所示。

圖4 變異操作執(zhí)行過程

(3)選擇算子設(shè)計

通過解碼，計算出每個個體對應(yīng)的項目的持續(xù)時間，最后一個活動的結(jié)束時間就是目標(biāo)值，顯然這個目標(biāo)值越小越好，屬于最小化問題，但在遺傳算法中，必須將原始目標(biāo)值最小化問題轉(zhuǎn)化成適應(yīng)值，以確保優(yōu)秀個體具有大的適應(yīng)值。

設(shè)i為當(dāng)前種群第i個個體，g(i)為適應(yīng)值函數(shù)，f(i)為第i個個體的目標(biāo)值(即項目持續(xù)時間)，f2和f1分別為當(dāng)前種群的最大目標(biāo)值和最小目標(biāo)值。將目標(biāo)值轉(zhuǎn)化成適應(yīng)值的轉(zhuǎn)換公式為

式中r是屬于［0，1］的正實數(shù)，文中取0.5。使用r的目的是:(1)防止式中分母為零的現(xiàn)象出現(xiàn);(2)如果染色體間適應(yīng)值的差距相對比較大，則采用適應(yīng)值比例選擇;如果區(qū)別相對較小，則選擇在相互競爭的染色體中進(jìn)行純隨機(jī)選擇。

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

算法初始種群由兩部分組成:一部分根據(jù)優(yōu)先級規(guī)則產(chǎn)生，保證種群有較好的基礎(chǔ);另一部分隨機(jī)產(chǎn)生，保證初始種群的多樣性。文中采用MINSLK、MINLFT、LST、GRU、WRUP、GRPW、GRD、SRD這幾種常用的優(yōu)先級規(guī)則產(chǎn)生的個體作為初始種群的一部分。執(zhí)行選擇操作過程中，選擇最優(yōu)保持的策略，最后結(jié)果不會比基于優(yōu)先級規(guī)則的算法所求得的結(jié)果差。

3 算例仿真與分析

3.1 算例確定與參數(shù)設(shè)計選擇

選擇標(biāo)準(zhǔn)問題庫PSPLIB中的單執(zhí)行模式項目調(diào)度問題的J30、J60兩組實例，用MATLAB軟件進(jìn)行遺傳算法的設(shè)計。J30和J60均有480個問題實例，J30中的每個實例包括32個活動，其中活動1和活動32是虛活動;J60中的每個實例包括62個活動，其中活動1和活動62是虛活動，每個項目實例需要4種可更新資源。

首先對實驗參數(shù)進(jìn)行分析，確定算法的最優(yōu)參數(shù)設(shè)置。具體參數(shù)設(shè)置為:種群規(guī)模分別取值10、20和40;迭代次數(shù)分別為100、50和25;交叉概率分別為 0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8和0.9;變異概率取值分別為 0.01、0.03、0.05、0.07、0.09、0.1、0.2、0.3 和 0.4。算法的初始種群由兩部分產(chǎn)生，但在確定參數(shù)過程中，為測試算法的有效性，通過盡量擴(kuò)大解的空間方式更清楚地分辨出在不同參數(shù)設(shè)置情況下算法的有效性。計算過程中初始種群均隨機(jī)產(chǎn)生，隨機(jī)產(chǎn)生初始種群存在的不確定性，通過對同一個項目實例測試多次，取其均值的方法予以消除。測試實例選j301_1.sm，為了測試的有效性，使種群規(guī)模保持一定，每個測試最終生成的個體皆為1000個，以項目調(diào)度時間最短作為選擇標(biāo)準(zhǔn)，選擇最優(yōu)個體作為比較對象。

實驗結(jié)果表明:在總個體數(shù)相同情況下，種群規(guī)模與迭代次數(shù)對求解效果的影響較小;當(dāng)Pc∈{0，7，0，8，0，9}、Pm∈{0，2，0，3，0，4}的組合時，求解效果最好。因此選擇參數(shù)如下:種群規(guī)模為40，迭代次數(shù)為25，交叉概率(Pc)為0.7，變異概率(Pm)為0.2。

3.2 仿真結(jié)果與分析

實驗中，對于標(biāo)準(zhǔn)問題J30，根據(jù)各個解距離最優(yōu)解的平均偏差avdew、最大偏差maxdev、最優(yōu)解比例optimal、可行解比率feasible四個指標(biāo)來統(tǒng)計算法的有效性，統(tǒng)計結(jié)果如表1所示。對于標(biāo)準(zhǔn)問題J60，通過各個解與當(dāng)前最好解的平均偏差avdev、最大偏差 maxdev、最優(yōu)解比例 optimal、可行解比率feasible四個指標(biāo)來統(tǒng)計算法的有效性，統(tǒng)計結(jié)果如表2所示。算例中比較的對象是基于2008年的最好結(jié)果。值得指出的是，對于J30這組項目實例的最優(yōu)解已通過精確算法得到;而J60目前還沒有獲得全部的最優(yōu)解，但通過大量的算法給出了最大下界，還給出了經(jīng)過多種算法獲得的當(dāng)前最好的解。

表1 J30.sm的測試性能表

表2 J60.sm的測試性能

從上述計算結(jié)果可以看出，本文所提出的遺傳算法是有效的，在解決關(guān)鍵鏈項目調(diào)度的基準(zhǔn)計劃方面具有較高的準(zhǔn)確性和精確度及可行性。

Kolisch和Drexl的自適應(yīng)搜索算法、Baar等人的禁忌搜索算法、Hartmann的遺傳算法和Bouleimen和Lecocq的模擬退火算法是求解SRCPSP較成功的幾種啟發(fā)式算法［6］。為進(jìn)一步分析本文所設(shè)計的算法的求解效果，將本文算法與這些算法進(jìn)行比較，比較結(jié)果如表3所示。

表3 不同算法結(jié)果比較表

由表3可見，與前人的算法相比，本算法的性能也較好。注意:本文的比較對象是近年的最新結(jié)果，其中有些最好解就是由上述算法得到的。

4 結(jié)束語

本文對單執(zhí)行模式資源受限項目的關(guān)鍵鏈調(diào)度問題基準(zhǔn)計劃的產(chǎn)生設(shè)計了一種遺傳算法，該方法在選擇操作上采用最優(yōu)保持和輪盤賭方法混合的方式，通過算法的結(jié)構(gòu)、編碼解碼規(guī)則、遺傳操作等產(chǎn)生初始種群，并進(jìn)行多次迭代得到最優(yōu)調(diào)度。通過對PSPLIB中J30和J60兩組實例的仿真計算驗證了該算法的有效性，并與目前比較流行的幾種算法比較，驗證了該算法的有效性。探索更有效的算法是進(jìn)一步研究的方向。

［1］彭武良，王承恩.關(guān)鍵鏈項目調(diào)度模型及遺傳算法求解［J］.系統(tǒng)工程學(xué)報，2010，25(1):123 －131.

［2］Bartusch M，M?hring R H，Radermacher F J.Scheduling Project Networks with Resource Constraints and Time Windows［J］.Annals of Operation Research，1988，16:201 －240.

［3］Blazewicz J，Lenstra J K，Rinnooy Kan A H G.Scheduling Subject to Resource Constraints:Classification and Complexity［J］.Discrete Applied Mathematics，1983，5:11－24.

［4］Pate－Cornell M E，Dillon R L.Success Factors and Future Challenges in the Management of Faster Bettercheaper Projects:Lessons Learned from NASA［J］.IEEE Transactions on Engineering Management，2008，48(1):25－35.

［5］Wuliang Peng，Zhongliang Zhang，Zhaofu Tian. The Scheduling of Project Time，Cost and Product Quality.Proceeding of the 2010 Chinese Control and Decision Conference［C］.Xuzhou，China，2010:150 －155.

［6］劉士新.項目優(yōu)化調(diào)度理論與方法［M］.北京:機(jī)械工業(yè)出版社，2007:1－53.

［7］Hartmann S.Project Scheduling with Multiple Modes:A Genetic Algorithm［J］.Annals of Operations Research，2001(102):111 －135.