復(fù)雜時(shí)間約束的水利工程項(xiàng)目調(diào)度問(wèn)題研究

張　松,陳華平,劉　建

(1.中國(guó)科學(xué)技術(shù)大學(xué)管理學(xué)院,安徽合肥230026; 2.淮河水利委員會(huì)治淮工程建設(shè)管理局,安徽 蚌埠233001)

復(fù)雜時(shí)間約束的水利工程項(xiàng)目調(diào)度問(wèn)題研究

張松1,陳華平1,劉建2

(1.中國(guó)科學(xué)技術(shù)大學(xué)管理學(xué)院,安徽合肥230026; 2.淮河水利委員會(huì)治淮工程建設(shè)管理局,安徽 蚌埠233001)

水利工程項(xiàng)目的調(diào)度屬于資源受限的項(xiàng)目調(diào)度問(wèn)題,但現(xiàn)實(shí)中這類項(xiàng)目存在著一種復(fù)雜的時(shí)間約束,即項(xiàng)目中的某些活動(dòng)在特定時(shí)間段內(nèi)不允許執(zhí)行.針對(duì)這類特殊約束,本文提出了一種新的資源受限項(xiàng)目調(diào)度擴(kuò)展模型,設(shè)計(jì)了多優(yōu)先規(guī)則的啟發(fā)式算法進(jìn)行求解.并在此基礎(chǔ)上提出了一種混合遺傳算法,構(gòu)造了新的交叉算子同時(shí)結(jié)合精英保留和雙對(duì)齊技術(shù)來(lái)改善解的質(zhì)量.最后,用調(diào)整后的項(xiàng)目調(diào)度問(wèn)題庫(kù)(project scheduling problem library)大量實(shí)例驗(yàn)證了算法的有效性.

資源受限;項(xiàng)目調(diào)度;遺傳算法;水利工程

1　引　言

水利工程建設(shè)項(xiàng)目通常具有周期長(zhǎng)、任務(wù)多、資金和資源投入高等特點(diǎn),對(duì)于水利工程項(xiàng)目的合理計(jì)劃和科學(xué)調(diào)度比較困難.上世紀(jì)五十年代發(fā)展起來(lái)的傳統(tǒng)的項(xiàng)目計(jì)劃和調(diào)度方法,如甘特圖、關(guān)鍵路徑法(critical path method,CPM)、計(jì)劃評(píng)審技術(shù)(program evaluation and review technique,PERT)都曾在水利工程項(xiàng)目中獲得廣泛的應(yīng)用.然而,隨著項(xiàng)目規(guī)模的擴(kuò)大、投入資源種類的增多以及工藝流程的復(fù)雜化,對(duì)水利工程項(xiàng)目的計(jì)劃和調(diào)度越來(lái)越困難,這時(shí)管理者更多依賴于其個(gè)人經(jīng)驗(yàn)和人際協(xié)調(diào),往往會(huì)導(dǎo)致調(diào)度安排不合理并帶來(lái)巨大的經(jīng)濟(jì)和社會(huì)損失.因此研究水利工程項(xiàng)目的科學(xué)調(diào)度非常有必要.水利工程項(xiàng)目的調(diào)度屬于資源受限的項(xiàng)目調(diào)度問(wèn)題(resource constraint project problem,RCPSP).RCPSP問(wèn)題是管理領(lǐng)域近幾十年來(lái)研究的熱點(diǎn),其基本模型是要求在滿足項(xiàng)目?jī)?nèi)部各任務(wù)之間的時(shí)序約束和資源約束的同時(shí),優(yōu)化項(xiàng)目的總工期.作為一類組合優(yōu)化問(wèn)題,很多學(xué)者從各個(gè)角度進(jìn)行了總結(jié),詳細(xì)綜述參見(jiàn)文獻(xiàn)[1-6].

