趙軒

（北京交通大學計算機與信息技術學院，北京 100044）

求解RCPSP問題的迭代局部搜索算法研究

趙軒

（北京交通大學計算機與信息技術學院，北京 100044）

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

迭代局部搜索；資源受限項目調度問題；擾動多個任務；關鍵鏈；雙對齊

0 引言

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

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

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

1 問述題描

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

RCPSP可描述如下[10]：

該問題的調度目標是在滿足約束條件下對所有任務排序，確定各個任務的開始時間和完成時間，使項目工期最短。式（2）要求項目調度計劃遵循任務之間的緊前關系，任何任務的開始時間必須大于等于其所有緊前任務完成時間的最大值。式（3）要求項目調度計劃滿足資源約束，在任何時刻，對可更新資源的總需求量不能超過該類資源的最大可使用量。

2 求解RCPSP問題的ILS算法

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

圖1 ILS偽代碼

圖2 所提ILS算法的擾動策略Perturbation

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

調度方案可表示為任務列表，為使任務列表與調度方案一一對應，列表中的任務依據(jù)先序關系按開始時間升序排列，對開始時間相同的任務按任務編號升序排列。

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

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

圖3 所提ILS算法的交換過程ExchangeProcess

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

圖4 本文ILS算法

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

3 參數(shù)評估和實驗結果分析

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

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

在項目調度問題中一般采用Kolisch提出的“平均偏差率LB”對算法進行評估。偏差率的求解公式如下：

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

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

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

表1 局部搜索對比

圖5 擾動強度對比圖

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

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

表2 關鍵鏈和關鍵路徑對比

如表2所示通過J30算出的10組平均偏差率可知，只移動關鍵鏈上的任務明顯可以得到更好的實驗結果。

試驗中嘗試加入精英解池，每次局部搜索過程中都從精英解池中選擇一個解進行局部搜索但是通過實驗證明該算法中精英解池無法生效。實驗結果如圖6所示。

圖6 精英解池實驗對比

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

表3 擾動中的exchange和insert對比

實驗結果表明exchange方式會比insert方式好一些。采用exchange的方式進行擾動直接交換兩個任務的位置可以產(chǎn)生更大擾動效果，因此效果會更好一些。

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

表4 迭代終止條件對比

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

最后通過實驗確定max_cnt的值，這個值決定了擾動的頻率對算法有著極大的影響。實驗結果如圖7所示。

圖7 max_cnt對比

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

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

表5 本文算法實驗結果

4 結語

本文算法通過參考Dong等人應用于同順序流水線調度問題的ILS算法，利用迭代局部搜索算法的特性，并加入新的擾動策略，配合關鍵鏈和雙對齊等技術成功的提出了一種適用于RCPSP問題的新的迭代局部搜索算法，并且得到了比較滿意的解。

參考文獻：

[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-），男，山西河津人，碩士研究生，研究方向為資源受限項目調度問題

2015-12-24

2016-02-28