郭 慶， 張明路， 孫立新， 劉 軒

(河北工業(yè)大學(xué)機械工程學(xué)院， 天津 300131)

車間生產(chǎn)調(diào)度作為關(guān)鍵技術(shù)和核心內(nèi)容在離散柔性制造生產(chǎn)計劃中起主要作用[1]，因為每個企業(yè)車間的生產(chǎn)資源是有限的，并且工件的加工也會受到設(shè)備工藝的限制，如何合理安排每個工件的每個生產(chǎn)步驟在哪臺設(shè)備上加工，以確保所選定的目標的最佳性能，這就是調(diào)度的目的。該問題的特征在于顯著的離散性、復(fù)雜性、多重約束和不確定性。傳統(tǒng)作業(yè)車間生產(chǎn)調(diào)度很難達到最佳的排產(chǎn)效果，這樣就會造成生產(chǎn)效率低下，浪費生產(chǎn)資源，增加企業(yè)生產(chǎn)成本。因此，用來實現(xiàn)柔性車間調(diào)度的智能算法亟需設(shè)計，進而可以提高生產(chǎn)效率，提高企業(yè)的市場競爭力。

柔性車間生產(chǎn)排產(chǎn)調(diào)度問題(flexible job shop scheduling problem，F(xiàn)JSP)是傳統(tǒng)作業(yè)車間生產(chǎn)調(diào)度問題(job shop scheduling problem，JSP)的擴展。FJSP 這個問題在1990年由Bruker等[2]提出，在JSP中，每道工序是預(yù)先確定的，并且其生產(chǎn)設(shè)備和生產(chǎn)時間也是預(yù)先確定的。而在FJSP中，每道工序的生產(chǎn)設(shè)備是不確定的。每道工序都有加工設(shè)備集，可在其中挑選任一設(shè)備進行加工，并且不同生產(chǎn)設(shè)備生產(chǎn)同道工序所花費時間不同，這增加了該類調(diào)度問題的靈活性，且在實際生產(chǎn)中為常見情況，所以解決該問題勢在必行。

目前，解決 FJSP 的常用方法有禁忌搜索(taboo search,TS)，模擬退火(simulated annealing，SA)，遺傳算法(genetic algorithm，GA)和粒子群優(yōu)化(particle swarm optimization，PSO)等[3-6]。其中，遺傳算法因其良好的魯棒性、通用性和計算機優(yōu)勢而被廣泛應(yīng)用。武韶敏等[7]研究出了基于矩陣編碼的方法對遺傳算法進行改進，并且詳細描述了初始種群的生成方法。崔琪等[8]在搜索方面采用混合變鄰域的方法對遺傳算法進行了改進。姚麗麗等[9]提出一種啟發(fā)式正序排產(chǎn)算法，該方法采用調(diào)度規(guī)則與邏輯約束兩層改進處理的作為總體排產(chǎn)方法。

現(xiàn)針對柔性車間生產(chǎn)調(diào)度問題，提出一種靈活的車間調(diào)度模型，并對該模型進行詳細的求解。針對模型結(jié)構(gòu)的特殊性，采用一種新的編碼思想進行染色體的雙層編碼，獲得具有較高質(zhì)量和多樣性的初始種群；將MATLAB編程應(yīng)用到解碼和適應(yīng)度函數(shù)的計算中，加快求解效率和降低問題的復(fù)雜性；給出了相應(yīng)的選擇操作設(shè)計，交叉操作采用多交叉機制，變異操作結(jié)合種群分割的思想實行兩種變異機制，進一步改善算法的全局和局部搜索能力；并且添加檢查操作增強優(yōu)化過程的可行性。最后通過一個6×6調(diào)度問題的仿真實例對算法的有效性進行驗證并繪制甘特圖。

1 FJSP的數(shù)學(xué)模型

1.1 問題描述

FJSP描述如下：n個工件{N1,N2，…,Nn}在m臺設(shè)備{M1,M2,…,Mm}上加工。工件i的總工序為ni，每個工序的順序都已確定，而且每個工件工序都有加工設(shè)備集，可挑選集合中任何設(shè)備加工該道工序，但生產(chǎn)時間因生產(chǎn)設(shè)備不同而不同。調(diào)度目的是在整個生產(chǎn)計劃中，為每道工序選擇最合適的設(shè)備，并確定每臺設(shè)備最佳生產(chǎn)順序和啟動時間，以保證最大完成時間(makespan)最小化，總設(shè)備負荷最小和臨界設(shè)備符合最小。

1.2 數(shù)學(xué)模型