針對(duì)RCPSP問(wèn)題在現(xiàn)實(shí)生活中的應(yīng)用,學(xué)者們已經(jīng)探索了很多領(lǐng)域,比如Bomsdorf等[7]研究了電影拍攝中的拍攝調(diào)度問(wèn)題;Lorenzoni等[8]討論了港口中船只在規(guī)定時(shí)間限制下的進(jìn)港操作;Vanhoucke[9]介紹了項(xiàng)目調(diào)度中跟質(zhì)量相關(guān)的時(shí)間槽約束,并以一個(gè)生物技術(shù)研發(fā)項(xiàng)目調(diào)度為例,提出了一種精確求解算法解決了之前提出的時(shí)間槽約束.然而,水利工程項(xiàng)目調(diào)度又不同于傳統(tǒng)的RCPSP問(wèn)題,主要體現(xiàn)在項(xiàng)目的特殊時(shí)間約束方面.關(guān)于時(shí)間約束的RCPSP調(diào)度模型最普遍的是RCPSP/max模型,研究的是活動(dòng)之間最小/最大時(shí)間延遲問(wèn)題,Neumann等[10]進(jìn)行了詳細(xì)的綜述.在此之前,有些學(xué)者從項(xiàng)目管理中活動(dòng)網(wǎng)絡(luò)關(guān)鍵路徑分析的角度Chen[11]提出了time-window和time-schedule兩種特殊的時(shí)間約束.time-window約束中有些活動(dòng)必須在一個(gè)時(shí)間窗口內(nèi)開(kāi)始,time-schedule約束中有些活動(dòng)必須在預(yù)先設(shè)定的時(shí)刻表中的一些時(shí)間點(diǎn)開(kāi)始,比如列車時(shí)刻表.Zhan和Franck等從項(xiàng)目計(jì)劃的角度考慮到了工作日和非工作日的區(qū)別,分別研究了活動(dòng)的日歷約束[12,13],并把活動(dòng)區(qū)分為可中斷活動(dòng)和不可中斷活動(dòng),但在非工作日,所有活動(dòng)都不能進(jìn)行.類似的Yang[14]提出了另外一種time-swtich約束,該約束假設(shè)活動(dòng)只能開(kāi)始于周期性的指定時(shí)間間隔內(nèi).Drexl 等[15]在介紹新的問(wèn)題實(shí)例生成器的構(gòu)建過(guò)程中提出了一種新的“forbidden periods”約束,以排課為例,相同的課不應(yīng)該被間隔成兩段分別排在第一天的結(jié)束和第二天開(kāi)始的時(shí)間,因此為每個(gè)活動(dòng)都指定了一個(gè)最早/最晚結(jié)束時(shí)間.程序[16]在time-window的基礎(chǔ)上提出了預(yù)約時(shí)間窗口約束模型,現(xiàn)實(shí)中有些活動(dòng)必須在預(yù)約時(shí)間段內(nèi)開(kāi)始并完成,針對(duì)這類問(wèn)題作者給出了一種混合智能算法.

已存在的時(shí)間約束關(guān)系大部分是關(guān)于項(xiàng)目中任務(wù)個(gè)體之間的各種相對(duì)時(shí)間限制,而實(shí)際應(yīng)用中既存在任務(wù)之間的相對(duì)時(shí)間約束又存在對(duì)于項(xiàng)目整體的時(shí)間約束,例如堤防和河道建設(shè),建設(shè)工期常常超過(guò)一年于是存在安全度汛的問(wèn)題.項(xiàng)目中有些活動(dòng)不受汛期影響可以安排在汛期進(jìn)行,有些活動(dòng)則必須考慮汛期的影響重新安排.汛期就是一種特殊時(shí)間段,在該特殊時(shí)間段內(nèi)某些活動(dòng)不能夠進(jìn)行而某些活動(dòng)可以進(jìn)行,這樣才能更好地確保項(xiàng)目的安全和工期及提高資源的利用率.這類特殊時(shí)間約束的項(xiàng)目調(diào)度在其他工程建設(shè)中也比較常見(jiàn),稱之為“禁止時(shí)間窗口”約束.Blazewicz等[17]已經(jīng)證明了RCPSP問(wèn)題是NP-hard問(wèn)題,有“禁止時(shí)間窗口”約束的項(xiàng)目調(diào)度進(jìn)一步增加了問(wèn)題的復(fù)雜性和求解難度.

2　問(wèn)題描述

經(jīng)典的RCPSP問(wèn)題描述如下:一個(gè)項(xiàng)目由J個(gè)活動(dòng)組成,活動(dòng)j=1和j=J分別表示項(xiàng)目開(kāi)始和結(jié)束的兩個(gè)虛擬活動(dòng),虛擬活動(dòng)的處理時(shí)間和資源需求都為零.J+表示所有活動(dòng)的集合.每個(gè)活動(dòng)的處理時(shí)間為dj.活動(dòng)j的開(kāi)始時(shí)間為sj,完成時(shí)間為cj,顯然有sj+dj≤cj.假定活動(dòng)一旦開(kāi)始就不能中斷.活動(dòng)之間存在著時(shí)序關(guān)系,用Pred(j)表示活動(dòng)j的緊前活動(dòng)集合,即活動(dòng)j必須在Pred(j)集合中所有活動(dòng)結(jié)束之后才能開(kāi)始,用Succ(j)表示活動(dòng)j的后繼活動(dòng)集合,即集合Succ(j)中所有的活動(dòng)都必須在活動(dòng)j結(jié)束之后才能開(kāi)始.項(xiàng)目涉及K種可更新資源,其中第k種資源每個(gè)周期的容量為Rk.活動(dòng)j在執(zhí)行時(shí)對(duì)資源k的需求量為rk,活動(dòng)在任一時(shí)刻對(duì)資源的需求量不能超過(guò)該資源的容量.所有的參數(shù)默認(rèn)為非負(fù)整數(shù).RCPSP問(wèn)題的優(yōu)化目標(biāo)是在同時(shí)滿足活動(dòng)之間的時(shí)序約束和項(xiàng)目資源約束的前提下,最小化項(xiàng)目的完成時(shí)間(makespan).

