關鍵詞：柔性作業(yè)車間調度；Q-learning；改進NSGA-II；多目標優(yōu)化 中圖分類號：TH165 文獻標志碼：A 文章編號：1001-3695（2025）07-016-2039-09 doi：10.19734/j. issn.1001-3695.2024.11.0479

Abstract：Fortheflexiblejob shopenergy eficientscheduling problem（EEFJSP），thispaperconstructedaFJSPmodel with theoptimizationobjectivesof minimizingthemaximumcompletiontimeand minimizingthetotal energyconsumption.Firstly， it proposedanadaptivealgorithmbasedonreinforcementlearningco-evolutionaryalgorithm（QNSGA-II）to characteriethe problemmodel．Secondly，it introduced theconceptsof state spaceandaction spaces，and designedareward-punishment functionbasedoheoverallaveragefinesandpopulationdiversitytoensuretheefectivenessofthealgoritinteiterative processInorder toimprovetheabilityof theglobal searchandlocalsearch，itproposedanimproved tabusearchalgorithmto updatethepopulationaftercrosoverandmutation.Inordertoimprovetheabilityof globalsearchandlocal search，itproposedanimprovedtaboosearchalgorithmtoupdate thepopulationaftercrosoverandmutation.Finall，itanalyzedtheeffectivenessoftheimproved tabusearch strategyandthe Q-learning parameteradaptationstrategy toverifythealgorithm’seffectiveness andsuperiority，anditcomparedtheproposedQNSGA-Iwithother multi-objectiveoptimizationalgorithmsto verify the superiority of the algorithms in solving the EEFJSP.

Key Words：flexible job shop scheduling；Q-learning；improved NSGA-I ；multi-objective optimization

0 引言

