混合流水車間插單重調度的超啟發式遺傳算法

劉思宇 李鐵克 王柏琳 袁帥鵬 張文新

摘 要：針對帶有緊急訂單的混合流水車間插單重調度問題，提出了一種雙層編碼的超啟發式遺傳算法。針對混合流水車間具有的訂單排序和機器選擇的雙決策特征，在算法低層設計雙層編碼方案，在個體中表示訂單排序和機器選擇兩類信息，對應一個唯一調度解，進而提出了12種排序和選擇啟發式對個體進行迭代優化；在算法高層采用自適應遺傳算法，用來確定訂單排序啟發式和機器選擇啟發式的操作組合以及各組合執行的次序，并設計了自適應變異算子來優化算法的有效性。大規模數據實驗的結果表明，所提算法具有很好的求解質量和求解效率。

關鍵詞：重調度； 混合流水車間； 超啟發式； 遺傳算法； 緊急插單

中圖分類號：TP205?? 文獻標志碼：A

文章編號：1001-3695（2023）09-007-0000-00

doi：10.19734/j.issn.1001-3695.2022.12.0831

Hyper-heuristic genetic algorithm for hybrid flow shop with

rush orders insertion rescheduling problem

Liu Siyu1，2， Li Tieke1，2， Wang Bailin1，2， Yuan Shuaipeng1，2， Zhang Wenxin1，2

（1.School of Economics & Management， University of Science & Technology Beijing， Beijing 100083， China; 2.Engineering Research Center of MES Technology for Iron & Steel Production， Ministry of Education， Beijing 100083， China）

Abstract：Aiming at the rescheduling problems of hybrid flow shop with rush order insertion， this paper proposed a hyper-heuristic genetic algorithm based on the two-layer coding. Aiming at the double-decision characteristics of order sort and machine selection in the hybrid flow shop， this algorithm designed a two-layer coding scheme in the low level. Each individual represented both order sort and machine selection information， and corresponded to a unique scheduling solution. Then the low level proposed 12 kinds of sorting and selection heuristics for iterative optimization of individuals. The high level of the algorithm used an adaptive genetic algorithm to determine the operation combination of order sort heuristic and machine selection heuristic and the sort of execution of each combination. And it designed an adaptive mutation operator to optimize the effectiveness of the algorithm. The results of large-scale data experiments show that the proposed algorithm has good solving quality and efficiency.

Key words：insertion rescheduling; hybrid flow shop; hyper-heuristic algorithm; genetic algorithm; rush order insertion

0 引言

隨著制造業水平的不斷提高和市場經濟的快速發展，企業需要提高服務水平來滿足客戶的個性化需求。其中，緊急訂單是訂單型企業面臨的常見問題，但它在給企業帶來額外利潤的同時也對生產的穩定性造成了破壞。在緊急訂單到來后，企業需要重新安排生產調度計劃，將緊急訂單合理安插在原有調度方案中，這對企業生產管理的快速反映能力是個巨大挑戰。因此，對緊急訂單插單重調度問題的研究具有很高的實際價值理論價值。混合流水車間是一類具有很強工程背景的復雜車間環境，廣泛存在于化工、紡織、鋼鐵、半導體等行業，其調度問題已被證明是強NP（non-deterministic polynomial）難的，因此緊急插單這種動態環境下的混合流水車間重調度問題具有更為復雜的求解難度，是訂單型企業亟需解決的重要問題。

在緊急插單重調度問題中，常見的插單方法有退單插單［1］和順延插單［2］。此外嚴浩云等人［3］提出了重排插單的方法，并驗證了其優越性。近年來，越來越多的學者關注到緊急插單重調度問題。Zakaria等人［4］通過操縱機器上的可用空閑時間和重新排序操作，將重新調度與非重組和重組策略相匹配，并提出了一種改進遺傳算法以適應緊急訂單的動態插入。Liu等人［5］將匹配策略和實時策略相結合，引入了10種經典優先級規則，并提出了一種新規則。任璽悅等人［6］采用匹配思路設計多緊急訂單到達的重調度策略，將重調度計劃分為靜態調度、基于匹配策略的混合重調度、基于實時策略的剩余原工序重調度三個階段，采用混合遺傳禁忌搜索算法對問題進行求解。由以上文獻可知，目前對緊急插單的重調度策略多集中于對原調度的部分改動，雖然保證了計劃的相對穩定性。但可能導致無法得到最優結果。

當前對求解插單重調度問題的方法主要集中在元啟發式算法上。何小妹等人［7］研究了多目標混合流水車間的緊急插單重調度問題，提出了多目標算法NSGA-Ⅲ（non-dominated sorting genetic algorithm-Ⅲ）。裴小兵等人［8］使用改進的果蠅優化算法尋求帶有插單問題的調度最優解，考慮建立三級優先級列表來確定訂單的優先級指導初始中心果蠅的產生。緊急訂單的插入或取消是引發重調度的常見擾動之一，而目前僅針對插單問題的研究較少，傳統方法中，一般將其歸于重調度問題中進行解決。Gao等人［9］提出了兩階段人工蜂群算法用來解決柔性作業車間的調度與重調度問題；隨后文獻［10］進一步改進了上述算法，使其適用于模糊柔性作業車間的調度與重調度問題。裴海燕等人［11］提出了一種改進的遺傳算法，對插單擾動下，流水線的生產調度與預防性維護進行聯合重調度優化。吉衛喜等人［12］提出異常事件驅動的離散車間重調度決策方法，借助模擬退火算法對最優重調度求解。