如前所述,水利工程項(xiàng)目的調(diào)度具有“禁止時(shí)間窗口”約束,在禁止時(shí)間窗口內(nèi),有些活動(dòng)無(wú)法進(jìn)行,因此這些特殊活動(dòng)的調(diào)度就需要提前或者推遲.如果不在該時(shí)間段內(nèi),則這些特殊活動(dòng)的調(diào)度跟普通活動(dòng)一樣就不再受影響.以一個(gè)項(xiàng)目示例來(lái)進(jìn)一步表述這一問(wèn)題.圖1表示一個(gè)由21個(gè)活動(dòng)(包括兩個(gè)虛擬活動(dòng))組成的項(xiàng)目,假設(shè)項(xiàng)目只使用一種資源R,資源數(shù)量為4.方框表示的活動(dòng)是特殊活動(dòng),特殊活動(dòng)集合為{2,7,11,15,18,19}.假設(shè)特殊時(shí)間段為[5,16].圖2是一個(gè)調(diào)度計(jì)劃.因?yàn)榛顒?dòng)2是特殊活動(dòng)受到特殊時(shí)間段的影響,因此在時(shí)刻15不能立即開(kāi)始,這段時(shí)間就造成了人員和資金等的極大浪費(fèi).圖3顯示的調(diào)度計(jì)劃在特殊時(shí)間段排除了特殊活動(dòng)的影響,因此相對(duì)就能夠獲得比較好的工期.

圖1　項(xiàng)目示例圖Fig.1　Sample project

圖2　調(diào)度計(jì)劃1Fig.2　Schedule 1

圖3　調(diào)度計(jì)劃2Fig.3　Schedule 2

進(jìn)一步擴(kuò)展,假設(shè)由于天氣或者技術(shù)等原因,項(xiàng)目中每個(gè)活動(dòng)都具有各自的“禁止時(shí)間窗口”,其對(duì)應(yīng)的特殊時(shí)間段記為[STi1,STi2],特殊活動(dòng)集合記為U+,U+?J+,則考慮特殊時(shí)間和特殊活動(dòng)約束的RCPSP模型整理如下.其中式(1)表示目標(biāo)函數(shù)為最小化項(xiàng)目的工期;式(2)表示活動(dòng)之間的時(shí)序約束;式(3)表示項(xiàng)目中的資源約束; 式(4)表示特殊的時(shí)間約束,特殊活動(dòng)必須在特殊時(shí)間段開(kāi)始之前完成或者在特殊時(shí)間段結(jié)束之后才能開(kāi)始,如果特殊活動(dòng)集合U+=?,則此問(wèn)題就退化為經(jīng)典的RCPSP問(wèn)題,如果所有活動(dòng)的特殊時(shí)間段都一致,則可以轉(zhuǎn)換為活動(dòng)的日歷約束[13]問(wèn)題.模型中的符號(hào)說(shuō)明整理見(jiàn)表1.

表1　模型中的符號(hào)說(shuō)明Table 1　The parameters used in model

3　求解算法

求解此類特殊時(shí)間約束的項(xiàng)目調(diào)度問(wèn)題,難點(diǎn)在于如何處理跟特殊時(shí)間段相關(guān)的項(xiàng)目活動(dòng),本文提出了多優(yōu)先規(guī)則的啟發(fā)式算法,在此基礎(chǔ)上提出了一種新的混合遺傳算法來(lái)進(jìn)一步改善解的質(zhì)量.

3.1多優(yōu)先規(guī)則的啟發(fā)式算法

啟發(fā)式算法在解決RCPSP問(wèn)題中具有廣泛的應(yīng)用,因?yàn)樗惴ㄇ蠼馑俣瓤?尤其適用大規(guī)模的計(jì)算;他們是很多高效率的元啟發(fā)算法的重要組成部分;算法邏輯直觀且易于理解,為大多數(shù)商業(yè)項(xiàng)目計(jì)劃和調(diào)度軟件所采用來(lái)獲得良好的可行解.通?；趦?yōu)先規(guī)則的啟發(fā)式調(diào)度算法主要由兩部分組成,即進(jìn)度生成機(jī)制和優(yōu)先規(guī)則[18].進(jìn)度生成機(jī)制可細(xì)分為以活動(dòng)為階段變量的串行進(jìn)度生成機(jī)制和以時(shí)間為階段變量的并行進(jìn)度生成機(jī)制.多優(yōu)先規(guī)則法多次使用進(jìn)度生成機(jī)制,每次選用不同的優(yōu)先規(guī)則,最后選擇其中的最優(yōu)解作為最終的調(diào)度方案.解決經(jīng)典的RCPSP問(wèn)題的優(yōu)先規(guī)則對(duì)于本問(wèn)題具有不適應(yīng)性必須對(duì)其進(jìn)行調(diào)整,調(diào)整的主要思路是要結(jié)合特殊時(shí)間段和特殊活動(dòng)的約束,在使用優(yōu)先規(guī)則選擇活動(dòng)時(shí),如果在備選活動(dòng)中有特殊活動(dòng)且特殊活動(dòng)能夠在特殊時(shí)間段開(kāi)始前完成則優(yōu)先選擇特殊活動(dòng).如果備選活動(dòng)中有兩個(gè)及以上的特殊活動(dòng)且這些特殊活動(dòng)都能夠在特殊時(shí)間段開(kāi)始前完成則優(yōu)先選擇活動(dòng)序號(hào)最小的特殊活動(dòng)(tie-breaker).

