安徽理工大學(xué)電氣與信息工程 汪 鵬

分段自適應(yīng)遺傳算法在流水車間調(diào)度中的應(yīng)用

安徽理工大學(xué)電氣與信息工程 汪 鵬

針對流水車間的優(yōu)化調(diào)度問題，提出一種分段自適應(yīng)遺傳算法，對遺傳算法交叉、變異算子進(jìn)行改進(jìn)，從而有效避免算法陷入局部，達(dá)到算法優(yōu)化調(diào)度的目的。通過對標(biāo)準(zhǔn)遺傳算法和改進(jìn)算法進(jìn)行仿真驗證得知，優(yōu)化后的算法具有更好的適應(yīng)度曲線，表明其有效的克服了標(biāo)準(zhǔn)遺傳算法不成熟收斂問題，具有一定的工程應(yīng)用價值。

分段自適應(yīng)；遺傳算法；流水車間

0 引言

隨著市場競爭的加劇，各制造加工企業(yè)為了提高自身的競爭力，必須合理分配資源，提高設(shè)備利用率與生產(chǎn)效率，降低生產(chǎn)成本，這就需要制定良好的車間生產(chǎn)調(diào)度。為此本文設(shè)計一種分段自適應(yīng)遺傳算法，隨著進(jìn)化代數(shù)和適應(yīng)度函數(shù)自動調(diào)整交叉概率和變異概率，以期以較快的收斂速度搜索到全局最優(yōu)解，從而滿足實際生產(chǎn)應(yīng)用的需要。

1 問題描述

流水車間調(diào)度問題（Flow shop Scheduling Problem, FSSP）是一種最重要的組合優(yōu)化問題， 該問題通?？梢悦枋鰹閚個工件要在m臺不同機(jī)器上加工，每個工件有m道工序，每道工序都要在不同的機(jī)器上加工，各個工件加工順序相同，且滿足如下的約束條件：1）每個工件在機(jī)器上的加工順序相同，且給定加工順序是1，2，3…，m；2）一個工件不能同時在不同的機(jī)器上進(jìn)行加工；3）每臺機(jī)器同時只能夠加工一個工件；4）工序的準(zhǔn)備時間與順序無關(guān)，且包含在加工時間內(nèi)；5）工件加工技術(shù)上的約束事先給定。

2 問題的算法設(shè)計

遺傳算法包括三個基本的操作：選擇、交叉和變異。遺傳算法的交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性，Pc的大小決定種群的更新速度和搜索快慢的指標(biāo)。Pm是保持種群多樣性，防止早熟的一種手段?；谝陨蠁栴}，本文提出了分段自適應(yīng)遺傳算法實時調(diào)整交叉概率及變異概率，從而獲得較優(yōu)解。

該算法分四個進(jìn)化階段。M為總進(jìn)化代數(shù)，itmax最大迭代代數(shù)，iter當(dāng)前代數(shù)，Pcmax最大交叉概率，Pcmin最小交叉概率，Pmmax最大變異概率，Pmmin最小變異概率，f變異個體適應(yīng)度（目標(biāo)函數(shù)值），fcmax為交叉兩個體較大適應(yīng)度，fave種群平均適應(yīng)度，fmax種群適應(yīng)度最大值。分別是1-0.4M代，Pcmax=0.8，Pcmin=0.6，Pmmax=0.08，Pmmin=0.05；0.4M-0.7M代，Pcmax=0.7，Pcmin=0.5，Pcmax=0.06，Pmmin=0.03；0.7M-0.9M代，Pcmax=0.6，Pcmin=0.4，Pmmax=0.04，Pmmin=0.02；0.9M到M代，Pcmax=0.5，Pcmin=0.3，Pmmax=0.02，Pmmin=0.01。

該算法參數(shù)設(shè)計的數(shù)學(xué)表達(dá)式如下：

其中，α和β為隨機(jī)產(chǎn)生的權(quán)重系數(shù)。

3 車間調(diào)度問題仿真及結(jié)果分析

為了驗證算法的有效性，本文分別將標(biāo)準(zhǔn)遺傳算法和分段自適應(yīng)遺傳算法的性能應(yīng)用于不同規(guī)模的流水車間調(diào)度問題，算法均用MATLAB2012a來實現(xiàn)，并在Pentium3.2Ghz×2GB內(nèi)存的機(jī)器上的加工時間使用著名的Taillard’s基準(zhǔn)算例。

圖1

如圖1所示，采用ta011(20×10)算例仿真，最優(yōu)值為1582，明顯看出分段自適應(yīng)遺傳算法優(yōu)于標(biāo)準(zhǔn)遺傳算法，具有較好的尋優(yōu)能力，從而驗證了算法的優(yōu)越性。

4 結(jié)論

本文研究了流水車間調(diào)度問題，提出了性能較優(yōu)的分段自適應(yīng)遺傳算法，仿真結(jié)果表明，該算法在處理流水車間問題更能優(yōu)化目標(biāo)函數(shù)，取得更好的效果。

[1]王凌．車間調(diào)度及其遺傳算法[M]．北京:清華大學(xué)出版社,2003．

[2]張博凡,黃宗南．基于變形遺傳算法交叉算子的Flow-Shop問題求解[J]．制造業(yè)自動化,2011(19):27-29,46．

[3]Taillard,E．Benchmarks for basic scheduling problems．European Journal of Operational Research[J]．1993,64:278-285．