牛 琳

(海南醫(yī)學(xué)院 醫(yī)學(xué)信息學(xué)院，?？?571100)

改進的初始種群的遺傳算法在柔性車間調(diào)度中的應(yīng)用

牛 琳

(海南醫(yī)學(xué)院 醫(yī)學(xué)信息學(xué)院，?？?571100)

針對柔性作業(yè)車間調(diào)度中單純的遺傳算法容易陷入局部陷阱問題，結(jié)合柔性作業(yè)車間調(diào)度的特點，采用模擬退火算法融合遺傳算法對調(diào)度領(lǐng)域進行了研究。應(yīng)用模擬退火算法能跳出局部陷阱的能力及克服了遺傳算法過早熟的現(xiàn)象，很大程度上降低算法的收斂速度，同時提高了全局的收斂性?；贛atlab2012b軟件編程實現(xiàn)混合調(diào)度算法，文中仿真實例用混合調(diào)度算法，將結(jié)果與單純的遺傳算法得到的結(jié)果進行比較，證明了混合算法的優(yōu)勢。

遺傳算法；柔性作業(yè)車間調(diào)度；初始種群

0 引言

柔性工作車間調(diào)度問題( Flexible Job Shop Scheduling Problem, FJSP)[1]，F(xiàn)JSP也稱為工件的排序問題。其分析與研究目的在于企業(yè)實現(xiàn)效益最優(yōu)化—對加工工序進行高效排序，在約束條件下，使得所選擇的某個性能指標(biāo)達(dá)到最優(yōu)狀態(tài)。遺傳算法的魯棒性好，通用性和計算性能強大，因此較多的用在FJSP的問題中。但在實際應(yīng)用時由于收斂條件難以保證，所以目前國內(nèi)外很多文獻對遺傳算法求解FJSP問題提出了改進策略。例如，歐陽珍，狄瑞坤[2]融入模擬退火算法，提高了種群個體的多樣性。柳青紅等[3]提出了基于禁忌搜索的遺傳交叉算子，改進收斂速度。Zhang H P, Gen M[4-6]提出了一種多階段遺傳算法有效的改進了局部收斂問題。KACEM I，HAMMADI S, BORNE P[7-8]將遺傳算法與模糊理論相融合并應(yīng)用于柔性作業(yè)車間調(diào)度問題。通過分析遺傳算法求解FJSP問題方面已經(jīng)取得一些成果，但在求解過程中出現(xiàn)的問題還有待于進一步探究改進。文獻[9]采用MPGA種群遺傳算法結(jié)合移民算子對車間調(diào)度問題進行了研究。劉韻[10]等采用PSO啟發(fā)搜索式的粒子群優(yōu)化算法，解決了柔性車間調(diào)度時間問題。文獻[11]通過遺傳算法結(jié)合模糊算法對車間空間的搜索時間和收斂速度進行了改進。

鑒于此，本文在文獻[2]的基礎(chǔ)上對算法進行改進，將遺傳算法和模擬退火算法結(jié)合在一起，通過典型的柔性作業(yè)車間調(diào)度問題，將改進前后的調(diào)度結(jié)果進行比較分析，調(diào)度結(jié)果有了一定程度的提高，速度也有了一定程度的縮短，并將混合算法和單純的遺傳算法進行調(diào)度最優(yōu)解的對比，詳細(xì)的分析了兩者收斂代數(shù)、調(diào)度時間，證明了混合算法的優(yōu)于單純的遺傳算法。

1 FJSP數(shù)學(xué)優(yōu)化模型

柔性操作車間可調(diào)度問題通?？珊喪鰹椋捍嬖贜個加工工件，需要用M臺機器加工，需加工的每個工件包含多重加工工序，每道工序可以在一臺或多臺機器上加工，加工時間隨機器因素的差異而異同，規(guī)定工件的前一道工序未加工后一道工序則不能進行，同一類工件的所有工序之間存在先后順序；每個工序同一時刻只能在一臺機器上加工。問題目標(biāo)為每重工序需選擇最合適的機器，需要在這些工藝約束條件下，調(diào)整每一臺機器上不相同工件間的加工順序,使機器加工性能達(dá)到最優(yōu)狀態(tài)。

1.1 FJSP變量定義

(1)N：工件數(shù)量，M：機器數(shù)量，n：工序數(shù)。

(2)工件集合用數(shù)組J表示，J={J1,J2,…,Jj}，Jj為第j個工件，j=1,2，……，N。

(3)機器集合用數(shù)組P表示，P={P1,P2,…,Pp}，PP為第p個機器，p=1,2，……，M。

