面向可持續生產中多任務調度的雙重增強模因算法

盧 弘 王耀南 喬 非 方 遒

可持續生產調度 (Sustainable production scheduling) 是順應當下制造業綠色與可持續發展需求的新興研究課題[1-2].相比于以優化經濟維度為核心的傳統調度,可持續生產調度在此基礎上,從調度目標或者約束角度擴充環境維度 (高能效、低碳排放等) 和社會維度 (工作公平、人員安全等) 的可持續制造指標[3-5],從而有效地兼顧制造業的正面績效和負面影響,有利于企業的長遠發展.

依據考慮的可持續維度,可持續生產調度研究可以細分為: 1) 高能效調度 (Energy-efficient scheduling),旨在通過制造調度實現能源效率最大化,由此得到的調度方案既降低能耗又兼顧生產性能[6-9];2) 低碳調度 (Low carbon scheduling),指的是通過制造調度優化生產性能,同時降低制造過程中的碳排放量[10-12];3) 考慮需求響應策略的調度(Scheduling with demand response strategies),是在調度過程中考慮供電方制定的策略,從而在保證生產性能的基礎上優化電力消耗[13-14].在綜述文獻方面,Giret 等在文獻[15]的基礎上,整理經濟、環境以及社會3 個維度的可持續制造性能指標,并從制造車間、目標系統、模型類型、目標函數、約束條件以及求解方法這6 個角度進行整理和歸納[3].結合已有綜述和細分領域的研究現狀來看,目前成果在優化目標或者約束上有各自的側重和不同,但關注的可持續性指標大多局限于經濟和環境兩個維度,對社會維度關注較少.隨著制造業用工合理和工人安全等社會性問題頻發,全面考慮經濟-環境-社會三維可持續性的調度研究有待深入開展.

隨著指標維度的拓寬,可持續生產調度的任務也由傳統生產任務 (投料、工件排序與機器指派)向機器控制與人員安排等相關任務泛化.環境維度上,引入包括調整機器加工速度[16-17]和選擇機器開關機[18-19]的機器控制任務,進一步降低能源消耗.社會維度上,工人是重要的考量因素,保證其工作負荷的公平是實現生產可持續性的必然要求[20].為滿足不同維度可持續指標的優化需求,調度決策過程中必將面臨多種不同類型的調度任務.因此,研究多類型任務的調度優化對提高制造企業生產方案的全方位可持續性有著重要的意義.針對制造生產中經典的并行機場景,本文將優化來自3 個維度的可持續目標,因而調度決策時包含機器指派、工件排序、工人安排以及機器開關機控制在內的4 種任務.

本文研究多維度目標和多類型任務的調度問題,相應的調度模型必然具有多目標優化和多決策變量的特點.算法在求解模型時,搜索空間的范圍大且結構復雜.在這樣的搜索空間中,算法往往極易陷入局部最優解,因此提高局部尋優能力是求解本文問題的研究重點.模因算法 (Memetic algorithm,MA) 是一類針對復雜優化問題的元啟發式方法,在平衡全局探索和局部開發上具有良好的性能[21-22].該算法使用交叉和變異等全局搜索算子,同時引入局部搜索技術增強其局部搜索能力.近年來有學者開始將其用于求解可持續調度問題,Geng等[23]針對考量工人安排的柔性流水車間調度問題,提出一種多目標模因算法優化最大完工時間、拖期時間以及工人負荷差異.Zhu 等[24]研究具有工人學習因子的低碳柔性作業車間調度問題,設計一種包含遺傳算法和變鄰域搜索的模因算法.Wu 等[16]提出一種多目標的模因差分進化算法,同時優化最大完工時間和總能耗這兩個目標.Zhang 等[25]針對考慮機器速度可調的高能效調度問題,在遺傳算法的基礎上,設計兩種優化策略以分別優化拖期時間和總能耗.

在上述基于模因算法的求解方法中,全局搜索基本是基于交叉和變異的遺傳算子,而局部搜索主要分為以下兩類: 1) 基于跳變的隨機搜索策略,即將當前的候選解作為起點,在該點附近的鄰域內,以迭代的方式隨機生成新解[24].這種方式往往是基于變鄰域搜索、模擬退火等已有算法,設計簡便但參數調整困難.2) 基于問題結構的特定策略,這是針對具體問題而設計的定向優化方法[16,23,25],通過分析問題的優化需求,構建針對性的啟發式策略,設計難度相對較高.已有研究在構建模因算法時,大多僅利用單一類型的策略,鮮有結合兩種策略的研究工作.對于復雜的可持續調度優化問題,這兩種局部搜索策略各有優勢,如何將兩者有效地結合起來以實現雙重優化,是一種值得探索的研究思路.

