一種求解柔性作業(yè)車間的改進遺傳算法

王玉芳，葛嘉榮，繆 昇，馬銘陽

(1.江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心， 南京 210044；2.南京信息工程大學(xué) 自動化學(xué)院， 南京 210044；3.江蘇省大數(shù)據(jù)分析技術(shù)重點實驗室， 南京 210044)

柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem，F(xiàn)JSP)是一種經(jīng)典車間調(diào)度問題，其作為傳統(tǒng)作業(yè)車間調(diào)度問題(job shop scheduling problem，JSP)的延伸，具有更廣泛的使用環(huán)境和更復(fù)雜的求解空間。超過3臺機器的JSP已被證明是NP問題[1]。因此，作為延伸問題的FJSP也具有NP困難。FJSP問題中包含2個子問題：機器選擇和工序排序問題。2個決策空間增加了求解難度。

多年來，如禁忌搜索[2]、遺傳算法[3]、粒子群算法[4]、人工蜂群算法[5]等的許多智能算法被用于解決車間調(diào)度問題。李明等[6]引入殖民同化和革命策略的新型帝國競爭算法在解決多目標FJSP中取得了高質(zhì)量的解；Zhang等[7]通過加強局部搜索彌補遺傳算法“易早熟”的缺陷；Maroua等[8]結(jié)合實際生產(chǎn)活動，提出了雙步粒子群算法，保持了算法的魯棒性；顧九春等[9]提出基于記憶池的離散個體更新方法，使多目標算法的適用性更強。但這些算法大多從算法本身或模型入手，未采取啟發(fā)式規(guī)則，難免造成算法性能冗余。另外，如何跳出局部最優(yōu)解一直都是求解FJSP的重點和難點，還存在很大的改進空間。針對上述問題，提出一種改進遺傳算法(new improved genetic algorithm，NIGA)求解FJSP。

1 問題描述

FJSP問題描述：工件集{J1，J2，…，Jn}中的n個工件要在機器集{M1，M2，…，Mm}中的總計m臺機器上進行加工，每個工件包含若干道工序，每道工序有若干臺機器可以選擇，工序的加工時間也因機器的選擇不同。

根據(jù)實際生產(chǎn)情況，F(xiàn)JSP問題需要滿足以下約束條件：

1) 每個工件的每道工序只能同時由1臺機器加工；

2) 同一機器在同一時間只能加工1個工件；

3) 工序一旦開始加工就不能停止；

4) 所有工件工序無優(yōu)先級配置；

5) 同一工件的工序具有先后約束，不同工件之間沒有先后約束。

為方便后續(xù)描述，進行符號定義，見表1。

表1 符號定義

目標函數(shù)分別為最大完成時間、總機器負載和最大機器負載。

Cmax=min{maxCi}

FJSP模型約束條件為：

Sij+Xijk×Tijk≤Cij

(1)

Ci(j-1)≤Sij

(2)

Cij≤Cmax

(3)

Sij+Tijk≤Sxy+H(1-Yijxyk)

(4)

Ci(j-1)≤Sij+H(1-Yijxyk)

(5)

(6)

Sij≥0，Cij≥0

(7)

式(1)和式(2)表示同一工件的工序必須按照順序逐步加工；式(3)表示任意工序的完工時間都不得超過最大完工時間；式(4)和式(5)表示任一時刻的任一機器只允許同時處理一道工序，其中H是一個很大的數(shù)；式(6)表示在某一時刻一道工序只能同時由1臺機器加工；式(7)表示任意工序的開始時間和完成時間均為非負，且任意工件都可以從0時刻開始加工。

2 算法設(shè)計

遺傳算法是由Holland[10]在1970年提出的一種基于自然選擇和遺傳學(xué)原理的智能算法。其通過模擬自然環(huán)境，對種群進行選擇、交叉和變異操作，得到下代種群，經(jīng)過若干代的進化獲得最終結(jié)果。因其魯棒性好、隱性并行性和全局搜索能力強等特點，被廣泛應(yīng)用于各領(lǐng)域。本文中根據(jù)FJSP模型和遺傳算法的特點，提出NIGA算法以求解FJSP問題。

2.1 編碼和解碼

