改進類電磁算法在資源受限項目調(diào)度問題中的應(yīng)用研究.pdf

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

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

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

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

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