一種遺傳-貪婪融合算法求解多目標綠色柔性車間調度問題

高 滔，葉春明

（上海理工大學 管理學院，上海 200093）

0 引言

隨著生產力的發展，能源消耗速度的不斷升高導致的資源枯竭和環境問題日益嚴重，綠色制造已經成為了學術和企業界熱議的話題[1]。綠色調度作為綠色制造的關鍵一環，作業車間調度中也愈加重視這一指標。

多目標柔性作業車間調度問題的求解難度較大，是NP-hard。當前求解該問題一種比較普遍和高效的方法是啟發式算法，如遺傳、蟻群、模擬退火算法等。鐘祾充等[2]設計一種混合布谷鳥算法求解綠色流水車間調度問題。姚明明等[3]求解混合流水車間調度問題時以最大完工時間和總拖期為目標，改進了灰狼算法。孟冠軍等[4]采用不同階段不同搜索機制，并與禁忌搜索結合改進人工蜂群算法求解多目標柔性車間調度問題。王春等[5]求解多目標柔性車間調度問題時用區間數表示工序加工時間，并設計了一種進化算法解決。Dai等[6]在求解含有運輸約束的多目標柔性車間調度問題時改進了遺傳算法。Amiri等[7]用組合優化策略對多目標柔性車間調度問題進行求解。何東東[8]改進遺傳退火算法用于求解柔性車間調度問題。弈飛等[9]求解低碳車間調度問題時加入自適應慣性權重和非線性收斂因子改進了鯨魚算法。朱光宇等[10]設計了一種基于直覺模糊相似度的遺傳算法求解多目標柔性車間調度問題。在王建華等[11]設計了一種基于Pareto最優解的自適應多目標Jaya算法求解帶綠色指標的多目標柔性車間調度問題。解瀟晗等[12]采用多層編碼策略優化遺傳算法并解決了面向能耗的多目標柔性車間調度問題。

多目標柔性作業車間調度問題多以算法改進和算法融合的方式求解，本文設計了一種基于遺傳貪婪思想的混合算法（Genetic Greedy Fusion Algorithm，GGFA）求解。遺傳部分：初始種群的工序編碼隨機生成、機器編碼采用挑選最短加工機器與隨機的方式生成[13]，適應度值等于優化指標統一量綱后求和，選擇方式采用輪盤賭，交叉方式是單點與順序交叉結合。貪婪部分：個體尋優時采用前后貪婪算子，設置貪婪上下限，實時更新非劣解表。最后通過算例求解驗證效果。

1 多目標柔性車間綠色調度問題

1.1 問題描述

多目標柔性綠色車間調度模型描述如下：m個工件在n臺機器上加工，工件i包含qi(i=1，2，…，m)道工序，qi不全相同，有工序可以在多臺機器上加工且加工時間不等，可選機器集Mij∈{1，2，…，n}。優化目標是最大完工時間CM、機器總負荷TM和總能耗ET。

建立模型前對問題做出的一些假設：

1）同一臺機器同一時刻只能加工一道工序；

2）任意工序只能被一個機器加工一次；

3）任意工序開始加工不能中斷；

4）各個工件之間不存在的優先級的差別；

5）同一工件的工序之間存在先后約束；

6）所有工件在零時刻都可以被加工。

為方便討論與讀者對本文理解，對本文出現的符號作如表1定義。

表1 符號定義

1.2 模型建立

根據問題模型和假設條件，本文的調度模型以經濟和綠色為目標，選擇最大完工時間、機器總負荷和總能耗為目標函數；具體的數學模型如下：

其中式(1)、式(2)、式(3)表示最小化最大完工時間、總負荷和總能耗。式(4)表示工序開始加工就不能停止。式(5)表示任意工序只能在一臺機器上加工一次。式(6)表示工序的先后約束。式(7)表示安排在相同機器上的工序，同一時刻只能加工一道。式(8)Xijz=1表示工序oij在機器z上加工，否則為0。式(9)Yijhk=1表示工序ohk在oij前加工，否則為0。

2 遺傳貪婪融合算法

