一種混合蟻群算法在JSP問題中的應用研究.pdf

1、隨著市場競爭的日趨激烈，每個企業(yè)都在尋求更好的生產與運作管理方案，以提高企業(yè)的生產、經營和管理效率，從而提高企業(yè)的核心競爭優(yōu)勢。生產與運作管理的核心是車間調度問題能否高效地獲得優(yōu)化解，研究車間調度問題具有很大的理論意義和現(xiàn)實價值。 車間調度問題是解決如何按時間的先后分配資源來完成不同的生產任務，使預定目標最優(yōu)化的問題。作業(yè)車間調度-(JSP)問題是許多實際車間調度問題的簡化模型，是一個典型的NP一難問題。該問題具有約束性、非線性

2、、不確定性、大規(guī)模性等復雜性，已被證明在多項式時間內得不到最優(yōu)值。近年來，對于Job-shop調度問題求解方式主要有啟發(fā)式算法和元啟發(fā)式算法，但各有其不足之處：元啟發(fā)式方法的運行時間長，可獲得較好的解，但其解不穩(wěn)定；啟發(fā)式方法可在較短的時間內得到魯棒性較強的解，但是極少獲得較優(yōu)的解。 為了更好地解決作業(yè)車間調度問題，將一些解決此類問題較好的算法組合起來。蟻群算法是通過信息素的累積和更新收斂于最優(yōu)路徑上，具有分布式并行全局搜索能力

3、，但初期信息素匾乏，求解速度慢。禁忌搜索法(TabuSearch)是一種通過鄰域搜索以獲取最優(yōu)解的方法，能有效地加快解的收斂速度。本文根據蟻群算法的特點，對蟻群算法進行改進，并將禁忌搜索算法熔入到蟻群算法中，以改善蟻群算法的收斂速度。算法動態(tài)融合的思想是首先應用改進的蟻群算法找到JSP問題的可行解，然后應用禁忌搜索在可行解的鄰域找到更優(yōu)的解。最后，本文對JSP問題應用實驗仿真計算。結果表明，改進的蟻群算法與禁忌搜索結合后的混合蟻群算法的