考慮到FJSP的2個子問題——工序排列和機器選擇，采用并行雙鏈式進行編碼。第1層為基于工序的編碼層(operation sequence，OS)，第2層為基于機器選擇的編碼層(machine sequence，MS)。如圖1所示，OS層的數(shù)字表示工件號，出現(xiàn)的次數(shù)為當前工件的工序號；MS層按照工件工序順序排列，在本圖中的4表示3號工件的第1道工序在4號機器上加工。OS層和MS層的長度相等，均為PS。這種編碼方式保證了后續(xù)的交叉、變異和局部搜索等策略產(chǎn)生的解仍然是可行解，并對工件的工序長度和工件數(shù)量無任何要求，簡單靈活；另一方面，對一層的單獨操作不會影響到另一層，具有很強的并行性能。

圖1 編碼示意圖

解碼的主要目標是根據(jù)編碼層的形式獲得空間范圍內(nèi)優(yōu)質(zhì)的解。提出一種最優(yōu)插入法(optimal insertion method，OIM)，以實現(xiàn)染色體解碼對解空間的高效搜索。其步驟如下：

步驟1判斷是否為該工件的第一道工序，如果是第1道工序，空閑起點判斷為0；否則，空閑起點為該工件上一道工序的完工時間；

步驟2尋找空閑起點之后的空閑時間段，選擇其中大于等于待加工工序的加工時間的時間段。如果不存在滿足條件的插入空閑，則按順序正常加工；

步驟3選擇與待加工工序加工時間最接近的空閑插入；

步驟4重復(fù)步驟1～3，直到所有工序加工完成；

步驟5計算最大完成時間。

OIM插入過程如圖2所示。工序Oih將在機器Mb上加工，根據(jù)當前加工情況，有3段空閑可供選擇，空閑1、2、3均大于等于Oih的加工時間?？臻e1的起始時間大于工序Oi(h-1)的結(jié)束時間，不滿足約束條件；空閑2和空閑3都滿足插入條件，且空閑2的空閑時間更接近Oih的加工時間，因而選擇空閑2插入。相對于一般的貪婪插入方法，該策略能夠為后續(xù)工序的插入提供更多的空間，減少空閑時間從而獲取更優(yōu)質(zhì)的解。

2.2 初始化

遺傳算法中，種群初始化是關(guān)鍵的一步，初始解的質(zhì)量直接影響種群在整個搜索空間的分布程度及算法收斂速度。已有研究通常采用隨機初始化方法，使得解的質(zhì)量偏低，往往需要更多的迭代次數(shù)才能獲得更優(yōu)的種群質(zhì)量。本文中針對單目標及多目標問題分別設(shè)計不同的初始化方法。

圖2 OIM插入過程示意圖

2.2.1面向單目標的種群初始化

單目標部分采用文獻[11]的GLS初始化方法。該方法將MS編碼層初始化分為3部分：全局選擇(global selection，GS)、局部選擇(local selection，LS)和隨機選擇(random selection，RS)；OS編碼層采取完全隨機的方式產(chǎn)生。

2.2.2面向多目標的種群初始化

多目標部分對GLS方法進行改進，在MS編碼層初始化部分添加完全最小化(global load minimization，GLM)和部分最小化(local load minimization，LLM)，以加快最大負載機器負載的收斂速度，OS編碼層不變。GLM為所有工件的工序選擇候選機器負載最小的機器進行加工，LLM為部分工件的工序選擇候選機器負載最小的機器進行加工。

2.3 交叉操作

交叉的目的是經(jīng)過一系列操作之后產(chǎn)生新的個體，在盡量保持優(yōu)良基因的前提下高效地搜索解空間，因而交叉操作必須滿足可行性、繼承性、信息非冗余等特性。針對編碼方式和遺傳算法的特點，采用兩種交叉方式：針對OS層染色體的IPOX[12]交叉和針對MS層染色體的多點交叉。因IPOX交叉具有低約束和良好基因繼承等特性，用其完成OS層的交叉操作；MS層采取順序編碼方式，對交叉的要求較高，故而采用不破壞基因有效序列的多點交叉方式。

多點交叉步驟如下：

步驟1隨機選擇2個父代個體father1和father2；

步驟2隨機產(chǎn)生1組維度與MS染色體一致的0、1數(shù)組L；

步驟3子代個體child1繼承father1對應(yīng)L數(shù)組為1位置的基因，子代個體child2繼承father2對應(yīng)L數(shù)組為1位置的基因；

步驟4將father2中未選中的基因按順序插入到child1的空白位置，將father1中未選中的基因按順序插入到child2的空白位置。

2.4 多重變異操作