本文針對多類型任務的可持續并行機調度問題,提出一種融合兩種局部優化策略的雙重增強模因算法 (Dual-enhanced memetic algorithm,DMA).考慮多決策變量,構造單步變鄰域搜索 (Onestep variable neighborhood search,1S-VNS).考慮多目標優化,設計分步優化的可持續目標導向策略(Sustainable goals-oriented strategy,SGS).最后,實驗對所提雙重模因算法在求解本文問題上的有效性和優越性開展驗證和分析.

1 問題描述和建模

帶多類型任務的不相關并行機三維可持續制造調度問題可以描述為: 車間里有N個獨立工件(i=1, 2,···,N) 和M臺不相關并行機(j=1, 2,···,M),由K個工人 (v=1, 2,···,K) 負責操作機器加工工件.問題的實際背景可參見車輛裝配生產過程[20,26],在組裝車輛外部構件時,要求工人操作機器完成上料、組裝以及下料等工作.出于生產效率的考慮,工人數量往往不大于投入使用的機器數量.因而,對于某個工件來說,會出現機器可用而工人不可用 (正在加工其他工件) 的情況.此外,這里假設機器允許出于節能考慮而出現開關機情況[18].調度問題的任務類型包含4 類: 1) 為機器指派所加工的工件;2) 為各個機器上的工件排序;3) 為工人安排所負責的工件;4) 控制處于非加工狀態的機器進入待機或者關機.

研究的調度目標涵蓋了可持續制造指標體系的全部維度: 1) 在經濟維度上,考慮最小化最大完工時間Cmax;2) 在環境維度上,最小化加工過程中的總能耗Eall,包括加工能耗Ep和非加工能耗Enp;3) 在社會維度上,最小化工人之間工作負荷的不平衡度W[20].

決策變量的定義如下:xijlv為決策變量,工件i在機器j上的第l個位置由工人v操作時xijlv=1 ;否則,xijlv=0.該決策變量對應工件排序、機器指派以及工人安排這3 個調度任務.ymac是輔助變量,用來指代機器開關機的決策條件,假如機器待機能耗比關機能耗低,則ymac=1;否則,ymac=0.

基于上述的問題定義和描述,帶多類型任務的不相關并行機三維可持續制造調度問題的三元命名是R|xijlv,ymac|Cmax,Eall,W,相應的數學模型如下所示.

目標函數為

在目標函數中,式(1)表明優化的是3 個不同維度的調度目標,各個調度目標的具體計算方式如式(2)～ (7)所示.在約束條件中,式(8)表示任何一個工件只能被安排到一臺機器上的一個位置并且由一個工人進行加工;式(9)約束了機器每個位置上最多加工一個工件;式(10)明確了最大工作負荷的計算方式;式(11)表示在機器j的l位置上工件的結束時間cj,l的計算方式;式(12)表示在機器j的l+1 位置上工件的開始時間sj,l+1的計算方式;式(13)表示決策變量xijlv是0-1 變量.

相比于文獻[27]中經典的并行機調度模型,本文研究的調度模型呈現以下特點: 1) 調度目標上,本文同時優化3 個可持續目標Cmax、Eall和W, 其中Cmax和W屬于時間量綱,Eall屬于能耗量綱,因此本文目標數量更多且量綱不一致.2) 決策變量上,本文不僅考慮傳統的機器指派和工件排序,而且拓展了工人安排和機器控制兩種任務.因此,決策變量xijlv的數量 (M×N×K) 遠大于傳統調度模型 (M×N).3) 約束條件上,隨著目標和決策變量的復雜化,約束條件的數量(2×N+1+2×M×N+M×N×K)也明顯更多.

鑒于調度模型的復雜度,本文基于模因算法框架,從目標優化需求和決策變量特點兩個角度入手設計雙重局部優化策略,進而提出一種融合兩種策略優勢的雙重增強模因算法.

2 雙重局部優化策略

2.1 任務對應的個體編碼

編碼是將問題的解空間轉變為算法尋優的個體,因此編碼方法與調度問題的決策任務直接相關.為匹配個體與R|xijlv,ymac|Cmax,Eall,W問題的調度方案,下面針對問題中的4 類調度任務設計編碼方式.考慮到機器開關機的選擇需要以其他三類任務的確定為前提,因此采取三段式編碼方式將算法個體與調度問題中的機器指派、工人安排以及工件排序三類任務相對應.圖1 給出了一個三段式個體的示例說明,針對的是5 個工件在3 臺機器上由2 個工人加工的案例.在圖1 的個體中,α段表示各個工件的加工順序,β段表示各個工件的機器指派,γ段則代表了各個工件的工人安排.基于三段式編碼形式,以隨機的方式形成初始種群.

