趙軒

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044）

求解RCPSP問(wèn)題的迭代局部搜索算法研究

趙軒

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044）

迭代局部搜索（Iterated Local Search）算法是一個(gè)簡(jiǎn)單、高效的元啟發(fā)式算法。提出一種新的求解資源受限項(xiàng)目調(diào)度問(wèn)題（RCPSP）的迭代局部搜索算法。通過(guò)對(duì)當(dāng)前解進(jìn)行迭代交換實(shí)現(xiàn)局部搜索過(guò)程，再通過(guò)擾動(dòng)多個(gè)任務(wù)的方式進(jìn)行有效的擾動(dòng)，防止陷入局部最優(yōu)。迭代過(guò)程中通過(guò)優(yōu)先對(duì)關(guān)鍵鏈的任務(wù)進(jìn)行局部搜索進(jìn)一步縮小解空間，通過(guò)雙對(duì)齊技術(shù)提高解的質(zhì)量。最終通過(guò)標(biāo)準(zhǔn)問(wèn)題庫(kù)求出各項(xiàng)參數(shù)并且驗(yàn)證算法的性能。

迭代局部搜索；資源受限項(xiàng)目調(diào)度問(wèn)題；擾動(dòng)多個(gè)任務(wù)；關(guān)鍵鏈；雙對(duì)齊

0 引言

資源約束項(xiàng)目調(diào)度問(wèn)題（Resource-Constrained project Scheduling Problem，RCPSP）主要任務(wù)是為調(diào)度項(xiàng)目的活動(dòng)安排時(shí)間和資源，合理使用資源實(shí)現(xiàn)既定目標(biāo)的最優(yōu)化[1]。RCPSP問(wèn)題廣泛地存在于各種領(lǐng)域，如交通設(shè)施的建設(shè)、通信帶寬資源的分配等[2]。

RCPSP問(wèn)題屬于NP-難問(wèn)題，其求解方法可以分為精確算法和啟發(fā)式算法[3]。精確算法能求得最優(yōu)的調(diào)度結(jié)果，但無(wú)法在可接受的時(shí)間內(nèi)求解大規(guī)模的調(diào)度問(wèn)題。因此大多數(shù)文獻(xiàn)都致力于啟發(fā)式方法包括啟發(fā)式算法（heuristic）和元啟發(fā)式算法（meta-heuristic）的研究。啟發(fā)式算法基于一定的啟發(fā)規(guī)則快速得到問(wèn)題的解，但不能保證解的質(zhì)量。與元啟發(fā)式算法相比，啟發(fā)式算法的求解結(jié)果普遍較差，目前不再是研究熱點(diǎn)，而各類元啟發(fā)式算法是RCPSP算法領(lǐng)域的重點(diǎn)研究對(duì)象[4]。盡管基于任務(wù)優(yōu)先規(guī)則的啟發(fā)式算法在解的質(zhì)量上不如元啟發(fā)式算法，但這類算法的計(jì)算速度很快，可用于產(chǎn)生元啟發(fā)式算法所需要的初始解，并且各類任務(wù)優(yōu)先規(guī)則是很多元啟發(fā)式算法的重要組成部分。常用的元啟發(fā)式算法包括禁忌搜索（TS）[5]、模擬退火（SA）[6]、蟻群算法（ACO）[7]、遺傳算法（GA）[8]、迭代局部搜索算法（ILS）[12]。迭代局部搜索算法是一種簡(jiǎn)單而強(qiáng)大的算法框架，已成功應(yīng)用于許多領(lǐng)域，如旅行商問(wèn)題（TSP）[20-21]、車間調(diào)度問(wèn)題[22]和同順序作業(yè)調(diào)度問(wèn)題等[9，23]。