在建立FJSP數(shù)學(xué)模型之前，做出如下基本假設(shè)：①任何設(shè)備在同一時刻不能處理兩個生產(chǎn)步驟；②任一工件必須嚴格按照自己的工序順序進行加工；③任一工件必須嚴格在自己的加工設(shè)備集里加工；④不同的工件的生產(chǎn)步驟之間沒有約束條件，優(yōu)先級相同；⑤生產(chǎn)開始后，不能中斷，并且能正常生產(chǎn)完成；⑥設(shè)備與工件的開始時間都允許在0時刻開始。

為建模方便，現(xiàn)將FJSP問題表述為：n個工件{N1,N2，…,Nn}在m臺設(shè)備{M1,M2，…,Mm}上加工。工件i的總工序為ni，則所有工件集的總生產(chǎn)步驟為Num=sumni。上述基本約束條件下，針對最大完成時間(makespan)最小化，總設(shè)備負荷最小和臨界設(shè)備符合最小。設(shè)oij為工件i的第j道工序；M[i,j]為工件i的第j道工序的可用設(shè)備集合；

xijk為判定函數(shù)。

FJSP數(shù)學(xué)模型如下。

(1)最小化完工時間：

(1)

式(1)中：f1為第1個目標函數(shù)；CM為所有設(shè)備的完工時間；Ck為第k臺設(shè)備上的完工時間；k為設(shè)備索引，k=1,2，…，m；m為設(shè)備總數(shù)。

(2)各臺設(shè)備的加工時間：

(2)

式(2)中：Wk為第k臺設(shè)備上的工作負荷；n為工件總數(shù)；ni為工件i的總工序；i、h為工件索引，i、h=1,2，…，n；j、g為工件序列索引，j、g=1,2，…，ni；Tijk為工件i的第j道工序在設(shè)備k上的加工時間。

則總設(shè)備負荷最小，即全部設(shè)備的總加工時間：

(3)

式(3)中：f2為第2個目標函數(shù)；WT為全部設(shè)備總加工時間。

(3)臨界設(shè)備負荷，即加工負荷最大的設(shè)備：

(4)

式(4)中：f3為第3個目標函數(shù)；WM為設(shè)備臨界負荷。

s.t.

Cij-Ci(j-1)≥Tijkxijk,j=2,…,ni;?i,j

(5)

式(5)中：Cij為工件i的第j道工序的完成時間。

[(Chg-Cij-thgk)xhgkxijk≥0]∨[(Cij-

thgk)xhgkxijk≥0],?(i,j),(h,g),k

(6)

式(6)中：thgk為工件h的第g道工序在設(shè)備k上的開始加工時間。

(7)

Cij≤Cmax,i=1,2,…,n

(8)

Sij≥0,Cij≥0

(9)

式(9)中：Sij為工件i的第j道工序的開始加工時間。

式(5)確保了工作順序的先后約束；式(6)限定每臺設(shè)備每次只能處理一道工序；式(7)表示可以從每道工序的加工設(shè)備集里選擇一臺設(shè)備進行加工；式(8)限定了每一個工件的完工時間不可能超過總完工時間；式(9)限定了所有參數(shù)變量的非負性。

2 FJSP的遺傳算法實現(xiàn)

遺傳算法(genetic algorithm)是一種基于自然物種進化規(guī)律的算法，即適者生存。遺傳算法過程如圖1所示。

圖1 遺傳算法過程Fig.1 Genetic algorithm process

2.1 編碼設(shè)計及初始化

遺傳算法解決任何問題的首要關(guān)鍵都是編碼，其次便是解碼，解決FJSP問題也不例外。由于FJSP模型的特殊性，采用雙層編碼的方式，對第一層染色體編碼，為所有工件所有工序進行排序，對另一層染色體編碼，為每道工序的加工設(shè)備編號，并最終通過MATLAB編程得以驗證方法可行。

M{i,j}表示工件i的第j道工序的加工設(shè)備集，T{i，j}表達工件i的第j道工序被不同生產(chǎn)設(shè)備加工的時間集。假設(shè)n=4，ni=4，則M、T如表1、表2所示。

表1 M加工設(shè)備集Table 1 M processing equipment collection

表2 T加工設(shè)備時間集Table 2 T Processing equipment time collection

兩層編碼即兩條染色體，分別命名為X、Y染色體，接下來分別對X、Y進行編碼。

X染色體代表隨機安放每個工件的每個工序，并保證每個工件的工序的先后順序，由于n=4，ni=4，則Num=16，則X染色體長度為16，X染色體編碼過程如下。

