王明星，李利民

WANG Ming-xing1，LI Li-min2

(1.中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，太原 030051；2.山西汾西重工有限責(zé)任公司，太原 030027)

0 引言

科學(xué)的計(jì)劃排產(chǎn)是提升加工制造企業(yè)市場競爭力的關(guān)鍵因素。但車間計(jì)劃排產(chǎn)長期以來都是生產(chǎn)調(diào)度的難題[1,2]，原因在于車間加工過程復(fù)雜，把不同零件按各自工藝路線有效的組織起來進(jìn)行加工并非易事，所以能以最短的時(shí)間、最高的效率、最少的成本完成生產(chǎn)指標(biāo)是很多企業(yè)的共同追求。20世紀(jì)80年代以來，模擬退火算法（Simulated Annealing, SA）、禁忌搜索算法（Tabu Search, TS）和遺傳算法（Genetic Algorithms, GA）等智能算法在生產(chǎn)調(diào)度領(lǐng)域應(yīng)用廣泛，優(yōu)化效果顯著[3]。其中，遺傳算法求解復(fù)雜優(yōu)化問題時(shí)潛力巨大，為車間的排產(chǎn)調(diào)度提供了新的思路。

遺傳算法（Genetic Algorithm, GA）是由美國學(xué)者J.H.Holland等人提出，模擬生物進(jìn)化自然選擇過程的計(jì)算模型。Wang H[4]用標(biāo)準(zhǔn)遺傳算法（SGA）求解調(diào)度問題時(shí)存在早熟收斂、求解精度低等問題，劉晶晶等人[5]將適應(yīng)度引入到父代之間的交叉操作中，克服了SGA交叉操作中較大的盲目性，劉愛珍等人[6]利用混沌優(yōu)化技術(shù)，對遺傳算法的交叉和變異概率進(jìn)行動(dòng)態(tài)控制，得到了可行解。

目前對基本遺傳算法改進(jìn)后應(yīng)用于機(jī)加車間排產(chǎn)的研究很少。借鑒相關(guān)文獻(xiàn)算法優(yōu)點(diǎn)，以工件加工時(shí)間最短為目標(biāo)，結(jié)合機(jī)加車間實(shí)際生產(chǎn)情況，建立對應(yīng)數(shù)學(xué)模型，以個(gè)體適應(yīng)度值為參照自動(dòng)調(diào)節(jié)交叉概率和變異概率，根據(jù)加工任務(wù)高度值劃分基因段來改善交叉操作，引入混沌理論優(yōu)化變異算子增強(qiáng)算法的全局搜索能力。最后用此算法和參考文獻(xiàn)中方法對給定算例進(jìn)行求解并做了對比分析。

1 機(jī)加車間生產(chǎn)工藝流程

機(jī)加車間依靠機(jī)床加工零件，主要負(fù)責(zé)中小型零件的車、銑、鏜、鉆、鉗、磨、電加工等機(jī)械加工及熱處理。其車間調(diào)度問題可描述如下：

在m臺(tái)機(jī)床上加工n個(gè)不同的工件，機(jī)床集M由m臺(tái)機(jī)床Mj（j=1，2，…，m）組成，工件集N由n個(gè)待加工工件Pi（i=1，2，…，n）組成，工件Pi的加工工藝有qi道工序序列集Oik（k=1，2，…，qi）組成，工序Oik的加工機(jī)床組合為Mik，對應(yīng)加工時(shí)間為tik，Mik表示第i個(gè)工件的第k道工序使用的機(jī)床號(hào)，Mik=0表示工件Pi在第k道工序不加工。機(jī)床集，工件集，工序序列集都用矩陣表示[7]。

該調(diào)度問題要求在一定條件下，整個(gè)調(diào)度的最大完工時(shí)間Cmax（從第一個(gè)工件開始加工到最后一個(gè)工件完成加工所需時(shí)間）最小，即：

