考慮雙資源約束的柔性機械加工車間逆調度問題研究

摘要：為提高機械加工車間在動態生產環境下的效率和穩定性，建立了考慮機器與工人約束的柔性機械加工車間逆調度問題模型。該模型以最小化完工時間、機器能耗和逆偏差指數為目標，通過調整工件排產、工人作業以及機加工工藝參數對原始調度方案進行優化。針對問題特征，提出了一種差分進化算法。在算法中，設計了混合雙層編碼方式以降低搜索難度；提出了兩種基于調度規則的初始化方式以提高種群質量；為加強和平衡全局與局部搜索，設計了自適應遺傳操作以及基于精英選擇的局部搜索策略；改進了哈明距離，并提出了一種擁擠度算子以反映種群真實多樣性。在實驗中構建了33組測試算例，并將所提算法與其他7種算法進行對比，驗證了所提算法性能。最后，分析了某液壓缸生產車間在兩種不同動態環境下的真實逆調度案例，結果表明，所提算法能夠在較小程度改變原始調度的情況下縮短4.2%的完工時間、降低20.2%的機器能耗。

關鍵詞：雙資源約束柔性作業車間調度；機械加工車間；逆調度；多目標優化；差分進化算法

中圖分類號：TP278

DOI：10.3969/j.issn.1004132X.2024.03.008

0引言

目前我國機械加工車間在生產管理、智能決策等方面還存在不足［1］。研究實際機械加工車間生產調度問題，探索新型調度方法，對提高車間產能、實現制造模式升級具有重要意義。機械加工車間具有離散、柔性制造特點，同時生產過程受機器、工人等資源約束。當前，考慮機器與工人雙資源約束的柔性作業車間調度問題已成為研究熱點。在問題特征方面，TAN等［2］針對工人疲勞特性，研究了機器、工人聯合調度問題；梁向檁等［3］構建了考慮工人配置的柔性作業車間調度模型；FABIAN等［4］研究了具有不確定加工時間的雙資源約束調度問題；易茜等［5］討論了工人作業能力對生產調度的影響。在調度目標方面，多數研究以完工時間為目標，部分研究優化了機器能耗［6］、拖期［3］、工件加工質量［7］等，然而，現有研究較少考慮機械加工參數對生產的影響，導致模型不完全符合實際。更重要的是，機械加工生產環境并不總是穩定的，動態事件（如機器故障、緊急訂單等）常導致原始調度方案不再是最優的甚至不可行［8］，因此，有必要在實際多資源約束下研究機械加工車間動態調度方法。

在柔性作業車間動態調度問題中，當前多數研究采用重調度方法獲得新調度方案。盡管重調度可以滿足全局最優，但由于它改變了原始生產方案，故往往伴隨高昂運輸成本，并且難以實施。實際機械加工車間存在重型、大型工件及材料搬運困難、輔助生產資源多等問題，重調度策略勢必會對生產系統整體造成更大的負面影響［9］。為了最大限度地保持原始調度方案，同時獲得接近最優的調度方案，逆調度成為了一種必要方法。目前關于逆調度的研究報道較少。KOULAMAS［10］最早研究了具有可控作業參數的流水車間逆排序問題，并設計了多項式求解方法，成功解決了小規模問題。BRUCKER等［11-12］分別建立了不確定交貨期的單機逆調度，以及具有不確定加工時間的雙機流水車間逆調度模型，并證明了問題的NP-hard屬性。范洪長等［13］提出了相同并行機逆調度模型，通過最小程度改變加工時間和權重來優化總加權完工時間，采用二次規劃法求得最優解。早期的逆調度研究側重于理論，近年來，一些學者設計了優化算法來解決實際逆調度問題，取得了良好效果。牟健慧等［14］將遺傳算法與變鄰域搜索算法相結合，提出了三種混合算法求解具有可調整交貨期的單機逆調度問題，實驗結果表明，交替與協同搜索效果優于單一算法求解效果。WANG等［15］探討了焊接車間的逆調度問題，通過調整焊機數量來改變焊接時間，并在改進灰狼算法中設計了矩陣編碼方式，同時采用外部檔案機制，有效提高了算法收斂速度。ZHANG等［16］針對汽輪機裝配問題，采用調整工人加班的方式進行逆優化，并設計了結合禁忌搜索的粒子群優化算法，通過實際案例分析驗證了算法的優越性。牟健慧等［17］建立了分布式流水車間逆調度模型，以最小化資源調整量和機器能耗為目標，并設計了基于啟發式規則的混合遺傳算法進行求解，在多規模的算例下，該算法的表現均優于傳統遺傳算法和粒子群算法。針對柔性作業車間逆調度問題，WU等［18］開發了一種離散粒子群優化算法，并設計了混合初始化方式，該算法與NSGA-Ⅱ和SPEA-Ⅱ等算法相比具有優勢。

現有的逆調度研究主要針對單機和流水車間進行建模，鮮有研究關注柔性作業車間。在參數或資源調整范圍的設定上，多數研究采用隨機生成或人為規定的方式，未能充分考慮實際生產環境、加工特征等限制因素，這可能導致優化結果不準確或不可行。此外，工人作為生產系統中不可或缺的資源，在逆調度優化中應該被進一步考慮。在逆調度模型求解方面，精確求解方法和智能算法是兩種常用的方法。然而，相比精確方法，智能算法在求解速度和魯棒性上更具優勢，特別是在處理復雜、大規模問題時能夠快速找到近似解。因此，有必要建立符合實際柔性作業車間特征的逆調度模型，并開發高性能優化算法。