(4)對應(yīng)工序所用的加工機器為Ppj(1)，Ppj(2)，…，Ppj(n)。則機器的加工順序矩陣為P：

其中,Ppj(n)：j工件的工序n在機器Pp(p=1,2,…,M)上加工。

(5)加工時間集合用矩陣Tp表示:

其中,Tpj(n)：j工件的工序n的加工時間(在機器Pp上)。

(6)tjp定義為工件j在機器p上的總加工時間。

(7)cjp定義為工件j在機器p上的完工時間。

1.2 調(diào)度目標(biāo)數(shù)學(xué)模型

目標(biāo)函數(shù)為：在給定的工藝約束條件下進行調(diào)度優(yōu)化，使最大完工時間(makespan)最小，或者最小生產(chǎn)周期，即如何安排加工使得加工所有工件的時間最短；

(1)

約束條件：

cjp-tjp+A(1-ajhp)≥cjh

(2)

cjp-cip+A(1-xijp)≥tjp

(3)

cjp≥0;xijp,ajhp=0,1

(4)

cjp-cjh≥tjh

(5)

i,j=1,2,…,N;p,h=1,2,…,M

(6)

tjp：表示工件j在機器p上的加工時間；A表示一個值較大的正數(shù)；若工件i先于工件j在機器p上加工，則Xijp=1，否則Xijp=0；

當(dāng)機器h比機器p先加工工件i時，aihp為1，否則aihp為0。

式(2)確保工序在某時刻只可在唯一機器上加工。

式(3)確保機器在某時刻僅加工唯一工件。

式(4)確保每道工序在此生產(chǎn)過程中都得到加工。

式(5)確保工件的加工順序按給定的工藝路線進行。

同時，每個工件、同一工件的每道工序之間必須嚴(yán)格按照給定的工藝約束，工序開始加工之后不能中止，每個工件的優(yōu)先級一樣。

2 模擬退火算法的算法設(shè)計

模擬退火算法主要由升溫過程、恒溫過程和降溫過程組成。升溫過程是初始化溫度參數(shù)的過程，一般選擇一個較高溫度作為初始溫度，這樣可以在一定程度上增加模擬退火算法搜索整個解空間最優(yōu)解的機會，溫度較高時，算法在進行Metropolis準(zhǔn)則判斷時可以選擇較差的解作為個體解；當(dāng)算法的溫度變低時，算法收斂到最優(yōu)解的概率逐漸變高。所以算法設(shè)計時一般選擇較高的溫度作為初始溫度，用來增強算法跳出局部最優(yōu)解的能力。降溫過程一般用當(dāng)前溫度T乘以降溫系數(shù)q來模擬降溫過程，降溫系數(shù)決定著退火速度。

模擬退火部分的主要步驟如下：

Step1:設(shè)定主要的控制參數(shù)。初始溫度T0=1000C，降溫速率q=0.2，結(jié)束溫度Te=1e-3。

Step2:初始解。對于混合算法來說，初始解即是遺傳算法中經(jīng)過交叉、變異后的個體。

Step3:生產(chǎn)新解。新解在初始解的鄰域生成。編程時通過隨機選擇相鄰的兩個工序，然后交換兩者的加工順序，產(chǎn)生新解。例如初始解S1=123214，新解可以是S2=213214，即交換了前兩個工件的加工順序。

Step4:Metropolis準(zhǔn)則。用f(S1)表示初始解的適應(yīng)度，f(S2)表示新解的適應(yīng)度，那么df=f(S2)-f(S1),則Metropolis準(zhǔn)則為：

(7)

3 混合調(diào)度算法的設(shè)計

分別對遺傳算法和模擬退火算法的關(guān)鍵部分進行設(shè)計以后，得到的混合算法步驟如下：

Step1:設(shè)定混合算法的初始參數(shù)，包括種群的規(guī)模、遺傳的代數(shù)、初始溫度、降溫系數(shù)、變異概率等參數(shù)；

Step2:依據(jù)個體的加工工藝進行染色體編碼，采用工件工藝和機器的雙層編碼方式，同時隨機初始化種群，并分析種群的適應(yīng)度；

Step3:根據(jù)步驟step2的適應(yīng)度進行個體選擇操作，主要依據(jù)個體適應(yīng)度的好壞來進行選擇。適應(yīng)度小的個體被選擇遺傳的概率也較??；

Step4:對選擇的個體隨機選擇基因位置，進行交叉操作；

Step5:交叉完成后，根據(jù)變異率選擇個體進行變異操作，產(chǎn)生新的個體，注意變異后要檢查工藝的邏輯性；