綜上，運用現有元啟發算法求解混合流水車間插單問題主要存在以下兩點不足：a）規則策略單一，雖然在部分場景下可以求得較優解，但算法通用性差，調度環境和目標的變化會影響算法的求解能力；b）插單重調度問題解空間呈指數爆炸性增長，常規算法難以實現有效搜索。目前對該問題的求解大多基于元啟發式算法的框架，并在其中融入一些局部搜索操作，雖在一定程度上提高了算法的局部搜索效率，但也存在易過早陷入局部最優的問題，算法在平衡全局搜索與局部優化的能力上仍有提升空間。

超啟發式算法（hyper-heuristic algorithm，HHA）是一種新型智能優化算法，通過某種高層策略控制多種低層啟發式算法（low-level heuristic，LLH）實現對解空間的搜索［13］。目前HHA已經在多領域得到應用，如路徑規劃問題［14，15］、項目調度問題［16］、組合優化問題［17］等。在生產調度領域上，連戈等人［18］提出一種超啟發人工蜂群算法對多場景的魯棒分布式置換流水車間調度問題進行研究，其中高層控制低層不斷生成新的混合啟發式算法，實現在不同場景對應解空間中的深入搜索。羅文沖等人［19］針對兩階段分布式裝配柔性作業車間調度問題，以最小化最大完工時間為優化目標，提出了一種超啟發式交叉熵算法。屈新懷等人［20］以最大完工時間和最小能耗為目標，設計超啟發式遺傳算法對多目標柔性作業車間綠色調度問題求解，算法解決了啟發式算法通用較差的問題。胡蓉等人［21］針對綠色雙邊裝配線平衡問題提出了超啟發式三維分布估計算法（hyper-heuristic three-dimensional estimation of distribution algorithm，HH3DEDA），其中三維分布估計算法用于對啟發式規則的選擇。由文獻調研可知，在高層動態控制LLH的過程中，高效的高層控制策略和針對問題特征設計的低層啟發式算法，是決定HHA求解性能的關鍵。綜上，將HHA應用于混合流水車間插單重調度問題具有以下優勢：a）HHA可以通過高層動態控制和選擇低層啟發式操作，動態生成與問題適配的多種混合啟發式算法，有效解決插單問題中由工序排序和機器選擇導致的復雜解空間問題，增加了局部優化能力；b）HHA通用性強，面對不同的生產模式，在不改變算法框架的基礎上，調整低層規則即可對求解條件進行有效控制，提高了混合流水車間插單重調度的靈活性。

基于以上分析，本文以最大總完工時間最小化為目標，基于超啟發式方法對混合流水車間環境下的緊急訂單插單重調度算法展開研究。首先，通過對問題的分析建立了混合流水車間插單重調度的數學模型。進而，設計超啟發式遺傳算法（hyper-heuristic genetic algorithm，HHGA）對問題進行求解。在超啟發式遺傳算法中，設計了12種底層啟發式操作，并通過高層策略遺傳算法對操作組合進行選擇。最后，通過數據實驗對算法性能進行驗證。

1 問題描述及分析

混合流水車間插單重調度問題描述如下：企業在生產的初始時刻，已定好了現有的n個訂單在流水線S個階段的生產計劃，各階段至少有一臺機器且至少有一個階段存在并行機，每道工序可在相應階段任意一臺機器上加工，各并行機處理時間相互獨立。每個訂單只包含一種工件。在加工開始前，緊急訂單k到達。現要將該緊急訂單插入到該生產批次中，尋求最優的訂單加工順序和訂單在各階段的機器選擇，使得所有訂單的最大完工時間最小。為便于描述，表1定義了問題的參數和變量。

目標函數式（1）為最小化最大完工時間；約束式（2）定義了訂單在最終工序S的完工時間，即訂單總完工時間由各訂單最后工序完工時間決定；約束式（3）要求每一訂單在前一工序完成后方可進入下一工序；約束式（4）表示訂單加工過程連續且不可中斷；約束式（5）表示同一機器不能同時加工多個訂單，即被選用的機器同一階段不能有交疊使用時間；約束式（6）確保每一訂單的任一工序只能在一臺機器上處理；約束式（7）表示被安排在同一階段同一機器的工序，排序靠前的先加工；式（8）和（9）是變量取值約束。

2 超啟發式算法設計

2.1 算法思路與求解框架

