改進(jìn)遺傳算法在車(chē)間調(diào)度問(wèn)題中的應(yīng)用

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

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

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

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

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

(1)

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

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

(2)

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

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

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ù)和機(jī)器數(shù)，為最大變量值。

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

(4)

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

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

Sih+xihkPihk=Cih

(5)

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

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

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

2.1 算法流程

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

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

2.2 種群初始化

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

2.3 解碼操作

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

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

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

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

2.4 適應(yīng)度計(jì)算

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

2.5 選擇操作

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

2.6 交叉操作

引入隨機(jī)算子提出一種單點(diǎn)交叉加隨機(jī)打亂的方式，以減小子代染色體對(duì)父代的依賴(lài)，擴(kuò)大種群的多樣性，步驟為

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

圖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)，用各個(gè)工件的實(shí)際工序數(shù)減去后半段各工序出現(xiàn)的次數(shù)，得到交叉點(diǎn)前合法的工序數(shù)并按順序填入。

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

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

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

2.7 變異操作

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

3 實(shí)例驗(yàn)證

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

表2 8×8 P-FJSP問(wèn)題算例Table 2 An example of 8×8P-FJSP

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

圖6 平均值對(duì)比Fig.6 Comparison of average values

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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