本文考慮機器與工人資源約束，研究機械加工車間逆調度問題，通過調整工件排產、工人作業以及機械加工參數來優化原始調度。以最小化完工時間、機器能耗以及逆偏差指數為目標建立多目標數學模型，并提出了一種改進差分進化算法。最后通過算例測試和實際案例分析來驗證逆調度方法的有效性。

1問題描述與模型的建立

本文研究的逆調度問題描述如下：在機械加工車間內，共有J個待加工工件，M臺加工機器以及W名工人。工件j具有θj道順序固定的工序，各道工序均需要選擇一臺可行機器加工，原始調度中第k道工序Ojk在機器m上的加工時間為Tjkm。機器加工需要工人輔助，工人可以在生產過程中操作多臺機器，但一次只能操作一臺，工人w在機器m上的加工效率為emw（emwSymbolNC@［0，1］）［7］。此外，機械加工參數同樣影響生產，與加工時間、機器能耗等指標密切相關。工序Ojk在機器m上的主要加工參數包括進給速度、主軸轉速、切削力及切削速度等。車間的原始調度方案包括各工序的加工機器、處理工人、加工參數（采用最優參數加工），以及每臺機器上操作的處理順序。然而，該調度方案可能不是最優的，甚至當動態事件發生時可能不再可行，因此需要采取逆調度策略進行調整。對于機械加工車間，工件的加工機器、加工順序不能隨意變動，但工人作業可以靈活調整，同時部分機械加工參數也可以基于最優參數在一定范圍內進行選擇。逆調度通過合理調整以上資源對原始調度進行優化，以提高車間整體生產水平。

為便于建立問題模型，給出以下假設：①在零時刻，所有工件均可被加工、所有機器和工人都已準備好；②一臺機器同時最多處理一個工件，一個工人同時最多操作一臺機器；③每道工序在一臺機器上由一名符合要求的工人加工，不能中斷；④不同工件的工序間沒有順序要求；⑤不考慮工件的轉運時間以及機器的準備時間。

基于以上描述和假設，建立數學模型。參數說明如下：C′max為逆調度的總完工時間；Pm為機器m的待機功率；R′m為逆調度中機器m的運行結束時間；T′jkm為工序Ojk在逆調度中的加工時間；P′jkm為逆調度中機器m加工Ojk的功率；r為調整加工參數的懲罰系數；T′jk為逆調度中Ojk的開始加工時間；njkm為Ojk在機器m上的原始即最優加工轉速；fjkm為原始即最優進給速度；n′jkm和f′jkm分別為逆調度中的主軸轉速和進給速度；F′jkm和v′jkm分別為逆調度中的切削力和切削速度；A1和B1分別為與轉速相關的系數；［njkm，n-jkm］為逆調度中主軸轉速的調整區間；［f-jkm，f-jkm］為進給速度的調整區間；xjkm為決策變量，若Ojk在原始調度中由機器m加工，其值為1，否則為0；yjkw為決策變量，若Ojk在原始調度中由工人w加工，其值為1，否則為0；x′jkm為決策變量，若Ojk在逆調度中在機器m上加工，其值為1，否則為0；y′jkw為決策變量，若Ojk在逆調度中由工人w加工，其值為1，否則為0；z′jkm為決策變量，若在逆調度中Ojk的加工參數發生變化，其值為1，否則為0；α（jklh）m為決策變量，若逆調度中Ojk為Olh在機器m上的緊前工序，其值為1，否則為0；β（jklh）m為決策變量，若逆調度中Ojk為Olh在工人w連續加工的前后兩道工序，其值為1，否則為0。

模型的目標為最小化完工時間、機器能耗及逆偏差指數。機器能耗由待機能耗和加工能耗兩部分組成，由于能耗受加工參數影響，且在逆調度中加工參數應盡可能保持不變，故在該目標中額外考慮了參數調整懲罰。逆偏差指數用來約束逆調度與原調度間的差異，由工序開始時間偏差ds、機器加工偏差dm及工人加工偏差dw組成。其中，ds為所有工序開始時間偏差之和；dm為所有工序的加工機器改變量之和，以最大程度保留原始加工路徑；同理，dw為所有工序的操作工人改變次數之和，以最大程度保留原始工人作業。三個目標的數學公式如下：

以上逆調度約束中，式（7）表示總完工時間為最后一個工件的加工完成時間；式（8）表示根據工人水平和加工參數計算各工序的加工時間；式（9）表示機器在加工完最后一道工序后停止運行；式（10）用于計算各工序的加工能耗；式（11）表示各道工序必須在一臺機器上加工；式（12）表示各道工序必須有一名操作工人；式（13）表示同一個工件的相鄰工序需要滿足順序約束；式（14）表示一臺機器同時最多只能完成一個操作，且一個工人同時最多只能操作一臺機器；式（15）和式（16）表示主軸轉速和進給速度只能在規定范圍內調整。