本文采用的進(jìn)度機(jī)制和優(yōu)先規(guī)則的組合如表2所示.

表2　調(diào)度生成機(jī)制和所用優(yōu)先規(guī)則Table 2　The schedule generation scheme and priority rules

3.2混合遺傳算法

Hartmann[19]在1998年提出的解決RCPSP問(wèn)題的遺傳算法被證明是非常有效的,本文在其基礎(chǔ)上針對(duì)新問(wèn)題的特點(diǎn)設(shè)計(jì)了禁止時(shí)間窗口交叉算子,引入了雙對(duì)齊技術(shù)和精英保留策略來(lái)提高求解質(zhì)量,構(gòu)建了一個(gè)混合遺傳算法.接下來(lái),先簡(jiǎn)單介紹混合遺傳算法的基本流程,然后詳細(xì)介紹混合遺傳算法的各要素.混合遺傳算法的步驟如下.

步驟1進(jìn)行初始化:種群規(guī)模為popsize,迭代代數(shù)為Gen,變異概率為Pm;

步驟2生成初始種群pop;

步驟3使用雙對(duì)齊技術(shù)調(diào)整種群中的染色體;

步驟4計(jì)算個(gè)體的適應(yīng)值;

步驟5選擇父代染色體;

步驟6應(yīng)用禁止時(shí)間窗口交叉算子;

步驟7進(jìn)行變異操作;

步驟8產(chǎn)生新的種群.如果達(dá)到設(shè)定的迭代代數(shù)則算法結(jié)束,否則轉(zhuǎn)向步驟3.

首先生成初始種群,種群規(guī)模為popsize值設(shè)定為一個(gè)偶數(shù),迭代代數(shù)為Gen、變異概率為Pm.然后使用一個(gè)簡(jiǎn)單有效的局部搜索策略―雙對(duì)齊技術(shù)調(diào)整種群中的染色體,詳細(xì)的描述在第3.2.2節(jié).接下來(lái)計(jì)算個(gè)體的適應(yīng)值.隨機(jī)的從父代種群中選擇兩個(gè)染色體應(yīng)用禁止時(shí)間窗口交叉算子(第3.2.3節(jié))產(chǎn)生兩個(gè)新的個(gè)體.再對(duì)新個(gè)體進(jìn)行變異操作.將新生成的個(gè)體加入種群則目前種群規(guī)模就變?yōu)榱?xpopsize,最后根據(jù)適應(yīng)值的大小將染色體進(jìn)行排序,從中選擇適應(yīng)值較好的個(gè)體保存,使得種群規(guī)?；謴?fù)為popsize,產(chǎn)生了新的種群.重復(fù)進(jìn)行以上步驟,直到達(dá)到設(shè)定的迭代代數(shù)Gen或者預(yù)定的CPU時(shí)間.

3.2.1初始種群的產(chǎn)生和適應(yīng)值函數(shù)

算法采用緊前關(guān)系可行活動(dòng)鏈表編碼方式,用串行調(diào)度方案作為解碼規(guī)則.與Hartmann遺傳算法不同的地方在于解碼的時(shí)候需要考慮“禁止時(shí)間窗口”的特殊時(shí)間約束,如果特殊活動(dòng)的開(kāi)始時(shí)間受到影響則推遲該活動(dòng)的開(kāi)始時(shí)間.初始種群一部分是隨機(jī)生成,另一部分則是采用多優(yōu)先規(guī)則啟發(fā)式算法當(dāng)中的比較好的規(guī)則產(chǎn)生的解.遺傳算法使適應(yīng)值高的個(gè)體具有較高的生存機(jī)會(huì),因此需將極小化目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)值函數(shù),適應(yīng)值函數(shù)f(i)=Fmax-Si,其中Fmax為最近5代中個(gè)體對(duì)應(yīng)的最大工期,Si是對(duì)個(gè)體i解碼所得的總工期即目標(biāo)函數(shù)值.

3.2.2雙對(duì)齊技術(shù)

