張　松,陳華平,劉　建

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

復雜時間約束的水利工程項目調(diào)度問題研究

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

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

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

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

1　引　言

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

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

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

2　問題描述

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

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

圖1　項目示例圖Fig.1　Sample project

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

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

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

表1　模型中的符號說明Table 1　The parameters used in model

3　求解算法

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

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

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

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

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

3.2混合遺傳算法

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

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

步驟2生成初始種群pop;

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

步驟4計算個體的適應值;

步驟5選擇父代染色體;

步驟6應用禁止時間窗口交叉算子;

步驟7進行變異操作;

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

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

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

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

3.2.2雙對齊技術(shù)

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

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

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

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

3.2.3禁止時間窗口交叉算子

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

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

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

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

3.2.4變異和選擇

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

4　仿真測試

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

4.1項目實例的生成

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

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

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

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

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

表3、表4中用粗體字顯示的是7個優(yōu)先規(guī)則中前兩位的最好的結(jié)果,從統(tǒng)計數(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平均值的對比.遺傳算法在活動數(shù)量比較小的情況下并沒有明顯優(yōu)勢,隨著活動數(shù)量的增加,遺傳算法的表現(xiàn)要優(yōu)于優(yōu)先規(guī)則,但是遺傳算法花費的時間要遠遠大于優(yōu)先規(guī)則.

表4　多優(yōu)先規(guī)則串行調(diào)度方案結(jié)果統(tǒng)計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對比Fig.6　Compare makespan between GA and priority rule

5　結(jié)束語

具有特殊時間和特殊活動約束的水利項目調(diào)度問題屬于經(jīng)典RCPSP問題的一類擴展,本文針對這類問題提出了多優(yōu)先規(guī)則的啟發(fā)式算法和一種改進的混合遺傳算法進行求解.根據(jù)實驗結(jié)果可以得出以下結(jié)論: 1)針對測試問題,多優(yōu)先規(guī)則的并行調(diào)度方案要優(yōu)于串行調(diào)度方案;2)針對測試問題,基于時間約束的優(yōu)先規(guī)則LFT和LST以及WCS要明顯優(yōu)于其他優(yōu)先規(guī)則;3)改進的遺傳算法在求解大規(guī)模問題時表現(xiàn)很好,但是求解時間隨著問題規(guī)模的增大變大并且遠遠大于啟發(fā)式優(yōu)先規(guī)則所用的時間;具有特殊時間約束的項目調(diào)度問題在實際應用中很普遍,如何結(jié)合問題實際開發(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]劉士新,王夢光,唐加福.資源受限工程調(diào)度問題的優(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]程序,吳澄.一種復雜項目調(diào)度問題的混合智能算法.計算機集成制造系統(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]劉士新,王夢光,唐加福.一種求解資源受限工程調(diào)度問題的遺傳算法.系統(tǒng)工程學報,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.

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

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

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

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