上述模型中，針對不同機加工方式，需要分別計算切削力和切削速度。常見的機加工方法包括車削、銑削和鉆削加工。車削加工的切削力和切削速度的計算公式如下：

2改進差分進化算法

差分進化（differentialevolutionalgorithm，DE）算法是一種基于群體差異的隨機搜索算法，包括交叉、變異、選擇等操作，具有結構簡單、魯棒性強等優點，已成功應用于車間調度問題［19］。然而，現有差分進化算法僅針對正向調度設計，不完全適用于逆調度問題，同時傳統差分算法為連續型算法，不適用于離散問題，因此，本文針對問題特征改進了差分進化機制，并設計了編解碼、初始化、局部搜索等策略以高效求解問題。改進差分進化（improveddifferentialevolution，IDE）算法流程如圖1所示。

2.1編碼與解碼

編碼和解碼是解決染色體與解之間轉換的關鍵。傳統調度問題通常采用基于操作序列的編碼方式，即使用作業編號生成一組長度為總工序數的序列OS，作業j在OS中出現的第k次代表工序Ojk，OS從左到右的順序表示工序的加工順序。此方法在正向調度中簡潔有效，但在逆調度中需要考慮額外的資源約束，包括加工機器、操作人員和機加工參數，因此不再適用。為解決該問題，本文提出了一種混合雙層編碼方式，采用序列OS來表示工序順序，同時設計了混合矩陣PM表示加工信息。這種編碼方式既保留了傳統編碼的優點，又充分考慮了逆調度中的資源約束，為求解逆調度問題提供了新思路。

在PM中，列和行分別表示工件和工序，每個元素的十位數字表示加工機器，個位數字表示操作工人，前兩位小數為進給速度調整系數，后兩位小數為主軸轉速調整系數。這種編碼簡單且高效，可以在一串字符中運行6層信息，同時在迭代過程中無需修正，降低了計算復雜度。

對于車間調度問題，半主動解碼是一種簡單有效的解碼方式［20］，已被廣泛使用。本文基于該方法進行解碼，具體步驟如下：從左到右依次對OS中工序進行解碼，工序的加工機器、處理工人以及加工參數由PM決定，各工序安排在最早可開始時間加工，每當一道工序完成后，相應的機器、工人等資源立即轉移到下一道目標工序。

為具體闡述本文編碼、解碼方法，舉例說明。圖2中，PM中的第3列第2行的元素為工序O32的加工信息：十位數字2表示該工序由第2臺可行機器M3加工；個位數字2表示由2號工人加工；前兩位小數為0表示進給速度與原調度保持一致；后兩位小數32表示主軸轉速需要調整。若32∈（0，100（n－n）/（n-－n）］，其中，n為原調度中主軸轉速，［n，n-］為逆調度轉速調整范圍，則降低轉速為n′=n－32［（n-－n）/100］；否則提高轉速為n′=n+32［（n-－n）/100］。

2.2種群初始化

初始種群質量直接影響算法的搜索精度和收斂速度，對求解多目標問題至關重要。逆調度是對原始調度的調整，且目標之一是減少更新調度與原始調度之間的偏差，因此，如果能夠合理利用原始調度信息初始化種群，則可以有效提高種群質量。基于此，本文設計了兩種初始化規則，同時為提高種群多樣性，部分初始個體隨機生成。

2.2.1基于原始關鍵路徑初始化

關鍵路徑是工件加工時間最長的路徑，它決定了調度方案的完工時間。通過調整非關鍵路徑上的工序加工，可以在保持原始調度方案總體框架不變的前提下進行局部優化，從而提高整體效率。此方法能減少對原始調度的干擾，降低逆偏差指數。因此，本文提出了一種基于原始關鍵路徑的初始化策略，具體步驟如下：

（1）在逆調度中保留原始關鍵路徑，隨后隨機選擇一道非關鍵路徑上的工序，各工序最多被選擇一次。

（2）判斷該工序是否能在其他可選機器的加工空閑間隔內加工（加工空閑間隔是指同一臺機器處理相鄰兩道工序的間隔時間），若是，則隨機選擇一個間隔安排該工件加工；否則隨機提高該工序加工參數或更換效率更高的工人。

（3）判斷是否所有非關鍵工序均被選擇，若是，則輸出當前調度方案作為初始個體；否則返回步驟（1）。

圖3為該初始策略的示意圖，圖3中工序右上方數字為加工時間，中間數字為編碼，藍色工序屬于關鍵路徑，可以看出，原始關鍵路徑為O11→O12→O21→O22。首先隨機選擇工序O41，將其插入M2的空閑時間加工，隨后選擇工序O31，由于該工序無法在其他機器的空閑時間內加工，故隨機提高其加工參數，此時所有非關鍵工序均被選擇，輸出該解作為初始個體。

2.2.2基于原始加工狀態初始化

若在逆調度中完全改變原始機加工參數和工人安排，勢必會影響生產系統穩定性，因此，本文設計了基于原始加工狀態的初始化策略，同時兼顧了完工時間與能耗目標，具體步驟如下：

（1）隨機選擇一個工序，并確保每個工序只被選擇一次。

（2）隨機改變當前工序的進給速度和主軸轉速，并計算新參數下的加工時間和加工能耗。