第1步將1～16隨機排序，代表所有工序隨機排列，得初始染色體{5 8 4 2 9 7 10 13 1 11 16 15 3 6 12 14}。

第2步將初始染色體{5 8 4 2 9 7 10 13 1 11 16 15 3 6 12 14}按照先后順序4個為一組進行分組，每一組代表一個工件的4個工序，得子染色體{5 8 4 2} {9 7 10 13} {1 11 16 15} {3 6 12 14}。

第3步將每個子染色體在各自內(nèi)部進行大小排序，得子二代染色體{2 4 5 8}{7 9 10 13}{1 11 15 16}{3 6 12 14}。

第4步將子二代染色體{2 4 5 8}{7 9 10 13}{1 11 15 16}{3 6 12 14}合并成中間染色體Z{2 4 5 8 7 9 10 13 1 11 15 16 3 6 12 14}。

第5步對Z染色體中的值的位置編號，并將編號根據(jù)Z染色體1～16序列編碼數(shù)字以形成X染色體，表3中1～4表示工件1的4道工序，5～8代表工件2的4道工序，以此類推。例如“8”在Z染色體中是第4個位置，則在X染色體的第8位置編碼為4。X染色體如表3所示。

表3 Z-X轉(zhuǎn)換表Table 3 Z-X conversion form

該編碼方式可以有效地避免工序錯亂的情況出現(xiàn)，確保每一個工件按照各自的工藝流程加工完成，大大提高了染色體的可行性，有助于保證種群質(zhì)量。

Y染色體代表依照X染色體的工序排序，加工每道工序的具體設(shè)備編號，Y染色體編碼過程如下。

第1步依照X{9 1 13 2 3 14 5 4 6 7 10 15 8 16 11 12}順序確定可加工該工序的生產(chǎn)設(shè)備集{[M6,M8],M4,[M1,M4],[M1,M2,M3],[M8,M9],

M3,M2,M3,M7,M4,[M2,M6],[M5,M7,M8],[M2,M3],M7,M5,[M4,M6]}。

第2步將生產(chǎn)設(shè)備集內(nèi)部重新進行編碼，得新染色體{[1,2], 1,[1,2],[1,2,3],[1,2], 1,1,1,1,1,[1,2],[ 1,2,3],[1,2], 1,1,[1,2]}。

第3步在各自的設(shè)備集中隨機挑選設(shè)備加工該道工序，最終得到Y(jié)染色體，即{1,1,2,3,2,1,1,1,1,1,2,3,1,1,1,1}。該編碼方式是為后續(xù)在時間集中采集設(shè)備加工時間提供便利。

重復(fù)以上編碼流程，直到形成完整的初始種群NP。

2.2 適應(yīng)度定義和選擇策略

選擇的目的就是實現(xiàn)適者生存，高質(zhì)量的親本遺傳給下一代。

在本FJSP模型中，目標函數(shù)是尋求最大的完工時間的最小值，為了概率篩選，令fit=1/makespan，其中fit為適應(yīng)度，makespan為最大完工時間。makespan是根據(jù)Y染色體中選擇的加工設(shè)備而定的。Y染色體為{1,1,2,3,2,1,1,1,1,1,2,3,1,1,1,1}，依照T{i，j}對應(yīng)的時間，得TY={2,3,3,3,2,2,3,6,4,5,4,2,2,3,1,2}。

假設(shè)n=4，ni=4，定義z來表示工件i的第j道工序，當z=1是表示工件1的第1道工序，z=2表示工件2的第1道工序，z=5表示工件1的第2道工序，以此類推。當z取值遍歷[1,16]后makespan的取值便得出，計算過程如下：

Tz=T{i,j}(z),z∈[1,16]

(10)

式(10)中：Tz為Y染色體在T{i,j}加工設(shè)備時間集中選取對應(yīng)加工時間。

Mz=M{i,j}(z),z∈[1,16]

(11)

式(11)中：Mz為根據(jù)X染色體選取M{i,j}加工設(shè)備集中的設(shè)備編號。

Ts=max[machtime(Mz),parttime(i)]

(12)

式(12)中：Ts為Mz和i中取最大值。

machtime(Mz)=Ts+Tz

(13)

式(13)中：machtime(Mz)為編號為Mz的設(shè)備加工第z道工序后經(jīng)歷的時間。

parttime(i)=Ts+Tz

(14)

式(14)中：parttime(i)為工件i加工完第z道工序后經(jīng)歷的時間。

makespan=max(machtime)

(15)

式(15)中：makespan為最大完工時間。

