基于改進蟻群算法的一類單機調(diào)度問題研究.pdf

1、單機調(diào)度問題(Single Machine Scheduling，SMS)是一類重要的生產(chǎn)調(diào)度問題，在理論上，單機調(diào)度可看作是其它調(diào)度問題的特殊形式，是復(fù)雜的多機調(diào)度系統(tǒng)的一個子系統(tǒng)，深入研究單機調(diào)度問題可以更好地理解復(fù)雜調(diào)度系統(tǒng)的結(jié)構(gòu)。在生產(chǎn)實踐中，復(fù)雜調(diào)度問題往往可以分解為多個單機問題來解決。單機調(diào)度問題也是一類經(jīng)典的NP難題，對單機調(diào)度問題求解算法的研究可以提供求解復(fù)雜調(diào)度問題的算法基礎(chǔ)，因此，設(shè)計一種簡單高效的求解算法是單機調(diào)度

2、問題研究的重要方面。 蟻群算法(Ant Colony Optimization,ACO)是一種智能啟發(fā)式算法，受自然界中真實螞蟻覓食行為啟發(fā)而來，在信息素的幫助下，蟻群在覓食時總能夠找到最短路徑。蟻群算法的解構(gòu)建程序是在搜索過程中通過不斷向部分解添加符合定義的解成分從而構(gòu)建出一個完整解，從這個意義上說，單機調(diào)度問題多階段決策的屬性非常適合蟻群算法求解。而且，蟻群算法具有系統(tǒng)性、自組織性、分布式計算、正反饋等特點，使得它在理論上比

3、其它算法求解單機調(diào)度問題時有更大的優(yōu)越性。但在實際應(yīng)用中，蟻群算法也出現(xiàn)了運算時間較長、容易陷入局部極小、參數(shù)選取過程比較復(fù)雜、算法的智能化程度(自適應(yīng)能力)較低等缺點。因此我們提出了進一步改善蟻群算法性能的策略與技術(shù)，發(fā)展了求解單機調(diào)度問題的改進蟻群算法。 本文以一類單機調(diào)度問題為研究對象，以設(shè)計求解該類問題的有效算法為研究重點，提出了求解單機加權(quán)延遲調(diào)度問題的幾種改進蟻群算法。具體的說，本文的主要內(nèi)容及創(chuàng)新點包括：

4、1、首先指出了論文所要研究的單機調(diào)度問題的概念及其研究背景，并從理論研究和生產(chǎn)實踐兩方面分別闡述了研究單機調(diào)度問題的意義；接著給出了單機調(diào)度問題的理論模型和結(jié)構(gòu)圖，建立了一個具有一般意義的基于模塊設(shè)計的蟻群算法流程框架；然后提出了本文所要研究的單機調(diào)度問題的特征，從理論上分析了蟻群算法求解單機調(diào)度問題的可行性和具有的優(yōu)勢：最后對包括單機調(diào)度問題、單機加權(quán)延遲調(diào)度問題和蟻群算法等相關(guān)問題的研究現(xiàn)狀進行了簡要的分析總結(jié)，提出了存在的問題，指

5、出本文的研究重點是設(shè)計適合求解SMTWT問題的蟻群算法。 2、從蟻群算法功能模塊的角度在方法層面和理論層面總結(jié)了蟻群算法的設(shè)計思路，分析了蟻群算法的不足，由此提出了分支蟻群動態(tài)擾動算法(DPBAC算法)，從以下五個方面對基本蟻群算法進行了改進：引入分支策略選取初始出發(fā)城市；對狀態(tài)轉(zhuǎn)移規(guī)則進行了改進；引入交叉變異策略改進螞蟻周游路徑；改進信息素更新規(guī)則，引入信息素交流策略中和螞蟻信息素的差距；引入條件動態(tài)擾動策略進行分階段局部搜索

6、，等等，并且對DPBAC算法的收斂性進行了證明。實驗表明，該算法可以有效改善基本蟻群算法搜索時間較長、容易陷入局部極小等缺點，并且與其它類型的蟻群算法相比也有一定的優(yōu)勢。 3、研究了求解一類強NP難的單機調(diào)度問題--單機加權(quán)延遲調(diào)度問題(SMTWT)的蟻群算法。首先從一般意義上給出了SMTWT問題的變量定義和數(shù)學(xué)模型，并從附加約束、啟發(fā)式規(guī)則和求解算法等方面對近年來關(guān)于SMTWT問題的研究文獻進行了綜述，然后基于DPBAC算法的

7、設(shè)計思想提出了一種求解SMTWT問題的改進蟻群算法AC_SMTWT，并針對SMTWT問題的特征做了相應(yīng)的改進，包括選用EDD(Earliest Due Date)規(guī)則產(chǎn)生問題的初始解，采用信息素累加規(guī)則計算狀態(tài)轉(zhuǎn)移概率，構(gòu)建兩兩交換(interchange)鄰域和插入(insertion)鄰域進行局部搜索，運用信息素中和策略消減各節(jié)點間信息素之間的差距，等等，并且結(jié)合算法的搜索機理從理論上推導(dǎo)了算法的參數(shù)值。通過大量標準數(shù)據(jù)實驗表明，A

8、C_SMTWT算法在計算結(jié)果和計算時間方面均優(yōu)于遺傳算法，而且與其它蟻群算法相比也有一定的優(yōu)勢。 4、針對AC_SMTWT算法在求解SMTWT問題的過程中參數(shù)選取過于復(fù)雜這一問題，提出了基于Q學(xué)習(xí)蟻群算法的SMTWT問題求解模型。首先，建立了單機加權(quán)延遲調(diào)度的多階段決策問題模型，推導(dǎo)了SMTWT問題的Markov性。其次，分析了蟻群算法的Markov性，在Q學(xué)習(xí)理論框架下對蟻群算法的流程進行了解釋。再次，對Q學(xué)習(xí)在單機調(diào)度研究中

9、的應(yīng)用進行了綜述，分析了用查找表方法計算Q函數(shù)的不足，在此基礎(chǔ)上建立了一個BP網(wǎng)絡(luò)模型對Q函數(shù)進行估計。最后，將Q函數(shù)的環(huán)境無關(guān)性、Agent的學(xué)習(xí)能力和蟻群算法的分布式計算、正反饋等優(yōu)點相結(jié)合，建立了基于AC_Q算法的SMTWT問題求解模型。實驗表明，AC_Q算法在計算性能上與AC_SMTWT算法基本相當，但對問題參數(shù)的依賴度更小，智能度也更高。 總之，單機調(diào)度問題研究不僅在理論上還是在實踐中都有重要的意義，由于單機調(diào)度問題是

10、NP難問題，因此對它的求解算法的研究非常重要。在本文中，首先提出了一種適用于一般組合優(yōu)化問題的改進蟻群算法-DPBAC算法，在此基礎(chǔ)上設(shè)計了一種求解SMTWT問題的改進蟻群算法AC_SMTWT，而為了解決AC_SMTWT算法參數(shù)選取復(fù)雜、螞蟻智能化程度較低等問題，又提出了基于Q學(xué)習(xí)的改進蟻群算法AC_Q，并建立了基于AC_Q算法的SMTWT問題求解模型。可見，本文的研究內(nèi)容是相互聯(lián)系自成體系的，本文的研究成果為單機調(diào)度問題的研究提供了一