楊 帆，方成剛，洪榮晶，吳偉偉

(1.南京工業(yè)大學(xué) 機械與動力工程學(xué)院，江蘇 南京 211800；2.揚州大學(xué) 機械工程學(xué)院，江蘇 揚州 225000)

調(diào)度是指在合理的時間內(nèi)將有限的資源進行分配，以滿足一個或多個優(yōu)化目標(biāo)的過程。車間調(diào)度是整個先進生產(chǎn)制造系統(tǒng)的核心，其中作業(yè)車間調(diào)度問題(JSP)作為生產(chǎn)過程中的關(guān)鍵模塊是典型的調(diào)度問題之一[1-2]。在作業(yè)車間中，加工系統(tǒng)中有m個功能各不相同的機床、n個加工路線不同的工件，各工件的每道工序按照其工藝路線對應(yīng)1臺機器進行加工。柔性作業(yè)車間調(diào)度問題(FJSP)與JSP相比,每道工序可選擇不同機床進行加工，已被證實是復(fù)雜的NP-Hard問題[3]。

柔性作業(yè)車間調(diào)度作為智能制造的核心技術(shù)，對其深入研究具有重大的理論意義和實際價值。目前對于FJSP的研究集中在各種智能算法，例如遺傳算法、粒子群算法、模擬退火算法等。王雷等[4]應(yīng)用遺傳算法解決了一種考慮AGV運輸時間的柔性作業(yè)車間調(diào)度問題。陳明等[5]將粒子群算法應(yīng)用在一個多目標(biāo)柔性作業(yè)車間調(diào)度模型并成功得到一組 Pareto 解集。黃海松等[6]提出了一種基于改進模擬退火算法的調(diào)度策略。

遺傳算法(GA)相比其他算法具有魯棒性強、搜索能力強等特點，在FJSP這類大規(guī)模收斂問題中得到了廣泛應(yīng)用。但FJSP問題是典型的NP-Hard問題，在使用傳統(tǒng)遺傳算法對其求解時，往往不能得到滿意的結(jié)果，并且FJSP包括機器選擇和工序排序兩個子問題。在進行遺傳操作時，目前需要對其分別進行操作，這使得在編寫算法時工作量較大。

交叉操作是遺傳算法中的重要環(huán)節(jié)，對其進行改進有重要理論價值和實際意義，目前應(yīng)用在FJSP問題中的交叉操作主要有部分映射交叉、次序交叉、循環(huán)交叉、基于位置的交叉等方式[1]，但以上傳統(tǒng)交叉方式對父代染色體依賴較強，造成算法的尋優(yōu)能力較弱，往往得不到理想解。趙詩奎等[7]采用雙鏈編碼，使用基于工件的機器交叉和兩點混合交叉的方式提出一種新型初始機制的遺傳算法解決了FJSP問題。吳秀麗等[8]采用基于工序的編碼方式，在解碼時引入機器順序矩陣和時間矩陣，選擇線性次序交叉方式解決了柔性作業(yè)車間多目標(biāo)調(diào)度優(yōu)化問題。不論是采用雙鏈編碼，或加入機器、時間矩陣，這都大大增加了編程的工作量。針對以上問題，筆者采用基于工序的單鏈編碼，以最大完工時間最小為目標(biāo)，提出一種基于元胞數(shù)組的解碼方式和一種新的單點交叉操作。

1 部分柔性作業(yè)車間調(diào)度的基本描述

1.1 問題描述

部分柔性作業(yè)車間調(diào)度問題(P-FJSP)描述為：車間內(nèi)有機器m臺，待加工工件n個，每個工件包含一道或多道工序，至少有一道工序可選擇車間內(nèi)多臺機器加工且至少有一道工序不能選擇所有機器進行加工。P-FJSP要解決的問題是為每道工序選擇加工機器并且確定每臺機器上各工序加工的先后順序，具體事例如表1所示。

表1 P-FJSP舉例Table 1 An example of P-FJSP