圖1 任務對應的個體編碼說明圖Fig.1 An example graph of individual coding corresponding for tasks

2.2 單步變鄰域隨機搜索策略

變鄰域搜索是圍繞單個解的鄰域展開迭代搜索,其關鍵在于設計合適的鄰域動作,以達到產生更優個體的效果[28].針對第2.1 節中三段式個體,每段代表不同的任務,因此需要為各段設計相應的鄰域動作.可選的鄰域動作包括插入、突變和交換等方式[29-34].本文借鑒已有方法的經驗,并通過多次試驗,設計了如下4 種鄰域動作:

1) 對機器指派β段,隨機改變一個工件的機器指派,以N1指代該鄰域動作;

2) 對工人安排γ段,隨機改變一個工件的工人安排,以N2指代該鄰域動作;

3) 對加工順序α段和機器指派β段做組合動作,對α段以插入的方式改變,同時以方式N1改變β段,以N3指代該鄰域動作;

4) 對加工順序α段和工人安排γ段做組合動作,對α段以插入的方式改變,同時以方式N2改變γ段,以N4指代該鄰域動作.

傳統的變鄰域搜索算法往往需要進行多次迭代,迭代是以計算時間換取解質量的方式.在模因算法的框架中,每一次全局尋優后,都會運行多次局部迭代.假設全局尋優次數是num_global,局部迭代次數是num_local,那么算法總的迭代次數將是num_global×num_local.如此大量的迭代次數,必然造成算法整體的搜索效率不高.另一方面,鑒于本文將融合兩種局部優化策略,無需展開過多的隨機搜索.因此,以單步的方式運作變鄰域隨機搜索策略,其更新單個個體的作用流程如算法1 所示.

算法1.單步變鄰域隨機搜索策略

2.3 可持續目標導向優化策略

基于單步變鄰域隨機搜索策略有助于產生新個體,但隨機性使其優化效果難以得到保障.通過探索問題的特征來構建的優化策略,往往能夠直接有效地改善解質量,并且時間復雜度也較低[16,25].因此,本文將針對帶多類型任務的可持續調度問題,分析各個維度目標與不同調度任務之間對應關系,進而設計針對性的優化策略.然后,考慮到不同目標之間的沖突耦合關系,構建了分步作用方式以逐步優化不同維度的目標.

2.3.1 社會維度目標導向的優化策略

研究問題中的社會維度目標,是降低工人工作負荷差異度W,這可以通過減小各個工人工作負荷bv與最大工作負荷bmax之間的差值(式(6))實現.在所有差值中,工作負荷最小值bmin與工作負荷最大值bmax的差值 ?b是最大的,因而降低 ?b對于優化W而言是最為直接且簡便的.鑒于此,下面針對 ?b開展優化策略的設計.

在R|xijlv,ymac|Cmax,Eall,W問題中,調整工人安排即改變工人負責的工件,可以有效改變 ?b.假設目前具有bmax和bmin的兩位工人分別是v和v′,社會維度目標導向的優化策略核心是從工人v負責的工件集Jmv中挑選合適的工件轉變為v′負責加工,以此來減小bmax同時增大bmin.在這樣的調整方式下,其余工人的工作負荷并不會發生改變.在不造成新bmin大于原bmax的情況下,其 余工人與bmax之間的負荷差異也會隨著bmax的減小而下降,結果是整體的W值得到優化.該優化策略是在不改變加工順序和機器指派的情況下,通過調整工人安排以優化社會維度目標,具體步驟如算法2 所示.

算法2.社會維度目標導向的優化策略

為了進一步說明社會維度目標導向優化策略的特點,圖2 基于附錄A 中的案例數據給出了該策略的作用效果.在未作用的調度方案(圖2(a))中,兩個工人的負荷分別是b1=16、b2=4,此時的社會維度指標W的值是12.將所提優化策略作用于此調度方案: 首先,bmax和bmin分別對應b1和b2,兩者之間的差異 ?b=12.接著,統計負荷是bmax的工人W1 所負責的工件集合Jmv及其加工時間:J1(3),J2(4),J3(3),J4(6).在不改變機器指派的情況下,由工人W2 負責Jmv,那么各個工件的加工時間是:J1(6),J2(2),J3(3),J4(2).按照設計步驟,針對Jmv中的每個工件計算 ?b′,即嘗試替換工人安排.可以發現,當J1 替換為W2 負責后,?b′=3.依據替換條件,加工J1 的工人由W1 調整為W2,由此形成了新調度方案(圖2(b)).此時b1=13,b2=10,目標值W的值是3.對比圖2(a)和圖2(b)兩種調度方案,社會維度目標W由12 降低為3,因此設計的優化策略改善了社會維度目標.