變異操作是指通過對染色體進行小幅度擾動形成新的個體，以維持種群多樣性，在一定程度上影響遺傳算法的局部搜索能力。常用的變異操作有互換、逆序、插入等，但用于FJSP問題都無法取得理想效果。在FJSP中，機器選擇往往比工序排列對結(jié)果影響更大，因此采用多種機器的多重變異策略——隨機機器和最小加工時間機器選擇，以維持種群多樣性。

多重變異偽代碼如下：

2.5 變鄰搜索策略

雖然引入基于MS染色體的變異操作在一定程度上能夠增加種群的多樣性，但OS染色體部分未做改進，算法仍然可能陷入局部最優(yōu)。針對這一問題，設(shè)計了針對OS編碼的變鄰搜索策略，該策略包括3種操作。

操作A：幾何排列出1段染色體的所有情況，其步驟如下：

步驟1隨機選擇1條OS染色體；

步驟2隨機從n個工件中選擇若干個工件；

此外，現(xiàn)場施工期間未見鋼拱架發(fā)生明顯變形現(xiàn)象，圍巖的承載能力和穩(wěn)定性顯著提高；采用全站儀對拱頂60°及拱底45°范圍內(nèi)的測點進行觀測，對比分析拱頂?shù)膰鷰r變形情況，發(fā)現(xiàn)圍巖變形量值不大，新增變形量不超過10 mm，收斂速度趨緩；在后續(xù)TBM掘進過程中，未出現(xiàn)明顯的涌水、塌方現(xiàn)象?？梢?，采用化學(xué)灌漿加固強蝕變巖洞段，對掌子面和護盾位置進行超前預(yù)注漿并及時封閉圍巖，并依據(jù)注漿模擬試驗成果對注漿及支護參數(shù)進行優(yōu)化，是一種有效的堵水和加固圍巖的實用方法。

步驟3從被選中的每個工件隨機選擇一道工序；

步驟4未被選中的OS染色體基因保持原位不動，對選中的部分進行枚舉排序，得到一組新的OS染色體；

步驟5對新得出的OS染色體組進行適應(yīng)度計算，如果存在適應(yīng)度大于原OS染色體的新個體，則替換原解；否則，不做任何操作。

操作B：將1段OS染色體隨機打亂順序。

操作C：隨機交換OS編碼層中2個位置的元素。

3種操作方法對OS編碼層的擾動程度逐漸降低，以應(yīng)對迭代過程中過度收斂的情況。在種群初期，采取擾動小的策略A，隨著迭代的進行，繼而采用B、C兩個策略以維持種群在后期的多樣性。

2.6 算法流程

根據(jù)上述改進策略，提出解決柔性作業(yè)車間問題的NIGA算法求解步驟：

步驟1根據(jù)2.2節(jié)中提出的規(guī)則進行種群初始化并設(shè)置相關(guān)參數(shù)；

步驟2通過OIM對種群進行適應(yīng)度計算；

步驟3通過錦標賽選出要進行后續(xù)操作的群體；

步驟4對被選中的群體的OS層進行IPOX交叉，MS層進行多點交叉；

步驟5對MS層進行2.4節(jié)中提出的多重變異操作；

步驟6對OS層進行2.5節(jié)中提出的局部搜索操作；

步驟7得到的新一代種群進行適應(yīng)度計算并根據(jù)適應(yīng)度降序排序，保存這一代的最優(yōu)個體；

步驟8循環(huán)終止判斷，如果滿足跳至步驟9；否則，跳轉(zhuǎn)至步驟3；

步驟9最優(yōu)解輸出，算法結(jié)束。

算法流程如圖3所示。

3 結(jié)果與分析

NIGA采用Matlab編程實現(xiàn)。程序在Windows 10系統(tǒng)，主頻為2.6 GHz、內(nèi)存為8 G的計算機上運行。各項參數(shù)設(shè)置：種群數(shù)量pop=2*n*m；交叉概率pc=0.8；變異概率pm=0.05；最大迭代次數(shù)gen=100；多重變異A、B和C三種操作的概率為[iter/gen； iter/(2*gen)； iter/(2*gen)]，其中iter為當前迭代次數(shù)。

圖3 NIGA算法流程框圖

3.1 算法復(fù)雜度分析

算法的復(fù)雜程度主要從時間復(fù)雜度和空間復(fù)雜度2個方面進行評價。

