考慮模糊質(zhì)檢時(shí)間的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題

摘 要：為解決更符合現(xiàn)實(shí)情形的模糊質(zhì)檢時(shí)間柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題，以最小化完工時(shí)間為目標(biāo)，立足緊急插單、機(jī)器在空載運(yùn)行時(shí)發(fā)生故障和機(jī)器在加工工件時(shí)發(fā)生故障的三種故障情形，建立了帶模糊質(zhì)檢時(shí)間的機(jī)器故障、緊急插單重調(diào)度模型。設(shè)計(jì)了基于元胞自動(dòng)機(jī)鄰域搜索和隨機(jī)重啟爬坡算法的改進(jìn)遺傳算法求解模型，即針對(duì)車間調(diào)度問(wèn)題中存在的訂單排序和機(jī)器選擇雙決策問(wèn)題特征，設(shè)計(jì)包含工序碼和機(jī)器碼的雙層編碼方案，并基于遺傳算法思想對(duì)工序碼和機(jī)器碼設(shè)計(jì)相應(yīng)的交叉、變異等遺傳操作。同時(shí)，將遺傳操作應(yīng)用于基于元胞自動(dòng)機(jī)的鄰域搜索算法框架中以增強(qiáng)算法全局搜索能力，整合基于關(guān)鍵工序的隨機(jī)重啟爬坡算法以提高算法局部開(kāi)發(fā)能力。實(shí)驗(yàn)選取10個(gè)柔性車間調(diào)度算例驗(yàn)證了所提算法的有效性，同時(shí)，測(cè)試1個(gè)模糊質(zhì)檢時(shí)間柔性車間調(diào)度算例驗(yàn)證了模型的有效性。另外，實(shí)驗(yàn)也測(cè)試了不同故障場(chǎng)景，得出該動(dòng)態(tài)調(diào)度方法優(yōu)于實(shí)際場(chǎng)景中常使用的“工件后移”調(diào)度策略。

關(guān)鍵詞：柔性作業(yè)車間調(diào)度問(wèn)題； 模糊質(zhì)檢時(shí)間； 重調(diào)度； 遺傳算法

中圖分類號(hào)：TP306.1;TH186 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）08-015-2351-09

doi：10.19734/j.issn.1001-3695.2023.11.0575

Flexible job shop dynamic scheduling problem withfuzzy quality control time

Zhang Xiaonan1， Gong Jialong1， Jiang Shuai1， Wang Luyu1， Li Yang2

（1.School of Mechanical & Electrical Engineering， Shaanxi University of Science & Technology， Xi’an 710021， China; 2.School of Economics & Management， Liaoning Petrochemical University， Fushun Liaoning 113001， China）

Abstract：To solve the flexible job shop dynamic scheduling problem with fuzzy quality control time， which is more realistic， this paper established two rescheduling models for machine breakdown and urgent order insertion with the objective of minimizing completion time. Two models were for three failure scenarios： emergency order insertion， machine failure during no-load operation， and machine failure during work-piece processing. To solve this model， this paper designed a novel genetic-neighborhood search algorithm that integrated cellular-automata-based neighborhood search and random restart hill-climbing. Aiming at the characteristics of dual sub-decisions involving order sequencing and machine selection， this paper designed a two-layer coding scheme including process code and machine code， and designed corresponding genetic operations such as crossover and mutation for them. After that， this paper applied the genetic operations into the framework of cellular-automata-based neighborhood search to enhance the algorithm’s global search capability， and integrated the random restart hill-climbing algorithm based on key operations to improve the algorithm’s local development capability. Experiments tested 10 flexible job shop scheduling instances and one flexible job shop scheduling instance with fuzzy quality control time to verify the effectiveness of the proposed algorithm and models. In addition， the test results under different failure scenarios show the proposed method outperforms the backward-based scheduling strategy used in practice.

Key words：flexible job shop scheduling problem; fuzzy quality test time; rescheduling; genetic algorithm

0 引言

柔性作業(yè)車間調(diào)度問(wèn)題（flexible job shop scheduling problem，F(xiàn)JSP）是指有m臺(tái)機(jī)器和n個(gè)工件，每個(gè)工件存在L道工序，每道工序可以選擇任意一臺(tái)機(jī)器進(jìn)行加工的生產(chǎn)調(diào)度問(wèn)題［1］。然而，在FJSP實(shí)際執(zhí)行期間可能會(huì)發(fā)生機(jī)器故障、緊急插單等多種干擾事件，這些干擾事件使得原有調(diào)度方案失效，若不及時(shí)處理會(huì)造成生產(chǎn)紊亂或生產(chǎn)中斷，導(dǎo)致工件無(wú)法如期完成。為避免此類情況發(fā)生，決策者必須在有限的時(shí)間內(nèi)作出代價(jià)小、響應(yīng)迅速的方案變更以保證生產(chǎn)系統(tǒng)穩(wěn)定運(yùn)行。另外，為防止出現(xiàn)大批不合格品，同時(shí)避免上道工序的不合格品流入下道工序，生產(chǎn)者通常會(huì)在每道工序后增設(shè)質(zhì)檢環(huán)節(jié)，然而，工序的質(zhì)檢時(shí)間依賴產(chǎn)品的不合格程度，呈現(xiàn)出不確定特性［2］。舉個(gè)例子，一個(gè)合格產(chǎn)品正常流入下一工序，質(zhì)檢時(shí)間小且固定；一個(gè)輕微不合格產(chǎn)品通過(guò)少量修正流入下一道工序，質(zhì)檢時(shí)間輕微增加；一個(gè)嚴(yán)重不合格產(chǎn)品通過(guò)大量修正后流入下一道工序，質(zhì)檢時(shí)間增加顯著。本文針對(duì)考慮模糊質(zhì)檢時(shí)間的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題（slexible job shop dynamic scheduling problem with fuzzy quality control time，F(xiàn)JDSP-FQC）展開(kāi)研究。相較于常規(guī)FJSP，該問(wèn)題同時(shí)具有模糊性和動(dòng)態(tài)性特征，更符合實(shí)際車間作業(yè)過(guò)程，但也更復(fù)雜、更難解決。