通過(guò)對(duì)RCPSP問(wèn)題的研究，發(fā)現(xiàn)應(yīng)用于RCPSP問(wèn)題的蟻群算法、遺傳算法等元啟發(fā)式算法已經(jīng)得到了深入的研究，而迭代局部搜索算法在RCPSP問(wèn)題中應(yīng)用較少。同時(shí)在研究中發(fā)現(xiàn)同順序流水線調(diào)度問(wèn)題與RCPSP問(wèn)題具有一定的相似性，而Dong等人應(yīng)用于同順序流水線調(diào)度問(wèn)題的ILS算法[9]展現(xiàn)出了強(qiáng)大的性能優(yōu)勢(shì)。因此,我們將ILS應(yīng)用到了求解RCPSP問(wèn)題上。在ILS算法中，局部搜索策略和擾動(dòng)方法對(duì)算法性能有著巨大的影響。為了提高ILS算法的性能，我們基于Dong等人的ILS算法提出了新的算法：優(yōu)先選擇關(guān)鍵鏈上的點(diǎn)進(jìn)行局部搜索，從而減少無(wú)效搜索過(guò)程，提高局部搜索效率；采用擾動(dòng)多個(gè)任務(wù)的擾動(dòng)方式，從而更有效的防止解陷入局部最優(yōu)；文獻(xiàn)[24]指出通過(guò)對(duì)齊技術(shù)可以進(jìn)一步提高RCPSP的求解質(zhì)量并且對(duì)算法運(yùn)行時(shí)間影響較小，因此本文采用雙對(duì)齊策略進(jìn)一步提高本文算法的求解質(zhì)量。通過(guò)改造其中的局部搜索策略和擾動(dòng)策略并加入了新的解的優(yōu)化策略，使其更加適用于RCPSP問(wèn)題。

1 問(wèn)述題描

典型的資源受限項(xiàng)目調(diào)度問(wèn)題可以描述為：在一個(gè)項(xiàng)目中包含任務(wù)集合V={1，…，n}，其中任務(wù)1和n為虛工序，不消耗任何時(shí)間和資源；所有任務(wù)在加工過(guò)程中不可中斷；n個(gè)任務(wù)共享K種可更新資源，其中第k種資源的最大可使用量為Rk；任務(wù)j對(duì)資源k的使用量為rjk，工期為dj，開(kāi)始時(shí)間為sj，結(jié)束時(shí)間為fj，緊前任務(wù)集合為Pj；時(shí)刻t正在進(jìn)行的任務(wù)集合為At。問(wèn)題的目標(biāo)是最小化項(xiàng)目的完工時(shí)間，記為Cmax，即Cmax=min {fj|j=1，…，n}。

RCPSP可描述如下[10]：

該問(wèn)題的調(diào)度目標(biāo)是在滿足約束條件下對(duì)所有任務(wù)排序，確定各個(gè)任務(wù)的開(kāi)始時(shí)間和完成時(shí)間，使項(xiàng)目工期最短。式（2）要求項(xiàng)目調(diào)度計(jì)劃遵循任務(wù)之間的緊前關(guān)系，任何任務(wù)的開(kāi)始時(shí)間必須大于等于其所有緊前任務(wù)完成時(shí)間的最大值。式（3）要求項(xiàng)目調(diào)度計(jì)劃滿足資源約束，在任何時(shí)刻，對(duì)可更新資源的總需求量不能超過(guò)該類資源的最大可使用量。

2 求解RCPSP問(wèn)題的ILS算法

ILS算法是一個(gè)簡(jiǎn)單而通用的求解組合優(yōu)化問(wèn)題的方法，它從一個(gè)初始解開(kāi)始進(jìn)行局部搜索。為了跳出局部最優(yōu)以搜索更好的解，需要通過(guò)接受準(zhǔn)則選擇一個(gè)解并擾動(dòng)該解，然后從擾動(dòng)得到的解出發(fā)再次執(zhí)行局部搜索過(guò)程。ILS算法的偽代碼如圖1所示。

圖1 ILS偽代碼

圖2 所提ILS算法的擾動(dòng)策略Perturbation

基于優(yōu)先規(guī)則的啟發(fā)式方法常被用來(lái)產(chǎn)生初始解[3]。在RCPSP問(wèn)題中通常采用某種優(yōu)先規(guī)則配合串行調(diào)度生成方案（Serial Schedule Generation Scheme，SSGS）來(lái)生成調(diào)度方案，常用的規(guī)則有最早開(kāi)始時(shí)間、最晚開(kāi)始時(shí)間和最晚結(jié)束時(shí)間等優(yōu)先規(guī)則[25]。本文算法采用最早開(kāi)始時(shí)間（Earliest Start time，EST）優(yōu)先規(guī)則配合SSGS生成初始解。

調(diào)度方案可表示為任務(wù)列表，為使任務(wù)列表與調(diào)度方案一一對(duì)應(yīng)，列表中的任務(wù)依據(jù)先序關(guān)系按開(kāi)始時(shí)間升序排列，對(duì)開(kāi)始時(shí)間相同的任務(wù)按任務(wù)編號(hào)升序排列。