已有眾多學(xué)者使用局部搜索策略作為算子改進(jìn)了遺傳算法獲得了更好的解,本文使用雙對(duì)齊技術(shù)作為局部改進(jìn)算子來(lái)實(shí)現(xiàn)同樣的目的.由于雙對(duì)齊技術(shù)的簡(jiǎn)單、快速和有效,很適合應(yīng)用于解決RCPSP問(wèn)題. Valls等學(xué)者[20,21]對(duì)該方法進(jìn)行了詳細(xì)的介紹.在實(shí)現(xiàn)對(duì)齊方法之前,對(duì)相關(guān)的概念進(jìn)行定義.

定義1一個(gè)積極調(diào)度(左積極調(diào)度)是指調(diào)度中沒(méi)有一個(gè)活動(dòng)能在不推遲其他活動(dòng)或不違反約束的情況下提早開(kāi)始.類似的,右積極調(diào)度是指一個(gè)調(diào)度,其中沒(méi)有一個(gè)活動(dòng)能在不提前其他活動(dòng),或者違反約束或者增加工期的情況下更晚結(jié)束.

定義2右齊(左齊)活動(dòng)操作,給定一個(gè)調(diào)度S,右齊(左齊)一個(gè)活動(dòng)j/=J(1),獲得一個(gè)新調(diào)度S′,并且盡可能的大.即在其他活動(dòng)開(kāi)始時(shí)間不變的條件下,盡可能的推遲活動(dòng)j的開(kāi)始時(shí)間.

對(duì)一個(gè)調(diào)度方案的雙對(duì)齊操作就是首先以活動(dòng)的完成時(shí)間降序排列,然后對(duì)每個(gè)活動(dòng)進(jìn)行右齊操作,依次獲得活動(dòng)最晚可以完成的時(shí)間,即其后續(xù)任務(wù)中最早開(kāi)始的時(shí)間之前且滿足資源約束關(guān)系的最晚時(shí)間.然后在此基礎(chǔ)上再對(duì)每個(gè)活動(dòng)進(jìn)行左齊操作,將活動(dòng)按開(kāi)始時(shí)間升序排列,逐個(gè)將活動(dòng)安排在最早可以開(kāi)始的滿足時(shí)序和資源約束的時(shí)刻上開(kāi)始.當(dāng)所有任務(wù)都調(diào)度完畢以后,即可得到至少不差于原方案的調(diào)度計(jì)劃.

3.2.3禁止時(shí)間窗口交叉算子