現(xiàn)有文獻(xiàn)多集中于研究常規(guī)動(dòng)態(tài)FJSP問(wèn)題（flexible job shop dynamic scheduling problem，F(xiàn)JDSP），而考慮模糊質(zhì)檢時(shí)間的FJDSP研究幾乎沒(méi)有。例如：Luo［3］以最小化最大完工時(shí)間為目標(biāo)，研究了緊急插單事件干擾的FJDSP；裴小兵等人［4］以訂單延期交貨為目標(biāo)，研究了緊急插單的FJDSP；張祥等人［5］考慮全局任務(wù)最大生產(chǎn)完成時(shí)間、機(jī)器負(fù)載和能耗等多優(yōu)化目標(biāo)，研究了緊急插單的多目標(biāo)FJDSP；包博等人［6］研究了考慮設(shè)備故障干擾的FJDSP； 文獻(xiàn)［7，8］研究了考慮機(jī)器故障的多目標(biāo)FJDSP。在算法應(yīng)用方面，眾多算法已被廣泛應(yīng)用于動(dòng)態(tài)FJDSP。侯婭楠等人［9］在傳統(tǒng)遺傳算法中融入了混合故障矩陣對(duì)機(jī)器混合故障下的FJDSP進(jìn)行求解； Sajadi等人［10］設(shè)計(jì)了“求解單目標(biāo)→求解多目標(biāo)”的二階遺傳算法求解機(jī)器故障的多目標(biāo)FJDSP；苗志鴻等人［11］等在遺傳算法中融合錦標(biāo)賽與精英選擇，求解緊急插單的FJDSP；金鵬博等人［12］將遺傳算法與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合，求解機(jī)器故障的FJDSP；李瑞等人［13］將遺傳算法與人工群峰算法融合，并在探索蜂階段引入了六種變鄰域方法，提高算法局部開(kāi)發(fā)能力。此外，Caldeira等人［14］提出改進(jìn)Jaya算法求解FJDSP，利用涉及三點(diǎn)交換和關(guān)鍵工序塊隨機(jī)交換的兩種局部搜索策略改善解質(zhì)量；Alzaqebah等人［15］整合頭腦風(fēng)暴算法、自適應(yīng)多選擇法和鄰域搜索算法； Baykasogˇlu等人［16］提出隨機(jī)貪婪自適應(yīng)搜索算法求解，并采用貪婪局部搜索進(jìn)行二次深化；Zarrouk等人［17］針對(duì)FJSP包含的訂單排序和機(jī)器選擇雙決策問(wèn)題，設(shè)計(jì)了面向工序順序和機(jī)器分配的兩級(jí)粒子群優(yōu)化算法； Serna等人［18］將禁忌搜索算法擴(kuò)展應(yīng)用于元胞自動(dòng)機(jī)鄰域搜索框架中，將可行解擴(kuò)展至其更大鄰域集合中來(lái)選擇最優(yōu)解，以提高全局搜索能力。

通過(guò)梳理可知：a）現(xiàn)有FJDSP的研究主要涉及“緊急插單”“機(jī)器故障”等干擾事件［3～8］，且其在考慮機(jī)器故障時(shí)多默認(rèn)機(jī)器在空載時(shí)發(fā)生故障，實(shí)際上，機(jī)器可能在加工工件時(shí)發(fā)生故障，這種場(chǎng)景下，加工中斷的工件需要重新流轉(zhuǎn)到其他機(jī)器上完成剩余部分的加工;b）遺傳算法［9～13］、改進(jìn)Jaya算法［14］、隨機(jī)貪婪自適應(yīng)搜索算法［16］等各類算法已被廣泛應(yīng)用于求解FJDSP，然而，尋求具有更高求解效率和質(zhì)量的改進(jìn)手段還需進(jìn)一步探索。另外，本文也發(fā)現(xiàn)，在應(yīng)用遺傳算法求解的文獻(xiàn)中，如文獻(xiàn)［9～13］，將遺傳算法與其他算法融合以保持算法全局搜索能力和改善算法局部開(kāi)發(fā)能力，是改進(jìn)的主流手段。

基于此，本文擴(kuò)展FJDSP的故障情形為“緊急插單”“機(jī)器在空載運(yùn)行時(shí)發(fā)生故障”和“機(jī)器在加工工件時(shí)發(fā)生故障”三種干擾情況，同時(shí)考慮模糊質(zhì)檢時(shí)間，以最小化完工時(shí)間為目標(biāo)，建立考慮模糊質(zhì)檢時(shí)間的FJDSP初始調(diào)度模型，并將其進(jìn)一步修正為帶模糊質(zhì)檢時(shí)間的機(jī)器故障和緊急插單重調(diào)度模型。為求解模型，將遺傳算法與元胞自動(dòng)機(jī)鄰域搜索算法、隨機(jī)重啟爬坡算法融合，設(shè)計(jì)了基于元胞自動(dòng)機(jī)鄰域搜索和隨機(jī)重啟爬坡算法的改進(jìn)遺傳算法（genetic algorithm with cellular automata-inspired neighborhood and random-restart hill-climbing，GA-CARRHCNS）。針對(duì)FJDSP包含的訂單排序和機(jī)器選擇雙決策問(wèn)題，設(shè)計(jì)包含工序碼和機(jī)器碼的雙層編碼方案，并分別對(duì)雙層編碼段設(shè)計(jì)相應(yīng)的交叉、變異等遺傳操作；將交叉、變異等遺傳操作置于元胞自動(dòng)機(jī)鄰域搜索算法框架中以增強(qiáng)算法全局搜索能力，同時(shí)，開(kāi)發(fā)基于關(guān)鍵工序的隨機(jī)重啟爬坡算法以提高算法局部開(kāi)發(fā)能力；在滿足迭代次數(shù)后，繼續(xù)采用帶插入和逆序的常規(guī)鄰域搜索算法深化最優(yōu)解的求解質(zhì)量。實(shí)驗(yàn)選取10個(gè)FJSP標(biāo)準(zhǔn)算例和1個(gè)考慮模糊質(zhì)檢時(shí)間的FJSP算例進(jìn)行測(cè)試，驗(yàn)證了本文算法的有效性，同時(shí)，測(cè)試1個(gè)考慮模糊質(zhì)檢時(shí)間的FJDSP算例，驗(yàn)證了模型和重調(diào)度策略的有效性。

需要說(shuō)明的是，本文問(wèn)題具有模糊性和動(dòng)態(tài)性特征，以往FJSP文獻(xiàn)中同時(shí)考慮模糊性和動(dòng)態(tài)性的僅有文獻(xiàn)［19］，然而，兩者研究問(wèn)題和求解技術(shù)均不相同。文獻(xiàn)［19］考慮模糊交貨期，研究了機(jī)器故障擾動(dòng)下的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題，并設(shè)計(jì)改進(jìn)的自適應(yīng)免疫遺傳算法求解；本文考慮模糊質(zhì)檢時(shí)間，考慮故障情形為“緊急插單”“機(jī)器在空載運(yùn)行時(shí)發(fā)生故障”和“機(jī)器在加工工件時(shí)發(fā)生故障”三種干擾情況，設(shè)計(jì)GA-CARRHCNS求解。另外，在算法設(shè)計(jì)方面，元胞自動(dòng)機(jī)鄰域搜索思想來(lái)源于文獻(xiàn)［17］，然而與文獻(xiàn)［17］將元胞自動(dòng)機(jī)鄰域搜索與禁忌搜索算法融合不同，本文將元胞自動(dòng)機(jī)鄰域搜索與遺傳算法、隨機(jī)重啟爬坡算法整合；在算例驗(yàn)證部分，也證明了本文算法優(yōu)于文獻(xiàn)［17］。

1 問(wèn)題描述和模型建立

1.1 問(wèn)題描述

FJSP可定義為：有n個(gè)工件，每個(gè)工件i=1，…，n有工序Oij。每道工序Oij都可以在m臺(tái)機(jī)器中選擇其中一臺(tái)進(jìn)行加工，且工序Oij在機(jī)器k上的加工時(shí)間為Pijk。研究目標(biāo)是通過(guò)為每道工序選擇一臺(tái)加工機(jī)器，并合理安排工序的加工順序，使總完工時(shí)間最小。

