改進類電磁算法在資源受限項目調度問題中的應用研究.pdf

1、資源受限項目調度問題(Resource Constrained SchedulingProbolem，RCPSP)是項目管理問題中的關鍵問題之一。此類問題與一般項目調度問題的不同之處在于，RCPSP問題要求項目工序在執(zhí)行時不僅要滿足時序約束，同時也要滿足特定的資源約束。因此RCPSP問題比一般的項目調度問題更復雜，而這類復雜的問題常見于工程建設、軟件開發(fā)以及制造業(yè)之中。RCPSP問題已經被證明為NP難問題，求解算法的研究一直是該領域的研

2、究熱點和研究難點。本文所研究的是類電磁算法在RCPSP問題上的應用，類電磁算法是一種十分適用于求解RCPSP這樣一類時間窗口問題的新算法，從已有的研究成果中可以看出類電磁算法應用在RCPSP問題上具有較高的求解性能。但由于算法提出時間比較短，研究成果還比較少，算法本身還有一些缺陷和值得改進之處，因此研究該算法在RCPSP問題上的應用具有重大的理論和現實意義。
　　 本文對RCPSP問題應用類電磁算法進行了研究，主要做了以下工作:

3、
　　 (1)首先本文介紹了RCPSP問題的產生與發(fā)展、研究現狀與研究意義。然后介紹了該問題的一般求解方法，包括精確求解算法、基于優(yōu)先規(guī)則的啟發(fā)式算法以及智能算法。文章重點介紹了目前研究比較成熟的遺傳算法、蟻群算法、粒子群算法及模擬退火算法，對這些算法的研究情況進行了梳理和總結并指出了現有算法研究的不足之處。然后文章對本文研究的新興的類電磁算法進行了介紹，對該算法的原理、特點以及參數設置進行了說明;文章同時指出EM算法適合于求解

4、RCPSP問題的根本原因，并對其優(yōu)勢與不足之處進行了詳細分析。
　　 (2)本文重點研究了類電磁算法在RCPSP問題上的改進，這同時也是文章的創(chuàng)新之處。鑒于標準類電磁算法求解RCPSP問題的不足，文章提出了三種相互聯系但又有區(qū)別的算法:IEM、IEM-SNS以及IEM-VNS。IEM算法對原有的EM算法參數進行了改進，改進后的參數設計使得算法收斂速度更快并且減緩了算法陷入局部最優(yōu)的速度，仿真實驗證明了改進的有效性。IEM-SNS

5、算法在IEM算法的基礎上引入了局部搜索策略，定義了粒子解的鄰域空間，每次迭代完成之后都會對每個粒子的鄰域空間進行搜索，加快算法的收斂速度。IEM-VNS是在IEM-SNS的基礎上引入了變鄰域搜索的概念，在鄰域搜索過程中有選擇的跳出原搜索鄰域，這樣做一方面能夠加快算法的收斂速度，同時也能夠避免算法陷入局部最優(yōu)，使得改進后的算法平衡了算法的搜索能力和探索能力。通過對比實驗，IEM-VNS比IEM-SNS及GA-SNS具有更好的求解性能，同時