基于蟻群優(yōu)化算法的批調(diào)度問題研究.pdf

1、批調(diào)度問題是一類重要的現(xiàn)代生產(chǎn)調(diào)度問題。在理論上，批調(diào)度問題突破和擴(kuò)展了經(jīng)典調(diào)度理論，它打破了經(jīng)典調(diào)度中對(duì)機(jī)器加工工件數(shù)目的約束，是一種新型的生產(chǎn)調(diào)度研究方向。在生產(chǎn)實(shí)踐中，批調(diào)度問題是從半導(dǎo)體生產(chǎn)過程的最后階段提煉出來的新型調(diào)度問題，具有極強(qiáng)的應(yīng)用背景。同時(shí)批調(diào)度問題也是一類經(jīng)典的NP-難問題。因此，設(shè)計(jì)一種簡(jiǎn)單高效的求解算法是批調(diào)度問題研究的重要方面。
　　 蟻群優(yōu)化算法是近年來提出的一種有效的求解組合優(yōu)化問題的元啟發(fā)式算法

2、。它是一種基于構(gòu)建性的元啟發(fā)式算法，在搜索過程中通過不斷向部分解添加符號(hào)定義的解成分從而構(gòu)建出一個(gè)完整解。從這個(gè)意義上說，批調(diào)度問題的分批特性非常適合蟻群優(yōu)化算法求解。除此之外，蟻群優(yōu)化算法還是基于種群的和具有記憶存儲(chǔ)的元啟發(fā)式算法，這些特征的組合使得蟻群優(yōu)化算法在理論上求解批調(diào)度問題具有獨(dú)特的優(yōu)勢(shì)。但在實(shí)際應(yīng)用上，蟻群優(yōu)化算法也出現(xiàn)了運(yùn)算時(shí)間較長(zhǎng)、易陷入局部最優(yōu)等缺點(diǎn)。因此本文基于對(duì)批調(diào)度問題的結(jié)構(gòu)分析，提出了進(jìn)一步改善算法性能的策略

3、與技術(shù)，從而提高了蟻群優(yōu)化算法求解批調(diào)度問題的質(zhì)量和效率。
　　 本文以批調(diào)度問題為研究對(duì)象，以設(shè)計(jì)求解該類問題的有效算法為研究重點(diǎn)，提出了求解不同類型的批調(diào)度問題的蟻群算法。具體的說，本文的主要研究?jī)?nèi)容及創(chuàng)新點(diǎn)包括：
　　 1.研究了螞蟻系統(tǒng)（ant system，AS）算法在差異工件單機(jī)批調(diào)度問題中的應(yīng)用。首先建立了差異工件單機(jī)批調(diào)度問題的數(shù)學(xué)模型，并給出了已有的啟發(fā)式算法和問題下界。針對(duì)不同的編碼方式，提出了基于工

4、件序列和基于批序列的兩種螞蟻系統(tǒng)算法。考慮目標(biāo)為總完工時(shí)間的特點(diǎn)，引入批權(quán)重的概念構(gòu)建螞蟻系統(tǒng)算法的啟發(fā)式信息；同時(shí)通過設(shè)置不同的信息素初始值，采用局部?jī)?yōu)化技術(shù)等改進(jìn)措施，克服傳統(tǒng)螞蟻系統(tǒng)算法收斂速度慢，易陷入局部最優(yōu)的缺點(diǎn)。通過全面的對(duì)比實(shí)驗(yàn)，結(jié)果表明了算法的有效性，尤其是基于批序列的蟻群算法效果更優(yōu)。2.研究了最大最小螞蟻系統(tǒng)（max-min ant system，MMAS）算法在工件含不同到達(dá)時(shí)間的單機(jī)批調(diào)度問題中的應(yīng)用。首先建立

