基于強(qiáng)化學(xué)習(xí)協(xié)同進(jìn)化算法求解柔性作業(yè)車(chē)間節(jié)能調(diào)度問(wèn)題

關(guān)鍵詞：柔性作業(yè)車(chē)間調(diào)度；Q-learning；改進(jìn)NSGA-II；多目標(biāo)優(yōu)化 中圖分類(lèi)號(hào)：TH165 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

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

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

1問(wèn)題描述與模型構(gòu)建

1.1 EEFJSP描述

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

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

1.2 模型建立

本文相關(guān)變量的符號(hào)及定義如表1所示。

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

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

b）最小化機(jī)器總能耗。機(jī)器在加工過(guò)程中會(huì)產(chǎn)生能耗，需要機(jī)器總能耗最低的調(diào)度安排，其目標(biāo)函數(shù)如式（2）所示。

c）約束條件。

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

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

2 QNSGA-II求解EEFJSP

2.1 QNSGA-I算法框架

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

2.2 編碼與解碼

1）兩段式編碼

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

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

1為工件1的第2個(gè)工序，依此類(lèi)推。

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

2）插入式解碼

解碼的過(guò)程是將編碼過(guò)程中形成的初始調(diào)度方案轉(zhuǎn)換成能表示每個(gè)機(jī)器上每個(gè)工序的時(shí)間列表，每一條染色體對(duì)應(yīng)一個(gè)調(diào)度方案。本文采用插人式解碼來(lái)對(duì)調(diào)度方案進(jìn)行解碼，如圖4所示， O_a1 表示待插入的工序，圖（a）為 TEval^′-TSval^′?PJT^′ 的情況，可以進(jìn)行插入。圖（b）為 TEval^′-TSval^′′ 的情況，空隙間隔時(shí)間小于加工時(shí)間，不能插入。

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

算法1插入式解碼

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

輸出：調(diào)度方案。

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

取出工序排序部分，生成調(diào)度工件和工序號(hào)初始化機(jī)器空隙時(shí)間TSE ：WN遍歷每一個(gè)工序if 判斷是否為第一個(gè)工序

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

2.3 種群初始化

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

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

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

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

a）假設(shè)對(duì) X 個(gè)樣本，Y個(gè)指標(biāo)進(jìn)行分析，則 x_uv 為第 u 個(gè)樣本的第 v 個(gè)指標(biāo)的數(shù)值。

b）指標(biāo)的歸一化處理：異質(zhì)指標(biāo)同質(zhì)化。

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

正向指標(biāo)：

負(fù)向指標(biāo)：

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

c）計(jì)算第 v 項(xiàng)指標(biāo)下第 u 個(gè)樣本值占該指標(biāo)的比重：

d）計(jì)算第 v 項(xiàng)指標(biāo)的熵值：

其中： ，滿足 e_v?0 。

e）計(jì)算信息熵冗余度（差異）：

d_v=1-e_vv=1，…，Y

f）計(jì)算各項(xiàng)指標(biāo)的權(quán)重：

g）計(jì)算各項(xiàng)樣本的綜合得分

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

2.5 交叉和變異

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

對(duì)于交叉方式，分為機(jī)器選擇部分和工序排序部分，機(jī)器選擇部分采用多點(diǎn)交叉的方式，工序排序部分采用工件交換的方式。

對(duì)于變異方式，也分為機(jī)器選擇和工序排序兩部分，機(jī)器選擇部分隨機(jī)選取可用機(jī)器，工序排序部分隨機(jī)交換兩個(gè)工序的位置。

2.6基于改進(jìn)禁忌搜索算法的局部搜索策略

在FJSP中，關(guān)鍵路徑是可行調(diào)度方案中前后工序間無(wú)閑置時(shí)間的最長(zhǎng)路徑，關(guān)鍵路徑上的工序稱(chēng)為關(guān)鍵工序。由此可見(jiàn)，關(guān)鍵路徑是對(duì)完工時(shí)間影響最大的一條調(diào)度路徑，在調(diào)度中識(shí)別和優(yōu)化關(guān)鍵路徑是至關(guān)重要的。因此，本文設(shè)計(jì)了一種基于關(guān)鍵路徑移動(dòng)操作的鄰域結(jié)構(gòu)來(lái)有效減少最小化的最大完工時(shí)間，同時(shí)結(jié)合禁忌搜索來(lái)避免陷入局部最優(yōu)。

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