圖2 社會維度目標導向的優化策略作用效果說明圖Fig.2 Explanation of the effectiveness of optimization strategy guided by social dimension goal

2.3.2 經濟維度目標導向的優化策略

研究問題中的經濟維度目標,是降低最大完工時間Cmax(式(2)).針對具有最大完工時間的機器,其消耗的時間主要由必要加工時間和空閑時間兩個部分組成,其中空閑時間是無效的非必要時間.本節通過調整工件之間的加工順序減少空閑時間,以優化該機器上所有工件的完工時間.為此,經濟維度目標導向優化策略的核心思路是,將完工時間靠后的工件提前至空閑時間段進行加工.因此,該策略調整的是工件的加工順序,而不改變機器指派和工人安排,其具體的優化步驟如算法3 所示.

算法3.經濟維度目標導向的優化策略

為了進一步說明經濟維度目標導向優化策略的效果,圖3 同樣基于附錄A 數據給出了優化策略作用前后的效果對比.作用前,調度方案(圖3(a))的經濟維度指標Cmax=21.將優化策略應用于該調度方案: 首先找到Cmax對應的機器是M3,其加工的工件集合Jmc包含了J3 和J4.接著,嘗試將J4的開始時間前移至J3 之前以降低機器的完工時間.由于此時J4 的加工時間是6,而J3 的開工時間是12,因而滿足前移條件.將J4 提前至J3 之前加工,形成了新調度方案(圖3(b)).對比作用前后的兩種調度方案,經濟維度目標Cmax從21 降低至了15,因此設計的優化策略改善了經濟維度目標.

圖3 經濟維度目標導向的優化策略作用效果說明圖Fig.3 Explanation of the effectiveness of optimization strategy guided by economic dimension goal

2.3.3 不同優化策略的分步作用方式

在第2.3.1 節和第2.3.2 節中,考慮社會維度目標導向的優化策略,也會影響其他兩個維度的目標值.對于經濟維度目標導向的優化策略,會同時影響經濟維度目標以及環境維度目標,但不會對社會維度目標造成影響.假如策略作用順序不當,相互的優化效果就會出現沖突,進而導致無效優化的情況.為了避免不同策略的優化沖突,有必要設計一種分步作用方式.

第1 步是運作社會維度目標導向的優化策略,第2 步是運作經濟維度目標導向的優化策略.在經濟維度目標導向設計的作用后,針對空閑時間段以調度機器控制任務的方式優化環境維度目標值 (控制機器處于待機或關機的任務),并將其作為分步作用方式的第3 步.這樣的分步作用方式使得三個維度目標依次得到針對性的調整,并且保證了后一步的優化策略不會破壞上一步的優化結果,不同優化策略分步作用方式的具體步驟如算法4 所示.

算法4.不同優化策略的分步作用方式

3 雙重增強模因算法

在模因算法框架中,尋優過程由全局搜索算子和局部搜索策略兩個部分完成.針對本文問題,全局搜索算子仍延續傳統交叉和變異的設計思路,對應上文個體做了相應的設計.針對多目標和多任務帶來的局部尋優困境,提出了隨機跳變和定向優化雙重優化策略.并且,依據不同策略的各自特點,將兩種策略作用于不同個體的更新,以融合各自的優勢.

3.1 全局搜索算子

對應第2.1 節中三段式個體,這里設計分段作用的全局搜索算子,以充分地更新每一段上的基因.依據各個個體支配等級,采取輪盤賭的方式挑選出PS×0.8個個體作為全局搜索算子的作用對象.

針對具有三段結構的個體,分段作用的全局搜索算子包括了交叉算子和變異算子,具體設計是:對于代表加工順序的α段,交叉操作以順序交叉(Ordered crossover) 的方式進行,變異操作以交換(Swap) 的方式進行;對于表示機器指派的β段,交叉操作以均勻交叉 (Uniform crossover) 的方式進行,變異操作則以單點 (Single point) 的方式進行突變;最后對于代表工人安排的γ段,交叉操作也采取均勻交叉,變異操作以單點突變.

