基于改進雙檔案多目標進化算法的柔性作業車間批量流混排調度

摘 要：針對柔性作業車間批量流調度問題，基于快速換模技術，考慮可變子批劃分柔性、子批混排加工柔性、自動換模柔性和物料運輸柔性，建立以最小化完工時間和加工子批總數為目標的混排調度優化模型，并提出一種改進雙檔案多目標進化算法以優化目標函數。基于進化算法框架，設計了基于超體積指標和基于改進帕累托支配的雙檔案篩選機制，以平衡種群的收斂性和多樣性；針對批量流混排調度問題特征，在解碼階段提出正/逆解碼和子批拆分左移策略，在鄰域探索和全局搜索階段分別設計子批劃分和混排調度的自適應進化算子，以提高算法的全局搜索與局部搜索能力。基于不同規模算例，測試了提出算法與經典多目標算法的性能。實驗結果表明，該算法在收斂性與多樣性上具有明顯優勢。

關鍵詞：作業車間；批量流調度；快速換模；多目標進化算法；解碼策略

中圖分類號：TP29；TH165 文獻標志碼：A文章編號：1001-3695（2024）06-010-1669-10

doi： 10.19734/j.issn.1001-3695.2023.09.0499

Flexible Job-Shop lot-streaming intermingling scheduling based on

improved two-archive multi-objective evolutionary algorithm

Abstract：Aiming at the flexible Job-Shop lot-streaming scheduling problem， based on the single minute exchange of die （SMED）， this paper established an intermingling scheduling optimization model with objections of minimizing the makespan and the total number of sub-lots， considering the flexibility of sublots splitting and sublots intermingling， automatic changeover and material transportation. Then it proposed an improved two-archive based multi-objective evolutionary algorithm to optimize the objective function. This algorithm adopted the framework of evolutionary algorithm. Based on the framework of evolutionary algorithm， it designed a two-archive based on hypervolume indicator and improved Pareto dominance to balance the convergence and diversity of the population. And according to the characteristics of lot-streaming intermingling problems， it proposed the forward/backward decoding and sub-lot splitting hS8lmMi49X4hwiqGxJYtTQ==left-shift strategies in the decoding stage. In the stages of neighborhood exploration and global search， it designed adaptive evolution operators for lot splitting and sub-lot intermingling schemes respectively to improve the global search and local search capabilities of the algorithm. Based on different scale examples， it tested the performance of the proposed algorithm and the classical multi-objective algorithms. The experimental results show that the algorithm has obvious advantages in convergence and diversity.

Key words：Job-Shop; lot-streaming scheduling; single minute exchange of die; multi-objective evolutionary algorithm; decoding strategy

0 引言

柔性作業車間批量流調度（flexible Job-Shop lot streaming scheduling，FJSLSS）問題作為柔性作業車間調度問題的一個擴展，通過引入批量流技術，將整批工件劃分為若干較小的子批，實現分批生產與分批傳輸，能夠有效減少設備空閑時間、縮短完工時間、提高生產效率，并被廣泛應用于汽車、航空航天、電子電器、家具等多品種定制化生產制造中［1，2］。FJSLSS問題通常涉及了批量分割和子批排產兩個子問題。根據批量分割方法不同，可分為等量分批［1，2］、一致分批［3～5］和可變分批［6～8］。在子批排產階段，FJSLSS較常采用非混排策略，即同一臺機器在加工同一類型工件的各個子批之間不允許其他類型工件子批的插入加工，以最大限度減少換模次數、節約換模時間、縮短機器停工等待時長、提高設備利用率。

非混排調度策略非常適用于換模效率不高的生產系統，并成為批量流調度領域的一個重要研究方向。例如，Huang［1］基于等量分批和子批非混排策略，考慮在制品庫存成本、機器空閑成本和子批運輸成本等目標，建立了批量流調度優化模型；Daneshamooz等人［2］以柔性作業車間為研究對象，采用等量分批和非混排策略，建立了最小化完工時間的批量流調度混合整數優化模型，并提出了基于變鄰域搜索的優化求解算法；Li等人［3］針對柔性裝配作業車間分批調度問題，將一致分批策略與非混排策略相結合，建立了混合整數優化模型，并提出了一種改進人工蜂群（ABC）算法進行求解；Defersha等人［4］基于一致分批與非混排策略，以最小化完工時間為目標，建立了柔性作業車間批量流調度混合整數規劃模型，并采用改進的遺傳算法（IGA）求解；Cheng等人［5］以兩階段柔性裝配作業車間為研究對象，考慮完工時間和成本目標，建立了一致子批劃分與非混排調度優化模型，并設計了基于列生成的方法；Li［6］集成可變子批劃分策略與非混排策略，以最小化完工時間為目標，研究柔性作業車間批量流調度問題，并通過超啟發式遺傳算法（HHIGA）求解；Bozek等人［7］分別針對可變子批劃分和子批非混排兩個子問題，以最小化完工時間和子批總數為目標，提出了一種兩階段的分批調度優化方法。

