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

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

關(guān)鍵詞：重調(diào)度； 混合流水車間； 超啟發(fā)式； 遺傳算法； 緊急插單

中圖分類號：TP205?? 文獻標(biāo)志碼：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 引言

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

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

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

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

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

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

1 問題描述及分析

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

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

2 超啟發(fā)式算法設(shè)計

2.1 算法思路與求解框架

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

2.2 高層策略域的遺傳算法

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

2.2.1 編碼方案

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

2.2.2 解碼方案

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

算法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）;? //執(zhí)行工序碼對應(yīng)位置的啟發(fā)式操作

chrom1=Chrom1′;

switch Chrom2（i）

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

do LLH（y）;? //執(zhí)行工序碼對應(yīng)位置的啟發(fā)式操作

chrom2=Chrom2′;

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

Objv2=f（Chrom′）; //新的適應(yīng)值

if Objv1>Objv2? ?//如果新解優(yōu)于舊解

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

Objv1=Objv2;

break；

else

continue；? //保留舊解繼續(xù)執(zhí)行循環(huán)

end if

end for

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

2.2.3 自適應(yīng)的遺傳進化操作

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

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

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

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

Xnewi=Xoldi r>PC

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

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

PM=0.1×α×genmax gen（12）

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

2.3 低層問題域的啟發(fā)式操作

2.3.1 編碼方案

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

圖3給出了一個編碼示例，其編碼為［1，1，2，1，2，2，1，3，1，2，2，1］?？梢钥闯?，其工序碼為［1，1，2，1，2，2］，表示工序按照{(diào)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 低層問題域的啟發(fā)式操作

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

1）基于工序的操作

工序碼由LLH1～LLH6構(gòu)成，其中LLH1～LLH2為針對工序排序設(shè)計的策略，LLH3～LLH6為四種經(jīng)典的鄰域變換操作。

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

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

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

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

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

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

2）基于機器選擇的操作

機器碼由LLH7～LLH9構(gòu)成，其中LLH7～LLH9為針對機器選擇設(shè)計的策略，同時引入LLH10～LLH12三種經(jīng)典的機器選取規(guī)則。

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

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

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

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

e）LLH11（工序最早開始加工規(guī)則）。根據(jù)工序排序，將機器碼按照能滿足當(dāng)前工序最早開始的條件重排。

f）LLH12（工序最早結(jié)束規(guī)則）。根據(jù)工序排序，將機器碼按照能滿足當(dāng)前工序最早結(jié)束的條件重排。

2.4 HHGA算法步驟

HHGA算法步驟描述如下：

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

b）對每一個高層個體依次執(zhí)行底層操作，根據(jù)目標(biāo)函數(shù)計算得到解的適應(yīng)值。高層和低層的適應(yīng)值大小相同。

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

d）用更新后的策略域個體依次執(zhí)行對應(yīng)的啟發(fā)式操作組合，更新問題的解，若新解的適應(yīng)值優(yōu)于舊解，則不再執(zhí)行后續(xù)的低層啟發(fā)式操作組合，否則繼續(xù)執(zhí)行。若全部新解均不優(yōu)于舊解，則保留舊解。

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

f）判斷迭代次數(shù)是否達到最大值，若沒有，轉(zhuǎn)入步驟c），否則終止循環(huán)。

2.5 算法示例說明

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

首先，隨機初始化高層和低層種群，得到的高層個體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進行解碼，得到的目標(biāo)值Cmax為24。

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

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

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

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

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

3 實驗設(shè)計與分析

3.1 算法參數(shù)設(shè)計

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

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

根據(jù)表6可以看出，當(dāng)P=30，PC=0.8，α =10時算法具有最優(yōu)性能，算法的實驗參數(shù)將依此設(shè)置。

3.2 實驗環(huán)境與數(shù)據(jù)

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

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

3.3 實驗結(jié)果與比較

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

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

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

由表7統(tǒng)計結(jié)果可以看出：

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

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

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

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

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

3.4 訂單規(guī)模的敏感性分析

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

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

3.5 實例仿真分析

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

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

4 結(jié)束語

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

參考文獻：

[1]胡東波，王國慶，左小德.實時動態(tài)排產(chǎn)系統(tǒng)研究［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]唐國蘭，唐成華，吳云忠.車間生產(chǎn)計劃動態(tài)調(diào)整應(yīng)用研究［J］.機電工程技術(shù)，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]嚴浩云，李宏余.基于面向負荷的生產(chǎn)控制的緊急訂單插單問題［J］.計算機集成制造系統(tǒng)，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]任璽悅，王修賢，耿娜，等.考慮多急件到達的作業(yè)車間重調(diào)度研究［J］.工業(yè)工程與管理，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]何小妹，董紹華.多目標(biāo)多約束混合流水車間插單重調(diào)度問題研究［J］.工程科學(xué)學(xué)報，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]裴小兵，楊景霞.一種解決帶有緊急插單問題的果蠅優(yōu)化算法［J］.系統(tǒng)工程，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]裴海燕，蔣祖華，胡家文，等.插單擾動下流水線生產(chǎn)與維護的重調(diào)度優(yōu)化［J］.工業(yè)工程管理，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]吉衛(wèi)喜，蔡酉勇，張朝陽，等.異常事件驅(qū)動的離散制造車間重調(diào)度決策［J］.系統(tǒng)仿真學(xué)報，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]李尚函，胡蓉，錢斌，等.超啟發(fā)式遺傳算法求解模糊柔性作業(yè)車間調(diào)度［J］.控制理論與應(yīng)用，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]張景玲，馮勤炳，趙燕偉，等.基于強化學(xué)習(xí)的超啟發(fā)算法求解有容量車輛路徑問題［J］.計算機集成制造系統(tǒng)，2020，26（4）：1118-1129.（Zhang Jingling，F(xiàn)eng Qinbing，Zhao Yanwei，et al.Hyper-heuristic for CVRP with reinforcement learning［J］.Computer Integrated Manufacturing Systems，2020，26（4）：1118-1129.）

