一種遺傳-貪婪融合算法求解多目標(biāo)綠色柔性車間調(diào)度問題

高 滔，葉春明

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

隨著生產(chǎn)力的發(fā)展，能源消耗速度的不斷升高導(dǎo)致的資源枯竭和環(huán)境問題日益嚴(yán)重，綠色制造已經(jīng)成為了學(xué)術(shù)和企業(yè)界熱議的話題[1]。綠色調(diào)度作為綠色制造的關(guān)鍵一環(huán)，作業(yè)車間調(diào)度中也愈加重視這一指標(biāo)。

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

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

1 多目標(biāo)柔性車間綠色調(diào)度問題

1.1 問題描述

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

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

1）同一臺機(jī)器同一時(shí)刻只能加工一道工序；

2）任意工序只能被一個(gè)機(jī)器加工一次；

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

4）各個(gè)工件之間不存在的優(yōu)先級的差別；

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

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

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

表1 符號定義

1.2 模型建立

根據(jù)問題模型和假設(shè)條件，本文的調(diào)度模型以經(jīng)濟(jì)和綠色為目標(biāo)，選擇最大完工時(shí)間、機(jī)器總負(fù)荷和總能耗為目標(biāo)函數(shù)；具體的數(shù)學(xué)模型如下：

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

2 遺傳貪婪融合算法

2.1 編碼及解碼

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

圖1 編碼示例

解碼：根據(jù)工序和機(jī)器編碼轉(zhuǎn)換出工序的加工時(shí)間，根據(jù)工序、機(jī)器和加工時(shí)計(jì)算每個(gè)機(jī)器的負(fù)載和終止時(shí)間。最大完工時(shí)間是最晚機(jī)器的終止時(shí)間。總負(fù)荷和總能耗分別是各機(jī)器的負(fù)荷和能耗之和，能耗根據(jù)空載和負(fù)載時(shí)間和具體的功率計(jì)算。

2.2 種群初始化

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

工序編碼：依次產(chǎn)生qi個(gè)i(i=1，2，…m)，隨機(jī)打亂即可；

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

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

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

2.4 選擇與交叉

選擇：輪盤賭方法生成個(gè)體可重復(fù)的相同規(guī)模的種群。

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

圖2 MK01的一個(gè)可行調(diào)度方案

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

2.5 非劣解表

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

2.6 貪婪算子

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

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

Step1：對染色體進(jìn)行解碼，輸出最大完工時(shí)間、負(fù)荷、能耗、最晚完工機(jī)器、最早完工機(jī)器；

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

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

Step4：舊染色體與第一個(gè)新染色體的三項(xiàng)優(yōu)化指標(biāo)作對比，如果部分新指標(biāo)優(yōu)于舊指標(biāo)，更新染色體和非劣解表，否則不更新，轉(zhuǎn)向與下一個(gè)新染色體比較。如果染色體發(fā)生更新，轉(zhuǎn)Step2，否則結(jié)束貪婪；

Step5：是否搜索到終點(diǎn)，是結(jié)束貪婪，否則繼續(xù)Step2；

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

圖3 貪婪選擇示例

2.7 算法流程

Step1：設(shè)置迭代次數(shù)，設(shè)置非劣解表，初始為空；

Step2：按2.2方法初始化種群，按2.3方法計(jì)算適應(yīng)度；

Step3：按照2.4方法對種群進(jìn)行選擇交叉，找到優(yōu)化種群的非劣解集及各項(xiàng)指標(biāo)；

Step4：優(yōu)化種群的每個(gè)個(gè)體按照2.6方法進(jìn)行貪婪操作并更新非劣解表；

Step5：判斷是否達(dá)到迭代次數(shù)和非劣解表是否更新，到達(dá)迭代次數(shù)或非劣解表未更新，結(jié)束算法，否則轉(zhuǎn)Step2；

圖4 算法流程

3 算法驗(yàn)證

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

[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]

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

表2 MK01算例結(jié)果

圖5 非劣解中各指標(biāo)的變化

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

為近一步測試算法性能，算法的各參數(shù)與MK01相同，依照2.6的算法流程分別對MK01～MK07做三個(gè)目標(biāo)和兩個(gè)目標(biāo)的尋優(yōu)，結(jié)果如表3所示，前兩列是對比文獻(xiàn)的結(jié)果。并繪制MK03的最小完工時(shí)間下調(diào)度方案的甘特圖如圖6所示，時(shí)間是222。

表3 MK01～07算例結(jié)果對比

圖6 MK03最小完工時(shí)間下的調(diào)度方案

表3第一行括號里的2，3表示目標(biāo)數(shù)，其他行括號里的第一個(gè)數(shù)是非劣解的個(gè)數(shù)，第二個(gè)是完工時(shí)間的最大值，第三個(gè)是能耗最大值，第四個(gè)是負(fù)荷時(shí)間最大值。相較于前面2個(gè)算法，本文算法2個(gè)目標(biāo)下在解的質(zhì)量優(yōu)于前者，在3個(gè)目標(biāo)下的表現(xiàn)也較好。

4 結(jié)語

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