我們使用SWAP方式的局部搜索方式，本文通過(guò)實(shí)驗(yàn)證明該方式優(yōu)于插入方式，最優(yōu)解記為π*，當(dāng)前解記為π，局部最優(yōu)解記為π'。查找滿足π（k）=π*（i）的k，將任務(wù)π（k）分別與調(diào)度序列中的最晚前序任務(wù)和最早后繼任務(wù)之間的其它任務(wù)進(jìn)行交換（開(kāi)始時(shí)間相同不交換），將產(chǎn)生的解中的最好解記為π'，如果π'比π好，則令π=π'，如果π比π*好，則令π*=π。局部搜索的順序由π*決定，由于搜索過(guò)程中可能會(huì)發(fā)現(xiàn)更好的解，此時(shí)π*會(huì)隨之更新，搜索的順序也會(huì)隨之更新。

本文測(cè)試了采用插入方式進(jìn)行擾動(dòng)的方法，由于擾動(dòng)強(qiáng)度不夠，無(wú)法取得較優(yōu)的實(shí)驗(yàn)結(jié)果，本文提出了一種新的擾動(dòng)策略，可以通過(guò)同時(shí)擾動(dòng)多個(gè)任務(wù)，更有效的擴(kuò)展解空間，防止局部搜索過(guò)程陷入局部最優(yōu)。算法中s1中存放滿足先序關(guān)系的任務(wù)，s2中存放已經(jīng)交換過(guò)的任務(wù)，防止重復(fù)進(jìn)行無(wú)意義的交換。每次擾動(dòng)后的下一次擾動(dòng)過(guò)程均可產(chǎn)生新的候選序列s1，從而有效擴(kuò)展解空間，防止陷入局部最優(yōu)。新的擾動(dòng)策略的偽代碼如圖2所示。

圖3 所提ILS算法的交換過(guò)程ExchangeProcess

交換過(guò)程可以在完成局部搜索后對(duì)解進(jìn)一步就行優(yōu)化。首先，查找滿足π*（k）=π（i）的k；然后，將任務(wù)π*（k）分別與調(diào)度序列中的最晚前序任務(wù)和最早后繼任務(wù)之間的其它任務(wù)進(jìn)行交換（開(kāi)始時(shí)間相同不交換），將產(chǎn)生的解中的最優(yōu)解記為π'；如果π'比π*好，則令π*=π'，完成一次交換過(guò)程。因?yàn)槿蝿?wù)1和n為虛工序，不能交換在調(diào)度序列中的位置，所以并不加入交換過(guò)程，因此i取值為2到n。交換過(guò)程的偽代碼如圖3所示，時(shí)間復(fù)雜度為O（mn3）。

圖4 本文ILS算法

基于ILS算法的基本思想，提出了新的求解資源受限項(xiàng)目調(diào)度問(wèn)題的ILS算法，首先產(chǎn)生初始解（行2）后開(kāi)始局部搜索過(guò)程，在局部搜索過(guò)程中優(yōu)先對(duì)關(guān)鍵鏈上的點(diǎn)進(jìn)行局部搜索（行6），關(guān)鍵鏈主要是用來(lái)縮小搜索空間，提高搜索效率，關(guān)鍵鏈上的任務(wù)主要是在資源約束下無(wú)自由工作時(shí)間的任務(wù)，文獻(xiàn)[13]中有詳細(xì)介紹。當(dāng)算法陷入局部最優(yōu)后采用新的Perturbation方法（行13）防止其陷入局部最優(yōu)。每次局部搜索過(guò)程后多要通過(guò)雙對(duì)齊操作對(duì)當(dāng)前最優(yōu)解進(jìn)行進(jìn)一步優(yōu)化，文獻(xiàn)[14]表明雙對(duì)齊技術(shù)可以進(jìn)一步提高資源受限項(xiàng)目調(diào)度問(wèn)題的求解質(zhì)量。而算法結(jié)束條件為解未改進(jìn)次數(shù)，當(dāng)解持續(xù)without_imp次未改進(jìn)時(shí)結(jié)束局部搜索過(guò)程。完成局部搜索后最后通過(guò)一個(gè)交換過(guò)程Ex-changeProcess（）（行18）進(jìn)一步提高解的質(zhì)量。ILS算法的偽代碼如圖4所示。

3 參數(shù)評(píng)估和實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)采用PSPLIB問(wèn)題庫(kù)[11]的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證提出的ILS算法的有效性，并使用C++實(shí)現(xiàn)，測(cè)試機(jī)內(nèi)存大小為8G，CPU速度為1.8GHz，運(yùn)行環(huán)境為Windows 7操作系統(tǒng)。