（3）比較原始參數和新參數，若新參數下的加工時間和能耗均優于原始參數，則替換原始參數，轉到步驟（5）；否則轉到步驟（4）。

（4）隨機改變當前工序的加工工人，并根據以下三種情況判斷是否保留新工人和新參數。

①若當前工序在新參數下由新工人加工的加工時間和機器能耗均變優，則保留；

②若新工人的加工效率為其他所有可選工人中最高的，則保留；

③若非以上兩種情況，則引入模擬退火Metropolis準則，根據下式以一定概率接受新參數和新工人：

式中，p為接受概率；i為加工時間和機器能耗兩個目標值的索引；fi（x）、fi（x）分別為新目標值和原始目標值；Ti為退火溫度。

（5）隨機選擇下一道工序，直到所有工序均被選擇，并輸出最終方案作為初始個體。

2.3變異與交叉

在差分進化算法中，個體Xi通過DE/rand/1策略進行變異，根據三個不同隨機數式中r1、r2和r（r1≠r2≠r3≠i）以及縮放因子F生成變異個體Vi：

上式適用于連續空間問題，但逆調度問題屬于離散優化問題，因此，需要對上式中相減、相加以及相乘運算進行離散化處理。兩層編碼采用相同的離散策略，具體定義如下。

定義1減法操作⊙：兩串編碼對應位置處元素相減得到交換對，直至編碼相等。舉例如下：編碼X2={3，1，5，2，4}，X3={4，3，5，1，1}，X2與X3第一位元素不同，對X3執行（3，4）交換操作，得到X′3={3，4，5，1，2}，再次對X′3進行（1，4）位置交換，得到X″3={3，1，5，4，2}，最后交換X″3的（2，4）位置，此時X3=X2，減法運算結束，如圖4所示。該減法操作表示如下：X2⊙X3={（3，4），（1，4），（2，4）}。

定義2乘法操作SymbolDC@：縮放因子F與減法運算得到的交換對數量相乘，結果取整，得到新的交換對。以上述交換對{（3，4），（1，4），（2，4）}為例，交換對個數為3，若F為0.6，則乘積為1.8，取整后為2，對應交換對為{（3，4），（1，4）}，即FSymbolDC@

：依據乘法操作得到交換對，交換相應位置處元素。例如：交換對為{（3，4），（1，4）}，對X1={5，3，2，4，1}進行加法操作，得到X3SymbolEC@

{（3，4），（1，4）}={5，1，2，3，4}。

在搜索初始階段，大概率變異、小概率交叉能夠擴大算法搜索范圍，從而提高種群多樣性，有更大機會獲得全局最優解；而在搜索后期，小概率變異、大概率交叉能夠保留種群中優秀基因，有利于局部搜索［21］。因此，本文設計了自適應交叉、變異策略以平衡算法搜索與開發能力。

在變異操作中，根據下式計算縮放因子F：

交叉操作具體步驟如下。

（1）設置交叉概率RC：

（2）生成與OS長度相等的隨機序列si以及與PM大小相等的隨機矩陣mi，二者中元素均屬于0到1。

（3）比較si中元素與RC的大小，若元素小于RC則復制個體V的染色體中對應位置基因到U；否則復制X的相應位置基因到U。

（4）比較mi中元素與RC的大小，若元素小于RC則復制個體V的相應位置基因到U；否則復制X的對應基因到U。

2.4選擇操作

完成變異、交叉后，對種群進行保留。傳統差分進化算法的貪婪選擇并不適用于多目標問題，因此引入非支配排序遺傳算法（non-dominatedsortedgeneticalgorithm，NSGA-Ⅱ）的選擇策略，優先將Pareto個體加入新種群。對于互不支配的個體，NSGA-Ⅱ通過計算擁擠度距離進行比較，但該方法在本文中并不適用。一方面，不同于傳統調度，逆調度的解均源于對同一原始調度的調整，且調整原則為最小限度改變原始資源或參數，因此存在擁擠度距離相差不大的情況；另一方面，決策空間兩個完全不同的解在目標空間的適應度仍可能相等。因此，本文設計了一種基于哈明距離（hammingdisdtance，HD）的擁擠度算子以反映種群的真實多樣性。

哈明距離是指兩條染色體中相應位置上的不同基因的數量［22］。IHD（A，B）定義為個體A與B的PM層編碼中整數部分與小數部分的哈明距離之和，如圖5所示。個體xi的擁擠度值是該個體和其他個體之間兩個最小IHD的平均值，記為DIHD（xi），其計算公式為

2.5局部搜索

在局部搜索中需要解決兩個關鍵問題：一是如何選擇個體進行搜索，二是進行怎樣的搜索。針對問題一，設計一種與文獻［23］類似的錦標賽機制，主要步驟如下：

（1）根據下式生成一組符合均勻分布的權重標量：

（2）隨機選擇一個向量λ，并從種群中隨機選擇st個個體。

（3）根據下式計算st個個體的臨時適應度值：

（4）對臨時適應度值最低的個體進行局部搜索，并在種群中更新個體。

（5）重復步驟（2）～（4）|Pls·N|次，其中，Pls為局部搜索概率，N為種群大小，因此共有|Pls·N|個個體被更新。

針對問題二，首先定義以下四種鄰域結構：