在HHGA中，高層是策略域，由12種啟發式操作經過不同排列組合而成，種群中的每個個體代表一種更新策略；低層是問題域，由工序碼和機器碼串聯組成，種群中的每個個體代表原問題的一個解。在求解過程中，高層策略域首先利用遺傳算法對種群個體進行優化，即改變低層多個啟發式操作的組合順序，從而得到新的高層策略域個體。而后更新后的高層策略域個體分別對應于每一個低層問題域個體，控制低層個體執行并行的變鄰域搜索，每一個低層個體均執行了工序碼和機器碼的更新操作，得到新的低層個體。若更新操作后的解優于舊解，則用新解代替舊解。所有個體中適應值的最優解即為原問題的目標函數值。HHGA的兩層結構如圖1所示。

2.2 高層策略域的遺傳算法

遺傳算法是一種基于自然界生物群體適者生存、優勝劣汰的元啟發算法，具有待定參數少、收斂速度快、不易陷入局部最優等特點。在本文提出的HHGA中，高層策略域設計了一種自適應遺傳算法來確定低層啟發式的執行順序。

2.2.1 編碼方案

對于高層策略域，高層的每一個個體均由低層啟發式操作的不同排列組成，也即高層的編碼，啟發式操作可重復出現。高層每一個染色體的長度等于低層啟發式操作的個數的總和。在本文算法中，低層由12個啟發式構成，包括6個訂單排序啟發式和6個機器選擇啟發式，分別命名為LLH1～LLH6和LLH7～LLH12，具體將在2.3節中詳細闡述，對應到高層算法編碼中，則采用序號1～12來表示。

2.2.2 解碼方案

在對高層個體解碼時，由于低層啟發式操作分為對工序排序和對機器選擇兩種，因此需依次執行染色體對應的基因位組合的操作。解碼方案的偽代碼如下：

算法1 高層個體解碼方法

輸入：高層染色體;原始解。

輸出：新解。

input：Chrom;Objv1;? //輸入高層染色體；原始解

Chrom1=Chrom（1：6）;

Chrom2=Chrom（7：12）; //將染色體分成工序碼和機器碼；

for i=1：6

switch Chrom1（i）

case x??? //x=（1，2，…，6）

do LLH（x）;? //執行工序碼對應位置的啟發式操作

chrom1=Chrom1′;

switch Chrom2（i）

case y??? //y=（1，2，…，6）

do LLH（y）;? //執行工序碼對應位置的啟發式操作

chrom2=Chrom2′;

chrom′=［Chrom1 Chrom2］; //更新后的染色體

Objv2=f（Chrom′）; //新的適應值

if Objv1>Objv2? ?//如果新解優于舊解

BestObjv=Objv2； //新解替換舊解

Objv1=Objv2;

break；

else

continue；? //保留舊解繼續執行循環

end if

end for

圖2為一個高層染色體示意圖，該染色體為1-2-5-4-3-6-7-9-12-10-8-11，表示對對應的底層個體首先執行訂單排序啟發式LLH1+機器選擇啟發式LLH7，進而依次執行LLH2+LLH9、LLH5+LLH12、LLH4+LLH10、LLH3+LLH8、LLH6+LLH11的操作組合。為避免操作次數太多導致染色體過度重組，每執行一次操作組合則計算當前方案的最大完工時間，若有所改進則停止執行后續組合。啟發式操作執行更新完成后的值即為染色體的適應值。

2.2.3 自適應的遺傳進化操作

遺傳進化的主要操作為選擇、交叉、變異。

選擇操作采用輪盤賭的方法按概率選擇適應值較強的染色體參與遺傳，選擇概率由適應函數決定。由于本文的目標是最大完工時間最小，而在輪盤賭中，適應值越大的個體被選擇的幾率越大，因此適應函數采用目標函數的倒數，表達式如下：

p（x）=1f（x）（10）

交叉操作采用兩點交叉，即在互相配對的兩個染色體中隨機設置兩個交叉點，交換兩個在所設定的兩個交叉點間的部分染色體，形成新的子代種群。交叉操作是否執行由交叉概率PC控制。交叉操作表達式如下，r為0～1的隨機數。

Xnewi=Xoldi r>PC

Xnewiotherwise i=1，2，…，n（11）

變異操作采用單點變異，即在染色體上隨機選擇一個變異位置，將該位置隨機替換成一個合法的染色體基因。變異操作采用參考文獻［13］，由自適應變異算子PM控制。自適應算子的表達式如下：

PM=0.1×α×genmax gen（12）

其中：gen表示當前迭代次數；maxgen表示總迭代次數；α是變化速率，它控制著變異概率增大的速率。隨著迭代次數的增加，變異概率也增大，這有助于到迭代后期幫算法跳出局部最優。

2.3 低層問題域的啟發式操作

2.3.1 編碼方案

對于低層問題域，采用基于工序碼與機器碼的雙層編碼方式。其原因是雙層編碼可以同時描述訂單的加工順序和加工機器的選擇兩種信息，共同完整表達問題的解。第一層為工序碼，不同的數字代表相應的訂單號，號碼出現的次數表示該訂單的工序數；第二層為機器碼，機器碼的索引號代表對應的訂單工序在可選機器集里所選擇的機器。由于低層個體由工序碼和機器碼共同組成，所以低層問題域中每個個體都代表著原問題的一個解，即原問題的一種調度方案。該調度方案的含義是：各訂單各工序所選擇的加工機器。

