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

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

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

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

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

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

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

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

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

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