考慮到本文問題中的多目標優化,采用了NSGA-II 中的非支配解排序和擁擠度計算等方法[20],可參考相關文獻,這里不再贅述.

3.2 雙重增強模因算法的主流程

基于上述設計,所提算法 (DMA) 求解R|xijlv,ymac|Cmax,Eall,W問題的主流程如下:

步驟 1.初始化種群PG,精英集合PE,令迭代次數i=0.

步驟 2.初始化精英集合,精英集合是由每代中對應非支配解的個體所構成,PE=PG×20%.當精英集合超過限定大小時,按照擁擠度挑選新的精英集合.

步驟 3.判斷是否終止迭代,如果達到終止條件,則算法終止并輸出非支配解;否則,令i=i+1.

步驟 4.針對種群PG,以第3.1 節中的全局搜索算子,形成新種群.

步驟 5.對于,以第2.2 節中的單步變鄰域隨機搜索策略,形成種群.

步驟 6.針對精英集合PE,以第2.3 節中的可持續目標導向優化策略更新精英集合中的個體,得到新精英集合.

步驟 7.結合和,更新種群PG和精英集合PE.返回步驟3.

從上述步驟中看出,雙重優化策略的融合方法是: 首先,將單步變鄰域隨機搜索作用于種群中的所有個體;接著,可持續目標導向策略進一步更新精英集合中的個體.之所以將可持續導向策略獨立作用于精英個體而非參與到所有個體的更新過程,主要是為了避免算法過早陷入局部最優解.假如將單步變鄰域隨機搜索策略和定向優化策略同時作用于種群,那么種群會早早地出現較多優質個體.在這些個體的引導下,算法會因為缺乏個體多樣性而過早收斂.其次是,相比所有個體參與優化策略,僅部分個體參與消耗的計算時間更少.綜上,所提DMA在全局搜索算子的基礎上,有效地融合兩種局部搜索策略,以期達到兼顧全局探索和局部開發的尋優效果.

4 實驗驗證

為了驗證雙重增強模因算法 (DMA) 在求解多目標和多任務的R|xijlv,ymac|Cmax,Eall,W問題上的有效性和優勢,接下來開展多組對比實驗和分析討論.所有測試實驗均采用MATLAB 2016b 編程實現,在8.0 GB 的RAM、2.30 GHz 的CPU 環境下運行.

實驗案例來源于Costa 等[26]的研究工作,文獻[26]在不相關并行機調度問題中考慮了人員安排,構建了相應的標準測試案例.基于此,本文從小規模和大規模案例中各選8 種,組成16 種測試場景.加工過程中的其余參數設置如下: 加工時間從均勻分布區間[2,6]隨機獲取;單位時間的加工能耗和空閑能耗分別從均勻分布區間[3,8]和[1,4]中隨機獲取;機器的開關機所需的能耗和時間分別從均勻分布區間[1,12]和[1,3]中隨機得到.考慮到參數隨機性,本文在各個場景下構建了5 個具有不同參數的案例,形成的測試案例總數是 16×5=80 個.

本文引入反轉世代距離 (Inverted generational distance,IGD) 和非支配解占比兩種性能指標,對算法求解案例的結果做分析和對比.反轉世代距離是常用于比較多目標算法在收斂性和多樣性上優劣的綜合指標.算法的IGD 值越小,則算法的性能越好.對于某一類算法來說,其IGD 的計算方式為

其中,A代表某一類算法;F表示所有對比算法求解結果中的非支配解集,即近似最優Pareto 解集.F的構造方式是將所有對比算法求解問題獲得的解集合并,然后以快速非支配排序的方式處理,最終獲得的非支配解集即為F.|F|代表F中解的個數,d(y?,y) 表示y?和y兩點之間的歐氏距離.

非支配解占比以Rnd表示,是將算法所得的非支配解集與近似最優解集F比較.算法的Rnd值越大,代表相應的算法越好,其Rnd的計算方式為

其中,Nnd(A) 表示算法所得非支配解同樣也存在于F中的數量.

為了保證比較的公平性,所有對比算法的運行時間均相同,即終止條件相同,都是N×M×K×100ms.此外,所有實驗中各個算法均獨立重復運行10 次后取平均結果,以消除隨機誤差.

4.1 雙重局部優化策略的提升作用

4.1.1 單步變鄰域隨機搜索策略的有效性

鄰域動作是單步變鄰域隨機搜索策略 (1S-VNS)能否發揮作用的關鍵,因此通過對比不同鄰域動作,以驗證本文所設計的方法是適用于問題的.這里參與對比的鄰域動作包括3 種,都是來源于第2.2 節中的變種.基于此,具體用于對比分析的算法如下:

