差異工件單機(jī)批調(diào)度的自適應(yīng)蟻群退火算法研究.pdf

1、組合優(yōu)化問題中有一類實(shí)際生活中常見的子問題即調(diào)度問題，對(duì)于調(diào)度問題而言，高質(zhì)量的調(diào)度方案能有效地降低生產(chǎn)成本、提高資源利用率以及生產(chǎn)力。
　　 批調(diào)度問題是調(diào)度問題的一個(gè)分支，它打破了經(jīng)典調(diào)度問題的假設(shè)，在批調(diào)度問題模型中，一臺(tái)機(jī)器可以同時(shí)處理多個(gè)工件。不同尺寸工件批調(diào)度問題對(duì)批調(diào)度問題進(jìn)行了擴(kuò)展，即工件尺寸有差異，且任一批中的所有工件尺寸之和不能超過機(jī)器的容量限制。例如，港口貨物卸載、陶瓷燒制、汽車貨運(yùn)等諸多問題域都屬于不同尺

2、寸工件批調(diào)度問題的研究范圍。因此，從現(xiàn)實(shí)的角度來看，研究不同尺寸工件批調(diào)度問題更能有效的指導(dǎo)現(xiàn)實(shí)生產(chǎn)。
　　 首先,本文介紹了組合優(yōu)化問題以及計(jì)算復(fù)雜性理論中的相關(guān)概念；描述了生成調(diào)度問題的三參數(shù)表示法以及生成調(diào)度問題的分類，區(qū)分了古典調(diào)度問題、批調(diào)度問題、不同尺寸工件的批調(diào)度問題。
　　 其次，本文對(duì)差異工件批調(diào)度問題的研究現(xiàn)狀進(jìn)行了簡要的回顧，闡述了現(xiàn)有的求解該類問題的三種主要方法：數(shù)學(xué)規(guī)劃法、啟發(fā)式規(guī)則、人工智能算

3、法，并簡要介紹各類方法的原理以及基本步驟。
　　 接著，本文將蟻群算法與模擬退火算法相結(jié)合，引入自適應(yīng)狀態(tài)轉(zhuǎn)移概率，提出了一種自適應(yīng)蟻群退火算法AACSA(Adaptive Ant Colony SimulatedAnnealing)。算法利用模擬退火算法實(shí)現(xiàn)了一種新的混合信息素更新策略，此外根據(jù)停滯次數(shù)，動(dòng)態(tài)改變狀態(tài)轉(zhuǎn)移概率，有效的避免算法陷入停滯以及局部最優(yōu)，提高算法的性能。通過仿真實(shí)驗(yàn)，與啟發(fā)式規(guī)則BFLPT、模擬退火算法