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

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

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

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

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

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

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

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

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

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

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