【摘要】：批調度問題是一類重要的現(xiàn)代生產(chǎn)調度問題。在理論上,批調度問題突破和擴展了經(jīng)典調度理論,它打破了經(jīng)典調度中對機器加工工件數(shù)目的約束,是一種新型的生產(chǎn)調度研究方向。在生產(chǎn)實踐中,批調度問題是從半導體生產(chǎn)過程的最后階段提煉出來的新型調度問題,具有極強的應用背景。同時批調度問題也是一類經(jīng)典的NP-難問題。因此,設計一種簡單高效的求解算法是批調度問題研究的重要方面。 蟻群優(yōu)化算法是近年來提出的一種有效的求解組合優(yōu)化問題的元啟發(fā)式算法。它是一種基于構建性的元啟發(fā)式算法,在搜索過程中通過不斷向部分解添加符號定義的解成分從而構建出一個完整解。從這個意義上說,批調度問題的分批特性非常適合蟻群優(yōu)化算法求解。除此之外,蟻群優(yōu)化算法還是基于種群的和具有記憶存儲的元啟發(fā)式算法,這些特征的組合使得蟻群優(yōu)化算法在理論上求解批調度問題具有獨特的優(yōu)勢。但在實際應用上,蟻群優(yōu)化算法也出現(xiàn)了運算時間較長、易陷入局部最優(yōu)等缺點。因此本文基于對批調度問題的結構分析,提出了進一步改善算法性能的策略與技術,從而提高了蟻群優(yōu)化算法求解批調度問題的質量和效率 本文以批調度問題為研究對象,以設計求解該類問題的有效算法為研究重點,提出了求解不同類型的批調度問題的蟻群算法。具體的說,本文的主要研究內(nèi)容及創(chuàng)新點包括： 1.研究了螞蟻系統(tǒng)(ant system, AS)算法在差異工件單機批調度問題中的應用。首先建立了差異工件單機批調度問題的數(shù)學模型,并給出了已有的啟發(fā)式算法和問題下界。針對不同的編碼方式,提出了基于工件序列和基于批序列的兩種螞蟻系統(tǒng)算法。考慮目標為總完工時間的特點,引入批權重的概念構建螞蟻系統(tǒng)算法的啟發(fā)式信息；同時通過設置不同的信息、素初始值,采用局部優(yōu)化技術等改進措施,克服傳統(tǒng)螞蟻系統(tǒng)算法收斂速度慢,易陷入局部最優(yōu)的缺點。通過全面的對比實驗,結果表明了算法的有效性,尤其是基于批序列的蟻群算法效果更優(yōu)。 2.研究了最大最小螞蟻系統(tǒng)(max-min ant system, MMAS)算法在工件含不同到達時間的單機批調度問題中的應用。首先建立了問題的混合整數(shù)數(shù)學模型。針對工件到達時間不同的特點,在算法構建可行解的階段,依據(jù)是否延遲當前批的加工提出了兩種候選列表,并給出了延遲當前批加工的約束條件。同時考慮不同候選列表中的工件對解的構造具有不同的影響,分別針對各自候選列表設計了相應的啟發(fā)式信息、。通過與標準螞蟻系統(tǒng)算法以及帶不同候選列表的最大最小螞蟻系統(tǒng)算法的對比實驗,驗證了提出的帶候選列表的算法的有效性。 3.研究了蟻群系統(tǒng)(ant colony system, ACS)算法在含不同到達時間差異工件單機批調度問題中的應用。首先建立了該問題的混合整數(shù)數(shù)學模型,并使用運籌學軟件CPLEX對該模型進行求解。通過分析工件到達時間和工件尺寸對優(yōu)化目標的影響,提出了空閑空間的概念,并證明極小化批序列空閑空間等價于極小化批序列最大完工時間�；诖嗽O計了ACS算法的動態(tài)啟發(fā)式信息以更精確的指導螞蟻行為。同時引入候選列表策略,有效地優(yōu)化螞蟻的尋優(yōu)空間,提高算法收斂速度。通過與CPLEX軟件、遺傳算法的對比分析,實驗結果表明了算法的有效性,本文提出的算法可在合理的時間范圍內(nèi)取得滿意解。 4.研究了多目標蟻群優(yōu)化(multiple objective ant colony optimization, MOACO)算法在平行機批調度問題中的應用。首先建立了多目標平行機批調度問題的數(shù)學模型；針對極小化最大完工時間和極小化最大延誤時間兩個優(yōu)化目標,分別提出了空閑空間和延誤空間的概念,并基于此設計了MOACO算法的啟發(fā)式信息和候選列表。在解的構建階段,利用MOACO算法構建性的特點,設計了一種新的構建可行解的機制,該機制使得分批、分機器以及批排序等三個步驟簡化到一個步驟,提高了算法的優(yōu)化效率。通過對Pareto解的質量、多樣性以及算法時間性能等多方面的實驗評估,驗證了算法的有效性。 總之,批調度問題研究不僅在理論上還是在實踐中都有重要的意義。由于本文研究的批調度問題均是NP-難問題,因此對它的求解算法的研究非常重要。在本文中,首先研究了差異工件、工件含不同到達時間等約束條件下的單機批調度問題,之后將單機單目標批調度問題擴展到更復雜也更接近實際生產(chǎn)環(huán)境的平行機多目標批調度問題。對于不同類型的批調度問題,首先建立批調度問題的數(shù)學模型,提出批調度問題的有效下界,并設計高效合理的蟻群優(yōu)化算法進行求解。針對傳統(tǒng)蟻群優(yōu)化算法搜索時間較長,易陷入局部最優(yōu)等缺點,本文在深入分析批調度問題結構的基礎上,通過設計合理的信息素和啟發(fā)式信息,構建基于約束條件和優(yōu)化目標的候選列表,改進信息素的更新方式,加入局部搜索等優(yōu)化策略,提高了蟻群優(yōu)化算法的求解質量和效率�？梢�,本文的研究內(nèi)容是相互聯(lián)系逐步遞進的,本文的研究成果為批調度問題的研究提供了一些新的理論和方法,同時也拓展了蟻群優(yōu)化算法的理論研究和應用研究的領域。
【學位授予單位】：中國科學技術大學
【學位級別】：博士
【學位授予年份】：2011
【分類號】：F273;F224

【引證文獻】

相關期刊論文 前1條

1 �？×�;王慶;孟彥軍;蔣曉劍;;并行多機批調度的混合粒子群算法研究[J];化工自動化及儀表;2014年04期

相關碩士學位論文 前2條

1 李丹;蟻群優(yōu)化算法在差異工件批調度問題的應用研究[D];安徽大學;2014年

2 孫笑蕓;考慮加工成本的雙目標平行機批調度問題的啟發(fā)式算法研究[D];安徽大學;2014年

，

本文編號：2640577