鄰域1：在OS中隨機選擇三道工序，交換它們的位置，所有新序列構成N1。

鄰域2：隨機選擇PM中的一道工序，更換其加工機器和工人，所有新組合構成N2。

鄰域3：分別在區間［5，10］和［15，20］中隨機生成調整量SymbolDA@

鄰域4：隨機選擇PM中n個工件，即n列，然后該n列中的基因被種群中另一隨機非支配解的對應位置基因隨機替換，所有新PM構成N4。

隨后基于以上四種鄰域進行局部搜索。需要說明的是，逆調度的基本原則是最小化調整資源和參數，且在實際生產中應盡量保證生產系統的穩定性，因此在局部搜索過程中，對于互不支配的兩個個體，本文優先考慮逆偏差指數較小的解。局部搜索過程偽代碼如下：

3實驗分析

3.1算例生成與評價指標

由于本文首次研究機械加工車間逆調度問題，無法直接使用已有測試集，故對柔性作業車間標準算例進行拓展以驗證算法性能。生成33組算例，其中算例IMK01～IMK15基于BRANDIMARE等［24］提出的MK01～MK15，算例I01a～I18a基于DAUZRE-PRS等［25］提出的01a～18a。算例生成步驟如下：工件和機器數據與標準算例一致；工人按加工能力分為初級、中級和高級，加工效率分別為0.8、1和1.2，各等級工人數量屬于離散均勻隨機數DU（1，m/2），其中m為標準算例中機器數量；加工直徑djk均勻分布于U［20mm，100mm］，加工深度屬于U［1mm，4mm］，機器待機功率屬于U［0.5kW，2.5kW］；各工序的基本進給速度和主軸轉速分別屬于區間U［0.1mm/r，2.0mm/r］和U［300r/min，1800r/min］，隨后在此基礎上乘以隨機數rand（0.8，1.2）以生成各工序在各機器上的最優加工參數njkm和fjkm。在實際生產中，并非所有工序的加工參數均能調整，因此對每道工序生成一個屬于0～1的隨機數，若小于0.5則設置對應工序加工參數調整范圍為［0.7njkm，1.3njkm］以及［0.7fjkm，1.3fjkm］，否則相應參數在逆調度中無法改變，即njkm=njkm=n-jkm，f-jkm=fjkm=f-jkm；算例中其他機加工參數依據文獻［26］設置。

算法運行環境為Windows10操作系統，編程環境為MATLAB2017b。各算例下各算法均獨立運行10次，且同一算例下運行時間一致，為∑Jj=1θj（s）。采用三種指標評價多目標結果：SP、IGD以及HV。其中，SP值用于評價多樣性，SP值越小說明解集多樣性越好；IGD值和HV值為綜合指標，用于同時衡量多樣性和收斂性，IGD值越小、HV值越大，說明算法綜合性能越好。在評價過程中，由于真實Pareto前沿可能是未知的，故將其設置為所有算法求得所有解的非支配解集，此外，為了消除不同目標維度對指標結果的影響，所有目標值通過下式進行歸一化：

3.2參數設置

改進差分進化算法中主要參數包括種群大小N，基于原始關鍵路徑的初始概率r1，基于原始加工狀態的初始概率r2，鄰域搜索概率Pls，以及鄰域搜索次數loop。本文自適應變異與交叉概率上下界分別設為0.8和0.2，并在此基礎上采用田口法確定其他參數最佳組合，各參數合理設置四個水平：NSymbolNC@

每種參數組合均在算例IMK06上獨立運行10次，使用IGD指標對結果進行評價，圖6為各參數水平趨勢圖，從圖6中可以選擇最佳參數組合：N=80，r1=0.2，r2=0.2，Pls=0.3，loop=20。

3.3策略有效性分析

為驗證本文初始化、交叉變異，以及局部搜索的有效性，構建三種變體算法與IDE算法進行比較，其中，IDE-α為采用完全隨機初始化的IDE算法，IDE-β為缺少自適應變異與交叉的IDE算法，IDE-γ為缺少局部搜索的IDE算法。采用三種指標對算法進行評價，結果見表1，表1中最優值加粗表示。

對比IDE算法與IDE-α算法可以看出，IDE算法在三個指標上均顯著優于IDE-α算法，這有力地證明了本文初始化方法的有效性。其原因是，兩種初始化策略能夠在降低偏差指數的基礎上同時優化其他目標，使得部分初始個體具有良好的適應度值；此外隨機初始個體保證了種群整體的多樣性，避免算法過早收斂。

IDE算法相對于IDE-β算法的優勢同樣明顯，其所有指標在所有算例上均優于IDE-β算法，

這是因為自適應交叉、變異在前期擴大了算法搜索范圍，而在后期保留了較優個體，有利于局部搜索。該結果同時也說明局部搜索中精英選擇策略與全局搜索配合良好，能夠在節約搜索時間的同時為變異操作提供高質量非支配解，有利于種群進化。

對比IDE和IDE-γ算法可以發現，雖然IDE算法在指標SP上稍遜于IDE-γ算法，但在所有算例上的IGD值和HV值均明顯優于IDE-γ算法。這是因為在有限的搜索時間內，相較于交叉與變異，局部搜索在一定程度上限制了算法擴大搜索范圍，使得種群多樣性下降，但該策略卻能有效提高種群質量，同時加快算法收斂。整體來說，局部搜索策略對提高IDE算法的性能仍是關鍵且有效的。