選擇采用輪盤賭選擇法(roulette wheel selection)，實現(xiàn)選擇公式Pi=fi/sumfi，其中n是種群大小，Pi是個體i被選擇概率，fi是個體適應(yīng)度值，即由各個適應(yīng)度的值在總體適應(yīng)度的比率確定。

2.3 交叉

交叉是選擇兩個親本個體，在兩個親本上選擇相同長度的染色體片段進行替換，最后重建新一代個體。根據(jù)FJSP的特點，設(shè)計了3種交叉機制，即單段交叉、兩段交叉和三段交叉，可提高遺傳算法的全局搜索能力，提高種群質(zhì)量，實現(xiàn)種群進化。

圖2 3種交叉機制圖Fig.2 Three cross mechanism diagrams

2.4 變異

變異操作也是關(guān)鍵的一步。其既可以使遺傳算法具有局部搜索能力，也可以保持群體多樣性，以防止不成熟得收斂。為了使變異操作過程具有方向性和目的性，引入了種群分割的概念[10]，基于種群分割的思想實行兩種不同的變異機制，以此來實現(xiàn)更加有效的變異操作。根據(jù)適應(yīng)度函數(shù)計算種群各個染色體的適應(yīng)度值并取種群適應(yīng)度平均值，將高于平均值的染色體定義為優(yōu)質(zhì)染色體，賦予變異概率Pm1，實行兩點變異機制，如圖3(a)所示；將低于平均值的染色體定義為劣質(zhì)染色體，賦予變異概率Pm2，實行翻轉(zhuǎn)變異機制，如圖3(b)所示。種群分割可以有效地避免無意義的變異，提高了遺傳算法的局部尋優(yōu)能力。

圖3 兩種變異機制圖Fig.3 Two variant mechanism dia

2.5 檢查

遺傳算法的過程中本無此操作，但由于編碼的特殊性，會在交叉和變異的流程中出現(xiàn)不可行解，如圖4中子代染色體Xnew1、Ynew1、Xnew2、Ynew2由于工序重復(fù)導(dǎo)致該染色體不能繼續(xù)遺傳給下一代并且必須被淘汰，這樣通過檢查程序的篩選，確保最終得到的最優(yōu)解符合遺傳規(guī)則，是可行的。

圖4 兩個父代XY交叉圖Fig.4 Two parent XY cross graphs

2.6 終止條件

通過數(shù)代后的求解，當群體中最佳適應(yīng)度滿足要求，或者不再上升，即式(1)取得最小值，再或者迭代次數(shù)到達了預(yù)先設(shè)置的值時，算法停止運行。

3 應(yīng)用案例分析

現(xiàn)對一個n=6，m=10，ni=6的FJSP進行仿真。接下來是M{i，j}和T{i，j}，如表4、表5所示。

表4 M{i，j}加工設(shè)備集Table 4 M{i，j} processing equipment collection

表5 T{i，j}加工設(shè)備時間集Table 5 T{i，j} processing equipment time

遺傳算法中的運行參數(shù)為：種群大小NP=40，最大進化代數(shù)maxgen=200，交叉概率Pc=0.8，變異概率Pm1=0.2，Pm2=0.6，代溝Gap=0.9。

基于以上技術(shù)及參數(shù)，現(xiàn)用MATLAB R2018a進行模擬仿真，結(jié)果如圖5所示。圖5中，縱坐標是加工設(shè)備編號，橫坐標是加工時間，J[i，j]為工件i的第j道工序。

圖5 調(diào)度甘特圖Fig.5 Scheduling Gantt chart

經(jīng)過混合改進遺傳算法優(yōu)化之后，與傳統(tǒng)遺傳算法方式進行對比，在收斂速度方面有著明顯的改善，對比結(jié)果如圖6所示。

圖6 求解收斂圖Fig.6 Solving convergence

4 結(jié)論

基于JSP模型，建立了FJSP的數(shù)學(xué)模型，并采用混合改進的遺傳算法對模型求解優(yōu)化。由于FJSP本身的相對復(fù)雜性，提出了一種新的編碼思想用于雙層染色體編碼，得到了優(yōu)質(zhì)的初始種群；算法交叉過程中只用了3種不同的交叉機制，增強了交叉流程的有效性；變異操作引進了種群分割的思想，根據(jù)不同的變異概率選擇不同的變異機制；但兩層編碼結(jié)構(gòu)具有一定的特殊性，可能導(dǎo)致交叉變異之后出現(xiàn)不可行解，因此新添加檢查操作，對交叉和變異之后的不可行解進行排除以確保種群生存能力。最后測試應(yīng)用實例結(jié)果表明該算法不僅是正確有效的，而且明顯提高了收斂速度，加強了最優(yōu)解的正確性。