遺傳算法的關(guān)鍵鏈項(xiàng)目調(diào)度基準(zhǔn)計(jì)劃問(wèn)題研究

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

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

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

1 模型構(gòu)建

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

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

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

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

2 遺傳算法設(shè)計(jì)

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

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

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

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

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

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

當(dāng)時(shí)刻為4時(shí)，部分拓?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ù)。以此類推，可得到這個(gè)項(xiàng)目在該優(yōu)先權(quán)下的拓?fù)渑判?，如圖2所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算例仿真與分析

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

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

首先對(duì)實(shí)驗(yàn)參數(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ù)過(guò)程中，為測(cè)試算法的有效性，通過(guò)盡量擴(kuò)大解的空間方式更清楚地分辨出在不同參數(shù)設(shè)置情況下算法的有效性。計(jì)算過(guò)程中初始種群均隨機(jī)產(chǎn)生，隨機(jī)產(chǎn)生初始種群存在的不確定性，通過(guò)對(duì)同一個(gè)項(xiàng)目實(shí)例測(cè)試多次，取其均值的方法予以消除。測(cè)試實(shí)例選j301_1.sm，為了測(cè)試的有效性，使種群規(guī)模保持一定，每個(gè)測(cè)試最終生成的個(gè)體皆為1000個(gè)，以項(xiàng)目調(diào)度時(shí)間最短作為選擇標(biāo)準(zhǔn)，選擇最優(yōu)個(gè)體作為比較對(duì)象。

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

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

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

表1 J30.sm的測(cè)試性能表

表2 J60.sm的測(cè)試性能

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

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

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

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

4 結(jié)束語(yǔ)

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

［1］彭武良，王承恩.關(guān)鍵鏈項(xiàng)目調(diào)度模型及遺傳算法求解［J］.系統(tǒng)工程學(xué)報(bào)，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］劉士新.項(xiàng)目?jī)?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.