改進(jìn)遺傳算法求解柔性作業(yè)車間的動(dòng)態(tài)重調(diào)度問題

摘要：針對柔性作業(yè)車間在生產(chǎn)過程中常因機(jī)器故障和緊急插單事件導(dǎo)致調(diào)度方案可實(shí)施性下降的問題，文章提出了一種重調(diào)度方法。該方法通過結(jié)合動(dòng)態(tài)調(diào)整策略與事件驅(qū)動(dòng)重調(diào)度策略，實(shí)現(xiàn)了對動(dòng)態(tài)事件的即時(shí)檢測與分析。同時(shí)，采用整合了POX交叉（優(yōu)先操作交叉）與鄰域搜索變異操作的改進(jìn)遺傳算法，對調(diào)度方案進(jìn)行了優(yōu)化。通過實(shí)施右移動(dòng)重調(diào)度和完全重調(diào)度的仿真實(shí)驗(yàn)，驗(yàn)證了改進(jìn)遺傳算法在動(dòng)態(tài)重調(diào)度中的優(yōu)化效果，表明該算法能夠有效提升生產(chǎn)系統(tǒng)的穩(wěn)定性和適應(yīng)性。

關(guān)鍵詞：柔性作業(yè)車間；動(dòng)態(tài)重調(diào)度；改進(jìn)遺傳算法；機(jī)器故障；緊急插單

中圖分類號：TP301.6" " "文獻(xiàn)標(biāo)識碼：A" " "文章編號：1674-0688（2024）11-0001-07

0 引言

隨著全球經(jīng)濟(jì)一體化的不斷深入，國際競爭日益激烈，企業(yè)生產(chǎn)面臨諸多不可預(yù)見的動(dòng)態(tài)性事件，這些事件極大地增加了生產(chǎn)的不確定性。柔性作業(yè)車間調(diào)度問題，因其對復(fù)雜生產(chǎn)環(huán)境的適應(yīng)性和靈活性，已成為學(xué)術(shù)界和工業(yè)界共同關(guān)注的焦點(diǎn)。在生產(chǎn)過程中，諸如機(jī)器故障、訂單變動(dòng)等動(dòng)態(tài)事件常導(dǎo)致初始調(diào)度方案失效，迫使企業(yè)進(jìn)行動(dòng)態(tài)重調(diào)度。由于傳統(tǒng)的靜態(tài)調(diào)度方法難以有效應(yīng)對這些突發(fā)變化，因此在動(dòng)態(tài)環(huán)境中實(shí)現(xiàn)高效的重調(diào)度成為解決柔性作業(yè)車間動(dòng)態(tài)重調(diào)度問題的關(guān)鍵。

近年來，國內(nèi)外眾多學(xué)者在復(fù)雜的柔性作業(yè)車間動(dòng)態(tài)重調(diào)度模型研究中取得了諸多成果。例如，Guo等［1］針對動(dòng)態(tài)柔性作業(yè)車間調(diào)度問題，提出了一種改進(jìn)的遺傳規(guī)劃超啟發(fā)式方法進(jìn)行求解；Tian等［2］考慮了多品種小批量動(dòng)態(tài)柔性作業(yè)車間中的多資源約束能效調(diào)度問題，并通過新的多目標(biāo)雙種群差分人工蜂群算法對模型進(jìn)行求解；Wei等［3］使用基于博弈論的多目標(biāo)候鳥優(yōu)化算法解決柔性作業(yè)車間的動(dòng)態(tài)重調(diào)度問題，并在改進(jìn)的遷移算法中設(shè)計(jì)了基于路徑重連和機(jī)器年齡的鄰域算子以提高搜索能力。此外，周爾民等［4］借助結(jié)合了變鄰域搜索的改進(jìn)遺傳算法，從機(jī)器故障角度對柔性作業(yè)車間動(dòng)態(tài)調(diào)度方法進(jìn)行研究，并建立了相應(yīng)的模型。趙新等［5］在改進(jìn)的GWO（灰狼優(yōu)化）算法的基礎(chǔ)上對柔性作業(yè)車間動(dòng)態(tài)調(diào)度模型進(jìn)行求解。劉思宇等［6］針對混合流水車間中的緊急插單重調(diào)度問題，提出了一種雙層編碼的超啟發(fā)式遺傳算法，并設(shè)計(jì)了自適應(yīng)變異算子以增強(qiáng)算法的有效性。苑明海等［7］通過回歸算法和K近鄰值分類算法，研究了帶有緊急訂單的混合流水車間插單重調(diào)度問題。王晉等［8］則構(gòu)建了一種基于非合作博弈和RFID的緊急訂單下的柔性作業(yè)車間動(dòng)態(tài)調(diào)度方法框架。

