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

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

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

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