對比三種變體算法可以看出，IDE-β算法的指標結果相較于IDE-α和IDE-γ算法更具有優勢，說明自適應變異、交叉策略對算法性能的改善效果最為顯著，而IDE-α和IDE-γ算法的指標值相差不大，說明在提高IDE算法性能方面效果大致相同。

3.4與其他算法對比分析

為進一步驗證算法性能，同時驗證本文選擇操作的有效性，將IDE算法與廣泛應用的NSGA-Ⅱ算法［27］、NSGA-Ⅲ算法［28］進行對比。由于這兩種算法均基于遺傳進化原理，且采用不同的種群保留機制，故與IDE算法具有相似性和可比性。為公平比較，所有對比算法的參數以及編碼、解碼方式均與IDE算法一致，并且從本文中選擇相應算子。

各算法獨立運行10次后SP、IGD以及HV指標均值統計結果見表2，可以看出，在33個算例上，IDE算法分別取得了23個最小SP值、29個最小IGD值，以及27個最大HV值，與NSGA-Ⅱ和NSGA-Ⅲ算法相比優勢明顯。IDE算法的優勢可歸于以下幾點：首先，IDE算法的自適應交叉與變異策略很好地平衡了開發和探索，能夠在有限時間內合理利用計算資源；其次，IDE算法的搜索結構加強了種群個體間的動態交流，有效提高了搜索效率和精度；最后，IDE算法采取基于改進哈明距離的種群保留策略，而非基于擁擠度距離或參考點選擇個體，這種方式更加符合問題和編碼特征，可以在更大程度上保證種群質量和多樣性。

4工程案例分析

我國某機械加工車間主要生產高端液壓缸設備，圖7所示為車間真實情況。圖8所示為該車間生產的一種夾緊缸，主要由油封口鋼板、缸蓋、缸體以及活塞桿四部分組成，四個工件的工藝信息見表3～表6，表中參數為原始加工方案中的最優加工參數。本文以該夾緊缸生產為例，分析兩種不同動態環境下的真實逆調度案例。

車間內共有8名工人及8臺機器參與生產。工人包括3名初級工人、3名中級工人及2名高級工人，每名工人均能操作所有機器，但效率不同，三個等級依次為0.8、1、1.2。機器包括車床、銑床、鏜床、鉆床等類型，各機器待機功率見表7。

該車間需要同時生產三臺相同的夾緊缸，因此共有12個工件被加工，為便于說明，對工件進行編號如下：1～3號工件為封油口鋼板，4～6號工件為缸蓋，7～9號工件為缸體，10～12號工件為活塞桿。圖9為原始調度方案甘特圖，該方案的完工時間為4474.6min，機器能耗為6290.2kW·h，圖9中括號中數字表示操作的工件工序和工人等級（初級為1，中級為2，高級為3）。

機器故障是機械加工車間常見的動態事件，在該車間，機器M4在2000～2500min發生故障，無法安排加工，在這種情況下，通過逆調度對原始調度進行優化。將IDE算法與NSGA-Ⅱ、NSGA-Ⅲ算法以及同樣基于遺傳思想的SPEA-Ⅱ算法［29］（strengthparetoevolutionaryalgorithm-Ⅱ）和NNIA算法［30］（non-dominatedneighborimmunealgorithm）進行對比。圖10為5種算法分別獨立運行10次得到的指標箱線圖，可以看出，IDE算法在三個指標上的平均值和穩定性均明顯優于對比算法，這說明IDE算法的多樣性、均勻性以及收斂性更優。圖11展示了5種算法在迭代過程中的最優IGD值，其中IDE算法的初始解質量更優，且迭代過程中收斂速度最快。

圖12所示為Pareto前沿比較，IDE算法求得的解決方案更靠近坐標原點，特別在能耗指標上具有優勢。工人短缺同樣是影響機加工車間的重要動態事件，當各等級工人均減少1名即共有2名初級工人、2名中級工人以及1名高級工人參與生產時進行逆調度時，此時5種算法的指標對比箱線圖見圖13，可以看出，IDE算法的所有指標結果均為最優，說明該算法搜索能力強、綜合性能好。圖14為IGD指標迭代圖，5種算法的收斂性從大到小依次是：IDE，NSGA-Ⅲ，NSGA-Ⅱ，NNIA，SPEA-Ⅱ。圖15所示為5種算法輸出的一組Pareto前沿，可以看出在各目標函數值整體上IDE算法均優于對比算法，能夠有效解決實際問題。

在機器故障下，IDE算法輸出的一個最優逆調度甘特圖見圖16，圖中白色數字表示操作加工時間的改變量，該方案的逆偏差指數為379.2，完工時間為4120.7min，機器能耗為4969.8kW·h，相比原始調度分別減小7.9%和21.0%。圖17為工人短缺情況下通過IDE算法得到的逆調度甘特圖，該方案完工時間相比原方案完工時間減少0.5%，為4452.0min；機器能耗減少19.4%，為5072.0kW·h，同時逆偏差指數為408.5，可以在較小改變原始調度的情況下合理應對動態事件。

5結語

