遺傳蟻群混合算法及其在車間調(diào)度問題中的應(yīng)用.pdf

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

2、具有約束性、非線性、不確定性、大規(guī)模性等復雜性，已被證明在多項式時間內(nèi)得不到最優(yōu)值。近年來，對于Job-Shop調(diào)度問題求解方式主要有啟發(fā)式算法和元啟發(fā)式算法，但各有其不足之處：元啟發(fā)式方法的運行時間長，可獲得較好的解，但其解不穩(wěn)定；啟發(fā)式方法可在較短的時間內(nèi)得到魯棒性較強的解，但是極少獲得較優(yōu)的解。 為了更好地解決作業(yè)車間調(diào)度問題，將一些解決某類問題較好的算法組合起來。遺傳算法具有快速隨機的全局搜索能力，但對于系統(tǒng)中的反饋信息

3、利用卻無能為力，當求解到一定范圍時往往做大量無為的冗余迭代，使得求精確解效率降低。蟻群算法是通過信息素的累積和更新收斂于最優(yōu)路徑上，具有分布式并行全局搜索能力，但初期信息素匱乏，求解速度慢。本文根據(jù)遺傳算法和蟻群算法的特點，嘗試將兩個算法動態(tài)融合來求解Job-Shop調(diào)度問題。算法動態(tài)融合的思想是：在最佳點(遺傳算法和蟻群算法融合時刻)之前利用遺傳算法的特性，快速、全面地生成優(yōu)秀染色體；從其中選出一部分比較優(yōu)秀的染色體并將其轉(zhuǎn)換為初始蟻