圖3給出了一個編碼示例，其編碼為［1，1，2，1，2，2，1，3，1，2，2，1］。可以看出，其工序碼為［1，1，2，1，2，2］，表示工序按照{O1，1， O1，2， O2，1， O1，3， O2，1， O2，3}的順序加工；機器碼為［1，3，1，2，2，1］，表示所選用的機器編號為{1，5，6，2，4，6}。

2.3.2 低層問題域的啟發式操作

低層啟發式操作決定了對問題解空間的搜索程度和解的質量。本文針對雙層編碼的特點，將低層啟發式操作設計為針對工序碼和機器碼的兩部分。從訂單和機器這兩個局部變化的角度出發構建策略池如下：

1）基于工序的操作

工序碼由LLH1～LLH6構成，其中LLH1～LLH2為針對工序排序設計的策略，LLH3～LLH6為四種經典的鄰域變換操作。

a）LH1（隨機插入）。從工序排列中隨機選擇一個工序碼，將之插入到工序排列中的隨機位置。

b）LLH2（隨機多點插入）。從工序排列中隨機選擇三個工序碼，將它們隨機插回原有的工序排列中。

c）LLH3（工序碼隨機交換）。隨機從工序碼中選取兩個進行交換。

d）LLH4（工序碼相鄰交叉）。隨機從工序排列中選擇相鄰的兩位，將它們交換。

e）LLH5（隨機反轉）。從工序碼序列中隨機選取長度為a的子序列，將其翻轉后，放入回原有序列。

f）LLH6（隨機前移）。從工序碼序列中隨機選取長度為a的子序列，將其移動到序列的最前端。

2）基于機器選擇的操作

機器碼由LLH7～LLH9構成，其中LLH7～LLH9為針對機器選擇設計的策略，同時引入LLH10～LLH12三種經典的機器選取規則。

a）LLH7（單個機器碼變異）。從機器碼中隨機選擇一個，將其隨機變成可選機器碼中的某個。

b）LLH8（多個機器碼變異）。從機器碼中隨機選擇多個，將其隨機變成可選機器碼中的某個。

c）LLH9（機器碼子序列變異）。隨機選取機器碼子序列，將子序列上每一個機器碼隨機變成該位置可選機器碼中的某個。

d）LLH10（機器最短加工時間規則）。將全部機器碼替換成按照對應工序可選機器集中加工時長最小的機器的索引號。

e）LLH11（工序最早開始加工規則）。根據工序排序，將機器碼按照能滿足當前工序最早開始的條件重排。

f）LLH12（工序最早結束規則）。根據工序排序，將機器碼按照能滿足當前工序最早結束的條件重排。

2.4 HHGA算法步驟

HHGA算法步驟描述如下：

a）初始化高層策略域和低層問題域種群。隨機生成長度為低層啟發式操作總個數的高層個體，和長度為雙倍工序總數的低層問題域個體。高層和低層對應的種群大小相同且染色體一一對應。

b）對每一個高層個體依次執行底層操作，根據目標函數計算得到解的適應值。高層和低層的適應值大小相同。

c）用輪盤賭選出策略域種群的精英解，進行交叉變異。

d）用更新后的策略域個體依次執行對應的啟發式操作組合，更新問題的解，若新解的適應值優于舊解，則不再執行后續的低層啟發式操作組合，否則繼續執行。若全部新解均不優于舊解，則保留舊解。

e）判斷是否全部低層問題域種群均已被更新，若已完成，則對兩個域中的種群進行保優，將精英解放入對應種群。若沒有，則轉入步驟d）。

f）判斷迭代次數是否達到最大值，若沒有，轉入步驟c），否則終止循環。

2.5 算法示例說明

為了更直觀地闡述本文HHGA算法運算過程，給出了一個小規模（6×3×6）的混合流水車間插單重調度問題作為算法示例，具體加工時間如表2所示，參數設置同3.1節，最大迭代次數為50。其中，訂單1～5為已排定的訂單，訂單6為緊急訂單，需將其插入到現有調度中。

首先，隨機初始化高層和低層種群，得到的高層個體1為{1，4，3，2，5，6，11，9，10，12，7，8}，低層個體1為{4，2，1，6，6，1，2，3，5，4，4，6，2，3，5，3，5，1，1，1，1，1，1，2，2，1，2，2，1，2，2，1，2，2，1，1}。對低層個體1進行解碼，得到的目標值Cmax為24。

進而，用自適應遺傳算法對高層個體進行第一次進化迭代，更新后的高層個體1為{2，6，5，1，4，3，9，8，12，10，11，7}，用其對低層個體1更新，在執行到組合LLH4+LLH11時，得到該個體的最優解17。更新后的低層個體1為{2，3，6，4，4，5，3，2，1，6，6，1，2，4，3，5，5，1，1，2，1，1，1，2，1，2，1，2，1，2，1，1，1，1，1，1}。依次更新完種群全部個體后，進行保優操作，得到種群全部個體的最優解為14。

循環迭代上述過程，在達到最大迭代次數50時算法終止。實驗結果表明，HHGA算法在進化到第6代時即收斂到算例的最優解12，得到的最優重調度方案如圖4所示。在該方案中，訂單6被插在訂單2后進行加工。

