基于改進遺傳算法的多目標柔性作業(yè)調度研究＊

李長云 谷鵬飛 林 多

（①智能信息感知及處理技術湖南省重點實驗室，湖南 株洲 412000；②湖南工業(yè)大學軌道交通學院，湖南 株洲 412000）

近年來，在“中國制造2025”的背景下，智能化、信息化和現代化制造已經成為企業(yè)發(fā)展的重要趨勢。如何使用科學且合理的生產調度方案來充分利用現有資源、如何合理組織生產過程來提高生產效率成為了企業(yè)關注的熱點問題。然而，車間調度的不確定性和多約束性使得這一問題變得更加復雜，但它也更加符合實際的生產需求。

隨著智能工業(yè)生產引起了越來越多的人的關注，國內外在柔性作業(yè)車間調度問題（flexible job-shop scheduling problem，FJSP）上也進行了多方面的研究，并且取得了一些成果。如：Luo R[1]等提出了一種改進的螢火蟲算法（FA），用于數據驅動的工作車間調度系統中的特征選擇優(yōu)化調度。Liang X[2]等使用混合量子粒子群優(yōu)化（QPSO）算法來解決靈活的作業(yè)車間。Jiang X[3]等提出了一種改進的PSO算法，基于前人利用隨機規(guī)劃知識建立的多目標隨機調度模型，來優(yōu)化RBF神經網絡（IPSORBF）的函數逼近。Chen W[4]等建立了模糊FJSP的數學模型，提出了一種基于局部優(yōu)化策略和改進優(yōu)化旋轉角度的混合量子算法。Wu P J[5]等建立了水處理方案的數學模型，結合車間的實際需求，設計了一種DLNN和遺傳算法相結合的綜合調度算法。桂林[6]等在現有的鄰域結構的基礎上進行拓展提出一種新型鄰域結構。梁迪[7]等改進了狼群優(yōu)化算法，并將其應用在了雙車間調度問題上。陳魁[8]等提出了一種小生境粒子群優(yōu)化算法。宋昌興[9]等改進了多目標遺傳算法。裴小兵[10]等提出了一種混合進化算法來解決流水車間調度問題。Phu-ang A[11]等提出了一種利用模糊選擇機制的微分演化（DE）算法來解決靈活的工作車間調度問題（FJSP）。Khan B[12]等擴展了i-NSGA-III算法，以解決具有多個目標的制造工作車間調度問題。從國內外對于FJSP的相關研究現狀來看，存在著如下幾個問題：（1）使用的優(yōu)化算法的尋優(yōu)能力一般，主要是算法的反應時間太長，且容易進入局部最優(yōu)解。（2）優(yōu)化的目標過于單一，優(yōu)化目標往往只考慮了最大完工時間，沒有反應車間的實際生產情況。因此，針對車間生產過程中由于加工機器的加工時間分配不均導致的機器負載過大或者機器閑置等問題，本文提出了一種基于均衡化加工機器使用率的改進遺傳算法，用來提高算法的搜索能力和穩(wěn)定性。

1 柔性作業(yè)車間調度問題

1.1 柔性作業(yè)車間調度問題的描述

FJSP可以描述為有n個待加工工件（O1，O2，···，On）需要在m臺機器上進行加工，每個工件需要經過Oij（Oij≥1）道工序，每道工序可以在任意一臺機器上完成加工，同一道工序在選擇不同的機器進行加工時，所需要的時間不同，所以在開始加工之前，需要確定每個工件的加工步驟以及各加工機器和工序加工的時間，因為在選擇不同機器加工時，所有工序所需的處理時間不同，因此大大提高了調度的靈活性和復雜性。

本文提出的柔性車間調度問題是一個多目標靜態(tài)靈活車間調度問題，不考慮機器突然故障、工人臨時休假、訂單突然取消、緊急工件插入以及忽略工序加工之間的轉移時間。在以最小化最大完工時間為主要優(yōu)化目標的條件下，均衡化各加工機器的利用率。最大完成時間是指在所有機器中完成時間最晚的機器的完成時間。

1.2 數學模型

數學模型中涉及到的參數如表1。

表1 模型參數表

對FJSP做以下假設：

（1）同一個工件中，相鄰工序之間存在加工順序約束，即后一道工序必須在前一道工序完成之后才能進行加工。

式中：Cij、Bi(j+1)分別代表工序Oij的加工完工時間和Oi(j+1)的加工開始時間。

（2）各道工序在同一時刻只能在一臺機器上進行加工。

如果在某一時刻，Wijk=1，則不能同時出現另一個工序Ouv使得Wuvk=1。