本文研究的考慮模糊質(zhì)檢時(shí)間的FJDSP是在FJSP基礎(chǔ)上進(jìn)一步考慮模糊質(zhì)檢時(shí)間，即同一個(gè)工件的兩道工序之間存在質(zhì)檢，且質(zhì)檢時(shí)間是模糊的，并基于這一問(wèn)題研究決策者在應(yīng)對(duì)故障干擾事件時(shí)（這里考慮“緊急插單”、同時(shí)存在“機(jī)器在空載運(yùn)行時(shí)發(fā)生故障”和“機(jī)器在加工工件時(shí)發(fā)生故障”的機(jī)器故障情形），如何在有限的時(shí)間內(nèi)作出代價(jià)小、響應(yīng)迅速的動(dòng)態(tài)變更方案以減少動(dòng)態(tài)事件的影響。

1.2 模糊質(zhì)檢時(shí)間和故障場(chǎng)景的說(shuō)明

1）關(guān)于模糊質(zhì)檢時(shí)間的說(shuō)明

本文采用模糊數(shù)表示模糊質(zhì)檢時(shí)間，即ij=［a，b］，其表示工序Oij的質(zhì)檢時(shí)間為模糊數(shù)［a，b］的模糊數(shù)。

2）關(guān)于故障場(chǎng)景的說(shuō)明

本文考慮了機(jī)器故障和緊急插單兩種動(dòng)態(tài)事件。為便于理解這兩種情況及其相應(yīng)的重調(diào)度模型構(gòu)建邏輯，這里以圖1為例展示了5個(gè)工件、6臺(tái)機(jī)器的機(jī)器故障和緊急插單情形及其相應(yīng)的處理策略。圖中橫坐標(biāo)為時(shí)間，縱坐標(biāo)為機(jī)器號(hào)，數(shù)字為工件與工序編號(hào)，如301表示工件3的第1道工序，虛線a、b表示機(jī)器故障發(fā)生與修復(fù)的時(shí)間節(jié)點(diǎn)，c對(duì)應(yīng)緊急插單情況的發(fā)生節(jié)點(diǎn)。

a）在發(fā)生機(jī)器故障時(shí)（如線a時(shí)間節(jié)點(diǎn)所示），所有工序包括已完工工序101、301、501，正在加工工序201、401、102、302、502，以及未加工工序202、402、103、203、303、403、503、104、204、304、404、504。針對(duì)此情況，將故障機(jī)器上的正在加工工序及未加工工序定義為新的工序集，其中故障機(jī)器上的正在加工工序的加工時(shí)間從b點(diǎn)開(kāi)始計(jì)算，其余機(jī)器上的正在加工工序的加工時(shí)間從a點(diǎn)開(kāi)始刻畫當(dāng)前狀態(tài)，建立重調(diào)度模型。

b）在發(fā)生緊急插單時(shí)（如線c時(shí)間節(jié)點(diǎn)所示），已開(kāi)始加工工序101、201、301、401、501、102、202、302、402、502，未開(kāi)始加工工序103、203、303、403、503、104、204、304、404、504。針對(duì)此場(chǎng)景，當(dāng)有新工件插入時(shí)，新工件的工序與未開(kāi)始加工工序定義為新的工序集，加工時(shí)間從c點(diǎn)開(kāi)始刻畫當(dāng)前狀態(tài)，構(gòu)建重調(diào)度模型。

1.3 假設(shè)條件和參數(shù)設(shè)置

為建立模型，本文考慮以下假設(shè)條件：a）初始方案加工從零時(shí)刻開(kāi)始；b）同一時(shí)刻下，每個(gè)工件只能由一臺(tái)機(jī)器進(jìn)行加工，且每臺(tái)機(jī)器只能加工一個(gè)工件；c）每道工序須在前一工序完成質(zhì)檢后才可加工；d）同一時(shí)刻，每道工序只能由一臺(tái)機(jī)器加工；e）當(dāng)動(dòng)態(tài)事件發(fā)生后，保留已完工工序，對(duì)剩余工序進(jìn)行重調(diào)度，并從動(dòng)態(tài)事件發(fā)生時(shí)刻開(kāi)始。表1列舉了模型所需的參數(shù)和符號(hào)說(shuō)明。

1.4 模型的建立

建立初始模型如下：

目標(biāo)函數(shù)：

f=min（Cmax）（1）

s.t.

Cijk=Sijk+Pijk×xijk（2）

Sijk≥Ci（j-1）k（3）

Sijk≥Ci（j-1）k+ij（4）

Sijk≥Ci′j′k（5）

Cijk≤Si′j′k（6）

其中：式（1）為最小化最大完工時(shí)間；式（2）表示工件在加工過(guò)程中不會(huì)中斷；式（3）表示每道工序需等前一工序完工后才能加工；式（4）表示每道工序都需等到前一道工序質(zhì)檢完成后才可加工；式（5）和（6）表示每臺(tái)機(jī)器在同一時(shí)刻只能加工一道工序。

1.4.1 機(jī)器故障下的重調(diào)度模型

當(dāng)機(jī)器故障事件發(fā)生時(shí)，定義機(jī)器故障發(fā)生時(shí)的未加工工件數(shù)為n′，可用機(jī)器為m′，工件集合為J={Ji|（i1=1，2，3，…，n）}，每個(gè)工件有hi1={hi1|（i1=1，2，3，…，l）}道工序。目標(biāo)函數(shù)不變，則考慮模糊質(zhì)檢時(shí)間的FJDSP在處理機(jī)器故障時(shí)需要在常規(guī)約束式（2）～（6）的基礎(chǔ)上，增加約束條件式（7）～（10）。

l=breaktime-Si1j1k1Pi1j1k1（7）

P′i1j1k1′=（1-l）Pi1j1k1′（8）

Ci1j1k1=Si1j1k1+l×Pi1j1k1×xi1j1k1（9）

S故障i1j1k1≥max（endtime，Si1j1k1+ij）（10）

其中：式（7）為機(jī)器發(fā)生故障時(shí)正在該機(jī)器上加工工件的已完工部分的比例；式（8）為加工中斷工件轉(zhuǎn)移到新機(jī)器上所需的加工時(shí)間；式（9）表示機(jī)器在加工工件過(guò)程中發(fā)生故障導(dǎo)致加工中斷；式（10）表示分配到故障機(jī)器上的工件需等質(zhì)檢結(jié)束后才可加工。

1.4.2 緊急插單下的重調(diào)度模型

當(dāng)緊急插單事件到來(lái)時(shí)，定義生產(chǎn)加工過(guò)程中有新訂單插入時(shí)的新工件與未加工工件總數(shù)為n，可用機(jī)器為m，工件集合為J={Ji2|（i2=1，2，3，…，n）}，每個(gè)工件有hi2={hi2|（i2=1，2，3，…，l）}道工序。目標(biāo)函數(shù)不變，則考慮模糊質(zhì)檢時(shí)間的FJDSP在處理緊急插單時(shí)需要在常規(guī)約束式（2）～（6）的基礎(chǔ)上增加約束式（11）。

Snewi2j2k2≥max（insertime，Si2′，j2′，k2′）（11）