通過(guò)分析具有“禁止時(shí)間窗口”約束的RCPSP問(wèn)題的調(diào)度方案,發(fā)現(xiàn)如果跟“禁止時(shí)間窗口”對(duì)應(yīng)的特殊時(shí)間段沒(méi)有安排活動(dòng),則該特殊時(shí)間段的資源利用率相對(duì)就比較低,反之,則說(shuō)明特殊時(shí)間段都安排了活動(dòng),項(xiàng)目調(diào)度沒(méi)有產(chǎn)生停頓的現(xiàn)象,更可能取得好的項(xiàng)目工期.于是借鑒Valls[21]中的尖峰交叉算子,本文提出了一種新的交叉算子,稱之為禁止時(shí)間窗口交叉算子.詳細(xì)描述如下.用S表示一個(gè)調(diào)度, [U1,U2]表示一個(gè)“禁止時(shí)間窗口”對(duì)應(yīng)的特殊時(shí)間段,用SA(u)表示調(diào)度中在特殊時(shí)間段內(nèi)運(yùn)行的活動(dòng)集合, 即SA(u)={i∈J+;[U1,U2[∩[si,ci[/=?}.調(diào)度方案S在特殊時(shí)間段內(nèi)資源使用率(resource utilisation ratio, RUR)為

給定一個(gè)閾值δ,這里設(shè)定δ=0.7,如果RUR(u)≥δ,則說(shuō)明調(diào)度方案S在特殊時(shí)間段內(nèi)是高資源使用率.用λ表示在特殊時(shí)間段執(zhí)行的活動(dòng)列表,λ=(jp,jp+1,...,jq),此列表有可能為空.假設(shè)選擇兩個(gè)個(gè)體F, M作為父代,如果父代F,M中的特殊時(shí)間段資源使用率都不高于δ,則使用傳統(tǒng)的一點(diǎn)交叉算子;如果F,M中任一特殊時(shí)間段的資源使用率高于δ,則使用兩點(diǎn)交叉算子,交叉點(diǎn)分別為λ的開(kāi)始和結(jié)束活動(dòng)的位置.如圖5所示.

圖5　禁止時(shí)間窗口交叉示例Fig.5　Forbidden time windows crossover operator

禁止時(shí)間窗口交叉算子跟特殊時(shí)間段的資源利用率密切相關(guān),如果父代中特殊時(shí)間段的資源利用率比較高則通過(guò)兩點(diǎn)交叉將該特征保存到子代中;如果父代中特殊時(shí)間段的資源利用率沒(méi)有達(dá)到閾值,則進(jìn)行一點(diǎn)交叉操作增加解的多樣性.

3.2.4變異和選擇

活動(dòng)鏈表中基因變異采用對(duì)換變異,隨機(jī)選擇兩個(gè)基因進(jìn)行對(duì)換,依變異概率交換其位置,如果交換后的活動(dòng)序列不滿足緊前關(guān)系約束,則恢復(fù)原來(lái)的位置.選擇采用二元競(jìng)賽機(jī)制,精英保留策略[22]嵌入其中,以保證當(dāng)前種群中一定數(shù)量的最優(yōu)個(gè)體直接進(jìn)入下一代種群.選擇概率為

4　仿真測(cè)試

本文的算法均采用java實(shí)現(xiàn),測(cè)試環(huán)境為Intel雙核CPU主頻3.4G,內(nèi)存大小8G,操作系統(tǒng)為Windows7.

4.1項(xiàng)目實(shí)例的生成

經(jīng)典RCPSP問(wèn)題基本上都采用Kolisch等設(shè)計(jì)[23]的PSPLIB實(shí)例庫(kù)來(lái)對(duì)算法進(jìn)行測(cè)試,而本問(wèn)題研究了新的擴(kuò)展模型,原有的實(shí)例庫(kù)不再適用,因此需要在PSPLIB實(shí)例庫(kù)的基礎(chǔ)上增加新的時(shí)間約束.PSPLIB實(shí)例庫(kù)中的每個(gè)項(xiàng)目實(shí)例都記載了當(dāng)前學(xué)者們用各種算法求得的項(xiàng)目完工最短工期,特殊時(shí)間段的大小隨機(jī)設(shè)定為原實(shí)例庫(kù)中最短工期的15%～25%,特殊時(shí)間段的起始位置在整個(gè)項(xiàng)目最短工期范圍內(nèi)隨機(jī)生成,但不包含開(kāi)始和結(jié)束的時(shí)刻.特殊活動(dòng)隨機(jī)生成不允許重復(fù),特殊活動(dòng)占整個(gè)項(xiàng)目活動(dòng)數(shù)量的8%～15%,不包括開(kāi)始和結(jié)束兩個(gè)虛活動(dòng).活動(dòng)數(shù)量為30、60、90、120的四類項(xiàng)目實(shí)例,對(duì)應(yīng)生成的算例數(shù)量分別為480、480、480和600.

遺傳算法中的各參數(shù)設(shè)置如下:變異概率Pm設(shè)定為0.05,popsize設(shè)定為活動(dòng)數(shù)量,算法的終止條件為迭代次數(shù)Gen設(shè)置為200或者在連續(xù)50代內(nèi)結(jié)果沒(méi)有變化.

4.2算法結(jié)果及比較

首先將J120的一個(gè)實(shí)例分別用并行調(diào)度方案和WCS優(yōu)先規(guī)則、串行調(diào)度方案和LST優(yōu)先規(guī)則以及混合遺傳算法進(jìn)行求解,發(fā)現(xiàn)makespan值分別為209、288、186.分析調(diào)度方案,發(fā)現(xiàn)該實(shí)例的“禁止時(shí)間窗口”對(duì)應(yīng)的特殊時(shí)間段比較長(zhǎng)并且起始位置位于項(xiàng)目前段,特殊活動(dòng)數(shù)量占整個(gè)項(xiàng)目活動(dòng)數(shù)量的12%,啟發(fā)式算法只能簡(jiǎn)單確定一個(gè)調(diào)度方案,目標(biāo)解值的優(yōu)劣非常隨機(jī),而混合遺傳算法能夠充分探索解空間,不斷進(jìn)行“優(yōu)勝劣汰”,從而一步步逼近問(wèn)題最優(yōu)解.接下來(lái)針對(duì)所有J30、J60、J90和J120的項(xiàng)目實(shí)例進(jìn)行求解,結(jié)果匯總?cè)缦卤硭?表3和表4分別記錄的是采用并行調(diào)度方案和串行調(diào)度方案多優(yōu)先規(guī)則求解的情況,在活動(dòng)數(shù)量是30、60、90的各480個(gè)項(xiàng)目實(shí)例和活動(dòng)數(shù)量是120的600個(gè)項(xiàng)目實(shí)例中,統(tǒng)計(jì)了各個(gè)優(yōu)先規(guī)則求出的解中是各優(yōu)先規(guī)則求得的解中的最小值的次數(shù)以及所用的時(shí)間.表5、表6中記錄了各個(gè)規(guī)則求取的所有算例makespan的平均值,最后一列是所有算例最好解的平均值.表7記錄的是使用遺傳算法的求解結(jié)果.

表3　多優(yōu)先規(guī)則并行調(diào)度方案結(jié)果統(tǒng)計(jì)Table 3　Result of multi-priority rules parallel schedule

表3、表4中用粗體字顯示的是7個(gè)優(yōu)先規(guī)則中前兩位的最好的結(jié)果,從統(tǒng)計(jì)數(shù)據(jù)可以看出并行調(diào)度方案中,優(yōu)先規(guī)則WCS和LST的表現(xiàn)最好;在串行調(diào)度方案中,優(yōu)先規(guī)則LST和LFT的表現(xiàn)最好.從表5、表6中可以看出使用多優(yōu)先規(guī)則的并行調(diào)度方案比串行調(diào)度方案表現(xiàn)要好,尤其是并行調(diào)度方案中的優(yōu)先規(guī)則WCS和LST表現(xiàn)最為突出.圖6展示了遺傳算法和并行調(diào)度方案多優(yōu)先規(guī)則(PSPR)、串行調(diào)度方案多優(yōu)先規(guī)則(SSPR)最好解的makespan平均值的對(duì)比.遺傳算法在活動(dòng)數(shù)量比較小的情況下并沒(méi)有明顯優(yōu)勢(shì),隨著活動(dòng)數(shù)量的增加,遺傳算法的表現(xiàn)要優(yōu)于優(yōu)先規(guī)則,但是遺傳算法花費(fèi)的時(shí)間要遠(yuǎn)遠(yuǎn)大于優(yōu)先規(guī)則.

表4　多優(yōu)先規(guī)則串行調(diào)度方案結(jié)果統(tǒng)計(jì)Table 4　Result of multi-priority rules serial schedule

表5　并行調(diào)度方案平均makespanTable 5　The parallel schedule mean makespan

表6　串行調(diào)度方案平均makespanTable 6　The serial schedule mean makespan

表7　遺傳算法平均makespanTable 7　The genetic algorithm mean makespan

圖6　遺傳算法和啟發(fā)式優(yōu)先規(guī)則makespan對(duì)比Fig.6　Compare makespan between GA and priority rule

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

具有特殊時(shí)間和特殊活動(dòng)約束的水利項(xiàng)目調(diào)度問(wèn)題屬于經(jīng)典RCPSP問(wèn)題的一類擴(kuò)展,本文針對(duì)這類問(wèn)題提出了多優(yōu)先規(guī)則的啟發(fā)式算法和一種改進(jìn)的混合遺傳算法進(jìn)行求解.根據(jù)實(shí)驗(yàn)結(jié)果可以得出以下結(jié)論: 1)針對(duì)測(cè)試問(wèn)題,多優(yōu)先規(guī)則的并行調(diào)度方案要優(yōu)于串行調(diào)度方案;2)針對(duì)測(cè)試問(wèn)題,基于時(shí)間約束的優(yōu)先規(guī)則LFT和LST以及WCS要明顯優(yōu)于其他優(yōu)先規(guī)則;3)改進(jìn)的遺傳算法在求解大規(guī)模問(wèn)題時(shí)表現(xiàn)很好,但是求解時(shí)間隨著問(wèn)題規(guī)模的增大變大并且遠(yuǎn)遠(yuǎn)大于啟發(fā)式優(yōu)先規(guī)則所用的時(shí)間;具有特殊時(shí)間約束的項(xiàng)目調(diào)度問(wèn)題在實(shí)際應(yīng)用中很普遍,如何結(jié)合問(wèn)題實(shí)際開(kāi)發(fā)更有效率的智能算法將是以后工作的研究方向.