實(shí)驗(yàn)數(shù)據(jù)包括PSPLIB問(wèn)題庫(kù)中的J30、J60、J120三個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集：J30包含480個(gè)實(shí)例，每個(gè)實(shí)例有30個(gè)任務(wù)；J60包含480個(gè)實(shí)例，每個(gè)實(shí)例有60個(gè)任務(wù)；J120有600個(gè)實(shí)例，每個(gè)實(shí)例有120個(gè)任務(wù)。所有問(wèn)題均有4種可更新資源。其中J30的最優(yōu)解已經(jīng)給出，而J60和J120只是給出了下界。

在項(xiàng)目調(diào)度問(wèn)題中一般采用Kolisch提出的“平均偏差率LB”對(duì)算法進(jìn)行評(píng)估。偏差率的求解公式如下：

其中S為利用當(dāng)前算法得到的最優(yōu)解，數(shù)據(jù)集為J30時(shí)SBest為已知最優(yōu)解，數(shù)據(jù)集為J60或者J120時(shí)SBest為無(wú)資源約束時(shí)的工期。

本小節(jié)主要對(duì)試驗(yàn)中的各個(gè)參數(shù)和方法進(jìn)行評(píng)估，首先是擾動(dòng)強(qiáng)度pert，擾動(dòng)是為了跳出局部最優(yōu)，不同的擾動(dòng)強(qiáng)度對(duì)實(shí)驗(yàn)的擾動(dòng)效果有較大的影響。對(duì)比結(jié)果如圖5所示。圖5中為通過(guò)J30計(jì)算擾動(dòng)強(qiáng)度分別為1-20時(shí)的平均偏差率，從圖中得出pert=17可得到最優(yōu)的解，因此在提出的ILS算法中將擾動(dòng)強(qiáng)度設(shè)為17。

下面討論在局部搜索過(guò)程中使用insert還是ex-change的方式進(jìn)行任務(wù)之間的交換。當(dāng)前實(shí)驗(yàn)參數(shù)如下Pert=17，max_cnt=n/2，精英解池大小為2，迭代局部搜索過(guò)程中分別采用exchange和insert的方式，只移動(dòng)關(guān)鍵路徑上的任務(wù),擾動(dòng)過(guò)程中采用exchange方式，結(jié)束條件為產(chǎn)生5000個(gè)解。實(shí)現(xiàn)結(jié)果如表1所示。

表1 局部搜索對(duì)比

圖5 擾動(dòng)強(qiáng)度對(duì)比圖

如表1所示，通過(guò)J30算出的10組平均偏差率可知，局部搜索過(guò)程中采用exchange的方式明顯可以得到更好的實(shí)驗(yàn)結(jié)果。exchange的方式比insert有更大的搜索范圍，更容易找出比較好的解。

分別選擇關(guān)鍵路徑和關(guān)鍵鏈作為約束條件的實(shí)驗(yàn)結(jié)果如表2所示。當(dāng)前實(shí)驗(yàn)參數(shù)如下pert=17，max_cnt= n/2，精英解池大小為2，迭代局部搜索過(guò)程中采用ex-change的方式，分別采用只移動(dòng)關(guān)鍵路徑上的任務(wù)和只移動(dòng)關(guān)鍵鏈上的任務(wù)的方式進(jìn)一步縮小解空間，擾動(dòng)過(guò)程中采用exchange方式，結(jié)束條件為產(chǎn)生5000個(gè)解。

表2 關(guān)鍵鏈和關(guān)鍵路徑對(duì)比

如表2所示通過(guò)J30算出的10組平均偏差率可知，只移動(dòng)關(guān)鍵鏈上的任務(wù)明顯可以得到更好的實(shí)驗(yàn)結(jié)果。

試驗(yàn)中嘗試加入精英解池，每次局部搜索過(guò)程中都從精英解池中選擇一個(gè)解進(jìn)行局部搜索但是通過(guò)實(shí)驗(yàn)證明該算法中精英解池?zé)o法生效。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 精英解池實(shí)驗(yàn)對(duì)比