混排調度策略相比于非混排策略具有更大柔性，其允許不同類型工件子批在同一臺機器上進行穿插加工，可進一步縮短生產周期、降低在制品庫存，但對生產系統的換模效率要求較高［8］。近年來，快速換模技術（single minute exchange of die， SMED）得到了快速發展，并被廣泛應用于汽車、食品加工、家用電器、工程機械、醫療器械等領域。SMED采用全自動快速換模系統來縮短換模停機時間，可有效提高機器生產效率［9］。例如，Basri等人［10］在汽車沖壓車間引入SMED，以減少沖壓工藝模具更換的時間，從而增加總產量；Ribeiro等人［11］將SMED應用于干豆類產品的包裝生產中；Ondra［12］在生產車間中引入了SMED和全面生產性維護等策略，以降低機器設備的空閑等待時長并縮短交貨期；Emekdar等人［13］將SMED技術應用于絲網印刷行業，并有效減少了生產線停機時間、提高了生產效率。將SMED引入制造車間中，可有效提高換模效率，能夠滿足多種類型工件子批在同一臺機器上的混排生產需求。將SMED引入柔性作業車間中，可有效提高換模效率，能夠滿足多種類型工件子批在同一臺機器上的混合生產需求。因此，本文以多品種、中小批量生產的柔性作業車間為研究對象，基于快速換模技術，將子批混合加工策略引入到批量流調度問題中，以進一步提高生產效率。

柔性作業車間批量流混排調度問題作為柔性作業車間調度問題的一個擴展，也屬于典型的NP-hard問題［14］，且其求解難度遠大于柔性作業車間調度問題，急需設計一種高效的優化求解算法。雙檔案優化算法（two-archive algorithm，Two_Arch）［15］是為平衡算法的收斂性和多樣性所提出的多目標進化算法，并在多目標、多約束組合優化領域得到了廣泛應用。例如，Li等人［16］為平衡解集的收斂性、多樣性和可行性，設計了檔案間互補的限制性交配選擇機制，提出了針對約束多目標優化的雙檔案進化算法（two-archive evolutionary algorithm for constrained multi-objective optimization，C_TAEA）；Gu等人［17］為求解數據驅動的混合整數優化問題，引入隨機森林分類器策略，提出了具有改進雙檔案的代理輔助多目標優化算法；Srinivasa等人［18］在Two_Arch基礎上引入改進MOEA/D中的權重向量自適應策略，提出了基于雙檔案引導分解的多目標進化算法，以求解多目標多約束問題；Li等人［19］為解決具有更復雜特征的約束多目標問題（constrained multi-objective problem，CMOP）并提高算法優化效率，改進了檔案CA的收斂策略，并提出新的DA檔案適應度評估方式，提出算法C_TAEA2；Li等人［19］引入推-拉雙階段的搜索策略，以提出雙檔案輔助推拉進化算法，解決具有復雜不可行區域的多目標多約束問題。

考慮到C_TAEA算法的檔案更新方式在解決更復雜的約束條件的問題上表現不佳，尤其是在解決柔性作業車間批量流混排調度這一NP-hard問題上。因此，本文針對柔性作業車間批量流混排調度問題，基于C_TAEA算法框架，設計了基于HV和改進帕累托支配的雙檔案篩選機制，創新性地提出了一種改進雙檔案多目標進化算法（two-arch based evolutionary multi-objective algorithm，TB-EMOA）。

1 問題描述及數學模型

柔性作業車間批量流混排調度問題描述為：柔性作業車間中共有K個自動化加工單元（每個加工單元由一臺加工設備組成）、一個自動化立體倉庫、一個配備有多臺AGV的自動化物料運輸系統、一套全自動快速換模系統；每個加工單元通過與不同工裝模具和其他輔助生產資源的配合，可滿足多種類型工件的混線生產需求；現有I種類型的待加工工件，每種工件i （i=1， 2， …，I）的批量大小為ρi；每種工件i的每個零件x （x=1， 2， …，ρi）均需經過ni道工序加工，且每種工件在每道工序上被分配的加工單元k （k=1， 2， …，K）是已知且確定的；基于批量流技術，每種工件在每個加工單元中可被拆分成多個子批進行加工，且同一種工件在不同加工單元中被劃分的子批數量ui，k與各子批的批量大小wi，k，s（s=1， 2， …，ui，k）不盡相同（可變子批劃分柔性［6］）；每個加工單元在加工同一種工件的任意兩個子批之間，允許其他種類工件子批插入加工（子批混排加工柔性［8］）；當同一個加工單元連續加工兩個不同種類的工件子批時，基于快速換模技術可自動快速更換模具，以提高多種類型工件混流生產效率（自動換模柔性［21］）；當子批中所有零件均到達加工單元的緩存區且待模具安裝（或更換）完成后，子批可開始加工；同一個子批中的所有零件必須被連續加工，不可被其他子批中斷；各工件子批在各加工單元之間的流轉由AGV完成，當子批結束某工序加工后，可立即被AGV運輸至下一個加工單元的緩存區中（各子批的等待運輸時間忽略不計，即物料運輸柔性［22］）。

為便于對問題進行建模，引入如下符號和變量：

a）符號和參數：

K為加工單元總數；

I為工件總數；

ρi為第i種工件的批量大小；

ri為第i種工件到達車間的時間；

ni為第i種工件的工序總數；

δ0為每個加工單元自動安裝（或更換）工裝模具的時間；

ε為子批在各加工單元之間的運輸時間；

πi，k為第i種工件的單個零件在第k個加工單元中的加工時間；