[1]Tamás K.Project scheduling:A review of recent books.Operations Research Letters,2005,33(1):105–110.

[2]Kolisch R,Padman R.An integrated survey of deterministic project scheduling.Omega:The International Journal of Management Science,2001,29(3):249–272.

[3]Hartmann S,Briskorn D.A survey of variants and extensions of the resource-constrained project scheduling problem.European Journal of Operational Research,2010,207(1):1–14.

[4]Brucker P,Drexl A,Mohring R,et al.Resource-constrained project scheduling:Notation,classification,models,and methods. European Journal of Operational Research,1999,112(1):3–41.

[5]Odedairo B O,Oladokun V.Relevance and applicability of multi-objective resource constrained project scheduling problem:Review article.Engineering,Technology&Applied Science Research,2011,1(6):144–150.

[6]劉士新,王夢(mèng)光,唐加福.資源受限工程調(diào)度問(wèn)題的優(yōu)化方法綜述.控制與決策,2001,16(B11):647–651. Liu S X,Wang M G,Tang J F.The optimization algorithms for solving resource-constrained project scheduling problem:A review. Control and Decision,2001,16(B11):647–651.(in Chinese)

[7]Bomsdorf F,Derigs U.A model,heuristic procedure and decision support system for solving the movie shoot scheduling problem. OR Spectrum,2008,30(4):751–772.

[8]Lorenzoni L L,Ahonen H,Alvarenga A G.A multi-mode resource-constrained scheduling problem in the context of port operations. Computers&Industrial Engineering,2006,50(1/2):55–65.