為進一步探究本文算法的有效性，將本算例應用于3.3節的三種對比算法：單層編碼超啟發式遺傳算法（single-level hyper-heuristic genetic algorithm，S-HHGA）、超啟發差分進化算法（hyper-heuristic differential evolution algorithm，HHDE）[22]、雙層編碼遺傳算法（double genetic coding genetic algorithm，DGCGA）[23]（有關對比算法的說明詳見3.3節）。考慮到本文HHGA算法在迭代到第6代時即取得最優解12，實驗中將對比算法的最大迭代次數設為6，以便觀察在相同迭代次數下各算法的求解效果，實驗結果如表3所示。

由表3可知，本文算法HHGA相對于其他三種算法有著明顯優勢。首先，HHGA可以生成高質量的初始解，即使對于解空間有限的小規模問題，HHGA得到的初始解也能明顯優于對比算法；其次，HHGA具有較快的收斂速度，在進化到第6代時，僅HHGA收斂到了最優解12。因此，HHGA在初始解質量和收斂速度方面均具有很好的性能。

此外，由實驗結果可以觀察得出，采用超啟發式方法的HHGA、S-HHGA和HHDE的求解效果均明顯優于元啟發式DCAGA，這說明了超啟發式算法對解決混合流水車間插單重調度問題的適用性。

3 實驗設計與分析

3.1 算法參數設計

算法的參數設置對算法性能有重要影響。HHGA中的算法關鍵影響參數包括：種群規模P，交叉率PC，變化速率α。其中，種群規模P和交叉率PC來源于高層策略遺傳算法，根據文獻［24］可知，常用的參數范圍為P=20～200，PC=0.5～1。為進一步確定針對本文算法的參數有效取值范圍，在上述參數范圍內對算例進行了多次預測式實驗，根據測試效果，最終將種群規模P的取值范圍限定在10～40，交叉率PC則為0.6～0.9。 變化速率α來源于文獻［13］，本文直接引用其參數設置值。為了探討參數設置對算法性能的影響，本文采用田口實驗設計法［25］進行實驗。針對HHGA每個參數設置4個水平值，如表4所示。選用隨機生成的中等規模的數據（20×5×11），對HHGA每種參數組合獨立運行10次，取它們的平均值作為平均響應值ARV，結果如表5所示。

根據表5進一步統計了各參數響應值對算法性能的影響，結果如表6所示。根據表6對三個主要參數的變化對算法性能的影響分析如下：種群規模P過小，算法優化性能不明顯，易陷入局部最優；規模過大易導致求解時間過長。交叉算子PC的大小影響個體間的交換頻率，個體間交流次數增多，有利于搜索到全局最優解。自適應變異算子α的變化速率越大，迭代后期變異率越大，會導致高層策略遺傳算法發散，破壞個體穩定性，因此選用較小值。

根據表6可以看出，當P=30，PC=0.8，α =10時算法具有最優性能，算法的實驗參數將依此設置。

3.2 實驗環境與數據

為測試HHGA的性能，本文選取了文獻［22］的HHDE和文獻［23］的DGCGA作為對比。為驗證雙層編碼方式的有效性，以本文HHGA為框架設計了S-HHGA作為對比算法。將這三種對比算法應用于本文問題。在參數設置上，前兩種對比算法均采用原文獻推薦的參數值，S-HHGA的參數與本文算法保持一致。四種算法的最大迭代次數統一設為500。此外 ，由于本文問題和文獻算法研究的問題不完全一致，所以對S-HHGA和HHDE均采用選擇使當前工序最早開始加工的解碼方式。

為檢驗算法在不同問題規模下的求解性能，將算例的問題規模設置如下：訂單數n={10，20，30，50，100}；工序數S={5，8，10}；單個工序可選機器數m={1，2，3，4}。總機器數為各工序可選機器數的總和。根據問題規模分成15組實驗，每組隨機生成10個算例。四個算法均采用MATLAB R2015b編程，運行環境為Intel CoreTM i5-7200U CPU @ 2.50 GHz 2.70 GHz和RAM 8.0 GB。

3.3 實驗結果與比較

算法性能從算法有效性的角度，以最大完工時間最小化為評價指標。采用相對偏差率（percentage relative difference，PRD）［26］來衡量算法性能計算公式如式（13），其中α為當前算法A所求得的目標函數Cmax值，CBest為所有算法求得的最好Cmax值。

PRD=Cmax（A）－CbestCbest×100%（13）

針對15組問題規模用上述算法分別求解，計算每種算法的PRD均值和標準差，并采用方差分析（analysis of variance，ANOVA）對每種算法PRD均值的差異性進行顯著性檢驗（γ=0.05）。實驗結果如表7所示。

由表7統計結果可以看出：

a）測試的所有規模問題經過ANOVA分析得到的P-value值均接近于0，遠小于α，這說明四種算法在求解質量上存在顯著差異。從表4的avg和std指標來看，除100×5×11的問題規模外，HHGA在其他規模問題上均取得了最小平均值。以上結果表明，HHGA的雙層結構有效避免了單一搜索策略或簡單鄰域操作導致的搜索深度有限問題，在求解性能的穩定性上優于其他三種算法。