算法2尋找關(guān)鍵工序

輸入：調(diào)度方案。

輸出：關(guān)鍵工序。

查找最后一道工序開(kāi)始時(shí)間的機(jī)器號(hào)、工序號(hào)以及工序在機(jī)器上

的位置

找出最后一道工序的開(kāi)始時(shí)間 KS₁

找出與最后一道工序緊挨的前一道工序的結(jié)束時(shí)間 JS₁

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

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

3基于 a -learning的自適應(yīng)策略

3.1 Q-learning簡(jiǎn)介

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

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

其中： ? 表示學(xué)習(xí)率，即新的值對(duì)更新后的值所造成的影響大小；γ表示折扣因子，即對(duì)未來(lái)獎(jiǎng)勵(lì)的衰減值。

3.2 設(shè)計(jì)思路

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

狀態(tài)空間：選擇種群的適應(yīng)度值作為狀態(tài)依據(jù)，并通過(guò)加權(quán)平均適應(yīng)度、種群多樣性、最佳個(gè)體適應(yīng)度三個(gè)指標(biāo)綜合描述當(dāng)前種群狀態(tài)。

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

獎(jiǎng)懲機(jī)制：基于交叉變異后的適應(yīng)度值變化，綜合考慮種群平均適應(yīng)度和多樣性的提升與否來(lái)給予正負(fù)獎(jiǎng)勵(lì)。

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

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

3.3 狀態(tài)空間

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

a）平均適應(yīng)度，如式（16）所示；

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

c）最佳個(gè)體適應(yīng)度，如式（18）所示；

式（19）為式（16）＼～（18）的加權(quán)。

B（h）=minO_f^h

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

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

3.4 動(dòng)作空間

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

3.5 獎(jiǎng)懲機(jī)制

在QNSGA-Ⅱ中，種群的平均適應(yīng)度值和多樣性對(duì)獲得優(yōu)秀個(gè)體的影響更大，故比較了交叉變異前后的平均適應(yīng)度和種群多樣性。如果種群平均適應(yīng)度和種群多樣性的加權(quán)增加，則給予正獎(jiǎng)勵(lì)，反之給予負(fù)獎(jiǎng)勵(lì)，因?yàn)槠骄m應(yīng)度值和多樣性對(duì)優(yōu)秀個(gè)體的影響程度相差不大， q₁…q₂ 均為0.5，具體如式（21）（22）所示。

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

其中： R 為種群平均適應(yīng)度和種群多樣性加權(quán)后的值，當(dāng) Rgt;1 時(shí)，智能體給予一個(gè)正獎(jiǎng)勵(lì)1，反之，給予一個(gè)負(fù)獎(jiǎng)勵(lì)-1。

3.6 動(dòng)作選擇策略

Q-learning的動(dòng)作選擇策略被稱(chēng)為搜索策略，是智能體在給定狀態(tài)下決定采取何種動(dòng)作的規(guī)則，這些策略對(duì)于智能體學(xué)習(xí)最優(yōu)行為至關(guān)重要，因?yàn)樗鼈冎苯佑绊懙街悄荏w與環(huán)境的交互效果和學(xué)習(xí)效率。

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

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

算法5動(dòng)作選擇策略

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

輸出：交叉率動(dòng)作 a_c 、變異率動(dòng)作 a_m ○

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

if randlt;ε

隨機(jī)選擇一個(gè)動(dòng)作

else

選擇目前Q表中最大 Q 值的動(dòng)作

end

對(duì)于確定變異率動(dòng)作同確定交叉率動(dòng)作選擇的方式retunacam

3.7 Q 表更新

在確定了狀態(tài)空間、動(dòng)作空間、獎(jiǎng)勵(lì)函數(shù)以及動(dòng)作選擇策

4仿真實(shí)驗(yàn)分析

4.1 實(shí)例測(cè)試

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

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

4.2性能指標(biāo)