其中，Cik表示工序Oik完工時(shí)間，Sik表示工序Oik開始加工時(shí)間，tik表示工序Oik加工時(shí)間。調(diào)度方案末道工序完工時(shí)間就是整個(gè)調(diào)度最大完工時(shí)間Cmax。假設(shè)改進(jìn)的遺傳算法在以下條件運(yùn)行：

1）每臺(tái)機(jī)床同一時(shí)間只能有一個(gè)加工任務(wù)且不能中斷；

2）各工件的加工工序一般相同，不同工件同一工序加工時(shí)間一般不同；

3）每個(gè)工件工序之間存在約束關(guān)系，工序應(yīng)該依次按順序執(zhí)行；

4）每個(gè)工件的工藝路線事先確定；

5）初始時(shí)刻，任何工件都能被加工。

2 改進(jìn)的遺傳算法

2.1 個(gè)體編碼

由于工件的加工順序存在優(yōu)先級(jí)，我們采用基于工序的編碼方式，每段基因代表加工的工序數(shù)，對于n個(gè)工件m臺(tái)機(jī)床的調(diào)度問題，編碼可表示為[k11，k12, …, k1m，…kn1，kn2，knm]，其中kj（j=11，12, …, nm）表示工件編號(hào)。工件Ji（i=1，2, …, n）的工件編號(hào)i在整個(gè)編碼中出現(xiàn)m次表示該工件共m道工序。上述編碼中，工件號(hào)i第一次出現(xiàn)表示Ji的第一道工序Oi1，工件號(hào)i第二次出現(xiàn)表示Ji的第二道工序Oi2，以此類推，Oim表示Ji的末道工序。

例如編碼[251415]表示工序順序?yàn)閇O21，O51，O11，O41，O12，O52]。

2.2 對交叉和變異概率自適應(yīng)調(diào)節(jié)

交叉與變異算子是影響遺傳算法性能的關(guān)鍵因素，通過交叉和變異不但可以把父代個(gè)體的優(yōu)秀品質(zhì)遺傳給子代，而且子代可能獲得比父代更好的基因結(jié)構(gòu)。SGA通常設(shè)定一定的交叉概率和變異概率，然后由貝努利實(shí)驗(yàn)決定是否進(jìn)行交叉或變異運(yùn)算，交叉概率和變異概率過大可能導(dǎo)致隨機(jī)搜索，過小可能導(dǎo)致早熟收斂，產(chǎn)生局部極值。對交叉概率和變異概率的改進(jìn)如下：

其中，Pc0和Pm0是初始化的交叉概率和變異概率，Pc1和Pm1是調(diào)整后的交叉概率和變異概率，Wmax是群體中的最大適應(yīng)度，Wavg是群體平均適應(yīng)度，W(x)是兩個(gè)待交叉?zhèn)€體中的較大適應(yīng)度。觀察表達(dá)式(2)和式(3)可知，適應(yīng)度低于平均適應(yīng)度的個(gè)體受破壞的可能性大，被淘汰；適應(yīng)度高于平均適應(yīng)度的個(gè)體受破壞的可能性小，被保存到下一代。

2.3 改進(jìn)的交叉操作

交叉在遺傳算法中發(fā)揮核心作用，當(dāng)交叉概率偏大時(shí)，遺傳算法對新空間的搜索能力增強(qiáng)，但優(yōu)秀基因遭到破壞的可能性也變大，算法收斂速度和穩(wěn)定性下降；當(dāng)交叉概率偏小時(shí)，遺傳算法的搜索會(huì)有滯后性。

隨機(jī)在父代中選擇交叉點(diǎn)盲目性很大，算法性能會(huì)嚴(yán)重下降，此改進(jìn)策略放棄對父代基因隨機(jī)交換，而是按照加工任務(wù)的高度值把父代基因劃分為若干個(gè)小段，高度值相同的加工任務(wù)劃分到一個(gè)基因段，劃分完成后在父代中按序選取等位基因段組成一個(gè)子代。父代的等位基因段適應(yīng)度越高，被選作子代基因段的可能性越大。這一改進(jìn)的最大優(yōu)勢在于：沒有改變加工任務(wù)的任何前驅(qū)限制關(guān)系，得到的結(jié)果都是可行解。交叉算法具體操作步驟如下：