然而，這些研究仍存在以下幾個(gè)問題：一是處理動(dòng)態(tài)變化時(shí)，僅側(cè)重于算法改進(jìn)，并在故障發(fā)生后采用完全重調(diào)度或右移重調(diào)度策略，缺乏對重調(diào)度必要性的充分考量以及對重調(diào)度方法的對比選擇，同時(shí)面臨局部最優(yōu)和尋優(yōu)效率不足的挑戰(zhàn)；二是現(xiàn)有研究多聚焦于靜態(tài)優(yōu)化層面，對動(dòng)態(tài)重調(diào)度問題的深入探討尚顯不足。因此，本文提出了一種改進(jìn)的遺傳算法，旨在解決柔性車間的動(dòng)態(tài)重調(diào)度問題。該算法結(jié)合了動(dòng)態(tài)調(diào)整策略和重調(diào)度策略，通過事件驅(qū)動(dòng)的方式實(shí)時(shí)監(jiān)控并響應(yīng)生產(chǎn)過程中的突發(fā)事件，如機(jī)器故障和訂單加急。在工序和機(jī)器選擇部分，分別采用POX交叉和均勻交叉進(jìn)行交叉操作，并利用鄰域搜索變異方法提高解的多樣性和質(zhì)量，從而提升算法在動(dòng)態(tài)環(huán)境中的魯棒性和響應(yīng)速度。在應(yīng)對機(jī)器故障和訂單加急等動(dòng)態(tài)事件時(shí)，該算法顯著提升了生產(chǎn)系統(tǒng)的調(diào)度效率和穩(wěn)定性。

1 柔性作業(yè)車間動(dòng)態(tài)重調(diào)度方法

1.1 問題描述

柔性作業(yè)車間動(dòng)態(tài)重調(diào)度問題是指在動(dòng)態(tài)事件的影響下，為包含多臺(tái)機(jī)器和多道工序的生產(chǎn)環(huán)境重新制定調(diào)度計(jì)劃的過程［9］。在此過程中，每臺(tái)機(jī)器在任何給定時(shí)間點(diǎn)僅能加工一個(gè)工件，并且每個(gè)工件必須按規(guī)定的順序完成其所有工序。這些工序可在其可選機(jī)器集合中的任意一臺(tái)機(jī)器上執(zhí)行。然而，在實(shí)際生產(chǎn)過程中，工件的到達(dá)時(shí)間、工序的加工時(shí)間及順序常因突發(fā)事件和不確定因素而變動(dòng)，因此必須采用動(dòng)態(tài)重調(diào)度方法及時(shí)調(diào)整生產(chǎn)計(jì)劃以適應(yīng)這些變化。

1.2 數(shù)學(xué)模型