[9]Vanhoucke M.Scheduling an R&D project with quality-dependent time slots//Computational Science and its Applications.Berlin: Springer,2006:621–630.

[10]Neumann K,Schwindt C,Zimmermann J.Resource-constrained project scheduling with time windows//Perspectives in modern project scheduling.New York:Springer,2006:375–407.

[11]Chen Y L,Rinks D,Tang K.Critical path in an activity network with time constraints.European Journal of Operational Research, 1997,100(1):122–133.

[12]Zhan J.Calendarization of time planning in MPM networks.Zeitschrift für Operations Research,1992,36(5):423–438.

[13]Franck B,Neumann K,Schwindt C.Project scheduling with calendars.OR Spektrum,2001,23(3):325–334.

[14]Yang H H,Chen Y L.Finding the critical path in an activity network with time-switch constraints.European Journal of Operational Research,2000,120(3):603–613.

[15]Drexl A,Nissen R,Patterson J H,et al.ProGen/πx:An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions.European Journal of Operational Research,2000,125(1):59–72.

[16]程序,吳澄.一種復(fù)雜項(xiàng)目調(diào)度問(wèn)題的混合智能算法.計(jì)算機(jī)集成制造系統(tǒng),2006,12(4):585–589. Chen X,Wu C.Hybrid algorithm for complex project scheduling.Computer Integrated Manufacturing Systems,2006,12(4):585–589.(in Chinese)

[17]Blazewicz J,Lenstra J K,Kan A H G R.Scheduling subject to resource constraints:Classification and complexity.Discrete Applied Mathematics,1983,5(1):11–24.

[18]Kolisch R.Serial and parallel resource-constrained project scheduling methods revisited:Theory and computation.European Journal of Operational Research,1996,90(2):320–333.

[19]Hartmann S.A competitive genetic algorithm for resource-constrained project scheduling.Naval Research Logistics,1998,45(7): 733–750.

[20]Valls V,Ballestin F,Quintanilla S.Justification and RCPSP:A technique that pays.European Journal of Operational Research,2005, 165(2):375–386.

[21]Valls V,Ballestín F,Quintanilla S.A hybrid genetic algorithm for the resource-constrained project scheduling problem.European Journal of Operational Research,2008,185(2):495–508.

[22]劉士新,王夢(mèng)光,唐加福.一種求解資源受限工程調(diào)度問(wèn)題的遺傳算法.系統(tǒng)工程學(xué)報(bào),2002,17(1):1–7. Liu S X,Wang M G,Tang J F.GA for solving resource-constrained project scheduling problem.Journal of Systems Engineering, 2002,17(1):1–7.(in Chinese)

[23]Kolisch R,Sprecher A.PSPLIB:A project scheduling problem library:OR software–ORSEP operations research software exchange program.European Journal of Operational Research,1997,96(1):205–216.

Research on the complicated time-constrained project scheduling in water conservancy

Zhang Song1,Chen Huaping1,Liu Jian2
(1.School of Management,University of Science and Technology,Hefei 230026,China; 2.Engineering Construction Management Bureau,Huaihe River Conservancy Commission,Bengbu 233001,China)

Water conservancy project scheduling is a resource-constrained project scheduling problem(RCPSP),which is usually limited by complicated time constraints and some activities cannot be executed within the predefined time period.To address this issue,a novel variant model of RCPSP is proposed and a multipriority rules heuristic approach is developed.Furthermore,a hybrid genetic algorithm is presented.And a new designed crossover operator is combined with the elitism strategy and double justification technique, which greatly improves the quality of the solution.Finally,computational experiments are conducted on randomly generated and modified instances based on the benchmark problem instance sets in a project scheduling problem library,and the results show the efficiency of the proposed approaches.

resource-constrained;project scheduling;genetic algorithm;water conservancy

TP273

A

1000-5781(2016)01-0135-10

10.13383/j.cnki.jse.2016.01.014

2013-11-27;

2014-08-25.

國(guó)家自然科學(xué)基金資助項(xiàng)目(71171184);水利部公益性行業(yè)科研專項(xiàng)資助項(xiàng)目(201001017).

張松(1980—),男,安徽宿州人,博士生,研究方向:項(xiàng)目調(diào)度、批調(diào)度、智能優(yōu)化算法等,Email:eshine80@mail.ustc.edu.cn;

陳華平(1965—),男,江蘇江陰人,教授,博士生導(dǎo)師,研究方向:信息系統(tǒng)、批調(diào)度、網(wǎng)絡(luò)計(jì)算、高性能計(jì)算、智能計(jì)算及其應(yīng)用等,Email:hpchen@ustc.edu.cn;

劉建(1961—),男,江蘇徐州人,教授,研究方向:管理、水利工程建設(shè)等,Email:liujian3037@163.com.