（3）任意工序一旦在某臺機器上開始加工，則加工過程不能中斷。

（4）每臺機器在一段時間內只能加工一道工序。

式中：A為一個較大的正數。

（5）各個工件在零時刻均可開始加工。

目標函數說明：

（1）最小化最大完工時間f1。

（2）均衡化機器利用率f2（各機器運行時間大致相同）。

式中：采用了標準差來計算各機器的使用時間，標準差越小，則代表各機器相應的運行時間就相差越小，因此求均衡化機器利用率等同于求解最小標準差。

綜合目標評價函數f為

式中：Ω為隨機給定數字，滿足0<Ω<1。

2 改進遺傳算法的實現

遺傳算法（GA）是一種通用的啟發(fā)式搜索算法。它是基于自然進化的自然選擇和突變。在運用遺傳算法進行FJSP求解時，先對種群進行初始化操作，種群中的每個個體都代表一種調度方案。以設定的目標函數為標準，通過選擇、交叉、變異過程，更新種群的適應度，然后經過多次迭代，最終找到一個可行解。

2.1 算法流程

算法流程圖如圖1所示，首先初始化種群，對加工工件OS以及機器MS進行整數編碼，將工件的工序、加工時間和機器數等信息存儲在染色體中，然后對隨機生成的種群進行解碼，計算個體的適應度，結合輪盤賭選擇和精英保留策略，將優(yōu)秀的個體保留下來，再進行交叉和變異操作，最后判斷是否達到迭代次數，將最優(yōu)個體輸出。

圖1 FJSP算法流程圖

具體步驟如下：

步驟一：設置參數、編碼，隨機生成一組初始種群。

步驟二：解碼、計算種群的適應度值。

步驟三：采取精英保留策略，保留父代中的優(yōu)秀染色體，然后使用輪盤賭選擇算子進行選擇操作，挑選優(yōu)秀染色體。

步驟四：交叉操作，根據交叉概率，讓父代染色體兩兩配對，采用POX交叉算子，得到子代染色體，提高種群多樣性。

步驟五：變異操作，根據變異概率，使用基于鄰域的變異算子。

步驟六：繼續(xù)執(zhí)行步驟二，直到迭代次數達到預定值，然后將種群中的最優(yōu)個體輸出。

2.2 種群初始化

編碼方式采用單鏈整數編碼，分別是基于工件OS和機器MS的編碼，將編碼分為3部分，第一部分的編碼為工件，第二部分的編碼為對應工件的加工機器，根據加工工件和加工機器，在第三部分編碼上自動生成工件在對應機器上加工的時間，例如，對于一個包含3個工件的FJSP問題，如圖2所示，第一部分工件加工順序為13233121，編碼中出現的第4個數字是3，它是出現的第二個3，所以它代表第三個工件的第二道工序；第二部分加工機器的編碼為23312132，這一段編碼中第7個數字是3，它代表第二個工件的第二道工序在第三臺機器上加工。編碼的最后一部分為加工時間，它在加工工件和加工機器生成后產生。根據種群大小隨機生成工序碼和機器碼。

圖2 染色體編碼

2.3 解碼及適應度計算

解碼過程等同于編碼的逆過程，同時遍歷編碼的3個部分，即可得到加工信息。本文求解的是多目標FJSP，基于上文的綜合目標評價函數f，使用一個權重系數Ω將多目標問題轉化為單目標問題。

式（9）為式（8）的變形，適應度函數應該與優(yōu)化方向相同，然而最小化最大完工時間及均衡化機器使用率均與優(yōu)化方向相反，因此將之前所得的目標函數做倒數運算得到新的目標函數f。

2.4 選擇操作

選擇操作是選取具有高適應度的個體，如果選擇操作符設計有問題的話，具有較大適應度值的個體就會使種群的進化方向單一，進而使種群丟失多樣性，本文將遺傳算法中的精英保留策略和輪盤賭相結合，使用輪盤賭挑選優(yōu)質的染色體，適應度越高的染色體在種群中的適應度的占比就越高，如果種群的數量為n，個體的適應度值為fi，則個體的選擇概率為Pi。

通過目標函數約束，得到最優(yōu)解，同時采取精英保留策略，將父代種群中優(yōu)秀的染色體放到子代種群中，不參與后面的交叉、變異操作，直到有更優(yōu)的個體替換它，采用這種選擇方式可避免優(yōu)質解的丟失，加快種群的收斂[13]。

2.5 交叉操作

在遺傳算法中，交叉是一個重要的操作，使用交叉算子能夠將父代的優(yōu)秀基因遺傳給子代，本文使用了一種POX交叉算子對工件編碼進行交叉操作，使種群的多樣性更加豐富，步驟為：