Step6:對經(jīng)過遺傳操作后的種群，在染色體解的鄰域內(nèi)產(chǎn)生新的個體擾動解，并利用Metropolis準(zhǔn)則判定是否接受新解；

Step7:執(zhí)行參數(shù)的更新操作，如遺傳代數(shù)，當(dāng)前溫度等；

Step8:如果相關(guān)參數(shù)沒有達(dá)到規(guī)定的數(shù)值，則轉(zhuǎn)到步驟Step3，當(dāng)參數(shù)到達(dá)設(shè)定值之后，直接結(jié)束，輸出最優(yōu)解。

圖1 混合算法流程圖

4 算例分析

以FJSP生產(chǎn)系統(tǒng)為例。本算例以makespan最小為優(yōu)化目標(biāo)。對本文提出的改進前后的方法進行仿真并分析(軟件版本為MATLAB2014a)。表1和表2給出了調(diào)度工藝及時間要求具。

表1 工件的工序邏輯表

表2 工件各工序的加工時間

表1給出的是6個工件的工藝加工要求，對每一個單獨的工件來說，各個工序必須一次加工作業(yè)，工藝順序不能顛倒。表中的2維數(shù)組是工件在加工相應(yīng)工序時機器的可選集，因為在實際制造系統(tǒng)中，通常工件的某一道工序可以有多個機器滿足加工條件，這樣可以一定程度上避免因爭搶機器資源而使制造系統(tǒng)陷入停頓。表2是按照表1 工序加工時對應(yīng)所用的時間。

改進前：在單純的遺傳算法下，取初始參數(shù)個體數(shù)量為40，最大遺傳代數(shù)為50，交叉率為0.8，變異率為0.1，得到甘特圖如圖2所示。

圖2 遺傳算法下的甘特圖

圖2顯示了遺傳算法產(chǎn)生的一組最優(yōu)調(diào)度方案，所有工件按照調(diào)度方案加工完成所用的最短時間是52個時間單位；圖3是遺傳算法迭代過程中各代種群均值及最優(yōu)解的變化情況，從圖中可以看出，在經(jīng)過10代之后，種群均值及最優(yōu)解基本已經(jīng)不再變化，但實際上是遺傳算法陷入了過早熟現(xiàn)象的原因，遺傳算法并沒有搜索到真正有效的最優(yōu)解。表3是遺傳算法運行10次的得到的比較好的最優(yōu)解情況。

圖3 種群迭代次數(shù)

通過表3可以計算出遺傳算法10次得到的調(diào)度最優(yōu)解的均值為51.2個時間單位。

改進后：當(dāng)采用混合算法時，同樣采用表1和表2的工件工藝順序和工藝時間，并取初始溫度為1000℃，降溫速率為0.2，得到的一組甘特圖和種群均值圖如圖4和圖5所示。

圖4 混合算法下的甘特圖

圖5 種群均值及最優(yōu)解變化

從圖4 中可以看到，混合算法下按照調(diào)度方案完成所有工件加工的最優(yōu)解時間是48個時間單位，從圖5中可以看出混合算法使得種群的均值在15代以后才收斂到最小值，最優(yōu)解也是如此。綜上，從結(jié)果上可以看出混合算法由于模擬退火操作的加入，算法沒有提前結(jié)束搜索使算法染色體想入同化的情況。表4是混合算法運行10次的結(jié)果。

表4 遺傳算法運行10次的最優(yōu)調(diào)度結(jié)果

通過表4可以得到混合算法在降溫速率為0.2時，10次調(diào)度的平均時間是47.8個時間單位，調(diào)度方案的最優(yōu)解要好于單純的遺傳算法。當(dāng)降溫速率變化時，通過實驗得到的實驗數(shù)據(jù)如表5所示。

表5 不同降溫速度下混合算法及遺傳算法最優(yōu)解

從表5中可以看出，當(dāng)遺傳算法和混合算法對同一問題進行調(diào)度時，無論降溫系數(shù)在0.1～0.9中間任何值，混合算法的調(diào)度最優(yōu)解都要優(yōu)于單純的遺傳算法所產(chǎn)生的調(diào)度方案。通過分析種群均值穩(wěn)定的代數(shù)也可以發(fā)現(xiàn)，混合算法有效地解決了遺傳算法所存在的過早熟現(xiàn)象，使得種群迭代過程中不再過度依賴于初始解的產(chǎn)生，同時，通過模擬退火操作，使得算法搜索整個解空間的能力大大加強，以降溫速率為0.6的調(diào)度最優(yōu)解為例，普通的遺傳算法10次當(dāng)中沒有一次得到的最優(yōu)解在50以下，而混合算法幾乎有8次以上低于50，分析調(diào)度結(jié)果可知，調(diào)度最差的降溫速率0.1也有6 次跳出了局部陷阱。而當(dāng)降溫速率為0.9時，混合算法幾乎全部跳出了局部最優(yōu)解，可見混合算法相對于單純的遺傳算法有著更好的跳出局部陷阱的能力，得到更優(yōu)的調(diào)度方案。

