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

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

中圖分類號：TP306.1;TH186 文獻標志碼：A

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

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

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

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

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

1 問題描述和模型建立

1.1 問題描述

FJSP可定義為：有n個工件，每個工件i=1，…，n有工序Oij。每道工序Oij都可以在m臺機器中選擇其中一臺進行加工，且工序Oij在機器k上的加工時間為Pijk。研究目標是通過為每道工序選擇一臺加工機器，并合理安排工序的加工順序，使總完工時間最小。

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

1.2 模糊質(zhì)檢時間和故障場景的說明

1）關于模糊質(zhì)檢時間的說明

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

2）關于故障場景的說明

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

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

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

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

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

1.4 模型的建立

建立初始模型如下：

目標函數(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）為最小化最大完工時間；式（2）表示工件在加工過程中不會中斷；式（3）表示每道工序需等前一工序完工后才能加工；式（4）表示每道工序都需等到前一道工序質(zhì)檢完成后才可加工；式（5）和（6）表示每臺機器在同一時刻只能加工一道工序。

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

當機器故障事件發(fā)生時，定義機器故障發(fā)生時的未加工工件數(shù)為n′，可用機器為m′，工件集合為J={Ji|（i1=1，2，3，…，n）}，每個工件有hi1={hi1|（i1=1，2，3，…，l）}道工序。目標函數(shù)不變，則考慮模糊質(zhì)檢時間的FJDSP在處理機器故障時需要在常規(guī)約束式（2）～（6）的基礎上，增加約束條件式（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）為機器發(fā)生故障時正在該機器上加工工件的已完工部分的比例；式（8）為加工中斷工件轉(zhuǎn)移到新機器上所需的加工時間；式（9）表示機器在加工工件過程中發(fā)生故障導致加工中斷；式（10）表示分配到故障機器上的工件需等質(zhì)檢結(jié)束后才可加工。

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

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

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

式（11）表示新插入工件只能在插入時間后開始加工，并且需要等到相應機器的前面工序完工后開始。

2 GA-CARRHCNS算法設計

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

2.1 編碼和解碼

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

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

解碼過程采用貪婪解碼方法，即對每道工序，找到該工序在所選機器上能夠加工的最早時間。

2.2 初始化種群

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

2.3 遺傳操作

2.3.1 選擇操作

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

2.3.2 交叉操作

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

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

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

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

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

2）面向機器碼的交叉操作

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

2.3.3 變異操作

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

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

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

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

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

2）面向機器碼的交叉操作

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

2.4 基于元胞自動機的鄰域搜索算法框架

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

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

2.5 隨機重啟爬坡算法

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

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

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

2.6 鄰域搜索

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

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

b）逆序。隨機選擇兩基因位，截取兩基因位之間的基因片段，將所有基因位上的工序號順序逆置，再將對應位置的機器號進行更換，如圖13所示。

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

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

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

2.7 整體算法流程

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

具體算法步驟為：

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

b）初始化種群；

c）采用精英篩選及錦標賽的方式對種群進行篩選；

d）將新種群進行交叉操作和變異操作；

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

f）隨機重啟爬坡；

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

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

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

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

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

3.1 算法有效性驗證

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

3.1.1 標準FJSP算例測試

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

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

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

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

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

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

RPD=BOV-BKVBOV×100（12）

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

另外，圖17以MK01為例展示了本文算法求解該算例的算法迭代曲線?？芍?，本文算法在迭代至第35次時已經(jīng)收斂到最優(yōu)解，說明算法穩(wěn)定有效。

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

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

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

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

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

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

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

1）機器故障的動態(tài)調(diào)度

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

參考文獻：

［1］米恬怡， 唐秋華， 成麗新， 等. 融合強化學習與變鄰域搜索的柔性作業(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)少鵬， 王婷， 周彤. 考慮多時間因素的綠色柔性作業(yè)車間動態(tài)調(diào)度［J］. 組合機床與自動化加工技術， 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］裴小兵， 楊景霞. 一種解決帶有緊急插單問題的果蠅優(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］張祥， 王艷， 紀志成. 基于動態(tài)交互層的柔性作業(yè)車間動態(tài)調(diào)度問題研究［J］. 系統(tǒng)仿真學報， 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］包博， 張琳， 張搏. 設備故障條件下柔性作業(yè)車間重調(diào)度方法［J］. 計算機工程與應用， 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］侯婭楠， 袁逸萍， 巴智勇， 等. 機器混合故障下柔性作業(yè)車間魯棒調(diào)度方法［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)先級的IPPS緊急訂單處理問題研究［J］. 西安理工大學學報， 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］金鵬博， 唐秋華， 成麗新， 等. 機器故障下柔性作業(yè)車間的生產(chǎn)重調(diào)度方式?jīng)Q策模型［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］李瑞， 徐華， 楊金峰， 等. 改進近鄰人工蜂群算法求解柔性作業(yè)車間調(diào)度問題［J］. 計算機應用研究， 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è)車間動態(tài)調(diào)度研究［J］. 數(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è)車間調(diào)度問題［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.