蟻群優(yōu)化算法在平行機批調(diào)度問題中的應(yīng)用與研究.pdf

1、生產(chǎn)調(diào)度問題是一類組合優(yōu)化問題，應(yīng)用背景十分廣泛，其研究成果已經(jīng)較為豐富，并且已被應(yīng)用到許多現(xiàn)實的生產(chǎn)實踐中。與經(jīng)典調(diào)度問題不同的是，在批處理機調(diào)度問題中，多個工件可以同時在一臺機器上加工，只有滿足容量約束的工件才能在該機器上加工。所以批調(diào)度問題更加接近實際，對批處理機調(diào)度問題的深入探索和研究具有十分重要的意義。
　　首先，本文簡單介紹了生產(chǎn)調(diào)度問題的產(chǎn)生背景、與調(diào)度問題有關(guān)的概念并簡單介紹了調(diào)度問題的分類;然后簡單介紹了批處理機

2、調(diào)度問題、差異工件尺寸的批處理機調(diào)度問題及動態(tài)環(huán)境下差異工件尺寸的批處理機調(diào)度問題以及這幾類問題的研究現(xiàn)狀。
　　第二，本文簡單介紹了當(dāng)前用于求解批處理機調(diào)度問題的兩種主流方法，即確定性方法和近似性方法，然后對這兩種主流方法的特點做了簡要的分析并且簡單介紹了這兩種主流方法的代表性算法及其大致框架。
　　第三，在容量差異的平行批處理機環(huán)境下，針對工件帶有差異尺寸以及機器適用限制的最小化制造跨度的批調(diào)度問題，提出一種有效的蟻群優(yōu)

3、化(ACO1)算法。首先給出了問題假設(shè)并且分析了問題的復(fù)雜性。為了衡量算法的性能，給出問題的一個有效下界。然后提出基于MultiFit規(guī)則的啟發(fā)式算法以及基于ACO1的元啟發(fā)式算法分別對問題進行求解。在基于ACO1的算法中，根據(jù)解的浪費空間與問題目標的相關(guān)性分析，基于浪費空間定義啟發(fā)式信息來指導(dǎo)螞蟻的行為。同時，采用候選集策略來構(gòu)建解，以減小搜索空間。此外引入一種局部優(yōu)化方法對螞蟻所構(gòu)建的解進行優(yōu)化，以進一步提高解的質(zhì)量。最后，通過仿真

4、實驗比較所提算法與其他已有算法的性能，實驗結(jié)果表明所提的ACO1算法優(yōu)于其他算法。
　　第四，在容量不同的平行批處理機環(huán)境下，針對工件動態(tài)到達且差異工件尺寸以及機器適用限制的最小化制造跨度的批處理機調(diào)度問題，提出一種有效的蟻群優(yōu)化(ACO2)算法。除了在靜態(tài)批調(diào)度問題中使用的策略之外，在構(gòu)建的過程中采用ERT規(guī)則對機器集合中每臺機器上已有的批序列排序，從而減少工件到達時間對解的影響。此外引入一種局部優(yōu)化策略對螞蟻所構(gòu)建的解進行優(yōu)化