為解決柔性作業(yè)車間動(dòng)態(tài)重調(diào)度問題，本研究在分析實(shí)際生產(chǎn)環(huán)境特征的基礎(chǔ)上，構(gòu)建了一套數(shù)學(xué)模型以優(yōu)化工件加工順序和資源分配。為簡化問題描述并確保模型的可行性和準(zhǔn)確性，在模型構(gòu)建時(shí)依據(jù)了以下假設(shè)條件：①單機(jī)加工約束，即一臺(tái)機(jī)器在同一時(shí)間內(nèi)只能對1個(gè)工件進(jìn)行加工，并且加工過程不被中斷或搶占。②單工件加工約束，即每個(gè)工件在任意時(shí)刻只能被分配到1臺(tái)機(jī)器進(jìn)行加工。③單時(shí)刻加工限制，即同一時(shí)刻，1臺(tái)機(jī)器至多加工1個(gè)工件。④初始狀態(tài)約束，即機(jī)器在零時(shí)刻處于空閑狀態(tài)，并且在整個(gè)加工周期內(nèi)保持可用。⑤連續(xù)加工約束，即機(jī)器可在任何時(shí)刻連續(xù)加工待加工的工件。⑥加工順序靈活性，即工件之間的加工順序具有靈活性，不存在固定的次序約束。⑦忽略運(yùn)輸時(shí)間，即不考慮機(jī)器之間的運(yùn)輸時(shí)間，工件在一臺(tái)機(jī)器上完成一道工序后，立即轉(zhuǎn)至下一道工序的加工機(jī)器。⑧計(jì)入工序安裝時(shí)間，即工序的安裝時(shí)間計(jì)入工序的總加工時(shí)長內(nèi)。⑨固定技術(shù)路徑，即工件的技術(shù)路徑是固定的，不可更改。

通過上述假設(shè)條件，本研究的數(shù)學(xué)模型有效簡化了柔性車間調(diào)度問題的復(fù)雜性，并確保了其在動(dòng)態(tài)生產(chǎn)環(huán)境中的適用性與可操作性，為后續(xù)求解算法的設(shè)計(jì)與優(yōu)化提供了理論基礎(chǔ)。模型中涉及的參數(shù)定義見表1。

在數(shù)學(xué)模型的構(gòu)建中，最小化最大完工時(shí)間的目標(biāo)函數(shù)表示為