近幾十年來，隨著環(huán)境的不斷惡化，政府呼呼節(jié)能減排，綠色制造已成為各國增強制造業(yè)核心競爭力的戰(zhàn)略重點。以航空航天為代表的高端裝備制造領域，更新迭代的速度加快，研制周期不斷縮短，研究如何利用柔性作業(yè)車間節(jié)能調度（EEFJSP）實現(xiàn)高端裝備總裝任務對各個生產環(huán)節(jié)的精準拉動生產，以達到降本增效、提升質量的目的，具有重要的理論意義和實際應用價值。FJSP最初由Brucker和Schlie于1990年提出，是經典JSP的延伸。而EEFJSP則更為復雜，屬于NP-hard問題[1]，旨在考慮了多個目標的情況下將待加工的作業(yè)更加合理地分配到各臺機器上，從而提高綜合效益。求解FJSP的方法主要分為精確算法、啟發(fā)式算法和智能優(yōu)化算法三類。精確算法的時間復雜度較大，不適合解決大規(guī)模的問題。啟發(fā)式算法的求解速度快，但解的質量往往不高。對于智能優(yōu)化算法，盡管近年來學者們已將諸如遺傳算法[2、蟻群算法[3、粒子群算法[4]、模擬退火算法[5]等智能算法應用到該問題的求解上，并取得了一定的效果，但至今仍沒有得出一套良好的解決方案，因此該問題仍具有很大的研究空間。

基于NSGA-Ⅱ解決車間調度問題的研究方面，Deb 等人[6]提出了NSGA-I算法，通過快速非支配排序和擁擠距離計算，被廣泛用于多目標優(yōu)化。然而，NSGA-I存在易早熟和多樣性不足等問題，許多學者對其進行了改進。姜一嘯等人[為解決以設備能耗、刀具磨損和切削液消耗為碳排放來源，能耗和人工費用為加工成本的多目標柔性作業(yè)車間低碳調度問題，提出一種改進帶精英策略的非支配遺傳算法，提高了算法后期的種群多樣性并保留了進化過程中的優(yōu)質個體。張國輝等人[8]考慮多名工人的協(xié)作與工人學習效應曲線，研究了一種考慮工人協(xié)作的雙資源柔性作業(yè)車間調度問題，并提出一種INSGA-I（improvenon-dominated sorted genetic algorithm-I）求解該問題。Tang等人提出了一種集成強化學習的改進非支配排序遺傳算法，并采用改進的 ε -貪心策略的雙Q學習自適應調整NSGA-I的關鍵參數(shù)。但是，對于NSGA-Ⅱ及其改進算法在車間調度問題中的研究仍有不足，在優(yōu)化過程中易早熟收斂且種群多樣性不足，特別是在進化的后期，這會限制對更優(yōu)解空間的探索并影響解的質量和穩(wěn)定性。

基于使用強化學習（reinforcementlearning，RL）解決車間調度問題的研究方面，Zhang等人[10]考慮到了運輸時間、調整時間和交貨時間與機器能耗相結合的問題，將進化算法與RL進行融合求解。Lei等人[1]提出了一種端到端深度強化框架，利用圖神經網絡自動學習FJSP的策略。Chen等人[12]提出了一種自學習遺傳算法，采用遺傳算法作為基本優(yōu)化方法，并基于RL對其關鍵參數(shù)進行智能調整。王艷紅等人[13]在考慮到車間中作業(yè)隨機到達的動態(tài)情況下，為提高調度規(guī)則在不確定動態(tài)條件下的自適應、自尋優(yōu)能力，提出一種調度規(guī)則與Q學習算法集成的作業(yè)車間動態(tài)調度算法。紀志勇等人[4為了保證調度方案的質量，提出了一種以最小化最大完工時間為優(yōu)化目標的多動作深度強化學習算法，設計了用于定義工序選擇策略和機器選擇策略的兩個編碼器，以預測選擇不同工序和機器的概率分布，并且采用圖神經網絡對析取圖進行編碼，以降低問題規(guī)模對解質量的影響。吳秀麗等人[15]考慮了動態(tài)擾動事件對生產的影響，研究了可重入混合流水車間綠色動態(tài)調度問題，提出了改進的Q學習算法，在可重入混合流水車間中，將各個加工階段抽象為智能體，搭建了多智能體RL模型，選用均值漂移算法對歷史狀態(tài)進行聚類。孫愛紅等人[1提出一種基于卷積神經網絡和深度強化學習的集成算法框架來求解作業(yè)車間中自動引導運輸車（automatedguidedvehicle，AGV）與機器聯(lián)合調度問題。車間調度還有一些動態(tài)問題不可忽略，如緊急訂單、機器故障、工件隨機到達等。針對此類問題，Leng等人[17]提出了一種基于雙深度強化學習智能體的訂單接收與調度集成方法來提高收益。Du等人[提出了一個具有起重機運輸和安裝時間的多目標FJSP的深度Q網絡模型，基于加權法對完工時間和總能耗兩個目標同時進行優(yōu)化。Chien等人[19]開發(fā)一種基于智能體的融合深度強化學習和混合遺傳算法的新方法，以解決具有序列依賴的不相關并行機器調度問題。但是，許多基于RL的改進方法引入了大量需要調整的參數(shù)。這些參數(shù)的優(yōu)化和調試過程復雜，往往需要進行大量和反復的實驗，增加了實際應用的難度。此外，多目標優(yōu)化問題本身具有較高的復雜性，現(xiàn)有方法在處理多目標優(yōu)化時，仍需在算法效率和解的質量之間進行權衡，難以同時滿足所有目標的優(yōu)化需求。

綜上所述，NSGA-I及其改進算法和RL的改進方法在車間調度問題上均存在不足之處，將Q-learning與NSGA-I結合使用能更好地解決多目標FJSP。目前對于這方面的研究較少。因此，本文針對EEFJSP，提出QNSGA-Ⅱ算法，并同時優(yōu)化最大完工時間、機器總能耗兩個關鍵目標。針對問題模型，設計三種種群初始化規(guī)則。引人Q-learming算法以使交叉率和變異率兩個參數(shù)能夠自適應當前種群的進化狀態(tài)。最后，將所提QNSGA-Ⅱ算法與其他前沿算法進行對比，以驗證其在解決EEFJSP上的性能。

1問題描述與模型構建

1.1 EEFJSP描述

EEFJSP是指在一個生產車間中，需要同時考慮多個目標或者多個約束條件來進行作業(yè)調度的問題。這些目標涉及到完工時間、成本、交貨時間等方面。一個 n×m 的FJSP可以表示為有 n 個獨立的工件 J={J₁，J₂，…，J_n} 和 ?_m 個獨立可加工的機器 M={M₁，M₂，…，M_m} ，每個工件 J_i 包含若干道工序O_ij，O_ij 是第 i 個工件的第 j 道工序 （j=1，2，3，…，h） 。該問題的調度包含機器選擇和工序排序兩個子問題，機器選擇是每道工序要選擇其對應合適的機器，而工序排序是每個機器上工序的加工順序。圖1是某車間生產流程，包含不同的工件、不同的機器，每個機器可加工的工件不完全相同，可以很直觀地看出FJSP的運作方式。

對于EEFJSP假設如下：a）零時刻，所有機器和工件處于就緒狀態(tài);b）同一時刻同一臺機器只能加工一個工件;c）每個工序只能由它的一個候選機器來處理，在處理完所有先前工序之前，不能開始處理下一個工序；d）一個工序的處理在完成之前不能停止或暫停;e）忽略所有工件的運輸時間;f）同一工件的工序具有優(yōu)先約束，工件之間相互獨立；g）忽略工件和機器之間的裝夾時間；h加工不可中斷且不存在返工。

1.2 模型建立

本文相關變量的符號及定義如表1所示。

以最小化最大完工時間、機器總能耗為優(yōu)化目標，其目標函數(shù)及約束如下所示：

a）最小化最大完工時間。完工時間是生產車間根據(jù)生產計劃和資源情況，在確定的時間范圍內完成生產任務并將產品交付給下一工序的時間點，需要使最后一道工序的完工時間最小，以提高生產效率。其目標函數(shù)如式（1）。

b）最小化機器總能耗。機器在加工過程中會產生能耗，需要機器總能耗最低的調度安排，其目標函數(shù)如式（2）所示。

c）約束條件。

約束式（3）（4）限制了工序只能進行一次加工；約束式（5）表示只有分配了機器的前一個位置，才能分配當前位置的工序；約束式（6）要求機器在同一個加工位置上只能分配一個工序，不允許在同一個位置上分配兩個工序;約束式（7）確保機器 k 的位置 ξ_l 上的開始加工時間不小于前一個位置的開始加工時間。

為了便于理解EEFJSP，表2提供了3工件、4機器的實例，在實例中，工件 J₁?J₂?J₃ 分別有2、3、2道工序，每道工序都有可選加工機器，選擇這幾臺加工機器時，加工時間和機器能耗各不相同。

2 QNSGA-II求解EEFJSP

2.1 QNSGA-I算法框架

本節(jié)介紹QNSGA-Ⅱ的算法框架，本文算法是將強化學習與進化算法進行協(xié)同，可以很好地解決復雜多變生產環(huán)境中的調度問題，以彌補NSGA- I 中的交叉率 （Pc） 和變異率 （Pm） 固定不變的缺陷。具體描述如下，首先，使用三種初始化策略生成初始解。然后，初始化Q-learning的學習過程， Pc 和 Pm 在一定范圍內隨機選擇。接下來，經過交叉變異操作后得到一個新的種群，計算它們的狀態(tài)和獎勵，用Q-learming中Q表更新公式來更新Q表。最后利用帶有禁忌搜索策略的局部搜索算法來獲得非支配解。算法流程如圖2所示。

2.2 編碼與解碼

1）兩段式編碼

本文采用兩段式編碼的方式，分別為機器選擇部分和工序排序部分。

對于機器選擇部分。編碼時，首先，將每個工件對應的所有工序按順序排列，找出每個工序對應的可選機器集，每個數(shù)字都代表對應工序在對應可選機器集的第幾臺機器上加工；對于工序排序部分，數(shù)字代表工件號，數(shù)字在染色體的工序排序部分是第幾次出現(xiàn)即為對應工件的第幾道工序。如圖3所示，染色體左半段為機器選擇部分，右半段為工序排序部分，一共有7道工序的，左虛線框中第一行表示工件1的第1道工序有3臺加工機器，選擇第3臺機器進行加工；第四行表示工件2的第2道工序有3臺加工機器，選擇第2臺機器進行加工，以此類推。右虛線框中第一個1為工件1的第一個工序，第二個

1為工件1的第2個工序，依此類推。

開始通過三種初始化策 初始化狀態(tài)空間、略進行種群初始化 動作空間以及Q表通過解碼生成初 執(zhí)行變異操作 度獲力是 最大迭代次數(shù)？ 香 執(zhí)行交叉操作 使用Q-learning算法更新Q表生成最終調度 局部搜索策略找出較方案 優(yōu)解使用e下降策略 對所有個體的目標值結束 gen=gen+1 選擇下一步要 進行非支配排序并計進行的動作 算擁擠距離

2）插入式解碼

解碼的過程是將編碼過程中形成的初始調度方案轉換成能表示每個機器上每個工序的時間列表，每一條染色體對應一個調度方案。本文采用插人式解碼來對調度方案進行解碼，如圖4所示， O_a1 表示待插入的工序，圖（a）為 TEval^′-TSval^′?PJT^′ 的情況，可以進行插入。圖（b）為 TEval^′-TSval^′′ 的情況，空隙間隔時間小于加工時間，不能插入。

插入式解碼算法偽代碼如算法1所示。

算法1插入式解碼

輸入：種群 S₁ 、各工件各工序使用的機器 J_m 、各工件各工序的加工時間 T 各工件各工序的能耗 c 、工件數(shù)量 PN. 最大工件數(shù) MP 機器數(shù)量 JN 、總工序數(shù) WN 。

輸出：調度方案。

取出機器選擇部分，建立機器使用矩陣 MU 加工時間矩陣 _PJT 、能耗矩陣 PC

取出工序排序部分，生成調度工件和工序號初始化機器空隙時間TSE ：WN遍歷每一個工序if 判斷是否為第一個工序

使用 MU，PJT 找出機器開始時間 _TM ，工件開始時間 TP if TMgt;TP 將機器開始時間作為工序的開始時間記錄空隙時間，其中包含空隙開始時間 TS 、空隙結束時間 TE （2號else非第一個工序，查找對應工序的 TS，TE ，并找出工序移動到機器上的時間與空隙開始時間的最大值 SJ if SJ+t?TE TSEOK=1 插空完成endendend根據(jù)每次記錄的工序開始時間和完成時間確定其位置，并依次迭代，得到完整的調度方案

2.3 種群初始化

種群初始化對算法很重要，直接影響解的多樣性和解的質量，解的多樣性意味著解有更大的搜索空間，解的質量表明初始解更接近最優(yōu)解。因此本文設計了三種初始化規(guī)則以保證適應度值的收斂速度和初始種群的質量。這些初始化策略有：a）完全隨機生成初始解;b）按照最小時間生成初始解;c）按照先加工最大剩余時間生成初始解。在初始種群中，為保證初始解有更大的隨機性，三種初始化策略的占比分別為 50% 、25% （204號 25% 。

2.4基于熵值法的排序與選擇

直接線性加權，容易受到經驗或偏好的影響，權重選擇的合理性和魯棒性難以保障。固定的目標權重也難以適應不同實例的優(yōu)化需求。熵值法通過目標數(shù)據(jù)的離散程度自動分配權重，離散程度較大的目標，賦予更高權重；對于變化較小的目標，權重賦予相對較低，而非依賴人為設定。

排序是將初始解進行快速非支配排序，選擇操作是從當前種群中產生具有更高適應度值的新種群。首先，應用基于排名的適應度分配的函數(shù)將個體的目標值轉換為適應度值。選擇操作使用輪盤賭選擇法，輪盤賭選擇法是一種常見的優(yōu)化算法中的選擇策略，其基本思想是將每個個體的適應度值作為它在輪盤上對應的扇區(qū)大小，然后通過隨機選擇來確定被選中的個體，由于輪盤賭選擇法通常應用于單目標的優(yōu)化方法，故應用熵值法將兩個不同的目標值，即最小化最大完工時間、機器能耗，進行加權處理組合成一個綜合的目標值，以支持后續(xù)的輪盤賭選擇法。具體流程如下：

a）假設對 X 個樣本，Y個指標進行分析，則 x_uv 為第 u 個樣本的第 v 個指標的數(shù)值。

b）指標的歸一化處理：異質指標同質化。

由于各項指標的計量單位并不統(tǒng)一，所以在用它們計算綜合指標前，先要進行標準化處理，即把指標的絕對值轉換為相對值，從而解決各項不同質指標值的同質化問題。正向指標和負向指標數(shù)值代表的含義不同（正向指標數(shù)值越高越好，負向指標數(shù)值越低越好），因此對于正向負向指標需要采用不同的方法進行數(shù)據(jù)標準化處理：

正向指標：

負向指標：

為了方便起見，歸一化后的數(shù)據(jù)仍為 x_uv 。

c）計算第 v 項指標下第 u 個樣本值占該指標的比重：

d）計算第 v 項指標的熵值：

其中： ，滿足 e_v?0 。

e）計算信息熵冗余度（差異）：

d_v=1-e_vv=1，…，Y

f）計算各項指標的權重：

g）計算各項樣本的綜合得分

本文采用精英保留策略，在每次迭代中保留最優(yōu)個體并將不良個體排除在種群之外的過程，可以使個體不斷朝著正確的方向進化，也能加快收斂速度。

2.5 交叉和變異

在傳統(tǒng)的遺傳算法中，交叉和變異是兩個核心的環(huán)節(jié)，交叉用于增加種群的多樣性并且發(fā)現(xiàn)新的解，而變異則用于增加尋優(yōu)過程的隨機性。本文為了更好地增加種群的多樣性，將交叉后種群直接當作變異的初始種群，而非采用傳統(tǒng)方法將種群直接進行合并，具體如下：

對于交叉方式，分為機器選擇部分和工序排序部分，機器選擇部分采用多點交叉的方式，工序排序部分采用工件交換的方式。

對于變異方式，也分為機器選擇和工序排序兩部分，機器選擇部分隨機選取可用機器，工序排序部分隨機交換兩個工序的位置。

2.6基于改進禁忌搜索算法的局部搜索策略

在FJSP中，關鍵路徑是可行調度方案中前后工序間無閑置時間的最長路徑，關鍵路徑上的工序稱為關鍵工序。由此可見，關鍵路徑是對完工時間影響最大的一條調度路徑，在調度中識別和優(yōu)化關鍵路徑是至關重要的。因此，本文設計了一種基于關鍵路徑移動操作的鄰域結構來有效減少最小化的最大完工時間，同時結合禁忌搜索來避免陷入局部最優(yōu)。

關鍵路徑在調度計劃中總持續(xù)時間最長，對整個調度計劃完成時間的影響最大，并且可能存在多條關鍵路徑。第一步要找到關鍵工序，具體流程如算法2所示。第二步是在保證前后工序約束的前提下將關鍵工序轉移到其他機器上，具體流程如算法3所示。第三步建立禁忌表，利用算法3對單個目標的個體進行局部搜索，并將相關信息記錄到禁忌表中，具體流程如算法4所示。

算法2尋找關鍵工序

輸入：調度方案。

輸出：關鍵工序。

查找最后一道工序開始時間的機器號、工序號以及工序在機器上

的位置

找出最后一道工序的開始時間 KS₁

找出與最后一道工序緊挨的前一道工序的結束時間 JS₁

for ：WNumber遍歷所有工序if b==1 判斷是否為首工序找出首工序的個數(shù)else找出本工件前一道工序的開始時間、結束時間if同機器前一道工序的結束時間 Σ=Σ 后一道工序的開始時間找出前一道工序的開始時間、結束時間、機器號、工序號以及工序在機器上的位置else找出本工件前一道工序的開始時間、結束時間

endend循環(huán)到出現(xiàn)開始時間為0的工序出現(xiàn)，記錄所有關鍵工序基于禁忌搜索的關鍵路徑移動操作算法偽代碼如算法3示。算法3基于禁忌搜索的關鍵路徑移動操作搜索算子輸入：種群 S₁ 、最大鄰域搜索范圍 NSA 。輸出：新種群 S₂ 、最優(yōu)目標值 O₁ ○基于算法1找到關鍵工序 n for ：NSA規(guī)定鄰域搜索的范圍ifmakespan lt; best_makespan記錄最優(yōu)解記錄較優(yōu)的目標值endfor yy=1：n 逐個選取關鍵工序進行移動識別要進行移動的工件號和工序號從關鍵工序的所有機器中找出所有可放位置的機器數(shù) g for zz=1 ：g遍歷當前機器的每個工序，確定可插入的位置，并確定完工時間 LP if LPlt; makespan判斷是否移動后完工時間有所減少調整本機器的后續(xù)工序并更新當前最大完工時間best_makespanendendendend算法4局部搜索輸入：種群 S₁ ，目標 ， ，跳出鄰域值不變代數(shù)BBD，單個目標局部搜索的個數(shù) n_?（ 。輸出：新種群 P₄ 、新目標值 o₇ 。對各個 O₁ 從小到大排序，并選取前 k 個較優(yōu)個體 P₁ 對 P₁ 解碼找到關鍵路徑建立禁忌表 J₁?J₂ （204for i=1 ：n對 O₁ 進行禁忌搜索，基于算法2在考慮到相關前后約束后關鍵工序移動到其他機器上，然后將工序移動完成記錄在禁忌表中，提高搜索效率，并輸出新個體 P₂ 和新目標值 O₃O₄ （204號對 O₂ 進行禁忌搜索，步驟同上，并輸出新個體 P₃ 和新目標值O₅、O₆ （204號合并個體 P₂，P₃ 和兩個目標值 O₃O₄ 與 （號endreturn P₄L，O₇ （20

3基于 a -learning的自適應策略

3.1 Q-learning簡介

近年來，RL的研究收到越來越多的關注[20]。給定一個環(huán)境的狀態(tài)（s）智能體根據(jù)某種策略 （c） 選出一個對應的動作（a） ，而執(zhí)行動作 （a） 后環(huán)境又會發(fā)生改變，即狀態(tài)（s）會轉換為新的狀態(tài) （s^′） 且每執(zhí)行完一個動作 （a） 后智能體會得到一個激勵值（正or負），而智能體就依據(jù)得到的激勵值大小調整其策略，使得在所有步驟執(zhí)行完后，所獲得的獎勵 （r） 之和最大。

Q-learning算法是RL的一種，是一種關于策略的選擇方式，它使用動作價值函數(shù) Q（s，a） 來估計在給定狀態(tài) s 下采取動作 a 的期望回報，核心和訓練目標是選擇一個合適的策略，使得在每個循環(huán)結束時得到的獎勵之和最大。Q-learning是在有限的狀態(tài)和動作組合的情況下，在迭代中不斷更新Q表，使其最終能夠收斂，即智能體能夠根據(jù)當前的狀態(tài)通過查表的方式來判斷它要選取的動作。Q表更新公式如式（15）所示。

其中： ? 表示學習率，即新的值對更新后的值所造成的影響大小；γ表示折扣因子，即對未來獎勵的衰減值。

3.2 設計思路

傳統(tǒng)NSGA-II中交叉率 （Pc） 和變異率 （Pm） 為固定參數(shù)，難以適應種群在不同進化階段的動態(tài)變化?；赒-learning的自適應策略，通過動態(tài)調整交叉率和變異率，解決了傳統(tǒng)方法無法兼顧多樣性與收斂性的不足。詳細設計思路如下：

狀態(tài)空間：選擇種群的適應度值作為狀態(tài)依據(jù)，并通過加權平均適應度、種群多樣性、最佳個體適應度三個指標綜合描述當前種群狀態(tài)。

動作空間：動作空間由 Pc 和 Pm 的可能取值（ Pc∈[0.4 0.9]， Pm∈[0.01 ，0.21]）組成，并加上隨機擾動，以提高兩者取值的多樣性。

獎懲機制：基于交叉變異后的適應度值變化，綜合考慮種群平均適應度和多樣性的提升與否來給予正負獎勵。

動作選擇策略：通過改進的 ε -貪心策略，使算法早期傾向于探索更多未知動作，后期逐漸穩(wěn)定，確保算法在不同階段適配解空間變化。

Q表更新：通過迭代更新，智能體學會在不同狀態(tài)下選擇最優(yōu)動作。

3.3 狀態(tài)空間

以最小化最大完工時間、機器總能耗為目標的EEFJSP在構建狀態(tài)空間前，需要以目標函數(shù)值計算適應度值，以適應度值的大小來當作狀態(tài)空間?？紤]到2.4節(jié)的輪盤賭選擇法通常應用于單目標的優(yōu)化方法，故本節(jié)的狀態(tài)空間將三維的狀態(tài)量通過加權的方式轉換成一維，再進行離散化映射處理。具體如下所示：

a）平均適應度，如式（16）所示；

b）種群多樣性，如式（17）所示；

c）最佳個體適應度，如式（18）所示；

式（19）為式（16）＼～（18）的加權。

B（h）=minO_f^h

其中： O_i^t 表示第 Φ_t 代的第 i 個體的目標值； minO_f^h 表示第 h 代的第 f 個個體的最優(yōu)目標值； A（h） 為第 h 代的平均適應度；A（1） 為第1代的平均適應度； ;D（h），D（1），B（h），B（1） 含義與A（h） 、A（1） 相似； 為權重值， w₁+w₂+w₃=1 。在本文中，經過多次實驗，種群的平均適應度值和多樣性能反映整個種群的狀態(tài)，更容易獲得優(yōu)秀的個體，故設 w₁，w₂，w₃ 的權重分別為0.35、0.350.3。

根據(jù)總體適應度，本文將狀態(tài)空間劃分為21個狀態(tài)，其中s=（s₁，s₂，…，s₂₁） ，當加權后的適應度值在[0，1]時，以0.05為區(qū)間值，每隔0.05為一個狀態(tài)，當適應度值大于1時為第21個狀態(tài)。具體如式（20）所示。

3.4 動作空間

對于每一代，智能體會采取不同的動作來獲得合適的交叉率 （Pc） 和變異率 （Pm），Pc 和 Pm 分別選取10個動作作為動作空間。對于 Pc ，其常用值為 0.4～0.9 ，每個動作間隔0.05；對于 Pm ，常用值為 0.01～0.21 ，每個動作間隔0.02。為了使動作的選擇更加靈活，在每個動作的基礎上增加了一個0～1的隨機數(shù)，具體如表3所示。

3.5 獎懲機制

在QNSGA-Ⅱ中，種群的平均適應度值和多樣性對獲得優(yōu)秀個體的影響更大，故比較了交叉變異前后的平均適應度和種群多樣性。如果種群平均適應度和種群多樣性的加權增加，則給予正獎勵，反之給予負獎勵，因為平均適應度值和多樣性對優(yōu)秀個體的影響程度相差不大， q₁…q₂ 均為0.5，具體如式（21）（22）所示。

略后，就可以進行基于Q-learning的交叉率、變異率的自適應。首先，智能體在狀態(tài) s （當前適應度值的大?。┫赂鶕?jù)動作選擇策略選取動作 a_c （交叉率）和 a_m （變異率），并獲得獎勵 r 和下一個狀態(tài) s^′ （下一代適應度值的大小）。其中，智能體選取哪一個動作是由Q表決定的。Q表的行表示狀態(tài)，列表示動作。在算法的迭代過程中，Q表根據(jù)學習經驗和對未來獎勵的預測進行更新，Q更新公式為式（15），Q表的更新過程如圖5所示。

其中： R 為種群平均適應度和種群多樣性加權后的值，當 Rgt;1 時，智能體給予一個正獎勵1，反之，給予一個負獎勵-1。

3.6 動作選擇策略

Q-learning的動作選擇策略被稱為搜索策略，是智能體在給定狀態(tài)下決定采取何種動作的規(guī)則，這些策略對于智能體學習最優(yōu)行為至關重要，因為它們直接影響到智能體與環(huán)境的交互效果和學習效率。

本文采用改進的 ε -貪心策略（ ε -greedystrategy），智能體在每次做決定前，先生成一個隨機數(shù)，如果這個rand值比 ε 小，那么就隨機選取一個動作，否則選取當前已知條件下能使得 Q 值最大的動作，具體如式（23）所示。為了使 ε 貪心策略在迭代后期更好地趨于收斂，本文設計了一種 ε 迭代下降策略， ε 值會隨著迭代的增加逐步衰減，衰減到設置的最小值后停止衰減，這使得算法在早期傾向于探索新的解，在后期傾向于保留和利用學習成果，具體如式（24）所示。

其中： rand 為[0，1]的隨機數(shù)； ε₁ 為 ε 的初始值； z 為當前迭代數(shù)； maxz 為最大迭代次數(shù)。

算法5動作選擇策略

輸入：交叉率Q表、變異率Q表。

輸出：交叉率動作 a_c 、變異率動作 a_m ○

創(chuàng)建 σ_ε 迭代下降公式 對于確定交叉率動作。

if randlt;ε

隨機選擇一個動作

else

選擇目前Q表中最大 Q 值的動作

end

對于確定變異率動作同確定交叉率動作選擇的方式retunacam

3.7 Q 表更新

在確定了狀態(tài)空間、動作空間、獎勵函數(shù)以及動作選擇策

4仿真實驗分析

4.1 實例測試

本文算法是在 CoreTM i5-1035G7 CPU 1.50GHz 和8.00GBRAM上實現(xiàn)的，使用MATLAB2023a對所提QNSGA-Ⅱ算法進行實例仿真實驗。首先，對算法進行多因子田口正交實驗確定因子的最優(yōu)參數(shù)組合，其中使用10個FJSP基準測試實例 MK01～MK10 進行求解。然后，將QNSGA-I與NSGA-I、IGA進行實驗對比，進一步驗證算法的有效性。

本文所使用的MRO1＼～MRO10算例是在10個FJSP基準測試實例 MK01～MK10 的基礎上對應隨機生成的，MK01＼～MK10與MRO1 ～ MRO10一一對應，后續(xù)為方便表示只顯示MK系列算例，相關測試數(shù)據(jù)可從鏈接https：//pan.baidu.com/s/1 dgyAUhnKByy0HRdw82iWTQ中下載，提取碼為yzxx。

4.2性能指標

本文針對QNSGA-Ⅱ求解EEFJSP，從三個方面來評價帕累托前沿（paretofront，PF）的質量，分別為反世代距離（invertedgenerational distance，IGD）解集覆蓋率（setcoverage，SC）、超體積指標（hypervolume，HV）。

IGD對于真實的最優(yōu)帕累托前沿（ PF^* ）中的每個解 y ，找到與其最近的PF中的解 x ，計算其歐氏距離，取平均值而無須開方，如果 PF^* 的數(shù)量大于PF數(shù)量，那么IGD就能最完整地表達PF的性能，IGD值越小，代表算法多樣性和收斂性越好，具體如式（25）所示。

SC用于評價兩個帕累托解集的支配關系，假設 A 和 B 是兩個PF，那么SC值可以表達如下， ∣B I代表 B 中的解數(shù)量，SC（A，B） 表示 B 中的解被 A 的某個解支配的百分比， SC（A，B） 值越大， ，A 的性能越好。具體如式（26）所示。

HV用于評價目標空間被一個近似集覆蓋的程度，是最為普遍的一種評價指標。其中需要用到一個參考點，HV值為PF與參考點（referencepoint）之間組成的超立方體的體積。HV的比較不需要先驗知識，不需要找到真實的 PF 。如果某個近似集 A 完全支配另一個近似集 B ，那么 A 的超容量HV會大于

B ，因此HV完全可以用于Pareto前沿比較，具體如式（27）所示。

4.3參數(shù)設置

因為學習率 α 、折扣因子 γ 、初始貪婪因子 ε 這三個參數(shù)直接決定了Q-learning部分的性能，故對三個參數(shù)設置三因子四水平的田口正交實驗設計（designof experiments，DOE），以IGD為評價指標選取最優(yōu)的參數(shù)組合。對于每個參數(shù)設置為 α∈ ，0.8，0.9，形成 L16^（4） DOE正交陣列如表4所示，將16組實驗，每組實驗進行5次并計算平均值，IGD值越小，表示該組測試參數(shù)匹配越好。利用表4的數(shù)據(jù)得到圖6所示的結果，由圖可知，最優(yōu)參數(shù)組合為 α=0.8，γ=0.6，ε₁=0.7

4.4策略有效性分析

為了驗證QNSGA-II中Q-learning和局部搜索兩個策略的有效性，構建了兩個QNSGA-II的變體，即QNSGA-I（A）和QNSGA-II（B）。QNSGA-II（A）代表沒有采用局部搜索策略，QNSGA-II（B）代表沒有采用Q-learning算法進行參數(shù)的自適應，使用上述三個指標對三種算法的性能進行評價，為了避免算法的隨機性，每個算法實例運行10次取其平均值。表5是在MKO1算例條件下使用IGD評價指標對QNSGA-II、QNSGA-Ⅱ（A）和QNSGA-II（B）三種算法進行評價的10次運行結果及其平均值，可以更清楚地了解如何獲得每個實例的最終數(shù)據(jù)。表6是在10個算例條件下使用IGD和HV對QNSGA-II、QNSGA-II（A）和QNSGA-I（B）三種算法進行評價的結果比較；表7是在10個算例條件下使用SC對QNSGA-II、QNSGA-Ⅱ（A）和QNSGA-I（B）三種算法進行評價的結果比較。表6、7最優(yōu)值以粗體表示。

對比QNSGA-II與QNSGA-I（A）可以看出，QNSGA-Ⅱ在大多數(shù)情況下的IGD小于QNSGA-II（A），并且在大多數(shù)情況下的HV和SC均大于QNSGA-II（A），各個部分的改進效果得到了驗證，證明了使用Q-learning去調整 Pc，Pm 值的有效性，加速算法的收斂速度。

對比QNSGA-II與QNSGA-I（B）可以看出，QNSGA-Ⅱ在所有情況下的IGD均小于QNSGA-ⅡI（B），并且在所有情況下的HV和SC均大于QNSGA-I（B），這驗證了基于關鍵路徑移動操作的局部搜索策略的有效性，有利于在搜索的過程中找到較優(yōu)的個體。

4.5對比實驗

為了進一步評估QNSGA-Ⅱ的有效性，將其與現(xiàn)有文獻中所研究的其他兩種前沿算法進行比較，分別為 IGA^[21] 、NSGA-II[22]和DQNSGA[9]。采用上述三個評價指標對三種算法的性能進行評估。表8是在10個算例條件下使用IGD和HV對QNSGA-II、IGA、NSGA-II和DQNSGA四種算法進行評價的結果比較，最優(yōu)值以粗體表示，為了使展示的效果更好，利用表8中的數(shù)據(jù)繪制了圖7的箱線圖。表9是在10個算例條件下使用SC對QNSGA-I、IGA和NSGA-I三種算法進行評價的結果比較，最優(yōu)值以粗體表示。從圖8的箱線圖更能清晰地看出 SC（Q，I） 和 SC（Q，N） 對應值的分布情況。

表8IGD和HV值對比

圖9為QNSGA-II、IGA、NSGA-II、DQNSGA四種算法的非支配前沿，為保證隨機性，選取了MK02算例進行展示。從圖中明顯可以看出，QNSGA-ⅡI中的非支配前沿比另外兩種算法分布更均勻，解的質量更好。

從表8可以看出，在IGD和HV評價指標下，QNSGA-ⅡI的IGD比IGA、NSGA-I和DQNSGA的值在每個算例條件下都要好，這表明QNSGA-I在算法的收斂性和多樣性上都要優(yōu)于其余三種算法。從圖中可以看出，QNSGA-ⅡI在整體上明顯比IGA 要優(yōu)，比 NSGA-ⅡI和DQNSGA略優(yōu)。

表9展示了在SC評價指標下，QNSGA-II、IGA、NSGA-II和DQNSGA的對比情況，可以看出QNSGA-I在每個算例條件下的帕累托解集都完全支配IGA中的帕累托解集，在絕大多數(shù)的算例條件下的帕累托解集完全支配NSGA-II和DQNSGA中的帕累托解集。從圖9的箱線圖中可以看出， SC（Q，I） 和SC（Q，N） 的對應值明顯優(yōu)于 SC（I，Q） 和 SC（N，Q） 。

為了更加直觀地比較每種算法的有效性，使得出的結果更具說服力。本文選取算例MK02作為代表。圖10顯示了兩個目標下四種算法的收斂曲線。從圖中可以明顯看出，QNSGA-Ⅱ在兩個目標上的精度都優(yōu)于其他兩種算法。圖11為MK02使用QNSGA-Ⅱ算法得到的甘特圖。

綜上所述，本文QNSGA-I在求解EEFJSP上優(yōu)于IGA、NSGA-II 和QDNSGA。

5結束語

本文研究了基于強化學習協(xié)同進化算法求解EEFJSP，提出了以最小化最大完工時間、機器總能耗為優(yōu)化目標的QNSGA-Ⅱ算法，結論如下：

a）對于問題模型，設計了三種種群初始化規(guī)則，保證適應度值的收斂速度和初始種群的質量。

b）為了使交叉率和變異率參數(shù)能夠自適應當前種群的進化狀態(tài)，在算法中加入了Q-learning進行參數(shù)自適應學習。在Q-learning框架中，首先選取了適應度值作為當前的狀態(tài)空間，將交叉率和變異率的選取作為動作空間，種群的平均適應度值和多樣性設計了一種獎懲機制。在動作選擇策略中，擴展了經典的 ε -greedy策略，引入了一種精英保存策略，使自適應參數(shù)能夠在迭代前期更好地選擇更多的未知動作，在迭代后期能夠更好地趨于收斂，并保存每一代中較優(yōu)的個體。

c）進行策略有效性驗證和對比實驗，策略有效性驗證保證了提出的兩個關鍵策略（Q-learning和局部搜索）的有效性，對比實驗將所提QNSGA-ⅡI與其他前沿算法對比，保證了算法整體的有效性。

此外，在柔性作業(yè)車間調度的過程中，還存在一些動態(tài)事件，如機器故障、緊急插單等，本文模型沒有與動態(tài)事件相結合，此模型對于動態(tài)環(huán)境下的調度情況還暫未可知，后續(xù)的工作將加入動態(tài)因素進一步研究，并與深度神經網絡相結合，提出相應的改進策略。

參考文獻：

[1］李瑞，徐華，楊金峰，等.改進近鄰人工蜂群算法求解柔性作業(yè) 車間調度問題[J].計算機應用研究，2024，41（2）：438-443. （LiRui，Xu Hua，YangJinfeng，etal. Improved algorithm of nearneighborartificial bee colony forflexible job-shop scheduling[J]. Application Research ofComputers，2024，41（2）：438-443.）

[2]李敬花，閆恒山，楊博歆，等，改進遺傳—和聲搜索算法求解海 工裝備制造車間調度問題［J]．計算機集成制造系統(tǒng)，2022，28 （12）：3923-3936.（Li Jinghua，Yan Hengshan，Yang Boxin，et al. Improved genetic-harmony search algorithm for solving workshop scheduling problem of marine equipment[J].Computer Integrated Manufacturing Systems，2022，28（12）：3923-3936.）

[3]張國輝，閆少峰，陸熙熙，等．改進混合多目標蟻群算法求解帶 運輸時間和調整時間的柔性作業(yè)車間調度問題［J]．計算機應 用研究，2023，40（12）：3690-3695.（ZhangGuohui，Yan Shaofeng，Lu Xixi，etal. Improved hybrid multi-objective ant colony optimization for flexible job-shop scheduling problem with transportation time and setup time [J].Application Research of Computers， 2023，40（12）：3690-3695.）

[4］顧文斌，李育鑫，錢煜暉，等．基于激素調節(jié)機制IPSO算法的相 同并行機混合流水車間調度問題［J]．計算機集成制造系統(tǒng)， 2021，27（10）：2858-2871.（Gu Wenbin，Li Yuxin，Qian Yuhui， et al.Improved particle swarm optimization algorithm with hormone modulation mechanism for solving hybrid flow-shop scheduling problemwith identical parallel machine [J].Computer Integrated Manufacturing Systems，2021，27（10）：2858-2871.）

[5]黎陽，李新宇，牟健慧．基于改進模擬退火算法的大規(guī)模置換流 水車間調度[J].計算機集成制造系統(tǒng)，2020，26（2）：366-375. （LiYang，LiXinyu，Mou Jianhui.Large-scalepermutation flowshop scheduling method based on improved simulated annealing algorithm [J].Computer Integrated Manufacturing Systems，2020，26 （2）：366-375.）

[6]DebK，PratapA，Agarwal S，et al.A fast andelitist multiobjective genetic algorithm：NSGA-II[J]. IEEE Trans on Evolutionary Computation，2002，6（2）：182-197.

[7］姜一嘯，吉衛(wèi)喜，何鑫，等．基于改進非支配排序遺傳算法的多 目標柔性作業(yè)車間低碳調度［J]．中國機械工程，2022，33 （21）：2564-2577.（JiangYixiao，JiWeixi，He Xin，etal.Lowcarbonscheduling of multi-objective flexible job-shop based on improved NSGA-II[J].China Mechanical Engineering，2022，33 （21） ： 2564-2577.）

[8]張國輝，張得雨，閆少峰，等.考慮工人協(xié)作與學習效應的柔性作 業(yè)車間調度[J].計算機集成制造系統(tǒng)，2024，30（12）：4369- 4385.（Zhang Guohui，Zhang Deyu，Yan Shaofeng，et al.Flexible job shop scheduling considering worker collaboration and learning effects[J].ComputerIntegrated Manufacturing Systems，2024，30（12）：4369-4385.

[9]Tang Hongtao， Xiao Yu， Zhang Wei， et al. A DQL-NSGA-l algorithmfor solvingthe flexible job shop dynamic schedulingproblem [J].Expert Systems with Applications，2024，237：121723.

[10]Zhang Guohui，Yan Shaofeng，Song Xiaohui，et al.Evolutionaryalgorithm incorporating reinforcement learning for energy-conscious flexible job-shop scheduling problem with transportation and setup times [J].EngineeringApplicationsof Artificial Intelligence，2024，133：107974.

[11] Lei Kun，Guo Peng，Zhao Wenchao，et al. A multi-action deep reinforcement learning framework for flexible job-shop scheduling problem [J].Expert Systemswith Applications，2022，205：117796.

[12] Chen Ronghua，Yang Bo，Li Shi，et al.A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem[J].Computers amp; Industrial Engineering，2020，149：106778.

[13］王艷紅，尹濤，譚園園，等，基于規(guī)則與Q學習的作業(yè)車間動態(tài) 調度算法[J]．計算機集成制造系統(tǒng)，2024，30（10）：3535-3546.（Wang Yanhong，Yin Tao，Tan Yuanyuan，et al. Dispatching ruleand Q-learming based dynamic job shop scheduling algorithm [J].Computer Integrated Manufacturing Systems，2024，30 （10）： 3535-3546.）

[14]紀志勇，袁逸萍，巴智勇，等．基于多動作深度強化學習的紡機 制造車間調度方法[J].計算機應用研究，2023，40（11）：3247-3253.（Ji Zhiyong，Yuan Yiping，Ba Zhiyong，et al.Multi-action deep reinforcement learning based scheduling method for spinning machine manufacturing shop floor[J].Application Research of Computers，2023，40（11）：3247-3253.）

[15]吳秀麗，閆曉燕．基于改進Q學習的可重入混合流水車間綠色 動態(tài)調度[J].機械工程學報，2023，59（13）：246-259.（Wu Xiuli，Yan Xiaoyan.Animproved Qlearming algorithm tooptimize green dynamic scheduling problem in a reentrant hybrid flow shop [J].Jourmal of Mechanical Engineering，2023，59（13）：246-259.）

[16］孫愛紅，雷琦，宋豫川，等．基于深度強化學習求解作業(yè)車間機 器與AGV聯(lián)合調度問題[J]．控制與決策，2024，39（1）：253-262.（Sun Aihong，Lei Qi，Song Yuchuan，et al.Deep reinforcement learning for solving the joint scheduling problem of machines and AGVs in job shop[J]. Control and Decision，2024，39（1） ： 253-262.）

[17]Leng Jiewu，Guo Jiwei，Zhang Hu，et al.Dual deep reinforcement learning agents-based integrated order acceptance and scheduling of mass individualized prototyping[J].Journal of Cleaner Production，2023，427：139249.

[18]Du Yu，Li Junqing，Li Chengdong，et al.A reinforcement learning approach for flexible job shop scheduling problem with crane transportation and setup times [J].IEEE Trans on Neural Networks and Learning Systems，2024，35（4）：5695-5709.

[19]Chien Chenfu，Lan Yubin.Agent-basedaproachintegratingdeepreinforcement learning and hybrid genetic algorithm for dynamic sheduling for industry 3.5 smart production[J]. Computers amp; Industrial Engineering，2021，162：107782.

[20]趙銳，梁承姬．強化學習下淺充淺放充電策略AGV調度研究 [J]．計算機應用研究，2024，41（10）：3038-3043．（ZhaoRui， Liang Chengji. Research on AGV scheduling of shallow charging and shallow discharging charging strategy under reinforcement learning [J].Application Research of Computers，2024，41（10）：3038-3043.）

[21]Zhang Guohui，Hu Yifan，Sun Jinghe，et al.An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints[J].Swarm and Evolutionary Computation，2020，54：100664.

[22]Yuan Minghai，Li Yadong，Zhang Lizhi，etal.Research on intelligent workshop resource scheduling method based on improved NSGAIIalgorithm[J].Robotics and Computer-Integrated Manufacturing，2021，71： 102141.