式（11）表示新插入工件只能在插入時(shí)間后開(kāi)始加工，并且需要等到相應(yīng)機(jī)器的前面工序完工后開(kāi)始。

2 GA-CARRHCNS算法設(shè)計(jì)

本文設(shè)計(jì)基于元胞自動(dòng)機(jī)鄰域搜索和隨機(jī)重啟爬坡算法的改進(jìn)遺傳算法（GA-CARRHCNS）求解模型。該算法是遺傳算法、元胞自動(dòng)機(jī)鄰域搜索算法、隨機(jī)重啟爬坡算法的融合，即：首先，針對(duì)車間調(diào)度問(wèn)題中存在的訂單排序和機(jī)器選擇雙決策問(wèn)題特征，設(shè)計(jì)包含工序碼和機(jī)器碼的雙層編碼方案，并基于遺傳算法思想對(duì)工序碼和機(jī)器碼設(shè)計(jì)相應(yīng)的交叉、變異等遺傳操作；其次，將遺傳操作應(yīng)用于基于元胞自動(dòng)機(jī)的鄰域搜索算法框架中，通過(guò)將種群擴(kuò)展為帶鄰域解的大規(guī)模種群，從而增強(qiáng)算法的全局搜索能力；再次，針對(duì)元胞自動(dòng)機(jī)鄰域搜索算法更新得到的新種群，設(shè)計(jì)基于關(guān)鍵工序的隨機(jī)重啟爬坡算法以進(jìn)一步改善解質(zhì)量，從而增強(qiáng)算法的局部開(kāi)發(fā)能力；最后，在滿足迭代次數(shù)后，繼續(xù)采用帶插入和逆序的常規(guī)鄰域搜索算法以深化搜索到的最優(yōu)解。

2.1 編碼和解碼

針對(duì)車間調(diào)度問(wèn)題中訂單排序和機(jī)器選擇的雙決策問(wèn)題特征，采用包含工序碼和機(jī)器碼的雙層編碼方式，第一層對(duì)工序排序子決策進(jìn)行編碼，第二層對(duì)機(jī)器選擇子決策進(jìn)行編碼。工序碼表示每道工序的順序，機(jī)器碼表示每道工序選擇的機(jī)器。工序碼長(zhǎng)度與機(jī)器碼長(zhǎng)度一致［13］。

圖2以簡(jiǎn)單FJSP問(wèn)題（如表2）為例展示了相應(yīng)的可能編碼示例。圖中，工序碼“1 3 1 2 3 2”表示（O11，O31，O12，O21，O32，O22），機(jī)器碼“1 3 3 2 1 2 ”表示（M1，M3，M3，M2，M1，M2）。該編碼表示：工序O31在M3上加工，工序O21對(duì)應(yīng)的加工機(jī)器為M2，依次類推。

解碼過(guò)程采用貪婪解碼方法，即對(duì)每道工序，找到該工序在所選機(jī)器上能夠加工的最早時(shí)間。

2.2 初始化種群

考慮到問(wèn)題的訂單排序和機(jī)器選擇雙決策特征，立足雙層編碼方式，采用隨機(jī)生成方法，隨機(jī)產(chǎn)生工件的加工順序生成工序碼，隨機(jī)選擇工序的可選擇加工機(jī)器生成機(jī)器碼，最終將工序碼和機(jī)器碼組成一個(gè)解個(gè)體。NIND個(gè)個(gè)體組成初始種群。

2.3 遺傳操作

2.3.1 選擇操作

采用精英選擇及錦標(biāo)賽雙選擇方式。精英選擇為：設(shè)置精英解概率Ep，精英解數(shù)量為En=Ep×NIND。將所有解從小到大排列，則前En個(gè)為精英解。錦標(biāo)賽選擇為：取第En+l到第NIND個(gè)解，在這些解中隨機(jī)抽取兩個(gè)解比較大小，將兩個(gè)解中更小的保留，此過(guò)程進(jìn)行NIND-（En+l）次，將第En+l到第NIND個(gè)解依次替換。

2.3.2 交叉操作

同樣考慮到所研究問(wèn)題的訂單排序和機(jī)器選擇雙決策特征，本文立足雙層編碼方式，分別針對(duì)工序碼和機(jī)器碼設(shè)計(jì)相應(yīng)的交叉操作。

1）面向工序碼的交叉操作

在面向工序碼的交叉操作中，設(shè)計(jì)了工序優(yōu)先交叉和工序常規(guī)交叉兩種方法。兩種交叉方法任意選擇執(zhí)行。下面以兩個(gè)父代n1和n2中的工序碼OS1和OS2交叉生成兩個(gè)子代OS′1和OS′2為例。兩種交叉方法具體描述如下：

a）工序優(yōu)先交叉。將工序J隨機(jī)分成兩JA和JB部分，滿足JA∩JB=和JA∪JB=J。在OS′1生成時(shí)，工件JA的工序參照OS1位置放置在OS′1的相同位置，而JB的工序按照OS2的加工順序依次填補(bǔ)OS′1的空位置。在生成OS′2時(shí)，工件JA的工序參照OS2位置放置在OS′2的相同位置，而JB的工序按照OS1的加工順序依次填補(bǔ)OS′2的空位置。圖3展示了一個(gè)有3個(gè)工件和6個(gè)工序的交叉示例。

b）工序常規(guī)交叉。將工序J隨機(jī)分成JA和JB兩部分，滿足JA∩JB=和JA∪JB=J。OS′1生成方式與上述“工序優(yōu)先交叉”相同。而在生成OS′2時(shí)，先將工件JB的工序參照OS2位置放置在OS′2的相同位置，然后將JA工序按照OS1的加工順序依次填補(bǔ)OS′2的空位置。圖4展示了一個(gè)有3個(gè)工件和6個(gè)工序的交叉示例。

2）面向機(jī)器碼的交叉操作

采用兩點(diǎn)式交叉執(zhí)行面向機(jī)器碼的交叉操作。同樣以兩個(gè)父代n1和n2中的工序碼MS1和MS2交叉生成兩個(gè)子代MS′1和MS′2為例。具體為：隨機(jī)選擇兩個(gè)位置p1和p2（0<p1<p2<pmax），將MS1的位置［1，p1-1］和［p2+1，pmax］編碼和MS2的位置［p1，p2］編碼結(jié)合，得到一個(gè)新的序列MS′1。同樣地，將MS1的位置［p1，p2］編碼和MS2的位置［1，p1-1］和［p2+1，pmax］編碼結(jié)合，生成新序列MS′2。圖5展示了一個(gè)有3臺(tái)機(jī)器和6個(gè)工序的交叉示例。

2.3.3 變異操作

同樣考慮到所研究問(wèn)題的訂單排序和機(jī)器選擇雙決策特征，這里也立足雙層編碼方式，分別針對(duì)工序碼和機(jī)器碼設(shè)計(jì)相應(yīng)的變異操作。

1）面向工序碼的變異操作

設(shè)計(jì)了交換變異和三點(diǎn)變異兩種方法執(zhí)行面向工序碼的變異操作。兩種變異方法任意選擇執(zhí)行。兩種變異方法具體描述如下：