5、了問題的混合整數(shù)數(shù)學(xué)模型。針對(duì)工件到達(dá)時(shí)間不同的特點(diǎn)，在算法構(gòu)建可行解的階段，依據(jù)是否延遲當(dāng)前批的加工提出了兩種候選列表，并給出了延遲當(dāng)前批加工的約束條件。同時(shí)考慮不同候選列表中的工件對(duì)解的構(gòu)造具有不同的影響，分別針對(duì)各自候選列表設(shè)計(jì)了相應(yīng)的啟發(fā)式信息。通過與標(biāo)準(zhǔn)螞蟻系統(tǒng)算法以及帶不同候選列表的最大最小螞蟻系統(tǒng)算法的對(duì)比實(shí)驗(yàn)，驗(yàn)證了提出的帶候選列表的算法的有效性。
　　 3.研究了蟻群系統(tǒng)（ant colony system，A

6、CS）算法在含不同到達(dá)時(shí)間差異工件單機(jī)批調(diào)度問題中的應(yīng)用。首先建立了該問題的混合整數(shù)數(shù)學(xué)模型，并使用運(yùn)籌學(xué)軟件CPLEX對(duì)該模型進(jìn)行求解。通過分析工件到達(dá)時(shí)間和工件尺寸對(duì)優(yōu)化目標(biāo)的影響，提出了空閑空間的概念，并證明極小化批序列空閑空間等價(jià)于極小化批序列最大完工時(shí)間?；诖嗽O(shè)計(jì)了ACS 算法的動(dòng)態(tài)啟發(fā)式信息以更精確的指導(dǎo)螞蟻行為。同時(shí)引入候選列表策略，有效地優(yōu)化螞蟻的尋優(yōu)空間，提高算法收斂速度。通過與CPLEX軟件、遺傳算法的對(duì)比分析，實(shí)

7、驗(yàn)結(jié)果表明了算法的有效性，本文提出的算法可在合理的時(shí)間范圍內(nèi)取得滿意解。
　　 4.研究了多目標(biāo)蟻群優(yōu)化(multiple objective ant colony optimization,MOACO)算法在平行機(jī)批調(diào)度問題中的應(yīng)用。首先建立了多目標(biāo)平行機(jī)批調(diào)度問題的數(shù)學(xué)模型；針對(duì)極小化最大完工時(shí)間和極小化最大延誤時(shí)間兩個(gè)優(yōu)化目標(biāo)，分別提出了空閑空間和延誤空間的概念，并基于此設(shè)計(jì)了MOACO 算法的啟發(fā)式信息和候選列表。在解的

8、構(gòu)建階段，利用MOACO 算法構(gòu)建性的特點(diǎn)，設(shè)計(jì)了一種新的構(gòu)建可行解的機(jī)制，該機(jī)制使得分批、分機(jī)器以及批排序等三個(gè)步驟簡(jiǎn)化到一個(gè)步驟，提高了算法的優(yōu)化效率。通過對(duì)Pareto 解的質(zhì)量、多樣性以及算法時(shí)間性能等多方面的實(shí)驗(yàn)評(píng)估，驗(yàn)證了算法的有效性。
　　 總之，批調(diào)度問題研究不僅在理論上還是在實(shí)踐中都有重要的意義。由于本文研究的批調(diào)度問題均是NP-難問題，因此對(duì)它的求解算法的研究非常重要。在本文中，首先研究了差異工件、工件含不同

9、到達(dá)時(shí)間等約束條件下的單機(jī)批調(diào)度問題，之后將單機(jī)單目標(biāo)批調(diào)度問題擴(kuò)展到更復(fù)雜也更接近實(shí)際生產(chǎn)環(huán)境的平行機(jī)多目標(biāo)批調(diào)度問題。對(duì)于不同類型的批調(diào)度問題，首先建立批調(diào)度問題的數(shù)學(xué)模型，提出批調(diào)度問題的有效下界，并設(shè)計(jì)高效合理的蟻群優(yōu)化算法進(jìn)行求解。針對(duì)傳統(tǒng)蟻群優(yōu)化算法搜索時(shí)間較長(zhǎng)，易陷入局部最優(yōu)等缺點(diǎn)，本文在深入分析批調(diào)度問題結(jié)構(gòu)的基礎(chǔ)上，通過設(shè)計(jì)合理的信息素和啟發(fā)式信息，構(gòu)建基于約束條件和優(yōu)化目標(biāo)的候選列表，改進(jìn)信息素的更新方式，加入局部搜