基于文化基因算法的車間作業(yè)調度理論研究及實踐.pdf

1、隨著市場競爭的日趨激烈，每個企業(yè)都在尋求最佳的生產與運作管理方案，以提高企業(yè)的生產、經(jīng)營和管理效率，從而提高企業(yè)的核心競爭優(yōu)勢。調度是影響制造業(yè)生產效率的關鍵因素。合理調度可以縮短制造期、減少庫存、按時交貨。生產調度問題種類繁多，方法多樣，其中車間作業(yè)調度問題（Job Shop Scheduling Problem，JSSP）是著名的機器調度問題，同時也是困難的NP-hard組合優(yōu)化問題之一。人們?yōu)榻鉀Q這一難題已經(jīng)付出幾十年的努力，但至

2、今在求解質量和計算效率上都還不能令人滿意。
　　在對車間作業(yè)調度問題的研究過程中，產生了大量確定性算法和啟發(fā)式算法。尤其是近二十多年來，通過模擬自然界中生物進化、物理變化和人類行為過程而開發(fā)的元啟發(fā)式算法，如遺傳算法、模擬退火算法、粒子群優(yōu)化算法、蟻群優(yōu)化算法等，為解決調度問題提供了新的手段，引起了國內外學者廣泛的興趣。但按照Wolpert等提出的“優(yōu)化問題沒有免費的午餐”理論，任何算法不能保證在所有問題或一類問題的所有實例上都產

3、生比其它算法好的結果。這樣，在算法研究中就不能追求優(yōu)于其它算法的最好算法，而是應該將需要解決問題的自身特征一并納入研究范圍，根據(jù)不同問題設計不同的算法。文化基因算法就是這樣的一種算法框架，在算法環(huán)節(jié)中既包含種群中個體間的信息交換，也包含基于問題特征的局部搜索，為不同類型的調度問題研究提供了一條新的思路。
　　本文在對用文化基因算法解決車間作業(yè)調度問題的各個環(huán)節(jié)進行深入分析研究的基礎之上，提出了適用于最小化制造期、最小化總加權拖期時

4、間和同時優(yōu)化多個目標的車間作業(yè)調度問題的文化基因算法。主要研究工作如下：
　?、儆梦幕蛩惴ń鉀Q車間作業(yè)調度問題首先要設計算法的各個環(huán)節(jié)。本文分析了基于工序的編碼和二進制編碼兩種典型的調度問題表示方法。定義了調度問題解空間的歐氏距離，并以此為工具對文化基因算法解決調度問題過程中包含的解碼方法、進化操作、進化模式等關鍵環(huán)節(jié)進行深入研究。
　?、谔岢隽艘环N新的種群進化模式。這種進化模式中的交叉過程和變異過程對相應的操作方法執(zhí)行

5、多次，然后選擇產生個體中的最優(yōu)者進入下一代，以保證父代個體的優(yōu)良特征得到較好地繼承。將交叉過程和變異過程并列，并在交叉過程中嵌入隨機變異，父代個體必須經(jīng)過交叉或者變異才能進入下一代種群，避免直接拷貝父代個體導致算法收斂到局部最優(yōu)。與簡單遺傳算法的對比分析表明，該進化模式能夠讓子代個體較好地繼承父代特征，且保持較廣的搜索范圍。
　　③針對最小化制造期車間作業(yè)調度問題，在對常見的基于關鍵路徑和關鍵工序塊的調度問題鄰域結構分析的基礎上，

6、為最小化制造期問題選定合適的鄰域結構。將提出的進化模式和采用最速下降控制策略的爬山法局部搜索相結合，組成文化基因算法。對經(jīng)典測試問題的數(shù)值實驗表明，該算法在計算效果上與其它主流算法相比具有一定優(yōu)勢。
　?、軐τ谟嬎汶y度更大、優(yōu)化指標和工期相關的最小化總加權拖期時間車間作業(yè)調度問題，本文分析研究了已有鄰域結構的移動操作定義模式，提出了三種新的鄰域結構。將這些鄰域結構與已有鄰域結構進行對比分析，以此為基礎設計文化基因算法，并通過數(shù)值實

7、驗驗證算法的有效性。
　?、輰τ诙嗄繕塑囬g作業(yè)調度問題，提出一種基于精英保留策略的多目標文化基因算法。研究了多目標優(yōu)化領域中主流算法的設計理念，提出在進化過程和局部搜索中嵌入精英保留策略的多目標文化基因調度算法。對擁有兩個和三個優(yōu)化目標的車間作業(yè)調度問題的數(shù)值實驗表明，所提算法計算效果好于經(jīng)典的NSGAII算法，得到的計算結果好于經(jīng)典文獻給出的結果。
　?、薇局碚撀?lián)系實際的原則，本文在理論研究的基礎上，結合企業(yè)實際需求，將