求解作業(yè)車間調度問題的元啟發(fā)式算法.pdf

1、作業(yè)車間調度問題是最難的組合優(yōu)化問題之一，已被證明是NP-Hard問題，它的求解對于NP-hard問題的求解將有很大的啟發(fā)和推動作用。由于求解作業(yè)車間調度問題有著巨大的理論和現(xiàn)實意義，它已經成為了學術界的研究熱點。
　　遺傳算法是一種有效的求解車間調度問題的元啟發(fā)式算法，遵從“適者生存，遺傳進化”準則，但其在求解過程中種群容易過早收斂。針對于遺傳算法過早收斂的缺點，本文引入了個體間分散度概念與其計算方法，提出了一種基于分散度的多種

2、群遺傳算法。在多種群遺傳算法中引入分散種群來防止種群過早收斂。在闡述了算法過程及算法設計的關鍵部分后，使用國際基準實例測試多種群遺傳算法的搜索性能，驗證該算法相比傳統(tǒng)的遺傳算法有著更好的搜索性能。
　　禁忌搜索算法是局部搜索算法中一種有效的求解車間調度問題算法。算法時間復雜度較小，搜索效率較高，但禁忌搜索算法容易陷入局部最優(yōu)解和搜索死循環(huán)中。為使算法有更好的跳出局部最優(yōu)和循環(huán)搜索能力，本文通過引入了分散度概念，設計了一種新的更新精

3、華解集策略和一種禁忌表長度動態(tài)變化策略。并用國際基準算例對這兩種策略進行測試，驗證了這兩種策略對傳統(tǒng)的禁忌搜索算法性能上有很大程度上的改進。
　　單一的近似算法對作業(yè)車間調度問題求解能力有限，而兩種或多種算法的混合算法具有更好的搜索能力。本文中將多種群遺傳算法與改進型禁忌搜索算法組成一種多種群遺傳禁忌混合算法。算法通過遺傳算法的分散搜索與禁忌搜索算法的集中搜索來提高對作業(yè)車間調度問題的求解能力。最后使用國際基準算例對算法測試，發(fā)現(xiàn)