NIGA的時間復(fù)雜度主要取決于種群初始化及適應(yīng)度計算。適應(yīng)度排序采取快速排序，其復(fù)雜度為O(pop2)；解碼部分最壞情況的復(fù)雜度為O(m*PS)；錦標賽選擇的復(fù)雜度為O(pop)。迭代次數(shù)為gen，算法的時間復(fù)雜度為O(gen*pop(pop+m*PS))。

空間復(fù)雜度是指算法在運行過程中占用計算機的內(nèi)存空間，一般為正常占用之外的額外開銷。NIGA采用的編碼占用PS*pop 的數(shù)組存儲空間，后續(xù)操作均未占用額外的空間，所以算法的空間復(fù)雜度為O(1)。

3.2 NIGA單目標測試分析

為了驗證NIGA的可行性和有效性，從單目標和多目標2個方面進行測試分析。其中單目標為最小化最大完成時間，初始規(guī)則比例為0.6∶0.3∶0.1。采用Brandimarte中的10個算例，與文獻[13-16]進行對比測試。

從表2的運行結(jié)果可以看出，所提出的算法在解決Brandimarte系列算例時，除了MK02外，其他9個算例均取得了4個算法中最優(yōu)解，證明NIGA在解決不同機器和不同工件的問題時都具備良好的性能。

表2 算法結(jié)果

以MK04為例，其收斂曲線如圖4所示，每代解在總體上呈現(xiàn)明顯下降，尤其在20代之前下降速度明顯，說明采取的初始化策略能夠有效加快收斂速度，在60代附近找到最優(yōu)解并保持穩(wěn)定；另外，種群的均值雖然也存在明顯下降趨勢，但與當代最優(yōu)解仍然存在較大差距，說明NIGA算法采取的變鄰域策略有效地維護了種群的多樣性。MK04的調(diào)度甘特圖見圖5。每個方塊的第1個數(shù)字為工件號，第2個數(shù)字為工序號。

3.3 NIGA多目標測試分析

為進一步探究NIGA的性能，進行多目標對比試驗。求解多目標問題仍然采用Brandimarte系列算例，初始化規(guī)則比例為0.6∶0.1∶0.1∶0.1∶0.1，以最小化最大完成時間、最小化機器總負載和最小化最大機器負載為目標函數(shù)。為適應(yīng)不同規(guī)模的算例，迭代次數(shù)調(diào)整為gen =2*n*m，交叉概率調(diào)整為Pc=0.8*(1-iter/gen )，變異概率調(diào)整為Pm=0.05+0.1*(1+iter/gen )，其他參數(shù)與單目標保持一致。NIGA的運行結(jié)果如表3所示。表中每個算例都得出了若干個非支配解，決策者可根據(jù)實際生產(chǎn)需求選擇具體的調(diào)度方案。

圖4 MK04收斂曲線

不同于單目標的衡量指標，多目標調(diào)度不能簡單地從單方面判斷性能，解的數(shù)量是衡量性能的重要指標之一。表4中，將NIGA與其他3個算法[17-19]進行對比。其中，N表示得到的非支配解個數(shù)，time為算法的運行時間?？梢钥闯?，NIGA在其中6個算例中均取得了最高數(shù)量的Pareto解，可給予決策者更多的選擇。在實際調(diào)度生產(chǎn)中，同時需要更快的處理速度，NIGA在解決同類問題時具有較快的處理速度，雖然在維數(shù)較低的問題上比MOGA稍有不足，但在處理多工件多機器的算例時，速度提升的同時未減少支配解的數(shù)量，可以證明NIGA具有良好的求解質(zhì)量和響應(yīng)速度。

表3 NIGA Brandimarte算例結(jié)果非支配解

表4 NIGA與其他算法的解的數(shù)量及運行速度

4 結(jié)論

針對柔性作業(yè)車間調(diào)度問題，建立了以最小化最大完成時間、最小化機器總負載和最小化最大負載機器為目標的數(shù)學(xué)模型，提出了改進的遺傳算法進行求解。初始解采用多種方式混合產(chǎn)生，提高了初始種群的質(zhì)量；使用OIM插入的解碼方式，實現(xiàn)了解空間的高效搜索，加快了收斂速度；針對不同編碼層使用不同策略維持種群的多樣性，避免算法陷入局部最優(yōu)；采取變鄰域搜索增強局部搜索能力。通過運行Brandimarte算例，從單目標和多目標2個方面對比驗證了本文中算法的有效性和尋優(yōu)性能。后續(xù)將研究以效率和碳排放為目標的多工廠多目標分布式調(diào)度。