b）與S-HHGA相比，本文算法的PRD均值降低了77.8%，這說明雙層編碼策略能容納更多的信息，使遺傳算法方便用于復雜問題的求解，同時避免了單一解碼策略易陷入局部最優的不足，合理規定了問題的搜索空間，在求解質量上要高于單層編碼。

c）與HHDE相比，HHGA的PRD均值和標準差平均降低80%、27.5%，這說明本文設計的高層策略域在尋求優質解上是有效的，相比于差分算法，在動態控制和選擇低層啟發式操作時，能生成更多有效的混合式啟發式算法對問題求解，增加了算法的求解深度。

d）與DGCGA相比，HHGA的PRD均值降低了90.7%，這驗證了本文算法的有效性，相比于傳統遺傳算法容易陷入局部最優的缺點，HHGA通過其兩層結構，由高層對低層啟發式操作的排序進行優化，使得低層可執行更緊湊的變鄰域搜索，從而增強了算法跳出局部最優的能力，更容易發現復雜解空間的較優解。

為進一步檢驗HHGA的收斂效率和求解質量，隨機選擇一個規模為10×5×11的算例給出四種算法迭代500次的收斂曲線對比，如圖5所示。從圖5可看出，在收斂效率上，HHGA在第170次迭代中取得最優目標值103，其收斂速度最快，且求解效果遠超其他三種算法。在尋優能力上，單層HHGA的最優值123小于HHDE的最優值130，且兩種算法求解結果均大于HHGA。這一方面說明雙層編碼策略的有效性，另一方面說明改進后的HHGA具有良好的求解性能。

3.4 訂單規模的敏感性分析

訂單規模是混合流水車間插單重調度問題的重要參數，其變化往往會影響到問題求解的難度。為確定訂單規模變化對問題求解難度的影響，本文選取工序數為中等規模8且固定機器數量為18的車間環境，設計訂單規模分別為10、20、30、50和100的算例組，針對每組由隨機生成的10個算例組成，并采用3.2節的四種算法求解，實驗結果取最大完工時間的平均值。通過該實驗，一方面觀察訂單規模對算法性能的總體影響趨勢，以此確定訂單規模對問題求解難度影響；另一方面則進一步對比四項基本原則種算法的求解效果，檢驗本文HHGA的有效性。

實驗結果如圖6所示，可以看出，首先，隨著訂單規模的增加，四種算法的Cmax均呈現出明顯上升趨勢，其中HHGA的增長趨勢較緩，這說明訂單規模會明顯延長車間的制造周期，但如果采用合適的算法則可以減緩這一因素變動的影響。其次，DGCGA的增長速度始終最快，這說明超啟發式算法在穩定性上較優于傳統算法，其雙層結構使低層的變鄰域搜索更加細致，解的質量更好。再次，在訂單數小于50時，S-HHGA的斜率小于HHGA，加工時間增長速度比HHGA慢，當訂單大于50時，HHGA的變化趨勢要比S-HHGA平穩，這說明在HHGA在大規模問題上，更具優勢，這是因為隨著訂單數量的增多，有效的機器選擇規則能使問題在求解中跳出局部最優，得到更滿意的解。

3.5 實例仿真分析

由于目前對該類問題研究較少，尚不存在benchmark數據集進行實例分析，本文選取文獻［27］提供的鋼鐵生產實際數據。實例對應鋼鐵生產中某煉鋼—精煉—連鑄—軋制過程，有3臺煉鋼爐、3臺精煉爐、2臺鑄機和2臺軋機，各階段存在不相關并行機，且機器加工能力不同，具體加工時間如表8所示。假設在開始加工前，已安排好前11個訂單的加工順序，現插入訂單12重新排序。4種算法獨立運行10次仿真結果如表9所示。

表9可知，HHGA的結果要優于其他三種算法的結果，且相對魯棒。就整體性能而言，只有HHGA尋得了最優解304，算法的性能也優于其他三種。因此，HHGA在混合流水車間插單重調度問題上的尋優性能和穩定性上都優于本文設定的對比算法。

4 結束語

本文針對混合流水車間的緊急訂單插單重調度問題，以最小化最大完工時間為優化目標，提出了一種雙層結構的超啟發式遺傳算法（HHGA）。該算法采用GA作為高層策略，動態控制和選擇低層的12種啟發式操作，生成有效混合啟發式算法對問題求解。本文的HHGA有如下特點：a）低層編碼采用工序碼加機器碼的雙層形式，提高了低層染色體的信息容量，避免了單一解碼策略易陷入局部最優的不足；b）算法高層動態控制12種啟發式操作來持續生成新的混合啟發式算法，可實現對問題解的深度搜索；c）算法高層采用自變異交叉算子的遺傳操作，避免算法過早陷入局部最優；d）在低層啟發式操作的設定上，除經典的鄰域變化外，加入機器選取規則，合理限定了問題的搜索空間。最后，本文采用田口實驗法對算法中的主要參數進行確定，并通過大規模實驗和算法比較驗證了所提HHGA的有效性。后續工作將對HHGA的高層策略進一步優化，同時考慮機器故障等其他擾動情況。