下面繼續(xù)討論擾動(dòng)過(guò)程中分別采用exchange和insert方式進(jìn)行擾動(dòng)的實(shí)驗(yàn)對(duì)比。當(dāng)前實(shí)驗(yàn)參數(shù)如下Pert=17，max_cnt=n/2，精英解池大小為2，迭代局部搜索過(guò)程中采用exchange的方式，只移動(dòng)關(guān)鍵鏈上的任務(wù),擾動(dòng)過(guò)程中采用exchange和insert方式，結(jié)束條件為產(chǎn)生5000個(gè)解。實(shí)驗(yàn)結(jié)果如表3所示。

表3 擾動(dòng)中的exchange和insert對(duì)比

實(shí)驗(yàn)結(jié)果表明exchange方式會(huì)比insert方式好一些。采用exchange的方式進(jìn)行擾動(dòng)直接交換兩個(gè)任務(wù)的位置可以產(chǎn)生更大擾動(dòng)效果，因此效果會(huì)更好一些。

然后是迭代終止條件的選擇，最初算法選擇按產(chǎn)生解的個(gè)數(shù)作為終止條件，后來(lái)參考了文獻(xiàn)[12]，發(fā)現(xiàn)用解的未改進(jìn)次數(shù)作為算法結(jié)束條件可以得到更好的解。實(shí)驗(yàn)結(jié)果如表4所示。

表4 迭代終止條件對(duì)比

在RCPSP問(wèn)題中通常是在生成相同數(shù)量的調(diào)度方案（1000或5000）的情況下對(duì)算法進(jìn)行評(píng)估。max_without_imp=80時(shí)對(duì)J30問(wèn)題的解有顯著優(yōu)化，并且平均產(chǎn)生4924個(gè)調(diào)度方案。

最后通過(guò)實(shí)驗(yàn)確定max_cnt的值，這個(gè)值決定了擾動(dòng)的頻率對(duì)算法有著極大的影響。實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 max_cnt對(duì)比

由圖7可知當(dāng)max_cnt=4時(shí)可以得到滿意的解并且擾動(dòng)頻率越大產(chǎn)生解的個(gè)數(shù)越多，當(dāng)max_cnt=4解的數(shù)目的平均值為4989符合要求因此確定參數(shù)max_cnt=4。

本文算法的實(shí)驗(yàn)結(jié)果如表5所示，分別列出了本文算法在J30、J60、J90問(wèn)題中的求解結(jié)果和計(jì)算時(shí)間。本文提出了一種新的迭代局部搜索算法，并且通過(guò)大量實(shí)驗(yàn)確定了算法中的各項(xiàng)參數(shù)，使算法性能達(dá)到最優(yōu)，最終求得了較優(yōu)的解。

表5 本文算法實(shí)驗(yàn)結(jié)果

4 結(jié)語(yǔ)

本文算法通過(guò)參考Dong等人應(yīng)用于同順序流水線調(diào)度問(wèn)題的ILS算法，利用迭代局部搜索算法的特性，并加入新的擾動(dòng)策略，配合關(guān)鍵鏈和雙對(duì)齊等技術(shù)成功的提出了一種適用于RCPSP問(wèn)題的新的迭代局部搜索算法，并且得到了比較滿意的解。

參考文獻(xiàn)：

[1]Hartmann S.Project Scheduling under Limited Resources:Models,Methods,and Applications[M].Berlin:Springer,1999.

[2]Weglarz J.Project Scheduling,Recent Models,Algorithms and Applications[M].Dordrecht:Kluwer，1998.

[3]Kolisch R，Drexl A．Adaptive Search for Solving Hard Project Scheduling Problems[J]．Naval Research Logistics(NRL)，1996，43(1): 23-40．

[4]Kolisch,R.,Hartmann,S.,1999.Heuristic Algorithms for Solving the Resource-Constrained Project Scheduling Problem:Classification and Computational Analysis.In:Weglarz,J.(Ed.),Handbook on Recent Advances in Project Scheduling.Kluwer Academic Publishers,Dordrecht,pp.147-178.

[5]Pinson,E.,Prins,C.,Rullier,F.,1994.Using Tabu Search for Solving there Source Constrained Project Scheduling Problem.Technical Report,Universite Catholique de l'Ouest,Angers.

[6]Slowinski,R.,Soniewicki,B.,Weglarz,J.,1994.DSS for Multiobjective Project Scheduling.European Journal of Operational Research 79,220-229.

[7]K.Bouleimen,H.Lecocq,A New Efficient Simulated Annealing Algorithm for the Resource-Constrained Project Scheduling Problem, in:G.Barbarosoglu,S.Karabati,L.?zdamar,G.Ulusoy(Eds.),Proceedings of the Sixth International Workshop onProject Management and Scheduling,Bogazici University,1998：19-22.

