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

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

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

中圖分類號(hào)：TP205?? 文獻(xiàn)標(biāo)志碼：A

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

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

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

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

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

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

1 問(wèn)題描述及分析

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

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

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

2.1 算法思路與求解框架

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

2.2 高層策略域的遺傳算法

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

2.2.1 編碼方案

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

2.2.2 解碼方案

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

算法1 高層個(gè)體解碼方法

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

輸出：新解。

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

Chrom1=Chrom（1：6）;

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

for i=1：6

switch Chrom1（i）

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

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

chrom1=Chrom1′;

switch Chrom2（i）

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

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

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

遺傳進(jìn)化的主要操作為選擇、交叉、變異。

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

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

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

Xnewi=Xoldi r>PC

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

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

PM=0.1×α×genmax gen（12）

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

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

2.3.1 編碼方案

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

圖3給出了一個(gè)編碼示例，其編碼為［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}的順序加工；機(jī)器碼為［1，3，1，2，2，1］，表示所選用的機(jī)器編號(hào)為{1，5，6，2，4，6}。

2.3.2 低層問(wèn)題域的啟發(fā)式操作

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

1）基于工序的操作

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

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

b）LLH2（隨機(jī)多點(diǎn)插入）。從工序排列中隨機(jī)選擇三個(gè)工序碼，將它們隨機(jī)插回原有的工序排列中。

c）LLH3（工序碼隨機(jī)交換）。隨機(jī)從工序碼中選取兩個(gè)進(jìn)行交換。

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

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

f）LLH6（隨機(jī)前移）。從工序碼序列中隨機(jī)選取長(zhǎng)度為a的子序列，將其移動(dòng)到序列的最前端。

2）基于機(jī)器選擇的操作

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

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

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

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

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

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

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

2.4 HHGA算法步驟

HHGA算法步驟描述如下：

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

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

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

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

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

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

2.5 算法示例說(shuō)明

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

首先，隨機(jī)初始化高層和低層種群，得到的高層個(gè)體1為{1，4，3，2，5，6，11，9，10，12，7，8}，低層個(gè)體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}。對(duì)低層個(gè)體1進(jìn)行解碼，得到的目標(biāo)值Cmax為24。

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)與分析

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果與比較

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

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

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

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

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

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

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

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

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

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

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

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

3.5 實(shí)例仿真分析

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1]胡東波，王國(guó)慶，左小德.實(shí)時(shí)動(dòng)態(tài)排產(chǎn)系統(tǒng)研究［J］.中國(guó)機(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]唐國(guó)蘭，唐成華，吳云忠.車間生產(chǎn)計(jì)劃動(dòng)態(tài)調(diào)整應(yīng)用研究［J］.機(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]嚴(yán)浩云，李宏余.基于面向負(fù)荷的生產(chǎn)控制的緊急訂單插單問(wèn)題［J］.計(jì)算機(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]任璽悅，王修賢，耿娜，等.考慮多急件到達(dá)的作業(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)度問(wèn)題研究［J］.工程科學(xué)學(xué)報(bào)，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]裴小兵，楊景霞.一種解決帶有緊急插單問(wèn)題的果蠅優(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]裴海燕，蔣祖華，胡家文，等.插單擾動(dòng)下流水線生產(chǎn)與維護(hù)的重調(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)喜，蔡酉勇，張朝陽(yáng)，等.異常事件驅(qū)動(dòng)的離散制造車間重調(diào)度決策［J］.系統(tǒng)仿真學(xué)報(bào)，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]張景玲，馮勤炳，趙燕偉，等.基于強(qiáng)化學(xué)習(xí)的超啟發(fā)算法求解有容量車輛路徑問(wèn)題［J］.計(jì)算機(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]趙燕偉，冷龍龍，王舜，等.進(jìn)化式超啟發(fā)算法求解多車型低碳選址—路徑問(wèn)題［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ā)式人工蜂群算法求解多場(chǎng)景魯棒分布式置換流水車間調(diào)度問(wèn)題［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)度問(wèn)題［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]屈新懷，紀(jì)飛，孟冠軍，等.超啟發(fā)式遺傳算法柔性作業(yè)車間綠色調(diào)度問(wèn)題研究［J］.機(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求解綠色雙邊裝配線平衡問(wèn)題［J］.系統(tǒng)仿真學(xué)報(bào)，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]沈鵬，王艷，紀(jì)志成，等.超啟發(fā)式DE算法求解零等待發(fā)酵工藝調(diào)度［J］.系統(tǒng)仿真學(xué)報(bào)，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］.中國(guó)機(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]李鐵克，欒治偉，王柏琳，等.求解板坯倒垛和落位問(wèn)題的分布估計(jì)算法［J］.系統(tǒng)工程理論與實(shí)踐，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é)報(bào)，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

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

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