1) MOA: 代表解決問題的多目標優化算法,即僅具有第3.1 節中全局搜索算子;

2) MMA_1: 代表在MOA 中加入第2.2 節中鄰域動作的第1 變種;

3) MMA_2: 代表在MOA 中加入第2.2 節中鄰域動作的第2 變種;

4) MMA_3: 代表在MOA 中加入第2.2 節中鄰域動作的第3 變種;

5) MMA: 代表在MOA 中加入第2.2 節中鄰域動作.

對比MMA 與MOA,可驗證局部優化方法(1S-VNS)是否有效.對比MMA 與其余變種,可驗證所設計的鄰域動作是否更為適用.5 種算法的初始種群大小均為100,交叉和變異概率均分別設置為0.9 和0.1.基于此,表1 統計了各算法求解不同案例所得的平均性能值,加粗形式表示占優的結果.

表1 MMA 與MOA、MMA_1、MMA_2、MMA_3 的性能指標結果Table 1 Results for MMA,MOA,MMA_1,MMA_2 and MMA_3

從表1 可知,MMA 在所有的小規模場景(前8 種)上占據優勢.無論是IGD還是Rnd,MMA 都比其他算法表現得更好,這說明所設計的1S-VNS在算法求解小規模場景時具有提升作用.對于大規模場景(后8 種),MMA 并沒有在所有案例上都取得最好的結果.尤其是20&12&10 場景,MOA 與MMA 的性能指標結果十分相近,這說明此時鄰域搜索并沒有起到改善算法性能的作用.究其原因,1S-VNS 本質是隨機尋優,在計算時間限定時,難以保證在大規模場景的復雜搜索空間中產生更優的個體.需要說明的是,表中的結果是多次測試后的平均值,因此有可能會出現IGD不同而Rnd相同的情況.對于20&12&8 場景,MMA 雖然表現不如MMA_2,但兩者的性能差距較小.綜合16 種場景,MMA 在大多數(15 種)結果上是具有求解優勢的.

本文進一步采用方差分析法 (Analysis of variance,ANOVA),對表1 中的算法性能差異展開顯著性檢驗.以5 種算法為控制變量,將2 種性能指標作為響應量,檢驗結果如圖4 所示.無論是指標IGD還是Rnd,MMA 與其他對比算法的置信區間都沒有重合,這表明MMA 的算法優勢是顯著的.綜合16 種案例的結果來看,1S-VNS 方法能夠明顯地提升算法性能,尤其是對于小規模案例.此外,MOA 與MMA_1、MMA_3 的置信區間存在重合,表明這些算法之間的差異并不顯著,這說明不合適的鄰域動作并不能有效改善算法求解結果.MMA_2 雖然與MOA 不存在明顯重合,但其性能遠不如MMA.因此,相比其他3 個變種,MMA 中的鄰域動作是最為適合本文問題的.

圖4 MMA 與MOA、MMA_1、MMA_2、MMA_3 性能指標的均值和95%置信區間Fig.4 Mean and 95% confidence interval of performance indicators of MMA,MOA,MMA_1,MMA_2 and MMA_3

4.1.2 目標導向優化策略的有效性

對于可持續目標導向策略(SGS)有效性的驗證,本文從有無策略以及融合方式兩個角度開展.因此,將所提DMA 與以下2 種算法進行對比:

1) MMA: 表示沒有融合目標導向優化策略的多目標模因算法(同第4.1.1 節);

2) MMA&SGS: 表示將SGS 作用于多目標模因算法中所有個體的算法.

對比DMA 和MMA,可以驗證SGS 是否有提升算法性能的作用.對比DMA 和MMA&SGS,能夠分析SGS 作用于個體和種群之間的效果差異.3種算法中種群大小均為100,交叉和變異概率都設置為0.9 和0.1.DMA 中的精英集合大小均設置為20.表2 統計了各個算法求解不同場景中案例所得的平均性能值,加粗的字體表示占優的結果.

表2 DMA 與MMA、MMA&SGS 的性能指標結果Table 2 Results for DMA,MMA and MMA&SGS