1）計(jì)算工件x1和x2中每道工序的加工時(shí)間，然后將分配到同一機(jī)床的加工任務(wù)按加工時(shí)間劃分為若干個(gè)基因段；

2）按照如下方法選取等位基因段（即工件x1和x2工序中在相同機(jī)床上相等的基因段）概率；

3）生成一個(gè)任意的隨機(jī)數(shù)Hi（i=1,2,3…,k；k為基因段個(gè)數(shù)），然后將Hi與 P (x1)或P (x2)進(jìn)行比較來確定所選取的等位基因段。如果 P(x1)＜ P (x2)，當(dāng)Hi＞ P (x2)時(shí)，選取x2的等位基因；當(dāng)Hi＜ P (x1)時(shí)，選取X1的等位基因。

2.4 混沌優(yōu)化變異算子

受加工任務(wù)之間約束關(guān)系的限制，SGA容易產(chǎn)生早熟收斂。SGA的變異操作通常采用隨機(jī)數(shù)決定，這會(huì)導(dǎo)致新個(gè)體產(chǎn)生的隨機(jī)性過大，不具有遍歷性和規(guī)律性?；煦缡亲匀唤缙毡榇嬖诘姆蔷€性現(xiàn)象，它看似很混亂，內(nèi)部結(jié)構(gòu)卻很精致，具有遍歷性、隨機(jī)性、敏感性和規(guī)律性?；煦绗F(xiàn)象在一定范圍之內(nèi)能依據(jù)自身規(guī)律沒有重復(fù)的遍歷所有狀態(tài)，這一特性可作為搜索過程中避免陷入局部最優(yōu)解的優(yōu)化機(jī)制[8]。因此，本文把混沌理論應(yīng)用到遺傳算法的變異操作中?；煦缧蛄胁捎萌缦滤緇ogistic映射公式，其中k為控制系數(shù)：

其中k=4，此時(shí)系統(tǒng)處于完全混沌狀態(tài)。任意取一個(gè)初始值X0，可產(chǎn)生一個(gè)迭代序列Xn+1，該序列會(huì)在[0,1]之間來回變化。本文將Xn+1作為控制遺傳算法是否變異的標(biāo)尺。

假設(shè)染色體中個(gè)體基因的取值范圍是[α,β]，即可供選擇的加工工序的范圍，混沌優(yōu)化變異的操作步驟如下：

1）選出待變異個(gè)體，確定個(gè)體進(jìn)行變異操作的基因位i和基因位對應(yīng)的工序碼Gi，取X0=Gi；

2）將X0代入式(7)調(diào)整為基因取值范圍內(nèi)的數(shù)；

3）將X1代入混沌優(yōu)化的映射公式(6)，得到X2；

4）再將X2調(diào)整為[0,1]之間的數(shù)；

5）令Gi= X3，更新個(gè)體基因編碼；

6）判斷變異操作是否結(jié)束，若結(jié)束，則返回到遺傳算法中，否則，選取下一個(gè)待變異的個(gè)體，轉(zhuǎn)步驟1）。

2.5 適應(yīng)度函數(shù)的建立

車間排產(chǎn)問題是求解加工工件耗費(fèi)總時(shí)間的最小值，這需要讓適應(yīng)度值最大化，所以適應(yīng)度函數(shù)定義為：

其中，tij為第i個(gè)工件第j道工序的加工時(shí)間；qi是加工第i個(gè)工件需要的最大工序數(shù)；n是最大工件數(shù)；C是的某極限值，保證F(x)是非負(fù)數(shù)，便于選擇和排序概率的計(jì)算。