（1）步驟一。隨機取出兩條染色體，分別作為父代F1和父代F2，然后建立兩個空子集J1和J2，隨機分配工件集｛1, 2, 3, ···,n｝到J1和J2中。

（2）步驟二。將父代F2包含在J1的工件復制到子代C2中，父代F1包含在J1的工件復制到子代C1中，保留它們的位置。

（3）步驟三。將父代F1包含在J2的工件復制到子代C1中，父代F2包含在J2的工件復制到子代C1中，保留它們的順序。

本文以4個工件為例，圖3表示了兩條染色體F1和F2的交叉操作，父代F1和F2交叉生成了子代C1和C2，其中C1的染色體基因為[3 1 2 4 3 2 1 2 4 1 3 4],C2的染色體基因為[2 3 3 2 4 1 4 1 2 4 1 3]，從圖3可以看出C1的染色體基因保留了F1中工件號為｛1，2｝和F2中工件號為｛3，4｝的次序，C2的染色體基因保留了F2中工件號為｛1，2｝和F1中工件號為｛3，4｝的次序，使子代能夠繼承父代的優(yōu)良特征。

圖3 POX交叉操作

2.6 變異操作

本文設計了一種改進的變異方法，針對工件編碼采用基于鄰域搜索的變異算子，它不會破壞種群的多樣性，還能夠提高子代的適應度，使其向更優(yōu)的方向進化，針對機器編碼采用單點變異法，替換可選機器。鄰域搜索如圖4所示，單點變異法的操作如圖5所示。

圖4 基于領域搜索的變異操作

圖5 單點變異操作

具體步驟如下：

（1）步驟一：首先隨機選取種群規(guī)模乘上變異概率數量的子代個體。

（2）步驟二：取變異染色體上幾個不同的基因，生成其排列的所有鄰域，本文選取了3個不同位置的基因，進行鄰域變換。

（3）步驟三：評價所有鄰域的適應度值，找到最優(yōu)的基因，然后讓它取代原染色體基因。

3 仿真實驗及分析

為了驗證所提的改進GA算法在解決FJSP上的性能，本文選取kacem測試集[14]中的10×10FJSP，其中改進GA算法是在MATLAB語言上進行編寫并調試，仿真實驗是在計算機內存為4 GB，處理器為Intel(R) Core (TM) i5 4 200H，主頻 2. 8 GHz、運行環(huán)境為Windows 10的個人計算機進行。實驗參數設置如表2所示。

表2 實驗參數

選擇10×10的kacem算例，詳細信息見表3。使用改進遺傳算法和標準遺傳算法以及帝王蝶優(yōu)化算法（monarch mutterfly optimization，MBO）各進行仿真實驗100次，以5次為1組取它們的平均值，得到平均值對比圖如圖6所示，通過圖6可以直觀地看出，在進行組內實驗時，改進遺傳算法相對其他優(yōu)化算法更容易接近全局最優(yōu)解。利用改進遺傳算法進行仿真實驗得到了FJSP甘特圖如圖7所示。

圖6 平均值對比

圖7 10×10FJSP甘特圖

表3 10×10FJSP工件加工時間

基于最大完工時間以及均衡化機器利用率的各優(yōu)化算法收斂曲線如圖8所示，實線表示改進GA算法，點劃線表示蝴蝶優(yōu)化算法(MBO)，虛線表示GA算法，從收斂曲線上可以發(fā)現隨著迭代次數的增加，改進GA算法在求解目標函數值的優(yōu)化效果上明顯優(yōu)于其他兩種算法，且相對于GA算法，改進GA算法收斂速度更快。

圖8 收斂曲線比較圖

4 結語

本文基于均衡化機器利用率以及最小化最大完工時間的多目標FJSP設計了一種改進遺傳算法，對多目標進行優(yōu)化求解，并通過在Kacem數據集上與其他優(yōu)化算法進行對比，實驗結果驗證了改進遺傳算法在求解多目標FJSP上具有更高的尋優(yōu)效率和有效性。最后得到的實驗結論如下。

（1）在進行染色體編碼時，采用了單鏈整數編碼，將工件號、機器號以及加工時間都放在一條染色體上，可以快速地計算適應度，提高了算法的求解效率。

（2）用標準差來表示均衡化加工機器的利用率，不僅符合了車間生產的實際情況，也提高了計算的精確度。

（3）采用了POX交叉算子和多點交叉法對工件編碼及機器編碼進行交叉操作，采用了基于鄰域搜索的變異算子，避免算法過早地陷入局部最優(yōu)解，從而擴大了尋優(yōu)范圍，增強了尋優(yōu)能力。