王明星，李利民

WANG Ming-xing1，LI Li-min2

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

0 引言

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

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

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

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

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

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

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

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

1）每臺機床同一時間只能有一個加工任務(wù)且不能中斷；

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

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

4）每個工件的工藝路線事先確定；

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

2 改進的遺傳算法

2.1 個體編碼

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

例如編碼[251415]表示工序順序為[O21，O51，O11，O41，O12，O52]。

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

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

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

2.3 改進的交叉操作

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

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

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

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

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

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

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

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

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

1）選出待變異個體，確定個體進行變異操作的基因位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，更新個體基因編碼；

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

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

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

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

3 改進的遺傳算法求解流程

改進的遺傳算法操作步驟：

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

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

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

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

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

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

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

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

圖1 改進的遺傳算法流程圖

4 實驗結(jié)果及分析

4.1 實驗數(shù)據(jù)

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

表1 工件加工時間明細表

4.2 最優(yōu)解比較

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

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

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

4.3 搜索能力比較

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

[3]張國慶,劉永進,梅中義.改進的遺傳算法在復(fù)合材料車間計劃排產(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]劉晶晶,翟正軍.基于改進的遺傳算法的任務(wù)分配與調(diào)度[J].微電子學與計算機,2006, 23(6):216-219.

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

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

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

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

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