本文基于兩組標準算例構建了33個擴展算例，驗證了IDE算法在指標SP、IGD和HV上優于其3種變體算法以及NSGA-Ⅱ和NSGA-Ⅲ算法。分析了兩個實際液壓缸生產車間逆調度案例，結果表明，相比NSGA-Ⅱ、NSGA-Ⅲ、SPEA-Ⅱ和NNIA算法，IDE算法的多樣性、均勻性和收斂性均為最優，能夠在較小程度改變原始調度的情況下，平均縮短4.2%的完工時間、降低20.2%的機器能耗。

本文問題源于工程實際，具有較強的理論意義和現實應用價值，但仍存在以下不足：首先，機械加工工藝復雜且多樣，可以進一步針對工藝特點設計逆調度策略；其次，可考慮與機械加工車間其他重要系統（如輔助和搬運系統）的聯合逆調度優化；最后，結合強化學習、深度學習等技術可提高逆調度方法在動態優化方面的效率和適用性。

參考文獻：

［1］臧冀原，劉宇飛，王柏村，等.面向2035的智能制造技術預見和路線圖研究［J］.機械工程學報，2022，58（4）：285-308.

ZANGJiyuan，LIUYufei，WANGBaicun，etal.TechnologyForecastingandRoadmappingofIntelligentManufacturingby2035［J］.JournalofMechanicalEngineering，2022，58（4）：285-308.

［2］TANWeihua，YUANXiaofang，WANGJinlei，etal.AFatigue-consciousDualResourceConstrainedFlexibleJobShopSchedulingProblembyEnhancedNSGA-Ⅱ：anApplicationfromCastingWorkshop［J］.Computersamp;IndustrialEngineering，2021，160：1-17.

［3］梁向檁，宋豫川，雷琦，等.考慮工人數量配置優化的柔性作業車間調度問題研究［J］.中國機械工程，2023，34（17）：2065-2076.

LIANGXianglin，SONGYuchuan，LEIQi，etal.ResearchonFlexibleJob-shopSchedulingProblemsConsideringOptimizationofWorkerNumberAllocation［J］.ChinaMechanicalEngineering，2023，34（17）：2065-2076.

［4］FABIAND，STEFANN.AMulti-methodApproachtoSchedulingandEfficiencyAnalysisinDual-resourceConstrainedJobShopswithProcessingTimeUncertainty［J］.Computersamp;IndustrialEngineering，2022，168：108067.

［5］易茜，何爽，寧輕，等.汽車試制車間考慮員工作業能力的多目標優化生產調度［J］.中國機械工程，2021，32（13）：1617-1629.

YIQian，HEShuang，NINGQing，etal.AnMulti-objectiveOptimizedProductionSchedulingforAutomobilePrototypeWorkshopsConsideringEmployeeWorkAbility［J］.ChinaMechanicalEngineering，2021，32（13）：1617-1629.

［6］JIANGTianhua，ZHUHuiqi，GUJiuchun，etal.ADiscreteAnimalMigrationAlgorithmforDual-resourceConstrainedEnergy-savingFlexibleJobShopSchedulingProblem［J］.JournalofIntelligentamp;FuzzySystems，2022，42（4）：3431-3444.

［7］孫愛紅，宋豫川，楊云帆，等.考慮關鍵件加工質量的雙資源約束車間調度算法［J］.中國機械工程，2022，33（21）：2590-2600.

SUNAihong，SONGYuchuan，YANGYunfan，etal.DualResource-constrainedFlexibleJobShopSchedulingAlgorithmConsideringMachiningQualityofKeyJobs［J］.ChinaMechanicalEngineering，2022，33（21）：2590-2600.

［8］呂巖，徐正軍，李聰波，等.考慮擾動事件的機械加工工藝參數與車間動態調度綜合節能優化［J］.機械工程學報，2022，58（19）：242-255.

LYUYan，XUZhengjun，LICongbo，etal.ComprehensiveEnergySavingOptimizationofProcessingParametersandJobShopDynamicSchedulingConsideringDisturbanceEvents［J］.JournalofMechanicalEngineering，2022，58（19）：242-255.

［9］SANGYanwei，TANJianping，LIUWen.ANewMany-objectiveGreenDynamicSchedulingDisruptionManagementApproachforMachiningWorkshopBasedonGreenManufacturing［J］.JournalofCleanerProduction，2021，297：126489.

［10］KOULAMASC.InverseSchedulingwithControllableJobParameters［J］.InternationalJournalofServicesandOperationsManagement，2005，1（1）：35-43.

［11］BRUCKERP，SHAKHLEVICHNV.InverseSchedulingwithMaximumLatenessObjective［J］.JournalofScheduling，2009，12：475-488.

［12］BRUCKERP，SHAKHLEVICHNV.InverseScheduling：Two-machineFlow-shopProblem［J］.JournalofScheduling，2011，14：239-256.

［13］范洪長，魯習文.平行機上單位加工時間加權總完工時間排序問題的反問題［J］.華東理工大學學報，2012，38（6）：757-761.

FANHongchang，LUXiwen.InverseProblemofTotalWeightedCompletionTimeObjecivewithUnitProcessingTimeonIdenticalParallelMachines［J］.JournalofEastChinaUniversityofScienceandTechnology，2012，38（6）：757-761.

