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

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

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

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

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

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

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

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