[makespan=minmax" makespan]。" " " " （1）

約束條件如下：

（1）任意工序在機(jī)器上只加工1次，工序唯一加工約束條件表示為

其中：Xijz?表示工件i的第j道工序是否分配到機(jī)器z加工；?是數(shù)學(xué)模型中的邏輯符號，表示“對于所有”或“任意”，?后跟隨的變量表示約束條件適用于這些變量的所有可能取值。

（2）工序開工后不能中斷，工序不可中斷約束條件表示為

其中：Cij?為工序j的完工時(shí)間；Sij?為其開工時(shí)間；Tijz?為工序在機(jī)器z上的加工時(shí)間。

（3）任意工序的完工時(shí)間要小于開工時(shí)間，工序時(shí)間先后約束條件表示為

（4）在同一時(shí)間內(nèi)1臺(tái)機(jī)器只能對1道工序進(jìn)行加工，單機(jī)加工約束條件表示為

其中： M為一個(gè)充分大的常數(shù)，Gabij? 表示工序a和工序b在時(shí)間上是否發(fā)生沖突。

（5）對于任意工件下一道工序的開工時(shí)間需要小于上一道工序的完工時(shí)間，工序順序約束條件為

2 動(dòng)態(tài)調(diào)整與重調(diào)度策略

2.1 重調(diào)度策略

重調(diào)度是指在生產(chǎn)過程中，為應(yīng)對機(jī)器故障、訂單變更或緊急任務(wù)等動(dòng)態(tài)變化事件，重新制定生產(chǎn)計(jì)劃的過程［10］。在柔性作業(yè)車間的生產(chǎn)中，這些動(dòng)態(tài)事件往往會(huì)擾亂原有的調(diào)度計(jì)劃，從而對生產(chǎn)效率產(chǎn)生不利影響。為應(yīng)對這一問題，本文提出了一種結(jié)合動(dòng)態(tài)調(diào)整與重調(diào)度策略的改進(jìn)遺傳算法。該算法首先通過實(shí)時(shí)監(jiān)控生產(chǎn)過程中的關(guān)鍵參數(shù)，實(shí)現(xiàn)對機(jī)器故障、緊急插單等動(dòng)態(tài)事件的即時(shí)檢測與識別。一旦檢測到相關(guān)事件，立即啟動(dòng)動(dòng)態(tài)調(diào)整機(jī)制，詳細(xì)記錄事件信息，并迅速生成初步的重調(diào)度方案，將受影響的工件任務(wù)重新分配給其他可用的機(jī)器。隨后，利用經(jīng)過改進(jìn)的遺傳算法對初步方案進(jìn)行全局范圍內(nèi)的優(yōu)化處理，通過采用混合編碼、均勻交叉及POX交叉等操作，進(jìn)一步提升調(diào)度方案的質(zhì)量和穩(wěn)定性。通過對MK01算例的仿真實(shí)驗(yàn)，驗(yàn)證了所提改進(jìn)遺傳算法在動(dòng)態(tài)環(huán)境下的有效性和魯棒性。實(shí)驗(yàn)結(jié)果表明，該策略能夠顯著降低生產(chǎn)延遲，提高生產(chǎn)系統(tǒng)的整體效率和適應(yīng)性，確保在動(dòng)態(tài)環(huán)境中生產(chǎn)的穩(wěn)定運(yùn)行。

2.2 調(diào)度策略及流程框架

動(dòng)態(tài)調(diào)度問題的復(fù)雜性更高，傳統(tǒng)的靜態(tài)調(diào)度方法通常無法直接應(yīng)用于動(dòng)態(tài)調(diào)度問題的研究中。目前，較為普遍的研究方向是將優(yōu)化算法與滾動(dòng)窗口重調(diào)度方法（圖1）相結(jié)合，以提升調(diào)度方案對復(fù)雜多變的動(dòng)態(tài)環(huán)境的適應(yīng)能力。

當(dāng)滾動(dòng)窗口被觸發(fā)時(shí)，需根據(jù)實(shí)際生產(chǎn)情況選擇合適的重調(diào)度方式。目前，滾動(dòng)重調(diào)度策略主要包括事件驅(qū)動(dòng)重調(diào)度、周期性重調(diào)度和基于周期與事件驅(qū)動(dòng)的重調(diào)度3種。本文主要聚焦于事件驅(qū)動(dòng)重調(diào)度（圖2）的研究。

事件驅(qū)動(dòng)重調(diào)度策略旨在應(yīng)對生產(chǎn)過程中發(fā)生的特定事件，以確保生產(chǎn)效率和滿足交貨期要求。該策略通過及時(shí)響應(yīng)突發(fā)事件，最大限度地減少對生產(chǎn)流程的負(fù)面影響，從而提升生產(chǎn)系統(tǒng)的適應(yīng)性和靈活性。常見的突發(fā)事件包括機(jī)器故障（即機(jī)器意外停機(jī)需修復(fù)）、訂單變更（涉及新訂單的加入、現(xiàn)有訂單的修改或取消，以及訂單優(yōu)先級的調(diào)整）、緊急插單（需優(yōu)先處理的緊急訂單，通常要求快速完成）、加工時(shí)間變動(dòng)（因材料問題、技術(shù)故障等因素導(dǎo)致的實(shí)際加工時(shí)間與預(yù)期不符）和資源變化（包括人力、材料供應(yīng)的波動(dòng)，可能源于供應(yīng)鏈問題或人員調(diào)整）。在事件驅(qū)動(dòng)的重調(diào)度機(jī)制中，機(jī)器故障和緊急插單對調(diào)度方案的影響最為直接，并且為車間實(shí)際生產(chǎn)中最為常見的動(dòng)態(tài)事件。因此，針對這兩類動(dòng)態(tài)事件，構(gòu)建了整體動(dòng)態(tài)調(diào)度流程框架（圖3）。

具體的執(zhí)行步驟如下：①根據(jù)車間的實(shí)際情況，制定并執(zhí)行初始調(diào)度方案。②在初始方案執(zhí)行期間，對生產(chǎn)過程進(jìn)行實(shí)時(shí)監(jiān)控，接收并判定動(dòng)態(tài)事件信息，主要包括緊急插單和機(jī)器故障。③若未檢測到事件發(fā)生，則繼續(xù)執(zhí)行原有生產(chǎn)調(diào)度方案。④一旦動(dòng)態(tài)事件發(fā)生，立即啟動(dòng)事件驅(qū)動(dòng)的重調(diào)度機(jī)制，并結(jié)合遺傳算法構(gòu)建重調(diào)度模型，生成新的調(diào)度方案。⑤評估執(zhí)行重調(diào)度操作后的任務(wù)完成情況，若全部任務(wù)已完成，則結(jié)束流程；若仍有未完成任務(wù)，則繼續(xù)執(zhí)行新的調(diào)度方案。

3 改進(jìn)遺傳算法

3.1 算法概述

遺傳算法是由Holland［11］基于自然生物的遺傳進(jìn)化原理提出的并行搜索算法，主要涉及目標(biāo)函數(shù)的選擇、初始化、適應(yīng)度計(jì)算及遺傳算子等多個(gè)關(guān)鍵問題，通過不斷迭代逐步趨近最優(yōu)解或次優(yōu)解［12］。然而，在應(yīng)對動(dòng)態(tài)變化時(shí)，傳統(tǒng)遺傳算法通常需要重新計(jì)算整個(gè)調(diào)度計(jì)劃，既耗時(shí)且效率低下。相比之下，改進(jìn)后的遺傳算法通過結(jié)合局部調(diào)整與全局優(yōu)化策略，顯著提高了調(diào)度系統(tǒng)在動(dòng)態(tài)環(huán)境中的魯棒性和響應(yīng)速度。同時(shí)，該算法還融入了動(dòng)態(tài)調(diào)整策略和重調(diào)度策略，能夠靈活應(yīng)對生產(chǎn)中的各種突發(fā)事件，進(jìn)而提高了調(diào)度系統(tǒng)的效率和穩(wěn)定性。

3.2 種群初始化

傳統(tǒng)遺傳算法通常采用直接的二進(jìn)制或整數(shù)編碼方式，而本文則對傳統(tǒng)的編碼方式進(jìn)行了改進(jìn)，設(shè)計(jì)了一種MSOS混合編碼方式（圖4）。該混合編碼方式將編碼結(jié)構(gòu)劃分為工序、機(jī)器及工件在對應(yīng)機(jī)器上的加工時(shí)間3個(gè)部分以更好地適應(yīng)復(fù)雜的動(dòng)態(tài)調(diào)度問題。

對于MSOS染色體，需進(jìn)行解碼操作，解碼的關(guān)鍵在于將工序排序部分轉(zhuǎn)化為對應(yīng)機(jī)器選擇部分的實(shí)際調(diào)度，具體解碼步驟如下。

步驟1：對機(jī)器選擇部分進(jìn)行解碼，從左至右依次讀取并轉(zhuǎn)換為機(jī)器順序矩陣[JM]和時(shí)間順序矩陣[T]。其中，[JMj， ?]表示工件[Jj]的工序[O?]所分配的機(jī)器編號，[JMj，?]表示工件[Jj]的所有工序按優(yōu)先順序排列所對應(yīng)的機(jī)器編號；[Tj， ?]表示工件[Jj]的工序[O?]的加工時(shí)長。

步驟2：對工序排序部分的染色體從左至右依次讀取。根據(jù)步驟1得到的機(jī)器順序矩陣JM和時(shí)間順序矩陣T，依次確定每個(gè)工件工序的加工機(jī)器和加工時(shí)間，并進(jìn)行排序，最終得到調(diào)度結(jié)果。

3.3 交叉操作

在遺傳算法中，交叉操作是通過特定方式組合父代個(gè)體以產(chǎn)生新的個(gè)體的主要操作之一。在機(jī)器選擇部分，采用均勻交叉操作，詳細(xì)步驟如下：①在區(qū)間[1， T0]內(nèi)隨機(jī)選擇一個(gè)整數(shù)[r]作為交換位置的數(shù)量。②隨機(jī)確定[r]個(gè)交換位置。③交換父代染色體[P1]和[P2]在這些位置上的基因，從而生成子代染色體[C1]和[C2]。④保留父代染色體中未被交換的基因，并按原順序填充到子代染色體中相應(yīng)的位置。

對于工序排序部分，采用POX交叉操作（圖5），旨在保留父代中的優(yōu)秀特征并傳遞給子代，具體步驟如下：①從工件集中隨機(jī)選擇若干工件，組成集合[J1]和[J2]。②直接將父代染色體[P1]和[P2]中屬于[J1]或[J2]的工件基因復(fù)制到相應(yīng)的子代染色體 [C1]和[C2]中，并保持原有位置不變。③將不屬于[J1]或[J2]的工件基因按順序填充到子代染色體中的空位上，同時(shí)保持這些基因間的相對順序一致。

3.4 變異操作

變異操作通過隨機(jī)調(diào)整染色體中的部分基因，實(shí)現(xiàn)對染色體的小幅擾動(dòng)，進(jìn)而生成新的個(gè)體，旨在增加種群的復(fù)雜性和多樣性。本文設(shè)計(jì)了一種改進(jìn)的變異方法，分別針對機(jī)器選擇和工件調(diào)度兩個(gè)部分進(jìn)行處理。在機(jī)器選擇部分的變異操作中，首先隨機(jī)選定變異染色體中的若干位置，隨后將這些位置上的機(jī)器基因替換為對應(yīng)工序加工時(shí)間最短的機(jī)器。工件調(diào)度采用鄰域搜索變異操作（圖6），通過調(diào)整工件的加工順序優(yōu)化調(diào)度結(jié)果。

鄰域搜索變異操作的具體步驟如下：①從變異染色體中隨機(jī)選取部分基因，生成其可能的鄰域解集合。②評估所有鄰域解的適應(yīng)度值，并從中選取適應(yīng)度最高的解作為子代個(gè)體。

3.5 選擇操作

本文的改進(jìn)遺傳算法采用了基于輪盤賭的選擇策略。該策略依據(jù)個(gè)體的適應(yīng)度比例進(jìn)行選擇，適應(yīng)度越高的個(gè)體被選中的概率越大。具體實(shí)現(xiàn)時(shí)，首先計(jì)算每個(gè)個(gè)體的適應(yīng)度值及其總和，確定各個(gè)體被選擇的概率，以此構(gòu)建輪盤。最終通過隨機(jī)數(shù)確定選擇結(jié)果，確保優(yōu)秀基因在進(jìn)化過程中的傳遞，進(jìn)而提升算法的整體性能。

4 仿真實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證改進(jìn)遺傳算法在柔性作業(yè)車間動(dòng)態(tài)重調(diào)度問題中的有效性，本文分別進(jìn)行了靜態(tài)調(diào)度和動(dòng)態(tài)重調(diào)度的仿真實(shí)驗(yàn)，并對實(shí)驗(yàn)結(jié)果進(jìn)行了詳細(xì)分析。實(shí)驗(yàn)選用了Brandimarte［13］提出的10個(gè)案例中的Mk01算例，在64位Windows10操作系統(tǒng)、配備Intel（R） Core（TM）i5-5600 CPU@3.60GHz處理器和NVIDIA RTX2060" Super GPU的硬件環(huán)境下進(jìn)行。實(shí)驗(yàn)參數(shù)設(shè)置見表2。

4.1 車間靜態(tài)調(diào)度性能

在靜態(tài)調(diào)度環(huán)節(jié)，分別采用改進(jìn)遺傳算法和改進(jìn)前的遺傳算法進(jìn)行仿真實(shí)驗(yàn)，每種算法均獨(dú)立運(yùn)行100次，并記錄各自的最優(yōu)結(jié)果以進(jìn)行對比分析。實(shí)驗(yàn)結(jié)果顯示，改進(jìn)遺傳算法在優(yōu)化效果和收斂性方面均優(yōu)于改進(jìn)前的遺傳算法。兩種算法在完工時(shí)間隨迭代次數(shù)變化方面的對比情況見圖7，改進(jìn)遺傳算法的甘特圖見圖8。從圖7和圖8中可以看出，改進(jìn)遺傳算法不僅顯著提高了最優(yōu)解的質(zhì)量，還加速了收斂進(jìn)程，充分驗(yàn)證了其在靜態(tài)調(diào)度任務(wù)中的優(yōu)越性。

4.2 車間動(dòng)態(tài)重調(diào)度性能驗(yàn)證

為驗(yàn)證動(dòng)態(tài)重調(diào)度方法的有效性，本文以最小化完工時(shí)間為目標(biāo)，結(jié)合動(dòng)態(tài)調(diào)整策略和重調(diào)度策略，針對機(jī)器故障和緊急插單兩種突發(fā)事件，選取適當(dāng)?shù)闹卣{(diào)度策略進(jìn)行調(diào)整和優(yōu)化。研究的重點(diǎn)在于右移重調(diào)度和完全重調(diào)度兩種策略。原始調(diào)度方案甘特圖見圖9，機(jī)器故障（設(shè)定發(fā)生于第40 s，機(jī)器M2故障，持續(xù)10 s）情境下的右移重調(diào)度和完全重調(diào)度甘特圖分別見圖10和圖11；緊急插單（設(shè)定于第40 s，在機(jī)器M2插入一個(gè)緊急任務(wù)，任務(wù)時(shí)長為10" s）情境下的右移重調(diào)度和完全重調(diào)度甘特圖分別見圖12和圖13。

根據(jù)圖10至圖13的仿真實(shí)驗(yàn)分析結(jié)果，當(dāng)面臨機(jī)器故障或緊急插單等突發(fā)事件時(shí)，完全重調(diào)度策略相較于右移重調(diào)度策略，能夠取得更短的完工時(shí)間和更優(yōu)的整體效果。這是因?yàn)橛乙浦卣{(diào)度方案僅是在特定時(shí)間點(diǎn)插入動(dòng)態(tài)事件，而不改變原始編碼，僅將受影響的任務(wù)向后推移；而完全重調(diào)度方案則會(huì)對原始編碼進(jìn)行調(diào)整，在既定約束條件下，受動(dòng)態(tài)事件影響的工序編碼具有可變性。通過運(yùn)用改進(jìn)的遺傳算法對可變部分進(jìn)行交叉和變異操作，完全重調(diào)度策略能夠生成更優(yōu)的新調(diào)度方案，從而提高重調(diào)度方案的效率。這一結(jié)果進(jìn)一步證實(shí)了改進(jìn)遺傳算法在復(fù)雜生產(chǎn)環(huán)境中對突發(fā)事件的快速響應(yīng)能力，以及其在求解柔性作業(yè)車間動(dòng)態(tài)重調(diào)度問題上的優(yōu)越性能。

5 應(yīng)用案例

本文的應(yīng)用案例為智能信息感知及處理技術(shù)湖南省重點(diǎn)實(shí)驗(yàn)室及其合作單位湖南云智迅聯(lián)科技發(fā)展有限公司的實(shí)踐案例。針對復(fù)雜的柔性作業(yè)車間中因機(jī)器故障和緊急插單事件引發(fā)的調(diào)度方案可執(zhí)行性下降問題，本文算法結(jié)合了動(dòng)態(tài)調(diào)整策略與事件驅(qū)動(dòng)重調(diào)度策略，對生產(chǎn)排程結(jié)果進(jìn)行了優(yōu)化。實(shí)際項(xiàng)目優(yōu)化后的部分排程結(jié)果見圖14。

6 結(jié)論

針對柔性作業(yè)車間的動(dòng)態(tài)重調(diào)度問題，本文提出了一種結(jié)合動(dòng)態(tài)調(diào)整與事件驅(qū)動(dòng)策略的改進(jìn)遺傳算法。該算法以最大完工時(shí)間作為目標(biāo)函數(shù)，采用Mk01數(shù)據(jù)集作為統(tǒng)一數(shù)據(jù)集，與改進(jìn)前的遺傳算法進(jìn)行對比。結(jié)果表明，改進(jìn)后的遺傳算法表現(xiàn)出更好的優(yōu)化效果和收斂性能。針對機(jī)器故障和緊急插單兩類突發(fā)事件，本研究驗(yàn)證了完全重調(diào)度策略的優(yōu)勢，該策略能有效減少生產(chǎn)延遲，提高調(diào)度效率，實(shí)驗(yàn)結(jié)論如下。

（1）在生產(chǎn)過程中，通過結(jié)合動(dòng)態(tài)調(diào)整與重調(diào)度策略，實(shí)時(shí)監(jiān)控關(guān)鍵生產(chǎn)參數(shù)，快速響應(yīng)并處理動(dòng)態(tài)事件，實(shí)現(xiàn)了生產(chǎn)調(diào)度的即時(shí)調(diào)整。該策略的實(shí)施顯著降低了生產(chǎn)延遲，提高了生產(chǎn)系統(tǒng)的整體效率和適應(yīng)性，確保了動(dòng)態(tài)環(huán)境下生產(chǎn)的穩(wěn)定運(yùn)行。

（2）在種群初始化階段，采用混合編碼方式，分別對機(jī)器選擇部分和工序排序部分進(jìn)行編碼，提升了編碼的靈活性，使其能更好地適應(yīng)調(diào)度規(guī)模的變化，同時(shí)加速了算法的收斂進(jìn)程。

（3）在交叉操作中，采用均勻交叉操作和POX交叉操作分別處理機(jī)器選擇部分和工序排序部分，并采用鄰域搜索變異方法，選取適應(yīng)度最高的解作為子代，從而有效避免了局部最優(yōu)解，增強(qiáng)了算法的尋優(yōu)能力。本研究為柔性作業(yè)車間在動(dòng)態(tài)環(huán)境下的生產(chǎn)調(diào)度提供了一種高效且穩(wěn)健的解決方案。然而，算法的復(fù)雜度和計(jì)算時(shí)間仍有待進(jìn)一步優(yōu)化。此外，當(dāng)前研究僅考慮了完工時(shí)間這一單一目標(biāo)，對于實(shí)際生產(chǎn)中可能涉及的其他重要目標(biāo)，仍需進(jìn)一步深入探索。

7 參考文獻(xiàn)

［1］GUO H X，LIU J H，WANG Y，et al.An improved genetic programming hyper-heuristic for the dynamic flexible job shop scheduling problem with reconfigurable manufacturing cells［J］.Journal of Manufacturing Systems，2024，74：252-263.

［2］TIAN Z Q，JIANG X Y，LIU W J，et al.Dynamic energy-efficient scheduling of multi-variety and small batch flexible job-shop：A case study for the aerospace industry［J］.Comput.Ind.Eng，2023，178：109111.

［3］WEI L X，HE J X，GUO Z Y，et al.A multi-objective migrating birds optimization algorithm based on game theory for dynamic flexible job shop scheduling problem［J］.Expert Systems With Applications，2023，227：120268.

［4］周爾民，馬暢，劉寧.考慮機(jī)器故障的柔性作業(yè)車間動(dòng)態(tài)調(diào)度［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2023（9）：188-192.

［5］趙新，譚殷飛，黎興寶，等.改進(jìn)GWO算法求解柔性鈑金車間動(dòng)態(tài)重調(diào)度問題［J］.工業(yè)控制計(jì)算機(jī)，2022，35（6）：141-144.

［6］劉思宇，李鐵克，王柏琳，等.混合流水車間插單重調(diào)度的超啟發(fā)式遺傳算法［J］.計(jì)算機(jī)應(yīng)用研究，2023，40（9）：2609-2615.

［7］苑明海，黃涵鈺，蔡仙仙，等.隱性擾動(dòng)下智能車間資源重調(diào)度決策方法研究［J］.制造技術(shù)與機(jī)床，2023（9）：102-108，137.

［8］王晉，彭琰舉，羅庚合.基于非合作博弈和RFID的緊急加單下柔性作業(yè)車間動(dòng)態(tài)調(diào)度方法［J］.制造技術(shù)與機(jī)床，2018（6）：164-170.

［9］王艷，丁宇.動(dòng)態(tài)柔性作業(yè)車間優(yōu)化調(diào)度與決策方法［J］.系統(tǒng)仿真學(xué)報(bào)，2020，32（11）：2073-2083.

［10］李俊青，李文涵，陶昕瑞，等.時(shí)間約束混合流水車間調(diào)度問題綜述［J］.控制理論與應(yīng)用，2020，37（11）：2273-2290.

［11］HOLLAND J H.Adaptation in natural and artificial systems［M］.Ann Arbor：The University of Michigan Press，1992：126-137.

［12］羅雄，錢謙，伏云發(fā).遺傳算法解柔性作業(yè)車間調(diào)度問題應(yīng)用綜述［J］.計(jì)算機(jī)工程與應(yīng)用，2019，55（23）：15-21，34.

［13］BRANDIMARTE P.Routing and scheduling in a flexible job shop by tabu search［J］.Annals of Operations Research，1993，41（3）：157-183.