Ak為第k個加工單元的初始空閑時間；

ξi， j，k為0-1變量，若第i種工件的第j道工序被安排在第k個加工單元上加工，則ξi， j，k=1，反之，ξi， j，k=0。

b）決策變量：

ui，k為整數變量，表示第i種工件在第k個加工單元中被劃分的子批數量；

wi，k，s為整數變量，表示第i種工件在第k個加工單元中第s個子批的批量大小（規模）；

Vk為整數變量，表示第k個加工單元所加工的子批總數；

τi，k，s，x為0-1變量，若第i種工件的第x個零件在第k個加工單元中被分配到第s個子批，則τi，k，s，x=1，反之，τi，k，s，x=0；

φi，k，s，v為0-1變量，若第i種工件在第k個加工單元中第s個子批被安排在第v個加工順序上，則φi，k，s，v=1，反之，φi，k，s，v=0；

θk，v，i，i′為0-1變量，若第k個加工單元所加工的第v個子批與第（v-1）個子批均來自同一種工件（i=i′），則θk，v，i，i′=0，反之，θk，v，i，i′=1；

ATi，k，s為連續變量，表示第i種工件在第k個加工單元中第s個子批的所有零件均到達緩存區的時間；

ati，x，k為連續變量，表示第i種工件的第x個零件到達第k個加工單元緩存區的時間；

CTi，k，s為連續變量，表示第i種工件在第k個加工單元中第s個子批的結束加工時間；

CT*i為連續變量，表示第i種工件的完工時間。

調度目標是基于可變子批劃分柔性、子批混排加工柔性、自動換模柔性和物料運輸柔性，以最大完工時間最小化、加工子批總數最小化為目標，確定最優的批量流混排調度方案。具體包括：a）確定每種工件i在每個加工單元k中被劃分的子批數量ui，k；b）確定每種工件i在每個加工單元k中的每個子批s的批量大小wi，k，s （s=1， 2， …，ui，k）；c）確定各工件子批在各加工單元中的完工時間CTi，k，s。

快速換模作業車間柔性批量流調度優化模型，建立如下：

最大完工時間最小化目標：

加工子批總數最小化目標：

約束條件為

式（3）表示每種工件在每個加工單元中劃分的各子批批量總和不得超過該工件的零件總數；式（4）表示任一子批同一時刻只能被一個加工單元加工；式（5）表示每個加工單元在任一時刻只能加工一個子批；式（6）表示被分配到同一個子批中的零件總數不得超過該子批的批量大小；式（7）表示每個零件在每個加工單元中只能被分配在一個子批中；式（8）表示每種工件的完工時間為該工件所有子批的最大完工時間；式（9）（10）表示安裝（或更換）模具必須在加工單元空閑時開始，且待模具安裝完成后，子批可開始加工；同時，式（10）表示同一個加工單元在加工同一種工件的任意兩個子批之間，允許其他種類工件子批插入加工；式（11）（12）表示當且僅當子批在加工單元的緩存區中準備就緒后，該子批可開始加工；同時，式（9）～（12）表示同一個子批中的所有零件必須連續加工，不可被其他子批的零件中斷；式（13）（14）表示當子批中所有零件均結束當前工序的加工后，該子批可立即被AGV運輸至下一個加工單元的緩存區中；式（15）表示采用可變子批劃分策略時，同一個子批中各零件到達同一個加工單元緩存區的時間不盡相同，因此當且僅當該子批中所有零件均到達加工單元緩存區后，該子批才準備就緒；式（16）表示在每個加工單元中，同一種工件的所有零件將按照先到先服務規則依次被劃分入各子批中。

2 TB-MOEA算法

所建立的柔性作業車間批量流混排調度優化模型是一個典型的多目標、多變量、多約束 NP-hard 問題。精英檔案的保留有助于提高算法的性能［22］，C_TAEA是一種解決約束性問題的多目標進化算法，其通過采取兩種不同的檔案篩選方式，以平衡算法的收斂性和多樣性。在C_TAEA中，檔案更新方式采取基于帕累托直接篩選和基于超容量HT指標的檔案更新策略，其在解決更復雜的約束條件的問題上表現不佳；在收斂性檔案（convergence archive，CA）更新中，其基于帕累托直接篩選的機制總是更傾向于可行的解，從而導致其僅在局部區域進行探索，而無法完整探索解空間，且基于超容量HT指標的多樣性歸檔（diversity archive，DA），處理具有更復雜特征的CMOP時，可能會遠離真實帕累托前沿。

基于強帕累托支配算法［23］，采取帕累托支配和鄰近法相結合的檔案修建方式，在求解多目標多約束問題時具有良好的性能。因此，在C_TAEA算法框架上，設計了基于HV指標和基于改進帕累托支配的雙檔案篩選機制，提出了TB-MOEA算法。算法框架如圖1所示。結合柔性作業車間批量流調度問題特征，對算法關鍵步驟（編碼方式、種群初始化、解碼策略、檔案修建、局部和全局搜索等）進行了詳細設計。

2.1 編碼

針對柔性作業車間批量流調度問題，需分別對可變子批劃分（BS）和子批混排調度方案（BP）兩個子問題進行編碼。采用兩級編碼Chrome=［X， Y］，其中X表示可變子批劃分， Y表示子批混排調度方案。

