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

【引證文獻(xiàn)】

相關(guān)期刊論文 前1條

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

相關(guān)碩士學(xué)位論文 前2條

1 李丹;蟻群優(yōu)化算法在差異工件批調(diào)度問(wèn)題的應(yīng)用研究[D];安徽大學(xué);2014年

2 孫笑蕓;考慮加工成本的雙目標(biāo)平行機(jī)批調(diào)度問(wèn)題的啟發(fā)式算法研究[D];安徽大學(xué);2014年

，

本文編號(hào)：2640577