a）交換變異。即在一個(gè)解的序列上隨機(jī)選取兩個(gè)位置的編碼進(jìn)行交換得到新解，如圖6所示。

b）三點(diǎn)變異。隨機(jī)改變?nèi)齻€(gè)不同編碼的位置，隨機(jī)交換三個(gè)編碼的位置得到子代，如圖7所示。通過(guò)此步驟，可使解的多樣性增加，從而可以使解以一定概率跳出局部最優(yōu)解。

2）面向機(jī)器碼的交叉操作

機(jī)器碼采用隨機(jī)指定機(jī)器突變的變異方式，即選擇任意隨機(jī)位置，將此位置上的機(jī)器號(hào)變?yōu)榕c初始機(jī)器不同的可行機(jī)器，如圖8所示。

2.4 基于元胞自動(dòng)機(jī)的鄰域搜索算法框架

為改善求解質(zhì)量，將2.3節(jié)的遺傳操作置于基于元胞自動(dòng)機(jī)（cellular automata，CA）［20］的鄰域搜索算法框架中，以改善種群解質(zhì)量。算法流程可以描述為：通過(guò)選擇、交叉和變異操作使種群中的每個(gè)解產(chǎn)生l個(gè)新型鄰域解，從而組成了種群規(guī)模為l×NIND的新鄰域種群，繼而在種群規(guī)模為l×NIND的鄰域種群中選擇最好的NIND個(gè)解組成新種群。

圖9展示了整合遺傳操作和基于元胞自動(dòng)機(jī)鄰域搜索算法的示意圖，圖中種群中的每個(gè)解n1～nNIND通過(guò)選擇、交叉、變異生成l個(gè)新型鄰域解。

2.5 隨機(jī)重啟爬坡算法

針對(duì)基于元胞自動(dòng)機(jī)的鄰域搜索算法框架整合遺傳操作后得到的新種群，本文將進(jìn)一步對(duì)新種群中的每個(gè)解執(zhí)行基于關(guān)鍵工序的隨機(jī)重啟爬坡操作，以進(jìn)一步改善解質(zhì)量。

隨機(jī)重啟爬坡算法的核心在于找到關(guān)鍵工序集。本文采用基于空閑時(shí)間的方法確定關(guān)鍵工序，具體描述為：從最后一個(gè)工序中選擇一個(gè)與最大完工時(shí)間相同的工序，從機(jī)器角度或工件角度檢查同一臺(tái)機(jī)器或同一作業(yè)的前一工序，若前一工序的加工完成時(shí)間等于當(dāng)前工序的開(kāi)始時(shí)間，則將其定義為關(guān)鍵工序。注意，若多個(gè)前工序均滿足加工完成時(shí)間等于當(dāng)前工序的開(kāi)始時(shí)間，則隨機(jī)選擇。重復(fù)上述步驟，直到?jīng)]有前序工序?yàn)橹?。圖10展示了關(guān)鍵工序的選擇示例，圖中按照O32、O12和O11的順序找到關(guān)鍵工序集。

隨機(jī)重啟爬坡算法可以描述為：首先，找到關(guān)鍵工序集，并任意選擇某一關(guān)鍵工序，將其分配給與先前方案不同的可行的機(jī)器加工，以此產(chǎn)生一個(gè)新機(jī)器序列MS′。然后，以概率αc選擇其他關(guān)鍵工序，并隨機(jī)選擇一個(gè)非關(guān)鍵工序與之配對(duì)，將兩者執(zhí)行交換操作，以獲得一個(gè)新的工序序列OS′。新的MS′和OS′生成一個(gè)新個(gè)體n′。若產(chǎn)生的新解n′優(yōu)于原解n，則新解n′替換原解n，否則，重新對(duì)原解n進(jìn)行隨機(jī)重啟爬坡。隨機(jī)重啟爬坡算法的終止條件為：滿足最大迭代次數(shù)Hn后退出迭代。圖11展示了隨機(jī)重啟爬坡的操作示例。圖中，隨機(jī)選擇關(guān)鍵工序O21，將其加工機(jī)器從M1更新為M2，生成新機(jī)器序列MS′；然后，對(duì)于其他關(guān)鍵工序O11和O12，以概率αc選中O11，將其與非關(guān)鍵工序O21交換，生成新工序序列OS′。圖11中左子圖為執(zhí)行隨機(jī)重啟爬坡算法的流程示例，右子圖為執(zhí)行隨機(jī)重啟爬坡算法后的新方案。

2.6 鄰域搜索

重復(fù)執(zhí)行整合遺傳操作的元胞自動(dòng)機(jī)鄰域搜索算法框架和隨機(jī)重啟爬坡算法，當(dāng)?shù)螖?shù)超過(guò)最大迭代次數(shù)MAXGEN時(shí)，針對(duì)輸出的最優(yōu)解繼續(xù)采用常規(guī)鄰域搜索算法深化其解質(zhì)量。鄰域搜索包含插入和逆序兩種鄰域操作：

a）插入。隨機(jī)在該解上選擇兩個(gè)位置，將后面位置的編碼插入到前面位置，將前面位置及其后面位置的編碼后移，如圖12所示，得到新解。

b）逆序。隨機(jī)選擇兩基因位，截取兩基因位之間的基因片段，將所有基因位上的工序號(hào)順序逆置，再將對(duì)應(yīng)位置的機(jī)器號(hào)進(jìn)行更換，如圖13所示。

圖14給出了鄰域搜索算法的流程。具體步驟如下：

a）設(shè)最大迭代次數(shù)為N1。當(dāng)插入操作次數(shù)達(dá)到最大迭代次數(shù)N1時(shí)，轉(zhuǎn)入步驟b）；

b）將步驟a）得到的當(dāng)前最優(yōu)解進(jìn)行逆序操作，當(dāng)達(dá)到最大迭代次數(shù)N2時(shí)，輸出最優(yōu)方案。

2.7 整體算法流程

圖15是GA-CARRHCNS的整體算法流程。

具體算法步驟為：

a）設(shè)當(dāng)前迭代次數(shù)gen=0，種群規(guī)模NIND，最大迭代次數(shù)MAXGEN，精英解概率Ep、交叉概率XOVR和變異概率MUTR；

b）初始化種群；

c）采用精英篩選及錦標(biāo)賽的方式對(duì)種群進(jìn)行篩選；

d）將新種群進(jìn)行交叉操作和變異操作；

e）將交叉變異后的新種群執(zhí)行基于元胞自動(dòng)機(jī)的鄰域搜索算法；

f）隨機(jī)重啟爬坡；

g）迭代次數(shù)n=n+1；

h）判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到，則輸出最優(yōu)解，并對(duì)最優(yōu)解執(zhí)行帶N次插入和逆序的常規(guī)鄰域搜索，否則，轉(zhuǎn)回步驟b）。

i）輸出靜態(tài)調(diào)度方案；

j）判斷是否發(fā)生動(dòng)態(tài)事件，若是，對(duì)受影響工序用本文算法重新求解，求出重調(diào)度方案，否則，輸出靜態(tài)調(diào)度方案。

3 算例驗(yàn)證和結(jié)果分析

3.1 算法有效性驗(yàn)證