參考文獻：

[1]胡東波，王國慶，左小德.實時動態排產系統研究［J］.中國機械工程，2004，15（8）：698-703，738.（Hu Dongbo，Wang Guoqing，Zuo Xiaode.Study on real-time dynamic production schedule system［J］.China Mechanical Engineering，2004，15（8）：698-703，738.）

［2]唐國蘭，唐成華，吳云忠.車間生產計劃動態調整應用研究［J］.機電工程技術，2004，33（8）：92-94.（Tang Guolan，Tang Chenghua，Wu Yunzhong.Study on the application of dynamic adjustment of workshop production plan［J］.Mechanical & Electrical Engineering Technology，2004，33（8）：92-94.）

［3]嚴浩云，李宏余.基于面向負荷的生產控制的緊急訂單插單問題［J］.計算機集成制造系統，2009，15（9）：1809-1815.（Yan Haoyun，Li Hongyu.Rush order inserting problem based on load-oriented manufacturing control technique［J］.Computer Integrated Manufacturing Systems，2009，15（9）：1809-1815.）

［4]Zakaria Z，Petrovic S.Genetic algorithms for match-up rescheduling of the flexible manufacturing systems［J］.Computers & Industrial Engineering，2012，62（2）：670-686.

［5]Liu Weibo，Yan Jin，Price M.New scheduling algorithms and digital tool for dynamic permutation flow shop with newly arrived order［J］.International Journal of Production Research，2017，55（11）：3234-3248.

［6]任璽悅，王修賢，耿娜，等.考慮多急件到達的作業車間重調度研究［J］.工業工程與管理，2022，27（3）：74-83.（Ren Xiyue，Wang Xiuxian，Geng Na，et al.Research on job shop rescheduling considering rush orders［J］.Industrial Engineering and Management，2022，27（3）：74-83.）

［7]何小妹，董紹華.多目標多約束混合流水車間插單重調度問題研究［J］.工程科學學報，2019，41（11）：1450-1457.（He Xiaomei，Dong Shaohua.Research on rush order insertion rescheduling problem under hybrid flow shop with multi-objective and multi-constraint［J］.Chinese Journal of Engineering，2019，41（11）：1450-1457.）

［8]裴小兵，楊景霞.一種解決帶有緊急插單問題的果蠅優化算法［J］.系統工程，2020，38（6）：139-146.（Pei Xiaobing，Yang Jingxia.An improved fruit fly optimization algorithm for problem with urgent orders insertion［J］.Systems Engineering，2020，38（6）：139-146.）

［9]Gao Kaizhou，Suganthan P N，Tasgetiren M F，et al.Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion［J］.Computers & Industrial Engineering，2015，90（12）：107-117.

［10]Gao Kaizhou，Suganthan P N，Chua T J，et al.A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion［J］.Expert Systems with Applications，2015，42（21）：7652-7663.

［11]裴海燕，蔣祖華，胡家文，等.插單擾動下流水線生產與維護的重調度優化［J］.工業工程管理，2017，22（1）：50-57.（Pei Haiyan，Jiang Zuhua，Hu Jiawen，et al.Integrating rescheduling with preventive maintenance in the flow-shop problem under rush orders［J］.Industrial Engineering and Management，2017，22（1）：50-57.）

［12]吉衛喜，蔡酉勇，張朝陽，等.異常事件驅動的離散制造車間重調度決策［J］.系統仿真學報，2018，30（11）：4043-4052.（Ji Weixi，Cai Youyong，Zhang Chaoyang，et al.Abnormal event driven rescheduling decision making in discrete manufacturing workshop［J］.Journal of System Simulation，2018，30（11）：4043-4052.）

［13]李尚函，胡蓉，錢斌，等.超啟發式遺傳算法求解模糊柔性作業車間調度［J］.控制理論與應用，2020，37（2）：316-330.（Li Shanghan，Hu Rong，Qian Bin，et al.Hyper-heuristic genetic algorithm for solving fuzzy flexible job shop scheduling problem［J］.Control Theory & Applications，2020，37（2）：316-330.）

［14]張景玲，馮勤炳，趙燕偉，等.基于強化學習的超啟發算法求解有容量車輛路徑問題［J］.計算機集成制造系統，2020，26（4）：1118-1129.（Zhang Jingling，Feng Qinbing，Zhao Yanwei，et al.Hyper-heuristic for CVRP with reinforcement learning［J］.Computer Integrated Manufacturing Systems，2020，26（4）：1118-1129.）

［15]趙燕偉，冷龍龍，王舜，等.進化式超啟發算法求解多車型低碳選址—路徑問題［J］.控制與決策，2020，35（2）：257-271.（Zhao Yanwei，Leng Longlong，Wang Shun，et al.Evolutionary hyper-heuristics for low-carbon location-routing problem with heterogeneous fleet［J］.Control and Decision，2020，35（2）：257-271.）

