基于兩種新型元啟發(fā)式算法的作業(yè)車間調(diào)度問題研究.pdf

1、作業(yè)車間調(diào)度問題(Job shop scheduling problem,JSP)是制造領(lǐng)域內(nèi)著名的車間調(diào)度問題，同時(shí)也是最困難的組合優(yōu)化問題之一。它可描述為，車間內(nèi)各工件都具備其特定的加工路徑，且使用機(jī)器的順序及每道工序的加工時(shí)間已知，目的是解決車間內(nèi)各工件在機(jī)器上的加工順序問題，以達(dá)到最優(yōu)的預(yù)期性能。該問題的發(fā)展過程也是學(xué)者們認(rèn)識(shí)問題本質(zhì)、探索新型算法和改進(jìn)已有算法的過程。考慮到問題求解的難度，元啟發(fā)算法的提出為車間調(diào)度問題的求解提

2、供了一種新的思路和手段，目前已得到了國內(nèi)外學(xué)者們廣泛的關(guān)注和興趣。本論文在對(duì)作業(yè)車間調(diào)度問題進(jìn)行分析的基礎(chǔ)上，采用兩種不同的新興元啟發(fā)式算法對(duì)作業(yè)車間調(diào)度問題進(jìn)行研究，主要內(nèi)容概括如下：
　　(1)首先對(duì)JSP問題的基礎(chǔ)知識(shí)進(jìn)行簡單的介紹，如JSP問題的描述、問題的特性、數(shù)學(xué)模型的建立、問題的表示、問題的分類、G&T算法以及編碼設(shè)計(jì)方法等。
　　(2)將候鳥遷徙優(yōu)化算法(Migrating birds optimizatio

3、n,MBO)應(yīng)用到作業(yè)車間調(diào)度問題的求解當(dāng)中。為了充分體現(xiàn)問題的特點(diǎn)，首先設(shè)計(jì)了合理的編碼和解碼機(jī)制，并給出了基于啟發(fā)式算法的種群初始方案，用于保證初始種群中解的質(zhì)量和多樣性。其次，根據(jù)所研究的問題特點(diǎn)，設(shè)計(jì)了三種鄰域結(jié)構(gòu)對(duì)個(gè)體鄰域解進(jìn)行構(gòu)造。此外，將變鄰域搜索算法嵌入到候鳥優(yōu)化算法中，以加強(qiáng)該算法的局部搜索能力。最后，使用五種基準(zhǔn)算例對(duì)所提出的改進(jìn)候鳥遷徙優(yōu)化算法(Improved migrating birds optimizati

4、on,IMBO)進(jìn)行測試，并將計(jì)算結(jié)果與其他文獻(xiàn)中算法結(jié)果進(jìn)行比較，驗(yàn)證該算法的有效性。
　　(3)將貓群算法(Cat swarm optimization,CSO)應(yīng)用到作業(yè)車間調(diào)度問題的求解當(dāng)中?？紤]到問題特點(diǎn)和算法特性，首先設(shè)計(jì)了可行的編碼和解碼機(jī)制，實(shí)現(xiàn)了算法中離散問題的連續(xù)編碼，并給出了基于啟發(fā)式算法的種群初始方案，保證了該算法初始種群中解的質(zhì)量和多樣性。其次，設(shè)計(jì)了兩種不同的搜尋模式和跟蹤模式，并給出了一種自適應(yīng)行為模