由于目前沒(méi)有FJDSP-FQC的標(biāo)準(zhǔn)測(cè)試算例，所以本文通過(guò)以下兩個(gè)層面測(cè)試算法性能：a）FJDSP-FQC屬于FJSP的擴(kuò)展，學(xué)術(shù)界雖無(wú)FJDSP-FQC標(biāo)準(zhǔn)測(cè)試算例，但有FJSP標(biāo)準(zhǔn)算例，故本文求解FJSP標(biāo)準(zhǔn)算例，并將求解結(jié)果與已有文獻(xiàn)求解結(jié)果進(jìn)行比較，以驗(yàn)證算法性能；b）為了證明本文算法適用于求解考慮模糊質(zhì)檢時(shí)間的FJSP，進(jìn)一步改進(jìn)生成一個(gè)6×6的考慮模糊質(zhì)檢時(shí)間的FJSP算例，采用樣本平均近似（SAA）方法處理模糊性，對(duì)比本文算法與基本遺傳算法（即不帶元胞自動(dòng)機(jī)鄰域搜索和隨機(jī)重啟爬坡算法的遺傳算法）的求解結(jié)果，從而驗(yàn)證本文算法對(duì)求解考慮模糊質(zhì)檢時(shí)間FJSP的適用性，以及所設(shè)計(jì)的元胞自動(dòng)機(jī)鄰域搜索和隨機(jī)重啟爬坡算法的有效性。

3.1.1 標(biāo)準(zhǔn)FJSP算例測(cè)試

這里選取標(biāo)準(zhǔn)FJSP算例庫(kù)中的MK01～MK10共10個(gè)案例進(jìn)行測(cè)試。其中，MK01～MK02為小規(guī)模案例，MK03～MK07為中規(guī)模算例，MK08～MK10為大規(guī)模算例。上述算例可以在網(wǎng)址http：//www.dsia.ch/monaldo下載［21］。

采用MATLAB 2018b編程，運(yùn)行環(huán)境為Windows 10 家庭版64位操作系統(tǒng)，Intel Core i5-7200U @ 2.50 GHz雙核處理器，8 GB RAM。算法參數(shù)設(shè)置：種群規(guī)模NIND=200、迭代次數(shù)MAXGEN=1000、交叉率0.5、變異率0.5，精英解概率為0.02，CA型鄰域解數(shù)量為3，其他關(guān)鍵工序選擇概率αc=0.05。

表3是GA-RHHCNS與INABC［13］、IJA［14］、BOS-LAHC［15］、GRASP［16］、TIPSO［17］、GLNSA［18］的求解結(jié)果對(duì)比。每個(gè)測(cè)試算例被重復(fù)求解10次，表中展示的是10次中的最優(yōu)解，BKV為已知最優(yōu)解。另外，*標(biāo)記最大完工時(shí)間的最優(yōu)值，加粗表示算法達(dá)到了已知最優(yōu)解BKV。從中可以看出：本文算法在MK01～MK10共10個(gè)算例中均能找到對(duì)比算法能搜索到的最好值，如對(duì)于MK10算例來(lái)說(shuō)，本文算法求解結(jié)果為197 min，優(yōu)于INABC的227 min、BOS-LAHC的204 min、GRASP的205 min、TIPSO的205 min、GLNSA的205 min，其他算例類似。綜合可見(jiàn)，本文算法適用于求解FJSP問(wèn)題，算法合理有效。

為測(cè)試展示算法的穩(wěn)定性，參考文獻(xiàn)［22］，本文進(jìn)一步采用每種對(duì)比算法在運(yùn)行10次時(shí)求解出最優(yōu)解的次數(shù)和相對(duì)百分比偏差（RPD）兩個(gè)指標(biāo)來(lái)檢驗(yàn)算法穩(wěn)定性。

a）每種對(duì)比算法在運(yùn)行10次時(shí)求解出最優(yōu)解的次數(shù)指標(biāo)。圖16展示了每種對(duì)比算法在運(yùn)行10次時(shí)求解出最優(yōu)解的次數(shù)，可見(jiàn)本文算法與GLNSA算法求解出最優(yōu)解的次數(shù)為9，數(shù)量多余其他算法。

b）相對(duì)百分比偏差（RPD）指標(biāo)。RPD計(jì)算如式（12）所示，式中，BOV是每個(gè)算法得到的最大完工時(shí)間值。RPD越小表示所得結(jié)果越接近BKV，算法性能越好。表4展示了每種對(duì)比算法的平均RPD值及排名，可知本文算法的平均RPD值最小。

RPD=BOV-BKVBOV×100（12）

綜上可見(jiàn)，本文算法較INABC、IJA、BOS-LAHC、GRASP、TIPSO、GLNSA算法穩(wěn)定性良好。

另外，圖17以MK01為例展示了本文算法求解該算例的算法迭代曲線?？芍疚乃惴ㄔ诘恋?5次時(shí)已經(jīng)收斂到最優(yōu)解，說(shuō)明算法穩(wěn)定有效。

3.1.2 考慮模糊質(zhì)檢時(shí)間的FJSP算例測(cè)試

進(jìn)一步生成一個(gè)6×6的模糊質(zhì)檢時(shí)間FJSP算例，表5展示了該算例的模糊質(zhì)檢時(shí)間范圍，另外， 表6給出了生成算例的具體數(shù)據(jù)。

采用GA-CARHHCNS求解，同時(shí)，采用樣本平均近似（SAA）方法處理模糊質(zhì)檢時(shí)間屬性，即預(yù)期目標(biāo)函數(shù)由隨機(jī)樣本的樣本平均估計(jì)來(lái)近似。樣本規(guī)模取200，其他算法參數(shù)同3.1.1節(jié)，則本文算法的求解結(jié)果為：應(yīng)對(duì)不同質(zhì)檢時(shí)間場(chǎng)景，綜合性能最優(yōu)的調(diào)度方案的平均最大完工時(shí)間為90 min。表7是本文算法和基本遺傳算法（即不帶元胞自動(dòng)機(jī)鄰域搜索和隨機(jī)重啟爬坡算法的遺傳算法）的求解結(jié)果對(duì)比，從表7中可以看出，本文算法結(jié)果相較于基本遺傳算法縮短了21.8 min，改進(jìn)率為19.5%。

另外，圖18展示了最優(yōu)方案下的某一隨機(jī)樣本的調(diào)度方案甘特圖。圖中，縱坐標(biāo)表示機(jī)器號(hào)，橫坐標(biāo)表示時(shí)間，相同顏色表示同一工件，數(shù)字表示工件與工序編號(hào)，如204表示工件2的第4道工序。需要注意的是，雖然圖中顯示所有工體的最大完成時(shí)間為77 min，但實(shí)際完工時(shí)間是89 min，原因在于：最后一道工序206質(zhì)檢之后整個(gè)生產(chǎn)任務(wù)才算完成。

