基于遺傳算法的車間生產(chǎn)調(diào)度問題研究.pdf

1、隨著客戶需求日趨多樣化，產(chǎn)品的生產(chǎn)技術在不斷更新，各行業(yè)間的競爭逐漸加劇，每一個企業(yè)都面臨著生存危機，為了占領市場，他們必須以低成本、快速度開發(fā)出高質(zhì)量的新產(chǎn)品。因此企業(yè)都迫切需要尋求一種新的生產(chǎn)方式來縮短產(chǎn)品開發(fā)周期，降低生產(chǎn)成本，最終實現(xiàn)效益最大化。作為企業(yè)生產(chǎn)管理中一個必不可少的環(huán)節(jié)，車間生產(chǎn)調(diào)度管理是生產(chǎn)管理任務順利實施和完成的重要保障。目前對于車間生產(chǎn)調(diào)度問題的研究主要集中在如何合理的配置加工過程的各種資源，減少工件加工準備、

2、等待時間。因此對這一問題的研究具有廣闊的應用前景。
　　作業(yè)車間調(diào)度問題是車間生產(chǎn)調(diào)度中的一個典型問題，它是在滿足一定約束條件下，研究對各道工序加工順序的排列以使相應的性能指標達到最優(yōu)。根據(jù)約束條件的不同，作業(yè)車間調(diào)度問題可分為經(jīng)典作業(yè)車間調(diào)度問題和柔性作業(yè)車間調(diào)度問題兩類。研究表明，隨著問題規(guī)模的擴大，求解作業(yè)車間調(diào)度問題的復雜度會呈指數(shù)增長。由于遺傳算法具有隱含并行性和全局優(yōu)化的特點，它已經(jīng)成為目前求解作業(yè)車間調(diào)度問題的有效方

3、法之一。但該算法所存在的早熟收斂和局部搜索能力較差的缺點卻制約了它在這一領域的深入研究。為了提高遺傳算法求解作業(yè)車間調(diào)度問題的效率，本文結合逆序數(shù)、信息熵和協(xié)同進化等理論，提出了一系列遺傳調(diào)度算法，主要取得了如下的研究成果:
　　(1)基于隨機性指導策略的作業(yè)車間遺傳調(diào)度算法由于遺傳算法在操作中具有隨機性操作，這些操作使算法的執(zhí)行結果具有不確定性，為了提高算法求解結果的穩(wěn)定性，有效指導算法的進化方向，針對經(jīng)典作業(yè)車間調(diào)度問題，提出

4、了一類基于隨機性指導策略的遺傳調(diào)度算法。這類算法包括基于信息熵的遺傳調(diào)度算法和基于逆序數(shù)的遺傳調(diào)度算法。其中，基于信息熵的遺傳調(diào)度算法是借助生態(tài)學的多樣性指數(shù)和決策樹算法的屬性選擇準則所提出的。該算法利用信息熵值的差異確定參與復制的個體，在交叉和變異算子的設計中引入信息熵衡量工序、機器的重要度，并利用交叉父代表示的調(diào)度方案所隱含的信息獲取優(yōu)良基因排列。其次，通過分析求解作業(yè)車間調(diào)度問題和旅行商問題所采用的遺傳算子，提出了基于逆序數(shù)的遺傳

5、調(diào)度算法。該算法在遺傳過程中利用相對逆序數(shù)檢驗群體的一致性，并根據(jù)排列奇偶性的改變進行交叉（或變異）操作，從而產(chǎn)生后代群體。實驗結果驗證了所提出的遺傳調(diào)度算法的有效性。
　　(2)基于協(xié)同進化的作業(yè)車間遺傳調(diào)度算法為了增強遺傳算法的并行處理能力，針對經(jīng)典作業(yè)車間調(diào)度問題，提出了一類基于協(xié)同進化的遺傳調(diào)度算法。該算法包括基于群體間協(xié)同進化的遺傳調(diào)度算法和基于個體間協(xié)同進化的遺傳調(diào)度算法。其中，基于群體間協(xié)同進化的遺傳調(diào)度算法借鑒標準

6、協(xié)同進化遺傳算法的性質(zhì)，在操作中結合子種群共同進化的原則，并利用基于排名的選擇方法，從多種遺傳算子中選擇出相應的交叉（或變異）方法而產(chǎn)生遺傳后代。基于個體間協(xié)同進化的遺傳調(diào)度算法則是利用多個個體參與遺傳算子的操作，借助個體間調(diào)度解和染色體結構的區(qū)別指導交叉（或變異）父代的產(chǎn)生。這類算法從群體和個體間的進化過程、遺傳操作中的選擇策略（父代的選擇、算子的選擇）等方面真正體現(xiàn)出了算法并行處理的特征。實驗結果表明，基于協(xié)同進化的遺傳算法能夠有效

7、求解經(jīng)典作業(yè)車間調(diào)度問題。
　　(3)改進的柔性作業(yè)車間遺傳調(diào)度算法通過對目前柔性作業(yè)車間調(diào)度算法的分析，針對具有不同目標的柔性作業(yè)車間調(diào)度問題，提出了兩種改進的遺傳調(diào)度算法。首先，針對單目標柔性作業(yè)車間調(diào)度問題，提出了一種分部遺傳調(diào)度算法。該算法將分部編碼方法和分部遺傳算子操作有效地加以結合，由此能夠直接產(chǎn)生可行的調(diào)度方案;其次，針對多目標柔性作業(yè)車間調(diào)度問題提出了一種改進的遺傳算法。該算法首先利用矩陣編碼方法縮小了求解空間，并

8、從符合各項約束條件出發(fā)，對解碼步驟進行詳細闡述，從而保證算法能夠產(chǎn)生可行的調(diào)度方案。然后借助根據(jù)選擇機制和木桶原理設計的遺傳調(diào)度算子的操作產(chǎn)生可行的遺傳后代。實驗結果驗證了所提出算法求解柔性作業(yè)車間調(diào)度問題的有效性和可行性。
　　(4)基于基尼指數(shù)的遺傳調(diào)度算法通過對不同類型作業(yè)車間調(diào)度問題的分析，提取各問題間的共性部分，并借鑒進化生態(tài)學原理和決策樹算法的屬性分裂準則，提出了一種基于基尼指數(shù)的遺傳調(diào)度算法。該算法針對經(jīng)典作業(yè)車間調(diào)

9、度問題和柔性作業(yè)車間調(diào)度問題，挖掘出各問題間的共性特征，對其相同的特性采用基于基尼指數(shù)的遺傳算子操作，同時采用基尼指數(shù)作為個體多樣性和優(yōu)劣性的衡量指標，通過和目前其它調(diào)度算法的實驗結果的比較，證實了所提出的算法對于具有共性特征的作業(yè)車間調(diào)度問題的求解是非常有效的。
　　總之，本文針對經(jīng)典作業(yè)車間調(diào)度問題、柔性作業(yè)車間調(diào)度問題及具有共性特征的車間調(diào)度問題提出了一系列遺傳調(diào)度算法，這些算法的提出不僅適用于求解制造業(yè)的各類車間調(diào)度問題，