3 改進(jìn)的遺傳算法求解流程

改進(jìn)的遺傳算法操作步驟：

1）獲取算法基礎(chǔ)數(shù)據(jù)：讀入工件的種類、加工工序數(shù)和對應(yīng)工序的加工時(shí)間，讀入機(jī)床的加工產(chǎn)能；

2）初始化算法各參數(shù)：設(shè)定算法的群體規(guī)模和結(jié)束的循環(huán)代數(shù)，設(shè)定算法的初始交叉概率Pc0和變異概率Pm0。設(shè)定初始解集作為初始染色體；

3）計(jì)算當(dāng)前染色體適應(yīng)度值，把函數(shù)適應(yīng)度值最大的個(gè)體設(shè)定為當(dāng)前一代的最佳解；

4）檢驗(yàn)是否滿足算法收斂準(zhǔn)則 ，若滿足，則轉(zhuǎn)步驟7），否則進(jìn)行步驟5）；

5）對染色體當(dāng)前的交叉概率和變異概率進(jìn)行動(dòng)態(tài)的自適應(yīng)調(diào)整，以調(diào)整后的交叉概率進(jìn)行改進(jìn)的交叉操作，以調(diào)整后的變異概率進(jìn)行混沌優(yōu)化變異操作；

6）對染色體進(jìn)行選擇操作[9]，把經(jīng)過遺傳操作的染色體作為當(dāng)前染色體。轉(zhuǎn)步驟3）；

7）得到最佳個(gè)體，輸出結(jié)果。

該算法的流程圖如圖1所示。

圖1 改進(jìn)的遺傳算法流程圖

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

設(shè)定機(jī)加車間要加工9個(gè)工件，每個(gè)工件都要經(jīng)過車、銑、磨3道工序的處理，現(xiàn)有2臺(tái)車床，3臺(tái)銑床，2臺(tái)磨床，不同工件在不同機(jī)床的加工時(shí)間各不相同，具體加工情況如表1所示。

表1 工件加工時(shí)間明細(xì)表

4.2 最優(yōu)解比較

將標(biāo)準(zhǔn)遺傳算法（SGA）[4]和本文算法應(yīng)用于該車間實(shí)際生產(chǎn)進(jìn)行仿真對比。設(shè)定初始交叉概率Pc0=0.70，變異概率Pm0=0.05，種群規(guī)模M=100，進(jìn)化代數(shù)T=100，分別獨(dú)立運(yùn)行20次取平均值[10]。得到的結(jié)果如表2所示。

表2 SGA和本文算法排產(chǎn)結(jié)果

比較分析可得：本文算法波動(dòng)率小，動(dòng)態(tài)穩(wěn)定性高，最優(yōu)解為77.7，排產(chǎn)效果優(yōu)于SGA。但由于算法復(fù)雜，運(yùn)行時(shí)間比SGA稍長，這對于排產(chǎn)優(yōu)化效果影響不大。

4.3 搜索能力比較

我們選用標(biāo)準(zhǔn)遺傳算法（SGA）、文獻(xiàn)[5]中算法、文獻(xiàn)[6]中算法和本文算法分別求解進(jìn)行性能評(píng)估。文獻(xiàn)[4～6]中GA主要參數(shù)見原文，本文算法參數(shù)和4.2中設(shè)置相同。仿真過程在一臺(tái)PC機(jī)上完成，操作系統(tǒng)是Windows XP，CPU是Intel(R)Q6600，內(nèi)存為3GB，工具是Matlab2012b。設(shè)平均改進(jìn)量為I，仿真結(jié)果如圖2所示。

為了減小算法隨機(jī)性產(chǎn)生的誤差，更加準(zhǔn)確的體現(xiàn)各算法的性能，圖2中每組數(shù)據(jù)都是各自運(yùn)行20次取平均值得到的，觀察可知，此算法得到的加工時(shí)間最短，全局搜索能力最好。