2.1 編碼及解碼

編碼：采用基于機器和工序的2級實數編碼方式。以每個工件含有兩道工序的3×2完全柔性車間調度問題為例：如圖1所示，該編碼表示工件1和3的第一道工序分別在機器2和3上加工，其余工序的加工機器以此類推，這種編碼方式能滿足工序和機器約束。

圖1 編碼示例

解碼：根據工序和機器編碼轉換出工序的加工時間，根據工序、機器和加工時計算每個機器的負載和終止時間。最大完工時間是最晚機器的終止時間。總負荷和總能耗分別是各機器的負荷和能耗之和，能耗根據空載和負載時間和具體的功率計算。

2.2 種群初始化

假設問題有m個工件，染色體長度為∑mi=1qi 。

工序編碼：依次產生qi個i(i=1，2，…m)，隨機打亂即可；

機器編碼：假設sig∈[0，1]，在0，1之間生成隨機數數rand，如果rand小于sig，所有工序隨機挑選機器，否則所有工序挑選加工時間最短的機器。

2.3 適應度計算

對于每個染色體對應的最大完工時間、總負荷、總能耗。最大最小值法統一量綱。如式(10)所示，x，y分別對應各指標歸一化前后的值，v為種群數量。適應度值取三個指標對應y(k)之和，且x(k)越小，y(k)越大，適應度值越大，個體就越優秀。

2.4 選擇與交叉

選擇：輪盤賭方法生成個體可重復的相同規模的種群。

交叉：順序與單點交叉方式結合。選擇得到的種群溝通依次兩兩一組交叉，具體方式如下：在1到之間隨機生成一個整數作為交叉位置c，對于兩個父代染色體C1、C2，分別在C3、C4存入C1、C2位置c前的染色體。C2去除C3的工序基因后與C3合并形成子代1。C1去除C4的工序基因后與C4合并形成子代2，機器編碼作相應交換。

圖2 MK01的一個可行調度方案

工序編碼變異引起的機器編碼變異較復雜，遺傳部分主要考慮工序優化，所以不考慮變異。合并選擇和交叉得到的種群，根據適應度值保留一半(v)個體進入貪婪操作。

2.5 非劣解表

大多多目標問題的求解是求出非劣解集，本文對完工時間、負荷和能耗尋Pareto占優進而找到非劣解集。非劣解表包含解的工序編碼、機器編碼及三個優化指標，初始為空，假設遺傳優化后種群的第一個個體非劣，加入非劣解表，依次遍歷種群個體，按照指標的支配關系不斷添加或刪除表里的解。

2.6 貪婪算子

以MK01為例，按照上述編碼生成方法初始化一個可行調度方案如上，完工時間是86。最晚完工的機器和工件分別是M2和工件2。算例數據知工序O25的可選機器集是[6，2，1]，對應加工時間[5，6，1]。假設把工序O25安排到M1上加工，對應圖中M2最后一個矩形移動到M1的工件6后面。最晚完工機器變成M4，最晚完工時間變短了，機器總負荷降低了5(O25加工時間由6變1)。空載時間不變，如果M2，M1負載功率差別不大，能耗也會降低。

由上面例子得到啟發，考慮貪婪策略優化機器編碼，完工時間的貪婪策略是把最晚完工機器的工序往其他機器安排。機器負荷的貪婪策略是把工序往加工時間短的機器安排。能耗的貪婪策略把工序加工時間少和功率低的機器安排。為減少算法復雜度和重復迭代，本文設計了前后貪婪算子，以后貪婪算子為例，算子步驟如下：

Step1：對染色體進行解碼，輸出最大完工時間、負荷、能耗、最晚完工機器、最早完工機器；

Step2：以最晚和最早完工機器在機器編碼的位置為起點和終點，對機器編碼反向遍歷，記錄基因等于最晚完工機器數的位置，讀出工序并找到工序的可選機器集，如果可選機器個數為1，轉Step5，否則轉Step3；

Step3：工序挑選其他不同機器，機器編碼對應位置的基因改變即可，工序編碼不變，新的染色體個數為可選機器數減1。新的染色體按Step1方法解碼；