在表2 的小規模場景 (前8 種) 求解結果中,DMA 在其中的5 種場景占據優勢,而MMA 在2種場景上表現最佳,3 個算法在最小規模場景下同時最優.這一方面說明,在精英個體上作用SGS,對DMA 在大多數小規模場景的求解性能的確具有提升效果.另一方面,MMA 求解結果占優表明,隨機局部搜索 (1S-VNS) 比定向優化 (SGS) 效果更好的作用場景是存在的.可以理解的是,小規模場景下的尋優個體簡單,算法尋優空間小,1S-VNS 通過鄰域動作仍可以有效地搜索到更優個體.并且,由于無需在定向優化上花費計算時間,MMA 相比DMA 有更多的隨機搜索次數.綜合搜索次數和單次尋優能力,才使得MMA 在小規模案例上仍保持著一定的競爭力.

對于表2 中大規模場景 (后8 種) 的求解結果,其中6 種場景由DMA 占優,而剩余2 種則是MMA&SGS 更優,MMA 在所有場景中都表現最差.相比小規模場景的結果,定向優化策略SGS 起到了更加明顯的作用.因為隨著場景規模變大,尋優空間隨之擴展,隨機搜索的盲目性更加明顯,而定向優化產生更優個體的概率更高.此外,DMA 在更多場景下優于MMA&SGS,這也說明將SGS 作用于精英個體比作用于所有個體對提升性能更為合適.主要原因是,當SGS 作用于所有個體,就意味著定向優化將消耗更多的計算時間.在限定運行時間的情況下,尋優過程難以平衡全局尋優、隨機搜索以及定向優化,這導致MMA&SGS 算法的整體搜索效率不高.

為了驗證上述算法性能之間的差異是否具有統計意義,接著利用ANOVA 對表2 中的實驗結果進行差異性檢驗,結果如圖5 所示.可以看出,在IGD和Rnd上,DMA 與其他兩種算法的置信區間都沒有重合,這說明DMA 是顯著地優于對比算法,驗證了作用于精英個體的SGS 是可以顯著提升算法性能的.此外,MMA 和MMA&SGS 在兩種性能指標上的差異都不顯著,這也側面說明SGS 作用于所有個體時不具有明顯提升性能的作用.

圖5 DMA 與MMA、MMA&SGS 性能指標的均值和95%置信區間Fig.5 Mean and 95% confidence interval of performance indicators of DMA,MAA and MMA&SGS

4.2 與其他算法對比

鑒于鮮有與本文R|xijlv,ymac|Cmax,Eall,W問題一樣的研究工作,這里從問題所屬的可持續制造調度領域研究中選取了3 種較為常見的求解方法,并從應用角度做了針對性的變更.通過對比現有技術,以驗證所提DMA 在求解本文問題上的有效性.對比算法的來源文獻以及應用說明具體是:

1) V-NSGA-II: 來自Akbar 等[20]提出的求解考慮人員安排的調度研究,是一種基于經典NSGAII 的變種算法.為了將其應用于本文問題,采用第2.1 節中的編碼和初始化,沿用了原文中的交叉和變異方式.

2) IABC: 來自Li 等[35]的研究工作,其在基本人工蜂群算法的基礎上引入遺傳算子,求解考慮3 種調度任務的多目標柔性作業車間調度問題,獲得了良好的性能結果.在將其應用于本文問題時,同樣采用第2.1 節中的編碼和初始化,沿用了原文中的更新方式.

3) MA: 選自文獻[24]中的研究成果,該模因算法是以變鄰域搜索算法對局部范圍展開搜索,用于求解考慮人員的柔性作業車間低碳調度問題.為了將該算法應用于本文問題,這里采用第2.1 節中的初始化以及第3.1 節中的全局搜索算子,沿用了文獻[24]中的變鄰域搜索算法.

DMA 的參數設置同第4.1.2 節,4 種算法的初始種群大小均為100,V-NSGA-II 的交叉和變異概率與DMA 相同,IABC 中的精英集合大小也與DMA保持一致.MA 中變鄰域搜索算法的迭代次數設置為50.基于上述設置,表3 統計了各個算法求解不同場景下案例所得的平均性能值,加粗形式表示占優的結果.

表3 DMA 與V-NSGA-II、IABC、MA 的性能指標結果Table 3 Results for DMA,V-NSGA-II,IABC and MA

從表3 可以看出,無論是IGD還是Rnd,DMA在所有場景的求解結果都是占據優勢的,這說明DMA 求解本文問題的性能優于其他3 種算法.與MA 相比,雖然兩種算法都同時具備了全局優化和鄰域搜索,但很明顯DMA 中的更新方式是針對本文問題設計的.不僅如此,DMA 還融合了可持續目標導向的定向優化策略,因此求解性能更具優勢.此外,MA 比IABC 和V-NSGA-II 表現更佳,這也驗證了模因求解框架在本文問題上比單一的全局優化更為合適.值得說明的是,IABC 和V-NSGA-II的更新方式仍是以沿用原文為主,原文問題和本文問題上的較大差異會造成算法力有不逮,尤其是在大規模場景上體現的較為明顯.

