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

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

(1.江蘇省大氣環境與裝備技術協同創新中心， 南京 210044；2.南京信息工程大學 自動化學院， 南京 210044；3.江蘇省大數據分析技術重點實驗室， 南京 210044)

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

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

1 問題描述

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

根據實際生產情況，FJSP問題需要滿足以下約束條件：

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

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

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

4) 所有工件工序無優先級配置；

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

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

表1 符號定義

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

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是一個很大的數；式(6)表示在某一時刻一道工序只能同時由1臺機器加工；式(7)表示任意工序的開始時間和完成時間均為非負，且任意工件都可以從0時刻開始加工。

2 算法設計

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

2.1 編碼和解碼

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

圖1 編碼示意圖

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

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

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

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

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

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

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

2.2 初始化

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

圖2 OIM插入過程示意圖

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

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

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

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

2.3 交叉操作

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

多點交叉步驟如下：

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

步驟2隨機產生1組維度與MS染色體一致的0、1數組L；

步驟3子代個體child1繼承father1對應L數組為1位置的基因，子代個體child2繼承father2對應L數組為1位置的基因；

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

2.4 多重變異操作

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

多重變異偽代碼如下：

2.5 變鄰搜索策略

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

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

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

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

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

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

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

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

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

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

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

2.6 算法流程

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

步驟1根據2.2節中提出的規則進行種群初始化并設置相關參數；

步驟2通過OIM對種群進行適應度計算；

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

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

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

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

步驟7得到的新一代種群進行適應度計算并根據適應度降序排序，保存這一代的最優個體；

步驟8循環終止判斷，如果滿足跳至步驟9；否則，跳轉至步驟3；

步驟9最優解輸出，算法結束。

算法流程如圖3所示。

3 結果與分析

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

圖3 NIGA算法流程框圖

3.1 算法復雜度分析

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

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

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

3.2 NIGA單目標測試分析

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

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

表2 算法結果

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

3.3 NIGA多目標測試分析

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

圖4 MK04收斂曲線

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

表3 NIGA Brandimarte算例結果非支配解

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

4 結論

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