5 結(jié)論

本文將遺傳算法和模擬退火算法結(jié)合在一起，通過典型的柔性作業(yè)車間調(diào)度問題，將改進前后的調(diào)度結(jié)果進行比較分析，調(diào)度結(jié)果有了一定程度的提高，速度也有了一定程度的縮短，并將混合算法和單純的遺傳算法進行調(diào)度最優(yōu)解的對比，詳細(xì)的分析了兩者收斂代數(shù)、調(diào)度時間，證明了混合算法的優(yōu)于單純的遺傳算法，說明了這種混合算法在求解FJSP問題上的優(yōu)勢。

[1] 藍(lán)萌, 徐汀榮, 黃斐. 使用混合鄰域搜索算法求解多目標(biāo)柔性JSP問題[J]. 計算機工程與設(shè)計, 2011, 32(1):293-296.

[2] 歐陽珍.基于遺傳算法的車間調(diào)度研究與應(yīng)用[D].杭州:浙江大學(xué),2004.

[3] 柳青紅,袁逸萍,李曉娟.基于改進遺傳算法的作業(yè)車間調(diào)度[J].機械工程與自動化，2014(6):1-3.

[4] Zhang H P, Gen M. Multistage-based genetic algorithm for flexible job-shop scheduling problem[J].Journal Complexity, 2005, 11: 223-232.

[5] 陳振同,邢英杰.基于改進遺傳算法的車間調(diào)度問題研究與應(yīng)用[D]. 大連:大連理工大學(xué)，2007.

[6] 趙振勇,王力,王保華,等.遺傳算法改進策略的研究[J].計算機應(yīng)用,2006(S2):189-191.

[7] Mastrolilli M, Gambardella L M. Effective neighbourhood functions for the flexible job shop problem[J],Journal of Scheduling, 2000, 3 (1):3-20.

[8] KACEM I，HAMMADI S, BORNE P. Pareto-optimality approach for flexible job shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation, 2002,60(3/4/5):245-276.

[9] 李運霞, 杜娟, 孫王路. 基于多種群遺傳算法的路徑柔性車間調(diào)度問題[J]. 組合機床與自動化加工技術(shù), 2014(3):152-157.

[10] 劉韻, 胡毅, 羅企,等. 一種解決柔性車間作業(yè)調(diào)度問題的粒子群優(yōu)化算法[J]. 組合機床與自動化加工技術(shù), 2015(12):144-147.

[11]馬磊磊, 王強. 基于改進遺傳算法的多目標(biāo)物料配送方法研究[J]. 組合機床與自動化加工技術(shù), 2015(12):156-160.

(編輯 李秀敏)

Genetic Algorithm of Improved Initial Population Applying to Scheduling for Flexible Job Shop

NIU Lin

(College of Medical Information, Hainan Medical University, Haikou 571100,China)

The quality of the initial population of genetic algorithm have a decisive influence on the quality and speed. When traditional genetic algorithm is applied in solving flexible job shop scheduling problems, the initial population is randomly generated, which may result in forming many infeasible solutions at the beginning of the iteration. Only through a complex operation will form optimum solutions, it may greatly reduces convergence speed of the algorithm.After study the characteristics of flexible job shop scheduling,Initial population give rules of base on the entire Search to code and generate initial population′s strategy, has been put forward.When the quality of initial population be improved,its diversity also won′t lose. At the same time, its global convergence can be improved.The instance in this article using the improved genetic algorithm,the results are compared with the traditional genetic algorithm′s results, It proved that the advantages of improved algorithm.

genetic algorithm; flexible job shop scheduling; initial population

1001-2265(2017)08-0157-04

10.13462/j.cnki.mmtamt.2017.08.041

2016-09-10；

2016-10-21

牛琳(1978—)，女，黑龍江巴彥人，海南醫(yī)學(xué)院講師，碩士，研究方向為數(shù)據(jù)挖掘，信息管理，(E-mail)2763253868@qq.com.

TH186;TG659

A