［16]Song Hongbo，Lin Jian.A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times［J］.Swarm and Evolutionary Computation，2021，60：100807.

［17]Jian Lin.Backtracking search based hyper-heuristic for the flexible job-shop scheduling problem with fuzzy processing time［J］.Engineering Applications of Artificial Intelligence，2019，77（1）：186-196.

［18]連戈，朱榮，錢斌，等.超啟發式人工蜂群算法求解多場景魯棒分布式置換流水車間調度問題［J］.控制理論與應用，2023，40（4）：713-723.（Lian Ge，Zhu Rong，Qian Bin，et al.Hyper-heuristic artificial bee colony algorithm for the multi-scenario-based robust distributed permutation flow-shop scheduling problem［J］.Control Theory & Applications，2023，40（4）：713-723.）

［19]羅文沖，錢斌，胡蓉，等.超啟發式交叉熵算法求解分布式裝配柔性作業車間調度問題［J］.控制理論與應用，2021，38（10）：1551-1568.（Luo Wenchong，Qian Bin，Hu Rong，et al.Hyper-heuristic cross entropy algorithm for distributed assembly flexible job-shop scheduling problem［J］.Control Theory & Applications，2021，38（10）：1551-1568.）

［20]屈新懷，紀飛，孟冠軍，等.超啟發式遺傳算法柔性作業車間綠色調度問題研究［J］.機電工程，2022，39（2）：255-261.（Qu Xinhuai，Ji Fei，Meng Guanjun，et al.Green scheduling of flexible job-shop based on hyper heuristic genetic algorithm［J］.Journal of Mechanical & Electrical Engineering，2022，39（2）：255-261.）

［21]胡蓉，丁帥，錢斌，等.超啟發式三維EDA求解綠色雙邊裝配線平衡問題［J］.系統仿真學報，2023，35（3）：454-469.（Hu Rong，Ding Shuai，Qian Bin，et al.Hyper-heuristic three dimensional estimation of distribution algorithm for solving green two-sided assembly line balancing problem［J］.Journal of System Simulation，2023，35（3）：454-469.）

［22]沈鵬，王艷，紀志成，等.超啟發式DE算法求解零等待發酵工藝調度［J］.系統仿真學報，2020，32（11）：2235-2243.（Shen Peng，Wang Yan，Ji Zhicheng，et al.Hyper-heuristic DE algorithm for solving zero-wait fermentation process scheduling［J］.Journal of System Simulation，2020，32（11）：2235-2243.）

［23]李平，唐秋華，夏緒輝，等.基于雙層遺傳編碼的柔性作業車間自適應重調度研究［J］.中國機械工程，2013，24（16）：2195-2201.（Li Ping，Tang Qiuhua，Xia Xuhui，et al.Self-adaptively rescheduling flexible job shop with double genetic coding［J］.China Mechanical Engineering，2013，24（16）：2195-2201.）

［24]席裕庚，柴天佑，惲為民.遺傳算法綜述［J］.控制理論與應用，1996，13（6）：697-708.（Xi Yugeng，Chai Tianyou，Yun Weimin.Survey on genetic algorithm［J］.Control Theory & Applications，1996，13（6）：697-708.）

［25]李鐵克，欒治偉，王柏琳，等.求解板坯倒垛和落位問題的分布估計算法［J］.系統工程理論與實踐，2017，37（11）：2955-2964.（Li Tike，Luan Zhiwei，Wang Bailin，et al.Estimation of distribution algorithm for solving the slab stack shuffling and relocation problem［J］.Systems Engineering Theory & Practice，2017，37（11）：2955-2964.）

［26]Wang Bailin，Huang Kai，Li Tieke.Permutation flow shop scheduling with time lag constraints and makespan criterion［J］.Computers & Industrial Engineering，2018，120（6）：1-14.

［27]崔建雙，李鐵克，張文新.混合流水車間調度模型及其遺傳算法［J］.北京科技大學學報，2005，27（5）：623-626.（Cui Jianshuang，Li Tieke，Zhang Wenxin.Hybrid flowshop scheduling model and its genetic algorithm［J］.Journal of University of Science and Technology Beijing，2005，27（5）：623-626.）

收稿日期：2022-12-26；

修回日期：2023-03-20

基金項目：國家自然科學基金資助項目（71701016，71231001）；教育部人文社會科學研究青年基金資助項目（17YJC630143）；北京市自然科學基金資助項目（9174038）；中央高校基本科研業務費資助項目（FRF-BR-20-04B）

作者簡介：劉思宇（1998-），女，吉林公主嶺人，碩士研究生，主要研究方向為生產計劃與調度；李鐵克（1958-），男，吉林長春人，教授，博導，博士，主要研究方向為先進制造管理、生產計劃與調度；王柏琳（1983-），女（通信作者），河北石家莊人，副教授，碩導，博士，主要研究方向為生產調度優化（wangbl@ustb.edu.cn）；袁帥鵬（1993-），男，河南鄭州人，講師，博士，主要研究方向為先進制造管理、智能優化算法；張文新（1966-），男，河北保定人，副教授，碩士，主要研究方向為生產計劃與調度、先進制造管理.