改進遺傳算法求解柔性作業車間的動態重調度問題

摘要：針對柔性作業車間在生產過程中常因機器故障和緊急插單事件導致調度方案可實施性下降的問題，文章提出了一種重調度方法。該方法通過結合動態調整策略與事件驅動重調度策略，實現了對動態事件的即時檢測與分析。同時，采用整合了POX交叉（優先操作交叉）與鄰域搜索變異操作的改進遺傳算法，對調度方案進行了優化。通過實施右移動重調度和完全重調度的仿真實驗，驗證了改進遺傳算法在動態重調度中的優化效果，表明該算法能夠有效提升生產系統的穩定性和適應性。

關鍵詞：柔性作業車間；動態重調度；改進遺傳算法；機器故障；緊急插單

中圖分類號：TP301.6" " "文獻標識碼：A" " "文章編號：1674-0688（2024）11-0001-07

0 引言

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

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

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

1 柔性作業車間動態重調度方法

1.1 問題描述

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

1.2 數學模型

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

通過上述假設條件，本研究的數學模型有效簡化了柔性車間調度問題的復雜性，并確保了其在動態生產環境中的適用性與可操作性，為后續求解算法的設計與優化提供了理論基礎。模型中涉及的參數定義見表1。

在數學模型的構建中，最小化最大完工時間的目標函數表示為

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

約束條件如下：

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

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

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

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

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

（4）在同一時間內1臺機器只能對1道工序進行加工，單機加工約束條件表示為

其中： M為一個充分大的常數，Gabij? 表示工序a和工序b在時間上是否發生沖突。

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

2 動態調整與重調度策略

2.1 重調度策略

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

2.2 調度策略及流程框架

動態調度問題的復雜性更高，傳統的靜態調度方法通常無法直接應用于動態調度問題的研究中。目前，較為普遍的研究方向是將優化算法與滾動窗口重調度方法（圖1）相結合，以提升調度方案對復雜多變的動態環境的適應能力。

當滾動窗口被觸發時，需根據實際生產情況選擇合適的重調度方式。目前，滾動重調度策略主要包括事件驅動重調度、周期性重調度和基于周期與事件驅動的重調度3種。本文主要聚焦于事件驅動重調度（圖2）的研究。

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

具體的執行步驟如下：①根據車間的實際情況，制定并執行初始調度方案。②在初始方案執行期間，對生產過程進行實時監控，接收并判定動態事件信息，主要包括緊急插單和機器故障。③若未檢測到事件發生，則繼續執行原有生產調度方案。④一旦動態事件發生，立即啟動事件驅動的重調度機制，并結合遺傳算法構建重調度模型，生成新的調度方案。⑤評估執行重調度操作后的任務完成情況，若全部任務已完成，則結束流程；若仍有未完成任務，則繼續執行新的調度方案。

3 改進遺傳算法

3.1 算法概述

遺傳算法是由Holland［11］基于自然生物的遺傳進化原理提出的并行搜索算法，主要涉及目標函數的選擇、初始化、適應度計算及遺傳算子等多個關鍵問題，通過不斷迭代逐步趨近最優解或次優解［12］。然而，在應對動態變化時，傳統遺傳算法通常需要重新計算整個調度計劃，既耗時且效率低下。相比之下，改進后的遺傳算法通過結合局部調整與全局優化策略，顯著提高了調度系統在動態環境中的魯棒性和響應速度。同時，該算法還融入了動態調整策略和重調度策略，能夠靈活應對生產中的各種突發事件，進而提高了調度系統的效率和穩定性。

3.2 種群初始化

傳統遺傳算法通常采用直接的二進制或整數編碼方式，而本文則對傳統的編碼方式進行了改進，設計了一種MSOS混合編碼方式（圖4）。該混合編碼方式將編碼結構劃分為工序、機器及工件在對應機器上的加工時間3個部分以更好地適應復雜的動態調度問題。

對于MSOS染色體，需進行解碼操作，解碼的關鍵在于將工序排序部分轉化為對應機器選擇部分的實際調度，具體解碼步驟如下。

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

步驟2：對工序排序部分的染色體從左至右依次讀取。根據步驟1得到的機器順序矩陣JM和時間順序矩陣T，依次確定每個工件工序的加工機器和加工時間，并進行排序，最終得到調度結果。

3.3 交叉操作

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

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

3.4 變異操作

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

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

3.5 選擇操作

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

4 仿真實驗及結果分析

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

4.1 車間靜態調度性能

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

4.2 車間動態重調度性能驗證

為驗證動態重調度方法的有效性，本文以最小化完工時間為目標，結合動態調整策略和重調度策略，針對機器故障和緊急插單兩種突發事件，選取適當的重調度策略進行調整和優化。研究的重點在于右移重調度和完全重調度兩種策略。原始調度方案甘特圖見圖9，機器故障（設定發生于第40 s，機器M2故障，持續10 s）情境下的右移重調度和完全重調度甘特圖分別見圖10和圖11；緊急插單（設定于第40 s，在機器M2插入一個緊急任務，任務時長為10" s）情境下的右移重調度和完全重調度甘特圖分別見圖12和圖13。

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

5 應用案例

本文的應用案例為智能信息感知及處理技術湖南省重點實驗室及其合作單位湖南云智迅聯科技發展有限公司的實踐案例。針對復雜的柔性作業車間中因機器故障和緊急插單事件引發的調度方案可執行性下降問題，本文算法結合了動態調整策略與事件驅動重調度策略，對生產排程結果進行了優化。實際項目優化后的部分排程結果見圖14。

6 結論

針對柔性作業車間的動態重調度問題，本文提出了一種結合動態調整與事件驅動策略的改進遺傳算法。該算法以最大完工時間作為目標函數，采用Mk01數據集作為統一數據集，與改進前的遺傳算法進行對比。結果表明，改進后的遺傳算法表現出更好的優化效果和收斂性能。針對機器故障和緊急插單兩類突發事件，本研究驗證了完全重調度策略的優勢，該策略能有效減少生產延遲，提高調度效率，實驗結論如下。

（1）在生產過程中，通過結合動態調整與重調度策略，實時監控關鍵生產參數，快速響應并處理動態事件，實現了生產調度的即時調整。該策略的實施顯著降低了生產延遲，提高了生產系統的整體效率和適應性，確保了動態環境下生產的穩定運行。

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

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

7 參考文獻

［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］.組合機床與自動化加工技術，2023（9）：188-192.

［5］趙新，譚殷飛，黎興寶，等.改進GWO算法求解柔性鈑金車間動態重調度問題［J］.工業控制計算機，2022，35（6）：141-144.

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

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

［8］王晉，彭琰舉，羅庚合.基于非合作博弈和RFID的緊急加單下柔性作業車間動態調度方法［J］.制造技術與機床，2018（6）：164-170.

［9］王艷，丁宇.動態柔性作業車間優化調度與決策方法［J］.系統仿真學報，2020，32（11）：2073-2083.

［10］李俊青，李文涵，陶昕瑞，等.時間約束混合流水車間調度問題綜述［J］.控制理論與應用，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］羅雄，錢謙，伏云發.遺傳算法解柔性作業車間調度問題應用綜述［J］.計算機工程與應用，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.