8個(gè)機(jī)床加工40個(gè)工件條件下四種算法分別進(jìn)化產(chǎn)生的靜態(tài)性能曲線如圖3所示。

圖2 各算法仿真結(jié)果比較

圖3 靜態(tài)性能曲線(m=8,n=40)

觀察圖3可以得到以下結(jié)論：

1）在不降低獲得最優(yōu)解質(zhì)量的前提下，本文算法擴(kuò)大了搜索范圍，提高了收斂速度，求解質(zhì)量和運(yùn)行效率比圖中其他算法顯著提高；

2）隨著進(jìn)化代數(shù)的遞增，完成時(shí)間持續(xù)減少最后趨于穩(wěn)定，說明優(yōu)秀基因被遺傳下來，使排產(chǎn)效果得以優(yōu)化；

3）收斂速度方面：此算法＞文獻(xiàn)[6]算法＞文獻(xiàn)[5]算法＞ SGA；

4）收斂代數(shù)方面：各算法進(jìn)化代數(shù)收斂區(qū)間：[50,200]。

5 結(jié)束語

通過研究某公司機(jī)加車間排產(chǎn)調(diào)度問題，建立其數(shù)學(xué)模型，并用遺傳算法對其求解。通過對基本遺傳算法三個(gè)方面的改進(jìn)，即以個(gè)體適應(yīng)度值為參照自動(dòng)調(diào)節(jié)交叉概率和變異概率，根據(jù)加工任務(wù)高度值劃分基因段來改善交叉操作，引入混沌理論優(yōu)化變異算子，極大提高了遺傳算法的收斂速度和對最優(yōu)解的搜索能力。通過對仿真結(jié)果的分析比較，改進(jìn)算法顯著縮短了機(jī)加車間的生產(chǎn)總時(shí)間，優(yōu)化效果比現(xiàn)有的算法更明顯，對機(jī)器加工行業(yè)排產(chǎn)優(yōu)化有一定借鑒意義。

[1]帥飛,陳兆剛,李向東.基于遺傳算法的橋式起重機(jī)節(jié)能調(diào)度優(yōu)化研究[J].制造業(yè)自動(dòng)化,2013, 35(14):97-99.

[2]王進(jìn)峰,陰國富,雷前召,等.基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度[J].現(xiàn)代制造工程,2013(5):50-53.

[3]張國慶,劉永進(jìn),梅中義.改進(jìn)的遺傳算法在復(fù)合材料車間計(jì)劃排產(chǎn)中的應(yīng)用研究[J].現(xiàn)代制造工程,2010(7):56-59.

[4]Wang H.Flexible flow shop scheduling: optimum,heuristics and artificial intelligence solutions[J].Expert Systems,2005,22(2):78-85.

[5]劉晶晶,翟正軍.基于改進(jìn)的遺傳算法的任務(wù)分配與調(diào)度[J].微電子學(xué)與計(jì)算機(jī),2006, 23(6):216-219.

[6]劉愛珍,王嘉禎,賈紅麗,等.改進(jìn)的多任務(wù)分配與調(diào)度遺傳算法[J].微電子學(xué)與計(jì)算機(jī),2007,24(9):162-168.

[7]張昕.改進(jìn)的遺傳算法在車間作業(yè)調(diào)度中的應(yīng)用研究[J].國防制造技術(shù),2013,2:019.

[8]李耀華,徐樂江,胡國奮,等.基于混沌遺傳算法的板坯入庫決策優(yōu)化方法[J].系統(tǒng)仿真學(xué)報(bào),2006,17(11):2620-2623.

[9]陳憶群,周如旗,林淑金,等.有車輛數(shù)限制的開放式車輛調(diào)度問題研究[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(003):595-601.

[10]蔣佳穎,王萬良,徐新黎,等.基于量子遺傳算法的染缸排產(chǎn)問題研究[J].計(jì)算機(jī)工程,2011,37(21):159-161,164.