[8]Leon,V.J.,Ramamoorthy,B.,1995.Strength and Adaptability of Problem-Space based Neighborhoods for Resource Constrained Scheduling.OR Spectrum 17,173-182.

[9]Dong X,Huang H,Chen P.An Iterated Local Search Algorithm for the Permutation Flowshop Problem with Total Flowtime Criterion[J]. Computers&Operations Research,2009,36(5):1664-1669.

[10]N.Christofides,R.Alvarez-Valdes,J.M.Tamarit,Project Scheduling with Resource Constraints:a Branch and Bound Approach, European Journal of Operational Research，29(1987)：262-273.

[11]R.Kolisch,A.Sprecher,PSPLIB-a Project Scheduling Problem Library:OR Software-ORSEP Operations Research Software Exchange Program,European Journal of Operational Research，96(1997)：205-216.

[12]LU Rui,WANG Chengen.Heuristic Method for the Resource-Constrained Project Scheduling Problem[J].Computer Integrated Manufacturing Systems,2009(12):2439-2444.

[13]Goldratt EM.Critical Chain.Great Barrington,MA:The North River Press,1997.

[14]Vallsv,Balles TINF,Quintanilla S.Justification and RCPSP:a Technique that Pays[J].European Journal of Operational Research, 2005,165(2):375-386.

[15]VA LLSV,Balles TINF,Quintanilla S.A Hybrid Genetic Algorithm for the RCPSP[J].European Journal of Operational Research, 2008,185(2):495-508.

[16]FLESZAR K,HINDI K.Solving the Resource-Constrained Project by a Variable Neighborhood Search[J].European Journal of Operational Research,2004,155(2):402-413.

[17]HINDI K S,YANG,H,FLESZAR K.An Evolutionary Algorithm for Resource-Constrained Project Scheduling[J].IEEE Transactions on Evolutionary Computation,2002,6(5):512-518.

[18]HARTMANN S.A Self-Adapting Genetic Algorithm for Project Scheduling under Resource Constraint[J].Naval Research Logistics, 2002,49(5):433-448.

[19]Helena R.Iterated Local Search.In"Handbook of Metaheuristics",Ed.F.Glover and G.Kochenberger,ISORMS 57,p321-353 (2002),Kluwer.

[20]Martin O,Otto SW,Felten EW.Large-step markov chains for the traveling salesman problem.Complex Systems 1991;5(3):299-326. [21]Martin O,Otto SW.Combining Simulated Annealing with Local Search Heuristics.Annals of Operations Research，1996;63:57-75.

[22]Lourenco HR.Job-Shop Scheduling:Computational Study of Local Search and Large-Step Optimization Methods.European Journal of Operational Research，1995;83:347-64.

[23]Dong X,Chen P,Huang H,et al.A Multi-Restart Iterated Local Search Algorithm for the Permutation Flow Shop Problem MinimizingTotal Flow Time[J].Computers&Operations Research,2012.

[24]Valls V,Ballestin F,Quitanills S.Justification and RCPSP:a Technique that Pays[J].European Journalof Operational Research, 2005,165(2):375-386.

[25]R.Kolisch,Serial and Parallel Resource-Constrained Project Scheduling Methods Revisited:Theory and Computation,European Journal of Operational Research，90(1996)：320-333.

Iterated Local Search Algorithms for the Resource Constrained Project Scheduling Problem

ZHAO Xuan

（School of Computer and Information Technology，Beijing Jiaotong University,Beijing 100044）

Iterated Local Search algorithm is a simple and efficient metaheuristic.Presents a new iterated local search algorithm for resource-con-strained project scheduling problem(RCPSP).Through the iterated exchange of current solution to achieve local search process,and the way of further perturbation of multiple tasks can also prevent local optimization.During the iterative process further reduces the solution space by prioritizing critical chain tasks for local search.Uses the double justification techniques to improve the quality of the solution. Uses the standard library to determine the parameters and verify the quality of the algorithm.

Iterated Local Search;RCPSP;Perturbation of Multiple Tasks;Critical Chain;Double Justification

1007-1423（2016）08-0003-07

10.3969/j.issn.1007-1423.2016.08.001

趙軒（1989-），男，山西河津人，碩士研究生，研究方向?yàn)橘Y源受限項(xiàng)目調(diào)度問(wèn)題

2015-12-24

2016-02-28