表1中Ji表示工件號，Oi，j表示工件i的第j道工序，Qi表示機器號。表中數(shù)字表示此工序在對應(yīng)機器上的加工時間(本文加工時間默認為min)，符號“—”表示該工序不能在表中對應(yīng)機器上加工。例如表1中，工件J1的第2道工序O1，2在Q1和Q2上的加工時間分別為15和8 min，但不能在Q3上加工。

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

定義符號n為工件總數(shù)、m為加工機器總數(shù)，li為工件i的工序數(shù)，P-FJSP可表示為

(1)

式(1)為基于完工時間的目標(biāo)函數(shù)，f是最大完工時間最小性能指標(biāo)，其中Ci代表工件的加工完成時間。

s.t.Cih≤Si(h+1)

(2)

式中：i=1，2，…，n;h=1，2，…，li。

式(2)表示工藝約束，其中Cih為工件i的第h道工序的加工結(jié)束時間，Sih為工件i的第h道工序的加工開始時間。

Cjhk-Cigk+A(1-yijk)≥Pjhk

(3)

式中：i，j=1，2，…，n;h=1，2，…，lj;g=1，2，…，li;k=1，2，…，m；n、m分別代表工件數(shù)和機器數(shù)，為最大變量值。

式(3)是工序唯一性約束，表示某臺機器在同一時刻只能加工一道工序，其中Cjhk、Cigk分別為工件j的第h道工序和工件i的第g道工序在機器k上的加工完成時間，Pjhk為工件j的第h道工序在機器k上的加工時間，A為一個足夠大的正數(shù)。

(4)

式中i=1，2，…，n;h=1，2，…，li。

式(4)是機器唯一性約束，表示某道工序在同一時刻只能被一臺機器加工，其中mih為工件i的第h道工序可選的機器集。

Sih+xihkPihk=Cih

(5)

式中：i=1，2，…，n;h=1，2，…，li;k=1，2，…，m。

式(5)表示某道工序在加工過程中不可中斷。

2 改進遺傳算法設(shè)計

2.1 算法流程

本節(jié)的設(shè)計過程均以表1中實例為對象。算法流程圖如圖1所示，利用元胞數(shù)組儲存各工件的工序、加工時間、可選機器等信息，并引入隨機算子進行解碼，在遺傳操作中加入保優(yōu)策略并引入新的交叉方式，算法的終止條件為是否達到迭代次數(shù)。

圖1 P-FJSP求解算法流程Fig.1 Algorithm solving process of P-FJSP

2.2 種群初始化

編碼采用基于工序的單鏈編碼，編號鏈代表遺傳算法中操作的染色體。以工件號表示的工序碼代表遺傳算法中操作的基因位，工件號出現(xiàn)的次數(shù)代表該工件包含的工序數(shù)，同工件出現(xiàn)的順序表示工序順序。以編碼122313312為例，第三個基因位的‘2’表示工件2的第2道工序。

2.3 解碼操作

針對元胞數(shù)組的P-FJSP解碼過程為

1)步驟一。按順序取出染色體中的基因乘10，按照上述種群初始化規(guī)則加上工序號，將其儲存在一行向量P中，如132113223中的第4個基因處理完后為12，在后續(xù)操作中對其分別進行取整和取余操作即可得到工件號和工序號；

2)步驟二。引入隨機算子在元胞數(shù)組中隨機取出對應(yīng)工序的某個加工機器，存入一行向量M中，并將此工序的隨機算子保存；

3)步驟三。取出步驟二中加工機器的對應(yīng)加工時間，存入行向量T中。

2.4 適應(yīng)度計算

根據(jù)約束條件將上述各機器上的工序進行排列，計算出最長加工時間,即為該條染色體的目標(biāo)函數(shù)值，根據(jù)目標(biāo)函數(shù)可知,種群中目標(biāo)函數(shù)值越小，該條染色體質(zhì)量越高。

2.5 選擇操作