［14］牟健慧，潘全科，牟建彩，等.基于遺傳變鄰域混合算法的帶交貨期的單機車間逆調度方法［J］.機械工程學報，2018，54（3）：148-159.

MOUJianhui，PANQuanke，MOUJiancai，etal.ResearchonSingle-machineInverseSchedulingMethodswithDue-datesBasedonVariableNeighborhoodSearchHybridAlgorithm［J］.JournalofMechanicalEngineering，2018，54（3）：148-159.

［15］WANGCuiyu，ZHAOLi，LIXinyu，etal.AnImprovedGreyWolfOptimizerforWeldingShopInverseScheduling［J］.Computersamp;IndustrialEngineering，2022，163：107809.

［16］ZHANGYahui，HUXiaofeng，CAOXianfeng，etal.AnEfficientHybridIntegerandCategoricalParticleSwarmOptimizationAlgorithmfortheMulti-modeMulti-projectInverseSchedulingProbleminTurbineAssemblyWorkshop［J］.Computersamp;IndustrialEngineering，2022，169：108148.

［17］牟健慧，段培永，高亮，等.基于混合遺傳算法求解分布式流水車間逆調度問題［J］.機械工程學報，2022，58（6）：295-308.

MOUJianhui，DUANPeiyong，GAOLiang，etal.HybridGeneticAlgorithmforDistributedFlowShopInverseSchedulingProblem［J］.JournalofMechanicalEngineering，2022，58（6）：295-308.

［18］WURui，LIYibing，GUOShunsheng，etal.AnEfficientMeta-heuristicforMulti-objectiveFlexibleJobShopInverseSchedulingProblem［J］.IEEEAccess，2018，6：59515-59527.

［19］CAOYang，SHIHaibo，CHANGDaliang.DifferentialEvolutionAlgorithmwithDynamicMulti-populationAppliedtoFlexibleJobShopSchedule［J］.EngineeringOptimization，2022，54（3）：387-408.

［20］ZHANGGuohui，SUNJinghe，LIUXing，etal.SolvingFlexibleJobShopSchedulingProblemsWithTransportationTimeBasedonImprovedGeneticAlgorithm［J］.MathematicalBiosciencesandEngineering，2019，16（3）：1334-1347.

［21］張源，陶翼飛，王加冕.改進差分進化算法求解混合流水車間調度問題［J］.中國機械工程，2021，32（6）：714-720.

ZHANGYuan，TAOYifei，WANGJiamian.AnImprovedDEAlgorithmforSolvingHybridFlow-shopSchedulingProblems［J］.ChinaMechanicalEngineering，2021，32（6）：714-720.

［22］牟健慧，郭前建，高亮，等.基于混合的多目標遺傳算法的多目標流水車間逆調度問題求解方法［J］.機械工程學報，2016，52（22）：186-197.

MOUJianhui，GUOQianjian，GAOLiang，etal.Multi-objectiveGeneticAlgorithmforSolvingMulti-objectiveFlow-shopInverseSchedulingProblems［J］.JournalofMechanicalEngineering，2016，52（22）：186-197.

［23］WANGChun，TIANNa，JIZhicheng，etal.Multi-objectiveFuzzyFlexibleJobShopSchedulingUsingMemeticAlgorithm［J］.JournalofStatisticalComputationandSimulation，2017，87（14）：2828-2846.

［24］BRANDIMARTEP.RoutingandSchedulinginaFlexibleJobShopbyTabuSearch［J］.AnnalsofOperationsResearch，1993，41（3）：157-183.

［25］DAUZRE-PRSS，PAULLIJ.AnIntegratedApproachforModelingandSolvingtheGeneralMultiprocessorJob-shopSchedulingProblemUsingTabusearch［J］.AnnalsofOperationsResearch，1997，70：281-306.

［26］LINWenwen，YUD.Y，ZHANGChaoyong，etal.AMulti-objectiveTeaching-learning-basedOptimizationAlgorithmtoSchedulinginTurningProcessesforMinimizingMakespanandCarbonFootprint［J］.JournalofCleanerProduction，2015，101：337-347.

［27］DEBK，PRATAPA，AGARWALS，etal.AFastandElitistMultiobjectiveGeneticAlgorithm：NSGA-Ⅱ［J］.IEEETransactionsonEvolutionaryComputation，2002，6（2）：182-197.

［28］DEBK，JAINH.AnEvolutionaryMany-objectiveOptimizationAlgorithmUsingReference-point-basedNondominatedSortingApproach，PartI：SolvingProblemswithBoxConstraints［J］.IEEETransactionsonEvolutionaryComputation，2013，18（4）：577-601.

［29］ZITZLERE，LAUMANNSM，THIELEL.SPEA2：ImprovingtheStrengthParetoEvolutionaryAlgorithm［C］∥ProceedingsoftheConferenceonEvolutionaryMethodsforDesign，OptimizationandControlwithApplicationstoIndustrialProblems.Athens，Greece，2001：95-100.

［30］GONGMaoguo，JIAOLicheng，DUHaifeng，etal.MultiobjectiveImmuneAlgorithmwithNondominatedNeighbor-basedSelection［J］.EvolutionaryComputation，2008，16（2）：225-255.