Step4：舊染色體與第一個新染色體的三項優化指標作對比，如果部分新指標優于舊指標，更新染色體和非劣解表，否則不更新，轉向與下一個新染色體比較。如果染色體發生更新，轉Step2，否則結束貪婪；

Step5：是否搜索到終點，是結束貪婪，否則繼續Step2；

前貪婪算子：正向遍歷染色體，遍歷的起點和終點是最早和最晚開始加工工件的機器的位置，其余類似。以2.1的編碼例子為例，一個可行調度的工序和機器編碼如下，假設機器2是最晚完工機器，其前后貪婪選擇如圖3所示。

圖3 貪婪選擇示例

2.7 算法流程

Step1：設置迭代次數，設置非劣解表，初始為空；

Step2：按2.2方法初始化種群，按2.3方法計算適應度；

Step3：按照2.4方法對種群進行選擇交叉，找到優化種群的非劣解集及各項指標；

Step4：優化種群的每個個體按照2.6方法進行貪婪操作并更新非劣解表；

Step5：判斷是否達到迭代次數和非劣解表是否更新，到達迭代次數或非劣解表未更新，結束算法，否則轉Step2；

圖4 算法流程

3 算法驗證

MK01～MK07是工件、工序、機器數不全相同的柔性車間調度問題算例[14]，本文算法測試基于這7個例子。文獻[15]的兩個優化目標完工時間和能耗計算方式與本文相同。為實現算法對比，采用該文獻設置的負載和空載功率，前后兩個矩陣分別表示負載和空載功率，矩陣中功率的位次表示機器，如第一臺機器的負載和空載功率分別是2和0.6。具體數據如下：

[2，1.8，1.6，2.4，2.4，4.1，3.5，4.1，2.8，2.7]，

[0.6，0.6，0.3，0.4，0.4，0.6，0.8，0.9，0.3，0.4]

設置迭代次數為20，種群規模為80，sig為0.8，交叉概率為0.8，對MK01例子進行最大完工時間，能耗、機器總負荷尋優，為清楚看出非劣解集的變化，該例子未加入非劣解集不更新結束算法的條件。其非劣解如表2所示，非劣解集中三個指標的最大、最小、平均值變化如圖5所示。

表2 MK01算例結果

圖5 非劣解中各指標的變化

圖5中迭代次數為0是首次遺傳操作后的非劣解集的各項指標，可以看出，第一次貪婪三個指標都有較大程度減低。第二次迭代后最大和平均時間完工上升，而能耗和負荷的相應指標下降，說明指標間存在矛盾關系，也說明該問題的指標無法優化到單目標下的結果。最小完工時間、最小能耗、最小負荷不增說明含有最小目標的解被保存下來。每個可行調度方案的工序以0.2概率選擇了最短加工時間機器，即最小負荷，該例子是153，所以最小負荷一直不變。各指標在14次左右趨于平緩說明該算法收斂較快。

為近一步測試算法性能，算法的各參數與MK01相同，依照2.6的算法流程分別對MK01～MK07做三個目標和兩個目標的尋優，結果如表3所示，前兩列是對比文獻的結果。并繪制MK03的最小完工時間下調度方案的甘特圖如圖6所示，時間是222。

表3 MK01～07算例結果對比

圖6 MK03最小完工時間下的調度方案

表3第一行括號里的2，3表示目標數，其他行括號里的第一個數是非劣解的個數，第二個是完工時間的最大值，第三個是能耗最大值，第四個是負荷時間最大值。相較于前面2個算法，本文算法2個目標下在解的質量優于前者，在3個目標下的表現也較好。

4 結語

本文針對綠色車間調度問題建立以最小化最大完工時間、能耗和機器總負荷的為目標的調度模型。考慮遺傳算法和貪婪算法結合對問題進行求解，在python平臺進行仿真實驗，得出問題的帕累托解，為決策者提供參考。并在最小化最大完工時間、能耗兩個目標下與其他文獻結果進行比較，驗證了算法的可行性和有效性。