基于改進(jìn)遺傳算法的多目標(biāo)柔性作業(yè)調(diào)度研究＊

李長(zhǎng)云 谷鵬飛 林 多

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

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

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

1 柔性作業(yè)車(chē)間調(diào)度問(wèn)題

1.1 柔性作業(yè)車(chē)間調(diào)度問(wèn)題的描述

FJSP可以描述為有n個(gè)待加工工件（O1，O2，···，On）需要在m臺(tái)機(jī)器上進(jìn)行加工，每個(gè)工件需要經(jīng)過(guò)Oij（Oij≥1）道工序，每道工序可以在任意一臺(tái)機(jī)器上完成加工，同一道工序在選擇不同的機(jī)器進(jìn)行加工時(shí)，所需要的時(shí)間不同，所以在開(kāi)始加工之前，需要確定每個(gè)工件的加工步驟以及各加工機(jī)器和工序加工的時(shí)間，因?yàn)樵谶x擇不同機(jī)器加工時(shí)，所有工序所需的處理時(shí)間不同，因此大大提高了調(diào)度的靈活性和復(fù)雜性。

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

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

數(shù)學(xué)模型中涉及到的參數(shù)如表1。

表1 模型參數(shù)表

對(duì)FJSP做以下假設(shè)：

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

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

（2）各道工序在同一時(shí)刻只能在一臺(tái)機(jī)器上進(jìn)行加工。

如果在某一時(shí)刻，Wijk=1，則不能同時(shí)出現(xiàn)另一個(gè)工序Ouv使得Wuvk=1。

（3）任意工序一旦在某臺(tái)機(jī)器上開(kāi)始加工，則加工過(guò)程不能中斷。

（4）每臺(tái)機(jī)器在一段時(shí)間內(nèi)只能加工一道工序。

式中：A為一個(gè)較大的正數(shù)。

（5）各個(gè)工件在零時(shí)刻均可開(kāi)始加工。

目標(biāo)函數(shù)說(shuō)明：

（1）最小化最大完工時(shí)間f1。

（2）均衡化機(jī)器利用率f2（各機(jī)器運(yùn)行時(shí)間大致相同）。

式中：采用了標(biāo)準(zhǔn)差來(lái)計(jì)算各機(jī)器的使用時(shí)間，標(biāo)準(zhǔn)差越小，則代表各機(jī)器相應(yīng)的運(yùn)行時(shí)間就相差越小，因此求均衡化機(jī)器利用率等同于求解最小標(biāo)準(zhǔn)差。

綜合目標(biāo)評(píng)價(jià)函數(shù)f為

式中：Ω為隨機(jī)給定數(shù)字，滿(mǎn)足0<Ω<1。

2 改進(jìn)遺傳算法的實(shí)現(xiàn)

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

2.1 算法流程

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

圖1 FJSP算法流程圖

具體步驟如下：

步驟一：設(shè)置參數(shù)、編碼，隨機(jī)生成一組初始種群。

步驟二：解碼、計(jì)算種群的適應(yīng)度值。

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

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

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

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

2.2 種群初始化

編碼方式采用單鏈整數(shù)編碼，分別是基于工件OS和機(jī)器MS的編碼，將編碼分為3部分，第一部分的編碼為工件，第二部分的編碼為對(duì)應(yīng)工件的加工機(jī)器，根據(jù)加工工件和加工機(jī)器，在第三部分編碼上自動(dòng)生成工件在對(duì)應(yīng)機(jī)器上加工的時(shí)間，例如，對(duì)于一個(gè)包含3個(gè)工件的FJSP問(wèn)題，如圖2所示，第一部分工件加工順序?yàn)?3233121，編碼中出現(xiàn)的第4個(gè)數(shù)字是3，它是出現(xiàn)的第二個(gè)3，所以它代表第三個(gè)工件的第二道工序；第二部分加工機(jī)器的編碼為23312132，這一段編碼中第7個(gè)數(shù)字是3，它代表第二個(gè)工件的第二道工序在第三臺(tái)機(jī)器上加工。編碼的最后一部分為加工時(shí)間，它在加工工件和加工機(jī)器生成后產(chǎn)生。根據(jù)種群大小隨機(jī)生成工序碼和機(jī)器碼。

圖2 染色體編碼

2.3 解碼及適應(yīng)度計(jì)算

解碼過(guò)程等同于編碼的逆過(guò)程，同時(shí)遍歷編碼的3個(gè)部分，即可得到加工信息。本文求解的是多目標(biāo)FJSP，基于上文的綜合目標(biāo)評(píng)價(jià)函數(shù)f，使用一個(gè)權(quán)重系數(shù)Ω將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題。

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

2.4 選擇操作

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

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

2.5 交叉操作

在遺傳算法中，交叉是一個(gè)重要的操作，使用交叉算子能夠?qū)⒏复膬?yōu)秀基因遺傳給子代，本文使用了一種POX交叉算子對(duì)工件編碼進(jìn)行交叉操作，使種群的多樣性更加豐富，步驟為：

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

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

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

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

圖3 POX交叉操作

2.6 變異操作

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

圖4 基于領(lǐng)域搜索的變異操作

圖5 單點(diǎn)變異操作

具體步驟如下：

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

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

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

3 仿真實(shí)驗(yàn)及分析

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

表2 實(shí)驗(yàn)參數(shù)

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

圖6 平均值對(duì)比

圖7 10×10FJSP甘特圖

表3 10×10FJSP工件加工時(shí)間

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

圖8 收斂曲線比較圖

4 結(jié)語(yǔ)

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

（1）在進(jìn)行染色體編碼時(shí)，采用了單鏈整數(shù)編碼，將工件號(hào)、機(jī)器號(hào)以及加工時(shí)間都放在一條染色體上，可以快速地計(jì)算適應(yīng)度，提高了算法的求解效率。

（2）用標(biāo)準(zhǔn)差來(lái)表示均衡化加工機(jī)器的利用率，不僅符合了車(chē)間生產(chǎn)的實(shí)際情況，也提高了計(jì)算的精確度。

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