［15]趙燕偉，冷龍龍，王舜，等.進化式超啟發(fā)算法求解多車型低碳選址—路徑問題［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]連戈，朱榮，錢斌，等.超啟發(fā)式人工蜂群算法求解多場景魯棒分布式置換流水車間調(diào)度問題［J］.控制理論與應(yīng)用，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]羅文沖，錢斌，胡蓉，等.超啟發(fā)式交叉熵算法求解分布式裝配柔性作業(yè)車間調(diào)度問題［J］.控制理論與應(yīng)用，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]屈新懷，紀飛，孟冠軍，等.超啟發(fā)式遺傳算法柔性作業(yè)車間綠色調(diào)度問題研究［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]胡蓉，丁帥，錢斌，等.超啟發(fā)式三維EDA求解綠色雙邊裝配線平衡問題［J］.系統(tǒng)仿真學(xué)報，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]沈鵬，王艷，紀志成，等.超啟發(fā)式DE算法求解零等待發(fā)酵工藝調(diào)度［J］.系統(tǒng)仿真學(xué)報，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]李平，唐秋華，夏緒輝，等.基于雙層遺傳編碼的柔性作業(yè)車間自適應(yīng)重調(diào)度研究［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］.控制理論與應(yīng)用，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］.系統(tǒng)工程理論與實踐，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]崔建雙，李鐵克，張文新.混合流水車間調(diào)度模型及其遺傳算法［J］.北京科技大學(xué)學(xué)報，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

基金項目：國家自然科學(xué)基金資助項目（71701016，71231001）；教育部人文社會科學(xué)研究青年基金資助項目（17YJC630143）；北京市自然科學(xué)基金資助項目（9174038）；中央高?；究蒲袠I(yè)務(wù)費資助項目（FRF-BR-20-04B）

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