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

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

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

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

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