2.1.1 可變子批劃分X

采用二維不規則數組X=［aij］I×N表示可變子批劃分編碼，其中aij=［wij1，wij2，…，wijs，…，wijui， j］，表示第i個工件在第j道工序上劃分的分批方案；wijs為第i個工件在第j道工序上的第s個子批的批量大小；uij為第i個工件在第j道工序上劃分的子批總數。以式（17）為例，其中a21=［w211，w212，w212］=［4，3，3］，即第2個工件所需要加工的零件總數為10，在第1道工序被分為3個子批進行加工，子批大小分別為4、3和3。

2.1.2 子批混排調度方案Y

采用一維數組Y=［aj］N表示子批混排調度編碼，其中每一個元素aj=（i， j）表示工件i的第j道工序；Y中每個元素aj=（i， j）重復出現的次數，則表示該工件i在第j道工序上拆分的子批數量。以圖2的染色體編碼為例，第一次出現的（3，1）表示第3個工件第一道工序上的第1個子批；第二次出現的（3，1）表示第3個工件第一道工序上的第2個子批。

2.2 初始化

為促進目標空間收斂并保證解的多樣性，分別針對工件分批方案和子批混排調度方案，設計了初始種群生成規則。

a）采用文獻［24］中的工件分批方案初始化方法，具體為：（a）平均分批；（b）隨機分批；（c）均勻劃分后引入隨機量以改變分批。

b）采用經典調度規則［25］生成子批混排調度方案：（a）最多工序剩余的子批最先開始加工；（b）最長剩余加工時間的子批最先開始加工；（c）隨機生成子批混排調度方案。種群生成比例設置為1∶1∶8。

2.3 解碼

解碼過程就是在算法的編碼基礎上進行信息讀取，以生成調度表。針對柔性作業車間批量流調度問題特征，設計了基于正序/逆序解碼+子批拆分左移+子批合并的解碼策略，以增強對個體解在解空間上的鄰域探索。

2.3.1 正解碼

傳統調度問題的解碼方式較常采用正解碼。在正解碼中，解碼順序為在Y染色體依次讀取子批混排調度方案 → X染色體上讀取該子批的零件數目 → 在工件加工信息上讀取單一零件的加工時間以獲取總子批的加工時間 → 獲取此前機器加工信息 → 在機器上安排該子批加工。

2.3.2 逆解碼

正解碼和逆解碼的不同點在于“X染色體上讀取子批加工零件數目”這一環節，逆序解碼策略需要將現有可變子批劃分方案X通過逆序操作來生成一個新的可變子批劃分方案。該策略的核心思想就是針對每個工件的每道工序所對應的可變子批劃分信息，在加工順序不發生改變的情況下，通過逆序可變子批劃分信息的方式獲取一個與當前染色體相似度較高的解，即在染色體上，將aij=［wij1，wij2，…，wijs，…，wijui， j］逆序后獲得aij=［wijui， j，…，wijs，…，wij2，wij1］。以式（18）中的染色體編碼為例，將原染色體SSori通過逆序操作變成SSrev。

2.3.3 子批拆分左移策略

將子批拆分與左移插空策略相結合，通過將某子批中的部分零件左移來提前加工，同時減少機器上的空閑時間以優化子批的最大完工時間。拆分左移的偽代碼如算法1所示。圖3中（a）為子批拆分左移策略的單一機器圖例，（b）為實際調度表案例。在圖（b）中，通過將原本安排在M3上加工的工件3的第二道工序的一個子批，拆分為兩個子批，并將一個子批左移至可加工的時間點，可顯著縮短最大完工時間。

2.3.4 子批合并策略

保證檔案篩選中的個體是本次迭代過程的更優解，算法引入子批合并策略。這一策略的核心思想是：在不影響任一工件的任意零件在其對應機器上的加工時間前提下，將兩個子批合并形成一個新的子批，新子批的大小等于原兩子批大小之和。子批合并策略偽代碼如算法2所示，實例如圖4所示。

算法1 子批拆分左移策略

算法2 子批合并策略

2.4 檔案修建

2.4.1 相似度篩選

在探索解空間以獲取最優帕累托前沿過程中，種群中存在部分編碼不同而目標值相同的個體。如圖5所示，任意序列①～⑤中所選中的子批批次數量改變和子批加工順序互換都不會改變目標值。當這些相似度高的個體適應度值較好時，這部分個體將被保留下來，從而降低種群多樣性、導致算法陷入局部最優。因此，在TB-MOEA算法中引入了相似度篩選，以避免過多近似解進入雙檔案中。在相似度篩選中，考慮到算法的多樣性需求及問題的目標值僅為兩個，因此僅對目標值一致的目標進行篩選。在獲取相似值后，對相似值大于0.95的解進行隨機保留，即保留一個個體解，以避免其占據后續迭代種群的位置。通過計算個體之間每個工件的對應工序的分批信息的絕對距離得到相似度篩選的適應值f，其計算公式如下：

其中： fi表示工件i的分批方案相似度； fi，k表示工件i在加工單元k上的子批分批方案相似度；wi，k，s和w′i，k，s代表需要進行相似度計算的兩個子批分批方案排序列表之間的絕對距離。

2.4.2 雙檔案機制

