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

1、隨著市場競爭的日趨激烈，每個(gè)企業(yè)都在尋求更好的生產(chǎn)與運(yùn)作管理方案，以提高企業(yè)的生產(chǎn)、經(jīng)營和管理效率，從而提高企業(yè)的核心競爭優(yōu)勢。生產(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)度-(JSP)問題是許多實(shí)際車間調(diào)度問題的簡化模型，是一個(gè)典型的NP一難問題。該問題具有約束性、非線性

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)度問題，將一些解決此類問題較好的算法組合起來。蟻群算法是通過信息素的累積和更新收斂于最優(yōu)路徑上，具有分布式并行全局搜索能力

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