對于算法求解性能差異的顯著性,圖6 展示了ANOVA 方法對表3 數據的檢驗結果.可以看出,DMA 與對比算法的置信區間在IGD和Rnd上都不重合,這表明DMA 的求解性能是顯著地優于其他算法.MA 與V-NSGA-II、IABC 也沒有性能值上的重合,說明模因框架的優勢也是較為顯著的.此外,V-NSGA-II 和IABC 在兩種性能指標上的檢驗結果都有明顯的重合,這表明這兩種算法在統計意義下具有相似的求解性能.

圖6 DMA 與V-NSGA-II、IABC、MA 性能指標的均值和95%置信區間Fig.6 Mean and 95% confidence interval of performance indicators of DMA,V-NSGA-II,IABC and MA

為了進一步可視化上述比較算法的求解性能,圖7 繪制了4 種算法求解大規模場景(40&10&6)所得的Pareto 前沿.圖7(a)展示了含所有目標的總體情況,其余子圖是含部分目標.在圖7(b)和圖7(c)中,可以清楚地看到3 種對比算法的解都被DMA的解所支配.在圖7(d)中,雖然DMA 所得解有少部分不如MA,但仍明顯優于IABC 和V-NSGAII 所得解.

圖7 DMA 與V-NSGA-II、IABC、MA 獲得的Pareto 前沿Fig.7 Pareto frontiers obtained by DMA,V-NSGA-II,IABC and MA

此外,從圖7 也可以看出最大完工時間Cmax與總能耗Eall之間存在一定的負相關性.當某個調度方案的最大完工時間較大時,往往其總能耗會較低.其主要原因是: 為了降低加工能耗,在挑選工人時會盡量選取加工時間或者能耗低的.結果會出現機器等待工人的情況,造成大量的非加工時間,因此延長了相應的完工時間.關于總能耗Eall與工人負荷差異度W,兩者之間存在明顯的沖突關系.相比出于降低能耗而盡可能挑選低加工時間的策略,優化工人負荷差異度是以增大某些工件的加工時間為代價來降低工人負荷差異的.最大完工時間Cmax與工人負荷差異度W兩者存在相對正相關關系.當某個調度方案的最大完工時間較高時,其相應的工人負荷差異度也較高.這里的原因也是由于降低工人負荷差異度時,往往會以增加加工時間為代價,由此機器完成工件的完工時間就會變大.

綜上所述,本文設計的DMA 算法對于帶多類型任務的不相關并行機三維可持續制造調度問題具有良好的尋優性能,其優勢可歸結為以下幾點: 1) 設計的單步變鄰域隨機搜索策略適用于本文問題,有效地加強了對局部范圍的尋優能力;2) 可持續目標導向策略針對問題優化需求并且作用于精英個體的構造,有效地提高了算法尋優效率;3) 相比領域文獻中的V-NSGA-II、IABC 和MA 這3 種算法,DMA求解本文問題所得解的質量更高.

5 結束語

本文提出了一種雙重局部優化策略增強的模因算法 (DMA) 求解帶多類型任務的不相關并行機三維可持續制造調度問題.考慮多任務決策,設計了單步變鄰域隨機搜索策略 (1S-VNS),有效地更新任務分配以產生新解.進一步分析不同維度目標的優化需求與任務調度之間的關系,設計了可持續目標導向的優化策略 (SGS),并分步作用于精英個體,實現調度目標的定向優化.在實驗過程中,驗證了單步變鄰域隨機搜索策略的有效性,并且說明了可持續目標導向策略能夠顯著地提升算法的求解性能.最后,與文獻中V-NSGA-II、IABC 和MA 這3 種算法對比,實驗結果表明所提DMA 求得的非支配解集在多樣性和收斂性上更具優勢.

由于本文研究的問題是在靜態環境下,實際生產中往往會存在不確定情況,下一步將著手研究考慮不確定性的可持續調度問題.當問題從確定轉變為不確定后,模因算法的設計也將要求兼顧高效和適應性,以應對生產過程中的變化.另外,隨著機器人在生產制造過程中的廣泛應用,如何集成調度機器人和傳統資源也是未來的另一個研究方向.

附錄 A 可持續目標導向優化策略的說明案例

表A1 各個工件的基本加工數據Table A1 Basic machining data for each job