TB-MOEA算法采用雙檔案篩選機制來平衡算法的收斂性和多樣性。該篩選機制核心思想是通過不同的更新機制分別更新CA和DA來平衡算法的收斂性和多樣性。兩種檔案的更新策略步驟如下：

1）檔案CA的更新策略（檔案上限設定為N，種群數量為M）

a）迭代的新種群POP與檔案CA合并形成QC。

b）通過快速非主導排序將QC劃分為多個子集。

c）按分層順序依次取出子集，并獲取子集個體數n。

d）若子集個體數（n+CA）現有個體數s小于CA上限N，返回步驟c），否則進行步驟e）。

e）計算該子集每個個體的獨立超體積貢獻值，并逐個刪除適應度最低的個體，即每次僅刪除一個解，直到（n+CA）現有個體數等于CA上限。

2）檔案DA的更新策略

a）將迭代的新種群POP與檔案DA合并形成QD；

b）獲取QD的個體數L，獲取需要保留的隨機解數量RN=min（25，（M-N）/2）；

c）通過式（22）（23）計算適應度值，保留適應度值較小的對應解，保留數量為A=max（25， （3N-M）/2），隨后通過隨機篩選的方式，在剩余解集中抽取個體數為RN，依次來有效確保算法的多樣性。

其中：F（i）為適應值；R（i）和D（i）分別為支配個體i的解所支配的個體數和k-鄰近法所求的種群密度值；S（i）為工件i所支配解的數量。

2.5 鄰域與全局搜索

為找到距離真實帕累托前沿最近且分布性好的帕累托前沿，對TB-MOEA算法的鄰域和全局搜索作出了改進。在鄰域搜索部分，考慮到收斂性需求，鄰域搜索僅在檔案CA上展開；全局搜索在集合［CA， DA］上展開，同時在全局搜索上采用了改進的交叉和變異算子，以提高種群多樣性并避免迭代過程陷入局部最優。

2.5.1 鄰域探索

在TB-MOEA算法中，分別針對可變子批劃分方案和子批混排調度兩部分設計了算子。在可變子批劃分方案上，通過所設計的自適應尋優算子在檔案CA上抽取親代以生成后代；在子批混排調度方案上，通過基于關鍵鏈的算子探尋鄰域解，具體如下：

a）針對可變子批劃分方案的自適應尋優變異算子。

通過改進文獻［26］中最優個體的變異方式，生成自適應尋優算子，具體如下：首先需要通過隨機抽取的方式，在檔案CA中抽取本次的親代F；隨后在檔案CA中獲取關于F的支配解集和非支配解集，在支配解集和非支配解集中，各抽取一個解作為優解和劣解，對比優、劣解的分批方案，獲取親代中與劣解相同或相似的某一工件某一工序的可變子批劃分方案，將優解中的方案替代原親代方案，生成新解，偽代碼如算法3所示。

算法3 自適應尋優變異算子

b）針對子批混排調度方案的變異算子。

基于關鍵鏈的鄰域搜索策略，可有效縮短車間調度問題的工件最大完工時間。關鍵鏈是從第一個開始加工的子批開始到最后一個完成加工子批的最長路徑；關鍵鏈上的操作被定義為關鍵工序；同一機器上前后多個關鍵工序合在一起被稱為關鍵塊。基于關鍵鏈子批混排調度變異算子的步驟如下：首先在調度表上獲取一條關鍵鏈；然后找出該關鍵鏈上的所有關鍵塊；最后隨機抽取若干關鍵塊，并將其關鍵工序互換，以生成新的子批混排調度方案。如圖6所示，在圖（a）中獲取關鍵鏈，通過改變機器M3上的關鍵塊中關鍵工序的加工順序，就可得到圖（b）中新的調度圖，并有效減少了工件的最大完工時間。

2.5.2 全局開發

針對柔性作業車間批量流調度問題特征，分別針對可變子批劃分方案和子批混排調度兩部分設計了算子，以提高在調度問題上的算子適用性，具體如下：

a）針對可變子批劃分的隨機變異算子。

變異算子的步驟如下：

（a）在檔案CA和檔案DA的檔案合集上，隨機抽取親代F；

（b）隨機抽取親代F上某一工件的某一工序的可變子批劃分信息w；

（c）在（1， N-length（w））上隨機抽取一個值，并將該值作為該可變子批劃分上隨機抽取的一個子批的新大小，并獲取前后改變的大小差值，d=old-new；

（d）生成隨機數GS=random（0，1），若GS小于0.5，轉到步驟（e），否則轉到步驟（f）；

（e）將差值均攤給其他子批，并在差值為負數時，子批大小為1的子批將不會減少子批大小，即保證子批數量不發生改變，轉到步驟（g）；

（f）在差值為正時，將差值重新生成一個新的子批；差值為負數的時候，將差值均攤給其他子批，但允許子批大小為0，當子批大小為0的時候將減少子批數量；

（g）獲取變異的子批信息，取代親代原片段以生成子代。

b）針對子批混排調度方案的進化算子。

采用進化算法中較為常用的進化算子［16］，即反演突變算子和子路徑交叉算子。其操作詳解如下：

（a）反演突變算子：通過隨機抽取染色體片段，對該片段進行逆序編碼以生成新解；然后考慮加工工序順序約束，對非可行染色體作修正。具體如圖7所示。