本文針對(duì)QNSGA-Ⅱ求解EEFJSP，從三個(gè)方面來(lái)評(píng)價(jià)帕累托前沿（paretofront，PF）的質(zhì)量，分別為反世代距離（invertedgenerational distance，IGD）解集覆蓋率（setcoverage，SC）、超體積指標(biāo)（hypervolume，HV）。

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

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

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

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

4.3參數(shù)設(shè)置

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

4.4策略有效性分析

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

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

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

4.5對(duì)比實(shí)驗(yàn)

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

表8IGD和HV值對(duì)比

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

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

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

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

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

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

本文研究了基于強(qiáng)化學(xué)習(xí)協(xié)同進(jìn)化算法求解EEFJSP，提出了以最小化最大完工時(shí)間、機(jī)器總能耗為優(yōu)化目標(biāo)的QNSGA-Ⅱ算法，結(jié)論如下：

a）對(duì)于問(wèn)題模型，設(shè)計(jì)了三種種群初始化規(guī)則，保證適應(yīng)度值的收斂速度和初始種群的質(zhì)量。

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

c）進(jìn)行策略有效性驗(yàn)證和對(duì)比實(shí)驗(yàn)，策略有效性驗(yàn)證保證了提出的兩個(gè)關(guān)鍵策略（Q-learning和局部搜索）的有效性，對(duì)比實(shí)驗(yàn)將所提QNSGA-ⅡI與其他前沿算法對(duì)比，保證了算法整體的有效性。

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

參考文獻(xiàn)：

[1］李瑞，徐華，楊金峰，等.改進(jìn)近鄰人工蜂群算法求解柔性作業(yè) 車(chē)間調(diào)度問(wèn)題[J].計(jì)算機(jī)應(yīng)用研究，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ìn)遺傳—和聲搜索算法求解海 工裝備制造車(chē)間調(diào)度問(wèn)題［J]．計(jì)算機(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]張國(guó)輝，閆少峰，陸熙熙，等．改進(jìn)混合多目標(biāo)蟻群算法求解帶 運(yùn)輸時(shí)間和調(diào)整時(shí)間的柔性作業(yè)車(chē)間調(diào)度問(wèn)題［J]．計(jì)算機(jī)應(yīng) 用研究，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］顧文斌，李育鑫，錢(qián)煜暉，等．基于激素調(diào)節(jié)機(jī)制IPSO算法的相 同并行機(jī)混合流水車(chē)間調(diào)度問(wèn)題［J]．計(jì)算機(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]黎陽(yáng)，李新宇，牟健慧．基于改進(jìn)模擬退火算法的大規(guī)模置換流 水車(chē)間調(diào)度[J].計(jì)算機(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)喜，何鑫，等．基于改進(jìn)非支配排序遺傳算法的多 目標(biāo)柔性作業(yè)車(chē)間低碳調(diào)度［J]．中國(guó)機(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]張國(guó)輝，張得雨，閆少峰，等.考慮工人協(xié)作與學(xué)習(xí)效應(yīng)的柔性作 業(yè)車(chē)間調(diào)度[J].計(jì)算機(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學(xué)習(xí)的作業(yè)車(chē)間動(dòng)態(tài) 調(diào)度算法[J]．計(jì)算機(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ì)志勇，袁逸萍，巴智勇，等．基于多動(dòng)作深度強(qiáng)化學(xué)習(xí)的紡機(jī) 制造車(chē)間調(diào)度方法[J].計(jì)算機(jī)應(yīng)用研究，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]吳秀麗，閆曉燕．基于改進(jìn)Q學(xué)習(xí)的可重入混合流水車(chē)間綠色 動(dòng)態(tài)調(diào)度[J].機(jī)械工程學(xué)報(bào)，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］孫愛(ài)紅，雷琦，宋豫川，等．基于深度強(qiáng)化學(xué)習(xí)求解作業(yè)車(chē)間機(jī) 器與AGV聯(lián)合調(diào)度問(wè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]趙銳，梁承姬．強(qiáng)化學(xué)習(xí)下淺充淺放充電策略AGV調(diào)度研究 [J]．計(jì)算機(jī)應(yīng)用研究，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.