為進(jìn)一步討論模糊質(zhì)檢時(shí)間的刻畫對(duì)調(diào)度結(jié)果的影響，本文進(jìn)一步對(duì)比了“采用模糊數(shù)刻畫不確定質(zhì)檢時(shí)間”以及“采用平均值刻畫不確定質(zhì)檢時(shí)間”的求解結(jié)果?！安捎闷骄悼坍嫴淮_定質(zhì)檢時(shí)間”的最大完工時(shí)間甘特圖如圖19所示。從中可以看出，“采用模糊數(shù)刻畫不確定質(zhì)檢時(shí)間”的最大完工時(shí)間平均期望值為90 min，而“采用平均值刻畫不確定質(zhì)檢時(shí)間”的最大完工時(shí)間為96.5 min，驗(yàn)證了模型的有效性。需要注意的是，與圖18同理，圖19雖然顯示所有工件的最大完工時(shí)間為84.5 min，但實(shí)際完成時(shí)間應(yīng)是96.5 min。

3.2 考慮模糊質(zhì)檢時(shí)間的FJDSP算例測(cè)試

以3.1.2節(jié)中求解得到的綜合性能最優(yōu)的調(diào)度方案為對(duì)象，以其應(yīng)對(duì)某一隨機(jī)場(chǎng)景下的調(diào)度甘特圖為例，進(jìn)一步探討機(jī)器故障、訂單插入等干擾事件下的重調(diào)度策略和方案。圖20是某一隨機(jī)場(chǎng)景下的調(diào)度甘特圖，最大完工時(shí)間為77 min。

1）機(jī)器故障的動(dòng)態(tài)調(diào)度

在圖20的基礎(chǔ)上，假設(shè)發(fā)生故障的機(jī)器為M6，故障發(fā)生時(shí)間t1=15 min，故障修復(fù)時(shí)間t2=35 min。根據(jù)圖20可看出，在機(jī)器M6發(fā)生故障時(shí)工序601正在M6上加工。經(jīng)過(guò)重調(diào)度后生成的重調(diào)度方案如圖21所示，最大完工時(shí)間89 min。

為驗(yàn)證該重調(diào)度方案的有效性，圖22展示了“工件后移策略”的調(diào)度甘特圖，最大完工時(shí)間為94 min。將其與本文結(jié)果對(duì)比，可知本文重調(diào)度方法下的最大完工時(shí)間遠(yuǎn)遠(yuǎn)少于“工件后移策略”，證明了該重調(diào)度方案的有效性。

2）訂單插入的動(dòng)態(tài)調(diào)度

在圖20的基礎(chǔ)上，假設(shè)初始方案開(kāi)始后第30 min有緊急訂單插入并且需要優(yōu)先加工，定義工件7為緊急訂單，工件7包含3道工序，每道工序的可選機(jī)器及加工時(shí)間如表8所示。

圖23是新插入工件與未加工工件共同進(jìn)行完全重調(diào)度方案，最大完工時(shí)間為79 min，圖中橙色部分為新插入訂單，其余顏色部分為原有訂單。同理，在不進(jìn)行重調(diào)度的情形下，新訂單需等待所有工件完工后才可加工。

圖24展示了“工件后移策略”調(diào)度方案，經(jīng)計(jì)算得出最大完工時(shí)間為110 min。對(duì)比兩種方案可以看出，采用完全重調(diào)度花費(fèi)的時(shí)間更短，驗(yàn)證了本文重調(diào)度方案應(yīng)對(duì)緊急插單干擾事件的有效性。

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

本文擴(kuò)展FJSP中的動(dòng)態(tài)調(diào)度故障情形為緊急插單、機(jī)器在空載運(yùn)行時(shí)發(fā)生故障和機(jī)器在加工工件時(shí)發(fā)生故障三種情況，同時(shí)將模糊質(zhì)檢時(shí)間考慮在內(nèi)，研究了考慮模糊質(zhì)檢時(shí)間的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題。首先，以最小化完工時(shí)間為目標(biāo)，建立考慮模糊質(zhì)檢時(shí)間的初始調(diào)度模型，并基于初始調(diào)度模型，立足緊急插單、機(jī)器在空載運(yùn)行時(shí)發(fā)生故障和機(jī)器在加工工件時(shí)發(fā)生故障的三種故障情形，進(jìn)一步修正為帶模糊質(zhì)檢時(shí)間的機(jī)器故障、緊急插單重調(diào)度模型。然后，設(shè)計(jì)帶元胞自動(dòng)機(jī)鄰域搜索和隨機(jī)重啟爬坡算法的改進(jìn)遺傳算法（GA-CARRHCNS）求解模型，即針對(duì)FJDSP包含的訂單排序和機(jī)器選擇雙決策問(wèn)題，設(shè)計(jì)包含工序碼和機(jī)器碼的雙層編碼方案，并分別對(duì)雙層編碼段設(shè)計(jì)相應(yīng)的交叉、變異等遺傳操作，同時(shí)，將遺傳操作應(yīng)用于基于元胞自動(dòng)機(jī)的鄰域搜索算法框架中以增強(qiáng)算法全局搜索能力，并整合基于關(guān)鍵工序的隨機(jī)重啟爬坡算法以提高算法局部開(kāi)發(fā)能力。最后，實(shí)驗(yàn)選取10個(gè)FJSP標(biāo)準(zhǔn)算例和1個(gè)考慮模糊質(zhì)檢時(shí)間的FJSP算例進(jìn)行測(cè)試，驗(yàn)證了本文算法的有效性，同時(shí)，測(cè)試1個(gè)考慮模糊質(zhì)檢時(shí)間的FJDSP算例驗(yàn)證了模型和重調(diào)度策略的有效性。實(shí)驗(yàn)結(jié)果如下：

a）本文算法較INABC、IJA、BOS-LAHC、GRASP、TIPSO、GLNSA算法而言，求解結(jié)果更優(yōu)，算法性能更有效，且算法穩(wěn)定性也更良好。

b）在求解考慮模糊質(zhì)檢時(shí)間的FJSP算例時(shí)，采用模糊數(shù)刻畫不確定質(zhì)檢時(shí)間的最大完工時(shí)間平均值為90 min，而采用平均值刻畫不確定質(zhì)檢時(shí)間的最大完工時(shí)間為96.5 min，本文所建模型是有效的。

c）在求解考慮模糊質(zhì)檢時(shí)間的FJDSP算例時(shí)，當(dāng)遭遇機(jī)器故障，相較于工件后移策略，本文的重調(diào)度策略能將最大完工時(shí)間從94 min縮減至89 min，效率提高了5.3%；當(dāng)遭遇緊急插單，本文的重調(diào)度策略能將最大完工時(shí)間從110 min縮減至79 min，效率提高了28.2%。

未來(lái)研究可結(jié)合問(wèn)題特點(diǎn)進(jìn)一步優(yōu)化算法的全局搜索與局部搜索能力，或者進(jìn)一步考慮其他生產(chǎn)條件，研究多種因素的柔性作業(yè)車間調(diào)度問(wèn)題。

參考文獻(xiàn)：

［1］米恬怡， 唐秋華， 成麗新， 等. 融合強(qiáng)化學(xué)習(xí)與變鄰域搜索的柔性作業(yè)車間調(diào)度研究［J］. 工業(yè)工程與管理， 2023， 28（5）： 101-107. （Mi Tianyi， Tang Qiuhua， Cheng Lixin， et al. Research on flexible job shop scheduling by integrating reinforcement learning and variable neighborhood search［J］. Industrial Engineering and Management， 2023， 28（5）： 101-107.）