（b）路徑交叉算子：在檔案CA和檔案DA中各抽取一個解作為親代F1和F2，并在親代上F1選擇一組基因片段；然后，在親代F2上尋找到親代F1上該片段每個元素所對應的位置，并將親代F1和F2中所選中位置上的元素進行替換，以完成交叉操作。具體操作以圖8為例。

3 實驗

為了確保模型的可靠性，本文對模型進行了有效性驗證。最終模型在輸入輸出關系、穩定性等方面都得到了較好的驗證。

算法采用Python編程實現，測試計算機參數：CPU為AMD Ryzen 7 5800H 3.2 GHz，內存為16 GB。為測試算法性能，設計了18個不同規模（I×O×M）算例。其中，工件數I的范圍為{7，10，15}；工序數設定為O={6，8}；機器數為M={8，10，15，20}。其余參數如表1所示。

3.1 參數設定

采用全因素實驗（DOE）設計確定TB-MOEA算法最優參數。TB-MOEA算法的關鍵參數包括鄰域解數量O、全局搜索中加工順序編碼概率PSP和可變子批劃分概率PSS。每個參數設置4個水平，如表2所示。選取案例L06作為測試對象，以總迭代次數50作為終止條件，在每種參數組合下運行算法十次，總運行次數為4×4×10=160次，記錄每次運行后獲得的非支配解集。在所有組合被測試后，獲得一個最終的非支配解集，并將其他每種組合所獲得的非支配解集占最終非支配解集的比例作為響應值（response variable， RV）。RV越大，表示其對應的參數組合下的算法性能更優。正交實驗結果如表3所示。表4表示TB-MOEA算法參數的均值響應。圖9表示TB-MOEA算法的參數水平，由圖9可知，TB-MOEA算法最優參數為：鄰域解數量O=40，全局搜索中加工順序編碼概率PSP=0.6，可變子批劃分概率PSS=0.8。

3.2 策略有效性驗證

為驗證所設計的正/逆解碼和左移拆分策略的有效性，在設計的算法框架等不改變的情況下，分為以下三種：a）只采用正序解碼的TB-MOEAnone；b）采用正序+逆序解碼策略的TB-MOEAre；c）采用正序解碼+逆序解碼+左移拆分策略的TB-MOEAre+le。每種算法在不同規模算例上分別運行十次，并采用多樣性指標Δ（S，P）、收斂性指標GD（generational distance，世代距離） 和綜合指標HV（hypervolume，超體積指標） 來對算法性能進行評價。其中，多樣性指標Δ（S，P）越小代表算法多樣性越好，指標GD值越小代表算法收斂性越好，指標HV越大表示算法綜合性能越好。

實驗結果如表5～7所示，其中加粗部分表示算法所獲得的指標更好，即該組對應獲得的帕累托前沿具有更好的收斂性和多樣性。

由表5～7可知，TB-MOEAre+le在18組規模算例中均獲得了多樣性指標Δ（S，P）、收斂性指標GD和綜合指標HV的最優值；TB-MOEAre在所有算例上的HV值均優于TB-MOEAnone，在15組算例上取得更優的Δ（S，P）值，在14組算例上GD值表現更優。TB-MOEAnone在三個性能指標上的表現最不理想。從指標數值結果來看，TB-MOEAnone、TB-MOEAre、TB-MOEAre+le算法的Δ（S，P）均值分別為7.131E-01、7.124E-01和5.380E-01，GD均值分別為1.452E-01、1.230E-01和8.724E-02，HV均值為1.113E-01、1.072E-01和1.722E-01，說明算法TB-MOEAre+le在收斂性、多樣性和綜合性能上均優于TB-MOEAnone和TB-MOEAre。為直觀地證實結論，通過置信度為95%的置信區間圖來展示。以三者的HV區間圖為例，如圖10所示，TB-MOEAnone與TB-MOEAre重疊部分較大，且置信區間上下限相近，但都明顯低于TB-MOEAre+le，說明TB-MOEAre+le在綜合性能上要明顯優于TB-MOEAre和TB-MOEAnone。TB-MOEAre+le相比于TB-MOEAnone和TB-MOEAre的優勢在于：a）通過正/逆解碼策略有效保證了種群多樣性，并提高了算法的全局搜索能力；b）左移拆分策略加強算法局部搜索能力，促進了種群收斂。

3.3 算法性能對比

為測試TB-MOEA 算法在柔性作業車間批量流調度問題上的有效性，將其與SPEA2、SMS-EMOA進行對比測試。其中，SPEA2、SMS-EMOA的種群大小設置與TB-MOEA 算法相同，所有算法均共用初始化、解碼、相似度篩選等策略。此外，在迭代階段，SPEA2、SMS-EMOA算法采用2.5節所提出的鄰域搜索和全局開發思想進行解空間探索，但在親代選擇方式上因算法框架不同而采取輪盤賭的方式。每種算法在不同規模算例上分別運行十次，得到的算法性能指標Δ（S，P）、GD、HV平均值如表8～10所示，其中加粗部分表示算法所獲得的指標更優。