利用輪盤賭規(guī)則對種群中的各條染色體進行選擇，目標(biāo)函數(shù)值越小的被選擇的概率越大。引入精英保留策略，將父代種群中最優(yōu)的染色體直接放到子代種群中，并且不參與接下來的交叉、選擇操作，直到有更優(yōu)的個體替換它。采用此種選擇方式可避免優(yōu)質(zhì)解的丟失，加快種群的收斂。

2.6 交叉操作

引入隨機算子提出一種單點交叉加隨機打亂的方式，以減小子代染色體對父代的依賴，擴大種群的多樣性，步驟為

1)步驟一。取出相鄰的兩條染色體A和B，隨機生成交叉點。

圖2 交叉操作步驟一Fig.2 First step of the cross operation

2)步驟二。交換A、B后半段染色體得到C、D。

圖3 交叉操作步驟二Fig.3 Second step of the cross operation

3)步驟三。為避免不合法的染色體出現(xiàn)，用各個工件的實際工序數(shù)減去后半段各工序出現(xiàn)的次數(shù)，得到交叉點前合法的工序數(shù)并按順序填入。

圖4 交叉操作步驟三Fig.4 Third step of the cross operation

4)步驟四。為增加種群多樣性隨機打亂交叉點前部分染色體順序，得到交叉后的染色體新A、新B。

圖5 交叉操作步驟四Fig.5 Fourth step of the cross operation

2.7 變異操作

為了避免非法染色體的產(chǎn)生，變異操作采用同一染色體的兩個基因交換的方式，即隨機在染色體上選擇兩個基因位，判斷這兩個基因位上的基因是否相等，若相等則重新選擇，若不相等則直接交換。

3 實例驗證

為驗證所提出的改進遺傳算法在P-FJSP中的有效性和優(yōu)越性，利用傳統(tǒng)單點交叉方式和改進方式對具體算例進行對比驗證。用Matlab編程實現(xiàn)，計算機內(nèi)存8 GB，處理器為Intel(R) Core(TM)i5-8250U，主頻1.6 GHz。算例采用高亮等[9]在著作中提出的8×8部分柔性作業(yè)車間調(diào)度問題算例，結(jié)果見表2。遺傳算法中種群規(guī)模設(shè)置為40、交叉概率Pc為0.7、變異概率Pm=0.1，最大遺傳代數(shù)根據(jù)文獻[10]提出的規(guī)則設(shè)置為100。

表2 8×8 P-FJSP問題算例Table 2 An example of 8×8P-FJSP

對比實驗中，每種算法各運行100次，按順序每10次為一組數(shù)據(jù)進行平均值對比，最后得到10組對比數(shù)據(jù)，實驗結(jié)果如表3和圖6。

圖6 平均值對比Fig.6 Comparison of average values

表3 各對比組內(nèi)實驗結(jié)果及平均值Table 3 Experimental results and mean values in each control group min

利用改進遺傳算法仿真實驗得到種群收斂圖及調(diào)度甘特圖如圖7和8所示。

圖7 種群收斂圖Fig.7 Graph of population convergence

圖8 調(diào)度甘特圖Fig.8 Gantt chart of the scheduling

以上仿真對比試驗正確得出了調(diào)度甘特圖，并且每一組數(shù)據(jù)中的改進交叉操作遺傳算法的平均目標(biāo)函數(shù)值都優(yōu)于傳統(tǒng)算法的平均目標(biāo)函數(shù)值，證實了改進算法的有效性并具有更好的尋優(yōu)能力。

4 結(jié)語

1)通過引入元胞數(shù)組進行解碼操作，避免了傳統(tǒng)矩陣解碼需引入大量0元素的操作，簡化了遺傳算法在求解P-FJSP問題時的解碼操作。

2)在遺傳算法求解P-FJSP問題的的交叉操作步驟中加入隨機算子，為機器選擇提供了多樣性，從而擴大了尋優(yōu)范圍，增強了尋優(yōu)能力。

3)選擇步驟中引入保優(yōu)策略，使得優(yōu)質(zhì)解在迭代中得以保存，使得算法在大范圍尋優(yōu)過程中能夠保證快速收斂。