［2］衛(wèi)少鵬， 王婷， 周彤. 考慮多時(shí)間因素的綠色柔性作業(yè)車間動(dòng)態(tài)調(diào)度［J］. 組合機(jī)床與自動(dòng)化加工技術(shù)， 2021（1）： 164-168. （Wei Shaopeng， Wang Ting， Zhou Tong. Dynamic scheduling of green flexible job shop considering multiple time factors［J］. Combined Machine Tools and Automated Machining Technology， 2021（1）： 164-168.）

［3］Luo Shu. Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning［J］. Applied Soft Computing， 2020， 91： 106208.

［4］裴小兵， 楊景霞. 一種解決帶有緊急插單問(wèn)題的果蠅優(yōu)化算法［J］. 系統(tǒng)工程， 2020， 38（6）： 139-146. （Pei Xiaobing， Yang Jingxia. A fruit fly optimization algorithm for solving the problem with urgent insertion orders［J］. Systems Engineering， 2020， 38（6）： 139-146.）

［5］張祥， 王艷， 紀(jì)志成. 基于動(dòng)態(tài)交互層的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題研究［J］. 系統(tǒng)仿真學(xué)報(bào)， 2020， 32（11）： 2129-2137. （Zhang Xiang， Wang Yan， Ji Zhicheng. Research on dynamic scheduling problem of flexible job shop based on dynamic interaction layer［J］. Journal of System Simulation， 2020， 32（11）： 2129-2137.）

［6］包博， 張琳， 張搏. 設(shè)備故障條件下柔性作業(yè)車間重調(diào)度方法［J］. 計(jì)算機(jī)工程與應(yīng)用， 2018， 54（19）： 248-253. （Bao Bo， Zhang Lin， Zhang Bo. A flexible job shop rescheduling method under equipment failure conditions［J］. Computer Engineering and App-lications， 2018， 54（19）： 248-253.）

［7］Ahmadi E， Zandieh M， Farrokh M， et al. A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms［J］. Computers & Operations Research， 2016， 73： 56-66.

［8］Salama S， Toshiya K， Nobutada F， et al. Evolving dispatching rules using genetic programming for multi-objective dynamic job shop scheduling with machine breakdowns［J］. Procedia CIRP， 2021， 104： 411-416.

［9］侯婭楠， 袁逸萍， 巴智勇， 等. 機(jī)器混合故障下柔性作業(yè)車間魯棒調(diào)度方法［J］. 機(jī)械設(shè)計(jì)與制造， 2022（4）： 1-4，9. （Hou Yanan， Yuan Yiping， Ba Zhiyong， et al. Robust scheduling method for flexible job shop under mixed machine breakdown［J］. Machine Design and Manufacturing， 2022（4）： 1-4，9.）

［10］Sajadi S M， Alizadeh A， Zandieh M， et al. Robust and stable flexible job shop scheduling with random machine breakdowns： multi-objectives genetic algorithm approach［J］. International Journal of Mathematics in Operational Research， 2019， 14（2）： 268-289.

［11］苗志鴻， 楊明順， 王雪峰， 等. 考慮優(yōu)先級(jí)的IPPS緊急訂單處理問(wèn)題研究［J］. 西安理工大學(xué)學(xué)報(bào)， 2019， 35（4）： 434-442. （Miao Zhihong， Yang Mingshun， Wang Xuefeng， et al. Research on IPPS emergency order processing problem considering priority［J］. Journal of Xi’an University of Technology， 2019， 35（4）： 434-442.）

［12］金鵬博， 唐秋華， 成麗新， 等. 機(jī)器故障下柔性作業(yè)車間的生產(chǎn)重調(diào)度方式?jīng)Q策模型［J］. 計(jì)算機(jī)集成制造系統(tǒng)， 2023， 29（11）： 3750-3761. （Jin Pengbo， Tang Qiuhua， Cheng Lixin， et al. A decision model for production rescheduling approach in flexible job shops under machine failure［J］. Computer Integrated Manufacturing Systems， 2023， 29（11）： 3750-3761.）

［13］李瑞， 徐華， 楊金峰， 等. 改進(jìn)近鄰人工蜂群算法求解柔性作業(yè)車間調(diào)度問(wèn)題［J］. 計(jì)算機(jī)應(yīng)用研究， 2024， 41（2）： 438-443. （Li Rui， Xu Hua， Yang Jinfeng， et al. Improved algorithm of near-neighbor artificial bee colony for flexible job-shop scheduling［J］. Application Research of Computers， 2024， 41（2）： 438-443.）

［14］Caldeira R H， Gnanavelbabu A. Solving the flexible job shop scheduling problem using an improved Jaya algorithm［J］. Computers & Industrial Engineering， 2019， 137： 106064.

［15］Alzaqebah M， Jawarneh S， Alwohaibi M， et al. Hybrid brain storm optimization algorithm and late acceptance hill climbing to solve the flexible job-shop scheduling problem［J］. Journal of King Saud University-Computer and Information Sciences， 2022， 34（6）： 2926-2937.

［16］Baykasogˇlu A， Madenogˇlu F S， Hamzaday A. Greedy randomized adaptive search for dynamic flexible job-shop scheduling［J］. Journal of Manufacturing Systems， 2020， 56： 425-451.

［17］Zarrouk R， Bennour I E， Jemai A. A two-level particle swarm optimization algorithm for the flexible job shop scheduling problem［J］. Swarm Intelligence， 2019， 13（2）： 145-168.

［18］Serna N J E， Seck-Tuoh-Mora J C， Medina-Marin J， et al. A global-local neighborhood search algorithm and Tabu search for flexible job shop scheduling problem［J］. PeerJ Computer Science， 2021， 7： e574.

［19］曹慶奎， 張曉麗， 任向陽(yáng). 考慮模糊交貨期的柔性作業(yè)車間動(dòng)態(tài)調(diào)度研究［J］. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)， 2019， 49（22）： 65-78. （Cao Qingkui， Zhang Xiaoli， Ren Xiangyang. Research on dynamic scheduling of flexible job shop considering fuzzy delivery date［J］. Practice and Understanding of Mathematics， 2019， 49（22）： 65-78.）

［20］Hernández-Gress E S， Seck-Tuoh-Mora J C， Hernández-Romero N， et al. The solution of the concurrent layout scheduling problem in the job-shop environment through a local neighborhood search algorithm［J］. Expert Systems with Applications， 2020， 144： 113096.

［21］劉瓊， 張超勇， 饒運(yùn)清， 等. 改進(jìn)遺傳算法解決柔性作業(yè)車間調(diào)度問(wèn)題［J］. 工業(yè)工程與管理， 2009， 14（2）： 59-66. （Liu Qiong， Zhang Chaoyong， Rao Yunqing， et al. Improved genetic algorithm to solve flexible job shop scheduling problem［J］. Industrial Enginee-ring and Management， 2009， 14（2）： 59-66.）

［22］Derrac J， García S， Molina D， et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms［J］. Swarm and Evolutionary Computation， 2011， 1（1）： 3-18.