在表8中，TB-MOEA在15個算例上獲取多樣性指標Δ（S，P）的最優值，SPEA2和SMS-EMOA分別取得了1、2個算例上的指標Δ（S，P）的最優值，由此初步推斷TB-MOEA在多樣性上優于SPEA2和SMS-EMOA算法。TB-MOEA、SPEA2和SMS-EMOA的多樣性指標Δ（S，P）平均值分別為5.380E-01、5.563E-01和5.459E-01。由于TB-MOEA的平均Δ（S，P）值小于SMS-EMOA，同時SMS-EMOA的平均Δ（S，P）值小于SPEA2，通過置信區間可以得出結論，TB-MOEA在多樣性上較優于SPEA2和SMS-EMOA。

在表9中，TB-MOEA在全部18個算例上獲取收斂性指標GD的最優值，由此說明在收斂性上，TB-MOEA優于SPEA2和SMS-EMOA。對收斂性指標求平均值，可得TB-MOEA、SPEA2和SMS-EMOA的GD平均值分別為8.724E-02、2.580E-01和2.166E-01。由于TB-MOEA的平均GD值小于SMS-EMOA，SMS-EMOA的平均GD值小于SPEA2，所以在收斂性上TB-MOEA>SMS-EMOA>SPEA2。通過執行一個雙邊t檢驗以獲得其95%的置信區間圖，如圖11所示。可以看出，TB-MOEA在收斂性上顯著優于SPEA2和SMS-EMOA，同時SMS-EMOA的收斂性優于SPEA2。

在表10中，TB-MOEA在全部18個算例上獲取綜合性指標HV的最優值，可初步得到在綜合性上TB-MOEA優于SPEA2和SMS-EMOA兩個算法。TB-MOEA、SPEA2和SMS-EMOA的HV平均值分別為1.722E-01、1.547E-01和1.604E-01。可以得到TB-MOEA的平均HV值大于SMS-EMOA，SMS-EMOA大于SPEA2。進一步推斷綜合性，TB-MOEA> SMS-EMOA > SPEA2。為驗證這一結論，通過執行一個雙邊t檢驗以獲得其95%的置信區間圖，如圖12所示。可以看出，TB-MOEA所占區間整體上較優于SMS-EMOA和SPEA2，可得到TB-MOEA要較優于SPEA2和SMS-EMOA。由此可以得出結論，TB-MOEA在綜合性上較優于SPEA2和SMS-EMOA。

圖13展示了柔性作業車間在批量流混排情況下的甘特圖，圖14展示了三種算法在18種不同算例下的帕累托前沿。由圖14可以明顯看出，TB-EMOA算法求解柔性分批調度問題所獲得的前沿明顯優于SPEA2和SMS-EMOA，所獲取的帕累托前沿大多都能支配SPEA2和SMS-EMOA所獲取的前沿中的個體解。此結果說明，TB-MOEA算法在求解多目標批量流調度問題上具有優越性。

綜上所述，TB-MOEA在多樣性、收斂性和綜合性上均優于SPEA2和SMS-EMOA，算法對比過程中共享大部分代碼，僅在算法框架上有所不同，其TB-MOEA算法性能更好的主要原因在于：通過能平衡算法的收斂性和多樣性的雙檔案機制，使用兩個外部精英檔案分別專注于算法多樣性和收斂性，來保障種群迭代過程中不至于陷入局部最優。

4 結束語

針對柔性作業車間批量流調度問題，集成可變子批劃分柔性、子批混排加工柔性、自動換模柔性和物料運輸柔性，以最大完工時間最小化、加工子批總數最小化為目標，建立了批量流混排調度混合整數線性規劃模型。在C-TAEA算法框架基礎上，設計了基于HV和改進帕累托支配的雙檔案篩選機制，并提出了一種改進雙檔案多目標進化算法；結合作業車間柔性批量流調度問題特征，設計了基于正/逆解碼和左移拆分策略的解碼，設計了鄰域探索和全局開發適應性算子，以提高算法的全局搜索與局部搜索性能。選取不同規模算例，驗證了所設計解碼策略的有效性，實驗結果表明，左移拆分策略對算法的多樣性和收斂性能有明顯提升，正/逆序解碼策略能有效提高算法的收斂性能；同時，在共享編碼、解碼、迭代策略的情況下，測試了TB-MOEA與經典多目標算法SPEA2、SMS-EMOA的算法框架在不同規模算例下的求解性能，結果表明，TB-MOEA在解集多樣性、收斂性和綜合性上均具有明顯優勢，由此說明雙檔案篩選機制所采取的使用兩個精英外部檔案保留種群的方式，有效地促進了算法在多樣性和收斂上的平衡，從而通過算法能有效獲得調度問題的最優帕累托前沿。后續研究可將批量流混排調度方法擴展到更為復雜的生產系統中（如動態生產環境），并添加更多約束以貼近實際生產，同時進一步提高算法的求解性能。

參考文獻：

［1］Huang Ronghua. Multi-objective Job-Shop scheduling with lot-splitting production ［J］. International Journal of Production Econo-mics，2010，124（1）：206-213.

［2］Daneshamooz F，Fattahi P，Hosseini S M H. Scheduling in a flexible Job-Shop followed by some parallel assembly stations considering lot streaming［J］. Engineering Optimization，2022，54（4）： 614-633.

［3］Li Xiulin，Lu Jiansan，Yang Chenxi，et al. Research of flexible assembly Job-Shop batch-scheduling problem based on improved artificial bee colony［J］. Frontiers in Bioengineering and Biotechnology，2020，10：909548.

［4］Defersha F M，Movahed S B. Linear programming assisted （not embedded） genetic algorithm for flexible Job-Shop scheduling with lot streaming［J］. Computers and Industrial Engineering，2018，117： 319-335.

［5］Cheng Ming，Sarin S C. Lot streaming in a two-stage assembly system［J］. Annual Reviews in Control，2020，50（8）：303-316.

［6］Li Lele.Research on discrete intelligent workshop lot-streaming sche-duling with variable sublots under engineer to order ［J］. Computers & Industrial Engineering，2022，165（8）：107928.

［7］Bozek A，Werner F. Flexible Job-Shop scheduling with lot streaming and sublot size optimisation［J］.Taylor & Francis，2018，56（19）： 6391-6411.

［8］Wang Wenyan，Xu Zhenhao，Gu Xingsheng. A two-stage discrete water wave optimization algorithm for the flowshop lot-streaming scheduling problem with intermingling and variable lot sizes［J］. Knowledge-Based Systems，2022，238：107874.

［9］Da Silva I B，Godinho F M.Single-minute exchange of die （SMED）： a state-of-the-art literature review［J］.International Journal of Advanced Manufacturing Technology，2019，102（9-12）： 4289-4307.

［10］Basri A Q，Mohamed N，Nelfiyanti，et al. SMED simulation in optimising the operating output of tandem press line in the automotive industry using WITNESS software［J］. International Journal of Automotive And Mechanical Engineering，2021，18（3）： 8895-8906.

［11］Ribeiro M A S，Santos A C O，De Amorim G D，et al. Analysis of the implementation of the single minute exchange of die methodology in an agroindustry through action research ［J］. Machines，2022，10（5）：287.

［12］Ondra P. The impact of single minute exchange of die and total productive maintenance on overall equipment effectiveness ［J］. Journal of Competiveness，2022，14（3）： 113-132.

［13］Emekdar E，Acikgoz-Tufan H，Sahin U K，et al. Process improvement and efficiency analysis using the single-minute exchange of dies method applied to the set-up and operation of screen-printing machines［J］. Coloration Technology，2023，139（2）： 209-218.

［14］李瑞，徐華，楊金馮，等. 改進近鄰人工蜂群算法求解柔性作業車間調度問題［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.）

［15］Praditwong K，Yao Xin. A new multi-objective evolutionary optimisation algorithm： the two-archive algorithm［C］//Proc of International Conference on Computational Intelligence & Security. Piscataway，NJ：IEEE Press，2006.

［16］Li Ke，Chen Renzhi，Fu Guangtao，et al. Two-archive evolutionary algorithm for constrained multi-objective optimization［EB/OL］. （2018）. https：//arxiv.org/abs/1711.07907.

［17］Gu Qinghua，Wang Danna，Jiang Song，et al. An improved assisted evo-lutionary algorithm for data-driven mixed integer optimization based on two_arch［J］. Computers & Industrial Engineering，2021，159：107463.

［18］Srinivasa R M，Mallipeddi R，Das K N. A twin-archive guided decomposition based multi/many-objective evolutionary algorithm［J］.Swarm and Evolutionary Computation，2022，71：101082.

［19］Li Wei，Gong Wenyin，Ming Fei，et al. Constrained multi-objective evo-lutionary algorithm with an improved two-archive strategy［J］. Knowledge-Based Systems，2022，246：108732.

［20］Qin Cifeng，Ming Fei，Gong Wenyin. Constrained multi-objective optimization via two archives assisted push-pull evolutionary algorithms ［J］. Swarm and Evolutionary Computation，2022，75：101178.

［21］Braglia M，Di Paco F，Marrazzini L. A new Lean tool for efficiency evaluation in SMED projects［J］. International Journal of Advanced Manufacturing Technology，2023，127（1-2）： 431-446.

［22］Zhang Huiyu，Xi Shaohui，Chen Qingxin，et al. Performance analysis of a flexible flow shop with random and state-dependent batch transport［J］. International Journal of Production Research，2020，59（4）： 982-1002.

［23］劉麗娜，南新元，石躍飛. 改進麻雀搜索算法求解作業車間調度問題 ［J］. 計算機應用研究，2021，38（12）： 3634-3639. （Liu Lina，Nan Xinyuan，Shi Yuefei. Improved sparrow search algorithm for solving Job-Shop scheduling problem ［J］. Application Research of Computers，2021，38（12）： 3634-3639. ）

［24］Zhang Bian，Pan Quanke，Meng Leilei，et al. An automatic multi-objective evolutionary algorithm for the hybrid flowshop scheduling problem with consistent sublots［J］.Knowledge-Based Systems，2022，238：107819.

［25］Caldeira R H，Gnanavelbabu A. Solving the flexible Job-Shop scheduling problem using an improved Jaya algorithm［J］. Computers & Industrial Engineering，2023，137：106064.

［26］張國輝，閆少峰，陸熙熙，等. 改進混合多目標蟻群算法求解帶運輸時間和調整時間的柔性作業車間調度問題 ［J］. 計算機應用研究，2023，40（5）：3690-3695. （Zhang Guohui，Yan Shaofeng，Lu Xixi，et al. 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（5）： 3690-3695.）