改進Jaya算法求解混合流水車間調度問題

摘要：混合流水車間調度問題（HFSP）是廣泛存在于流程制造系統中的NP-hard問題。針對最小化完工時間的HFSP，結合Jaya算法和禁忌搜索的優勢，提出了一種改進Jaya算法。在該算法迭代更新階段，根據設計的編碼方式提出一種基于路徑重連的方法來進行離散更新，以保證種群的多樣性，提高全局搜索能力。為提高局部搜索能力，提出融合兩種鄰域結構的禁忌搜索算法來進一步提高解的質量，并根據問題特性對鄰域結構進行適配調整。采用所提算法求解三種基準測試集，在大規模經典測試集中求出新的最優解，在解的質量方面優于當前文獻中其他算法，驗證了所提算法的有效性和優越性。

關鍵詞：混合流水車間調度；路徑重連；禁忌搜索；完工時間

中圖分類號：TH186

DOI：10.3969/j.issn.1004132X.2024.08.014

開放科學（資源服務）標識碼（OSID）：

Improved Jaya Algorithm for Solving HFSPs

ZHOU Hao1 ZHANG Chaoyong1，2 LIU Hui1，3 LUO Min2

1.School of Mechanical Science amp; Engineering，Huazhong University of Science and Technology，

Wuhan，430074

2.School of Electrical and Information Engineering，Hubei University of Automotive Technology，

Shiyan，Hubei，442002

3.WISDRI Engineering and Research Incorporation Limited，Wuhan，430223

Abstract： HFSP was an NP-hard problem widely presented in process manufacturing systems. For HFSP aimed at minimizing makespan， an improved Jaya algorithm was proposed by combining the advantages of Jaya algorithm and Tabu search. During the iterative update phase of the algorithm， a path reconnection-based method was proposed for the discrete update of the algorithm according to the designed coding， which ensured the diversity of the population and enhanced the global search capability. To improve local search capability， a Tabu search algorithm integrating two types of neighborhood structures was proposed to further enhance the quality of solutions， and the neighborhood structures were adjusted adaptively according to the characteristics of the problem. The proposed algorithm was used to solve three types of HFSP benchmark sets. New optimal solutions are found in large-scale classic benchmark sets， which are superior to other algorithms in the current literatures in terms of solution quality， verifying the effectiveness and superiority of the proposed algorithm.

Key words： hybrid flow-shop scheduling problem（HFSP）; path relink; Tabu search; makespan

0 引言

混合流水車間調度問題（hybrid flow shop scheduling problem， HFSP）在離散、流程生產系統中廣泛存在，例如鋼鐵冶煉、紡織、汽車制造等，并已被證明是強NP-hard問題［1］。在HFSP中，一組有相同加工路線的作業需依次經過多個階段，每階段配備并行相同的機器設備。調度策略作為連接生產前端設計與后端制造的關鍵環節，其優化與創新直接影響到制造業的效率、質量和競爭力［2］。HFSP問題的研究和應用不僅是提高生產效率、降低成本的關鍵，更是實現客戶定制化、小批量多樣化生產的基礎。

目前，求解HFSP問題主要可歸納為三大類：精確算法、啟發式算法和元啟發式算法。精確算法，如混合整數線性規劃、分支定界（branch and bound， Bamp;B）和拉格朗日松弛旨在找到問題的最優解［3］。MENG等［4］根據不同的建模思想制定八種混合整數線性規劃模型，用于求解最小化完工時間的不相關并行機的HFSP及其擴展問題，并驗證基于階段優先的模型是最優的，然而當問題規模增大時，這些算法的計算時間和復雜度也會隨之上升，導致求解時間較長且需大量算力資源，故精確算法更適合于小規模的HFSP問題。鑒于實際應用中的問題規模常常較大，啟發式及元啟發式算法因能迅速獲得近似最優解而逐漸受到學者們的青睞。啟發式算法通常基于一些經驗或直覺的啟發規則，如任務排序或分配至機器的簡化策略。MISSAOUI等［5］設計了一種針對具有時間設定和截止日期窗口的HFSP的無參數貪婪算法。啟發式算法雖然計算迅速，但并非總能確保找到最優解，故常被用作精確或元啟發式算法的輔助工具。

元啟發式算法能在較短時間內獲得問題高質量的解，能夠在求解速度、質量、靈活性和魯棒性之間達到較好的平衡，受到越來越多研究者的重視。元啟發式算法借鑒自然界中的生物進化和物理過程所表現出來的規律，有多種元啟發式算法可以解決各類型的HFSP問題，例如：遺傳算法（genetic algorithm， GA）［6］、人工蜂群算法（artificial bee colony， ABC）［7］、差分進化（differential evolution，DE） 算法［8］、粒子群優化 （particle swarm optimization， PSO） 算法［9］、灰狼 （grey wolf optimization， GWO）算法［10］、果蠅優化算法（fruit fly optimization algorithm， FOA）［11］等。不同的元啟發式算法通常各具優點和局限性，例如：禁忌搜索（tabu search， TS）［12］局部搜索能力較強，具有較高的求解質量，但存在一定的可能性出現局部最優解；路徑重連（path relink，PR）［13］可以自適應地調整搜索空間和搜索方向，但對初始解的要求較高。Jaya算法是文獻［14］提出的一種新型的簡單、無需參數調整的無約束優化算法，近年已應用于各類車間調度問題，如置換流水車間調度問題、柔性作業車間調度問題等。BUDDALA等［15］將變異策略納入教學的優化（teaching-learning-based optimization， TLBO）和Jaya算法并用于求解HFSP問題。連裕翔等［16］提出一種擴展離散操作機制的改進Jaya算法來求解柔性作業車間調度問題。Jaya算法簡單易于實現，適用于解決多階段和多機器的調度問題，但需要設計與其編碼方式相適應的離散迭代更新方式，同時其局部搜索能力較弱，需要引入特定形式的局部搜索算法。將不同元啟發式算法組合在一起，充分發揮各自的優勢，可以提高算法的求解效率和質量。例如，AMIRTEIMOORI等［17］設計了一種混合并行PSO-GA算法來求解有限運輸車和具有并行無關機器階段的HFSP問題，并驗證了混合算法的表現優于單獨算法。

在元啟發式算法的設計中，編解碼策略與鄰域結構是決定算法搜索空間和效率的關鍵因素［18］。當前大部分針對HFSP問題的求解算法都采用基于單階段的排列編碼，因其簡便性而導致求解效率相對較高。但此編碼方式不包括機器選擇，只有經過解碼后才得到完整解。常見的解碼方式包括置換解碼和排列解碼，但此策略可能會遺漏某些優解。任彩樂等［19］在候鳥算法的基礎上引入一種兩階段解碼方法，并證明該算法的結果優于原算法。不僅如此，由于先前采用的編碼策略，現有的針對HFSP的局部搜索算法的鄰域結構多數不是基于關鍵路徑設計的，而更多是隨機選取工件進行擾動的［1］，這種對非關鍵路徑上的工序塊的隨機擾動并不能高效地更新當前解，使得現有的局部搜索效果受限且速度較慢。目前高效的鄰域結構設計出來是為了求解作業車間調度問題（job shop scheduling problem， JSP）和柔性作業車間調度問題（flexible job shop scheduling problem， FJSP），但是由于混合流水車間的特性，一些鄰域結構設定的擾動和鄰域裁剪方式可進一步進行相應的適配修改。FAN等［20］設計了兩種編碼方式的混合進化算法來求解HFSP問題，通過析取圖的表達方式，在禁忌搜索階段運用基于關鍵路徑的鄰域結構，所得結果質量超過其他算法。

本文提出了一種改進Jaya算法，旨在求解最小化完工時間的HFSP問題。應用一種基于機器的全階段編碼方法，無需復雜的解碼步驟，且能表示所有潛在的半主動調度方案。基于此編碼特性，開發了一種離散Jaya迭代方法，利用路徑重連技術來保證種群的多樣性并避免過早收斂，有助于在解空間中探索不同區域，從而提高找到全局最優解的可能性。在局部搜索階段引入基于關鍵路徑的高效鄰域結構的禁忌搜索，并針對問題特點對鄰域結構進行調整。最后，將所提算法應用于多個基準測試集，并與當前文獻中其他優秀算法進行對比，以驗證該算法的有效性和優越性。

1 問題模型

1.1 問題介紹

HFSP問題是流水車間問題的擴展，由于包括作業順序和機器分配的子問題，并且在實際生產中主要用于大規模的生產制造，故大大增加了問題的計算復雜性。該問題定義為有待加工的工件N={J1，J2，…，Jn}和加工階段S={S1，S2，…，Ss}。每個工件包含的每道工序Oi={Oi1，Oi2，…，Ois}需依次通過每個階段，每個階段都有一定數量的并行機器M={M1，M2，…，Mm }，至少有一個階段的并行機器數量大于1，工序Oij在機器上的加工時間Pij已知，工序Oij的完成時間記為COij。即Cmax=max{i∈N，j∈S|COij}。求解以最小化完工時間為目標函數的HFSP問題，即為每個工件在每個階段分配可用機器，并確定每臺機器上工件的加工順序，使得最長完工時間Cmax最小。

本文研究的問題模型基于以下約束條件和假設：①工件順序約束。每個作業都需要按照預定的工序順序在各個階段進行加工。在進入下一個階段之前，作業必須在當前階段完成。②工序不可中斷約束。一旦作業開始在某臺機器上加工，它必須連續進行，直到完成加工。工件在加工過程中不能被暫停或移動到另一臺機器上。③機器可用性約束。開始時，所有機器可用。在每個階段，作業可以在多臺機器中選擇一臺進行加工。機器在同一時間只能加工一個作業，即機器在加工期間不能被其他作業預占。④資源和運輸約束。在兩個階段之間的緩沖區容量無限，并且不考慮機器工件轉換時間和工件在兩階段之間的運輸時間。

1.2 析取圖模型

析取圖模型（disjunctive graph model）是HFSP的一種重要的表現形式。它將工件、加工階段和機器之間的關系表示為有向圖，使得問題可以通過圖論算法進行求解。HFSP的析取圖模型為G=（N，A，E），圖1為某個3工件3階段HFSP實例的具體析取圖，其中第2階段含有兩臺并行機，其余階段只含有一臺機器。N為作業節點（job nodes），表示各個工件在各個加工階段的加工任務。另有兩個虛設的開始和結束節點Obeg和Oend來表示調度的開始和結束。例如圖1中的N={Obeg，O11，O12，O13，O21，O22，O23，O31，O32，O33，Oend }。A 為連接弧（conjunctive arcs），用于將相鄰階段的同一工件的作業節點連接起來，表示同一產品的不同工序或者不同產品之間的工序順序。這些工序必須按照特定的順序進行，表示工序間的依賴關系。圖1中A={（Obeg，O11），（Obeg，O21），（Obeg，O31），（O11，O12），（O21，O22），（O31，O32），（O12，O13），（O22，O23），（O32，O33），（O13，Oend），（O23，Oend），（O33，Oend）}，弧長為工序在機器上的加工時間。E為析取弧（disjunctive arcs），用于將同一階段的同一臺機器上的不同工件作業節點連接起來。在相同加工階段，由于機器資源的有限性，析取弧之間存在時間和資源上的競爭關系，同一臺機器不能同時加工多個工件。圖1中E={（O11，O21），（O21，O31），（O31，O11），（O12，O22），（O22，O32），（O32，O12），（O13，O23），（O23，O33），（O33，O13）}。需要注意的是，該集合僅列出階段中某一個機器的析取弧，在HFSP中各個階段有并行機，這些并行機的析取弧相同，弧長根據方向為指出工序在機器上的加工時間。

通過構建HFSP的析取圖模型，可以將問題轉化為在圖上尋找一種調度方案，使得目標函數最小化完工時間最優。這種模型通常與關鍵路徑方法（critical path method，CPM）相結合來求解調度問題。關鍵路徑是指在析取圖中從Obeg到Oend的最長路徑，在關鍵路徑上的工序為關鍵工序，關鍵塊是指同一臺機器上相鄰的一系列關鍵工序［21］。

2 改進Jaya算法

2.1 算法流程

Jaya算法的核心概念是一個解應該盡可能地接近最好的解，同時遠離最差的解。這導致了算法的兩個主要操作步驟：向最優解靠攏和遠離最差解。這些步驟通過迭代過程進行，每一次迭代都會更新候選解集。Jaya算法流程可以概括為以下步驟：①初始化；②評估；③更新；④選擇；⑤檢查。Jaya初始的設計是為了求解連續優化問題，在此基礎上的更新公式為

Xnewi，j=Xi，j+r1（Xbest，j-|Xi，j|）-

r2（Xwst，j-|Xi，j|）（1）

其中，Xi，j 是第i個解的第j個參數變量，Xbest，j、Xwst，j分別是當前最優解、當前最差解的第j個參數。上式中r1（Xbest，j-|Xi，j|）表示當前解朝著最優解的方向移動，r2（Xwst，j-|Xi，j|）表示當前解朝著遠離最差解的方向移動。r1和r2是［0，1］范圍內的隨機數，給算法引入隨機性，幫助跳出局部最優和增強全局搜索能力。在每一次迭代中，算法都會試圖更新解，如果生成的新解比原始個體更優，則會替換掉原始個體；否則保持原始個體不變，然后對下一個個體進行Jaya迭代，直到遍歷完所有個體。然而HFSP是一個離散問題，不能直接采用傳統Jaya的迭代方式，如果將Jaya算法應用于求解HFSP問題，則必須對其進行離散化操作。

本文提出一種改進Jaya算法求解HFSP問題。由于Jaya算法依賴于當前種群中的最佳解和最差解進行更新，故它可能在長時間的迭代中逐漸喪失種群的多樣性，導致過早收斂。與其他進化算法一樣，Jaya算法也需要平衡探索新解與利用當前已知的優解之間的關系。Jaya算法在某些情況下更偏向利用當前已知優解，這可能導致其陷入局部最優。基于此特性，本文引入路徑重連進行Jaya算法迭代的離散更新，建立當前解與最優解和最差解的路徑，該方法可能會找到原本通過傳統Jaya更新策略無法直接達到的解。根據計算個體之間的相似度和適應度來選出候選解集，再通過禁忌搜索算法對解空間進一步深度探索。這種混合策略的好處是：Jaya算法提供了一種高效的全局搜索策略。路徑重連有助于加強種群的多樣性，并能幫助算法跳出局部最優解。禁忌搜索提供了一種強大的局部搜索策略，可以在局部區域內深入探索，并利用禁忌列表避免重復搜索。本文提出的改進Jaya算法流程如圖2所示。

2.2 編碼方式

在元啟發式算法中，編碼方式的選擇和設計對算法的性能有著至關重要的影響。編碼方式直接決定了解空間的大小，合理的編碼方式應該準確且有效地表示問題的所有潛在解。以往求解混合流水車間調度問題大都采用基于排列的單階段編碼方式，這種編碼方式搜索效率較高，但是無法表示出全部的半主動調度的解。因此，這種編碼方式求得的結果質量高度依賴于解碼方式，并且有可能會錯失優解［18］。對此，本文提出用一種基于機器的全階段編碼方式來表示HFSP的求解方案。

該種編碼方式的具體形式為各個階段每臺機器上所有工序的加工順序，每個求解方案個體包括m條子序列，分別對應m臺機器，子序列中的順序為工序在機器上加工的順序。因為HFSP中每個工件需要流經每個階段，所以各個階段的所有機器序列應包含所有的工序，此編碼方式對應的解的空間［22］為∏stagei=1（n+mi-1）！/（mi-1）！，其中stage代表階段數，mi表示第i個階段包含的機器數。該編碼方式能夠有效地表示求解空間中所有的半主動調度解，且無需解碼過程，能避免解碼的復雜計算，同時避免了因解碼策略而導致的解質量損失［18］。

2.3 種群初始化

初始化種群在算法中扮演著至關重要的角色，它直接影響到算法的整體性能。這個階段主要是為算法引入多樣性，具有高度多樣性的初始種群可以更廣泛地覆蓋搜索空間，從而增大找到全局最優解的幾率。一個好的初始種群應該包含一些接近最優解的個體，可以加速算法的收斂過程，提高搜索效率。設計初始化策略時，平衡種群多樣性與個體解的質量是關鍵。在以往的研究中，初始化方法都是基于排列編碼設計的，對于本文設計采用的全階段編碼并不適用，由于HFSP的特性，后一階段的開始依賴于前一階段的狀態，排列編碼代表的解是全階段機器編碼的子集，因此本文通過將排列編碼結合機器選擇規則來進行全階段編碼的生成。采用四種啟發式算法（SPTB、NEHLPT（λ）、bLPTB、NEHbSPT（λ））來生成一半不同特征的高質量的排列編碼個體［7］。為了強化種群的多樣性，采取隨機策略來初始化其余個體，有利于增加種群內個體的差異，確保了種群的多樣性。通過將生成的排列編碼結合最先可用機器準則［23］進行全階段的編碼生成。

2.4 Jaya迭代更新

Jaya算法是一種優化算法，其核心在于迭代更新過程，這一過程對找到問題的最優解至關重要。由于HFSP需要處理離散變量，傳統Jaya算法的更新規則不再適用，需要設計特定的策略來更新離散變量。在最近的車間調度問題研究中，路徑重連（path relink）算法因能處理多種約束條件和較強的搜索能力而經常與其他算法相結合，用于解的尋優［13］。路徑重連特別適用于離散優化問題。在離散空間中，通過逐步從一個解轉移到另一個解，可以更自然地處理離散變量，而不需要復雜的連續到離散的映射。路徑重連通過在已知解之間創建路徑，提供了一種更系統的探索方法，這種策略有助于更全面地覆蓋解空間，可能會發現那些通過傳統迭代更新不易觸及的區域。因此，本文設計應用基于路徑重連的方式來進行Jaya的離散迭代更新。路徑重連的基本思想是在兩個解之間生成一條路徑，并沿著該路徑繼續搜索以查找更優的解。在此階段，會構建出當前解到最優解和最差解的兩條路徑。離散的變換操作主要包括工序的插入和交換，選取含有8工件的Xi中一個階段的編碼轉變到Xbest具體路徑構建的過程如圖3所示，首先將工件2從機器2上轉移插入機器1的工件4、5之間，然后交換機器2上的工件8和機器3上的工件1，最后交換機器3上的工件3、7。其他階段以此類推。

由于問題規模的擴大以及需要構建兩條路徑，可能會遇到搜索路徑過長的問題，路徑過長會導致算法的搜索范圍過于廣泛，從而增加搜索時間和計算復雜度。基于算法效率考慮，本文僅部分解會加入候選解集執行禁忌搜索，選擇方法如圖4所示，該方法借鑒于文獻［13］。首先選擇Xi經過α次工序交換后的解作為第一個解，然后每經過β次工序交換，選擇當前解為候選解直到當前解轉換為Xbest需要的工序交換次數小于α。這種選擇方法在Xwst路徑上同樣適用，但是在此階段，基于Jaya的思想，選擇的解集應該更加靠近當前最優解，遠離當前最差解，所以在選擇中，在Xbest路徑上的個體會有更大的可能性被選取，增大了個體的尋優概率。而為了保證種群整體的多樣性，在Xwst路徑上的個體仍有小概率會被選取。這種選擇方式可以很方便地通過控制參數α、β來實現。值得注意的是，如果在路徑上出現了超過目前最優解Xbest的個體，也會被添加到候選解集中進行進一步的局部搜索。

2.5 距離與相似度計算

應用路徑重連算法時，定義兩個解之間的距離是至關重要的。通過距離的定義，可以根據個體之間的距離來動態自適應地調整參數α、β，使得算法有著更強的魯棒性和適應性。兩個解之間的距離越短，其相似度就越高。但需要注意的是，過短的路徑可能會使算法的搜索范圍過窄，從而限制其搜索空間，而個體之間過高的相似度會使種群趨于相同，導致過早的收斂。針對HFSP每個工件流經每個階段的問題特性，而在全階段編碼中每個階段的工件號互不相同，本文將Kendall-Tau 距離（Kendall-Tau distance，KTD）擴展應用于兩個解之間的距離計算。KTD是序列之間差異的一種度量方式，用于比較兩個序列之間的相似程度，度量它們之間的距離。假設有兩個序列P和Q，長度為n，Kendall-Tau距離計算公式如下：

D（P，Q）=|{（i，j）|1≤ilt;j≤n，

（P（i）lt;P（j）∧Q（i）gt;Q（j））∨

（P（i）gt;P（j）∧Q（i）lt;Q（j））}|（2）

其中，P（i）表示序列P中第i個元素，Q（i）表示序列Q中第i個元素。逆序對指的是在一個序列中，某兩個元素的相對順序與另一個序列中它們的相對順序相反。上式中，|（i，j）|表示逆序對數量，即序列P和Q之間的距離。例如P={0，3，1，6，2，5，4}，Q={1，0，3，6，4，2，5}，兩個序列之間的逆序對為{0，1}，{3，1}，{2，4}，{5，4}，一共4對。定義相似度的具體計算方式如下：

S（P，Q）=1-2×D（P，Q）/（n（n-1））（3）

其中，n代表序列的元素個數，S（P，Q）為兩序列的相似度。經過公式轉化，相似度在［0，1］范圍內，便于控制不同規模問題的相似度分析。兩個序列完全一致時，相似度為1；兩個序列完全相反時，相似度為0。選擇候選集和更新種群時，會計算各個個體之間的相似度，如果相似度超過0.9，則選擇另外的個體加入種群。

2.6 禁忌搜索

為了提高算法的局部搜索能力，本算法采用禁忌搜索（tabu search，TS）進一步對候選集中個體解的質量進行優化。禁忌搜索是一種元啟發式搜索方法，廣泛用于解決復雜的離散優化問題。該方法利用局部搜索策略迅速找到較優解，并通過禁忌列表避免陷入局部最優。在搜索過程中，禁忌列表會記錄一段時間內搜索過的決策變量，以防止回到已搜索過的解。禁忌列表中包含禁忌解和禁忌屬性兩種元素，前者是已搜索過的解，后者是已交換過的決策變量。禁忌列表在算法中起到關鍵作用，它根據記錄的信息限制搜索方向，以避免陷入局部最優解，其長度對算法性能有著重要影響，需要針對不同問題進行適當的調整。

禁忌搜索的主要步驟包括初始化、鄰域搜索、禁忌及特赦準則判定和解的更新。初始化過程從前述的候選解開始，為算法提供起始搜索點；鄰域搜索過程通過特定方式生成新解，以擴展搜索空間；禁忌及特赦準則判定過程有助于確保搜索方向的合理性，當得到的新解優于當前最優解時滿足特赦準則，如果不滿足特赦準則，則在未被禁忌的解中選擇最優解；解的更新過程是將新解加入當前解集，更新禁忌表，不斷優化解的質量。禁忌搜索的優勢在于其出色的局部搜索性能和避免陷入局部最優解的能力，禁忌搜索具體流程如圖5所示。

鄰域結構通過對當前解進行微小擾動來生成相鄰解，在禁忌搜索中，它決定了從一個解轉移到另一個解的方法，因此它對搜索效率有直接影響。設計鄰域結構時，應去除不必要和不可行的移動，同時在不損害解質量的基礎上，使鄰域結構具有更強的約束性［24］。目前由于單階段編碼方式的限制性，HFSP以往的鄰域結構設計都是隨機選擇工件進行交換、插入等操作，但是不改變調度方案中的關鍵路徑就不可能縮短完工時間。同時有研究表明，交換關鍵工序塊內的相鄰工序不可能縮短最長完工時間，故大多數研究都是對關鍵塊中的塊首或塊尾進行操作的。

本算法采用的基于機器的全階段編碼能夠更好地適用于高效的基于關鍵路徑的編碼。為了提高鄰域結構移動的有效性，本文采用N7［24］鄰域用于改變作業排序，采用Nk［25］鄰域用于改變機器選擇。N7的具體操作如下：①如果工序u和v及JS［v］（ v的后續工件）都在關鍵路徑上，那么移動u至v之后或插入v至u之前；②如果工序u和v，及JP［u］（u的前續工件）都在關鍵路徑上，那么移動v至u之前或插入u至v之后。N7的這種設計是因為如果析取圖中存在一個循環路徑，將無法轉換成為一個可行解，可以防止有向循環的產生，保證產生的解都是可行解，提高了鄰域結構的搜索效率，詳細證明過程見文獻［24］。在車間調度中，如果O（i，j，k，p）表示工件i的工序j在機器k

上加工順序為p，假定四個工序為O1（i1，j1，k1，p1），O2（i2，j2，k1，p2），O3（i1，j3，k2，p3），O4（i2，j4，k2，p4），p1≠p2，p3≠p4，那么構成有向循環死鎖對的充要條件為j3lt;j1，j2lt;j4和p1lt;p2，p4lt;p3。而在混合流水車間調度中，如果在同一機器上加工，則工序編號相同，j3=j4，j1=j2與條件j3lt;j1，j2lt;j4沖突，所以不存在循環死鎖對。同時可從圖1中看出，HFSP析取圖中每個機器的析取弧都只在同一階段上下連接，并不存在前向或后向的析取弧，故圖1中的任何析取弧選擇方案都無法產生有向循環。綜上所述，可以不必對HFSP的N7鄰域結構的移動可行性有著過多的約束，Nk鄰域結構同理。修改N7的鄰域結構如下：嘗試選取所有關鍵塊內的工序移動至其塊首之前或塊尾之后，或將關鍵塊首工序或塊尾工序插入至塊內部。修改Nk的鄰域結構如下：從當前階段的機器中移除一個關鍵工序，并將其插入同階段另一個可用機器中。

3 實驗結果與分析

本文所提改進Jaya算法（以下記為IJA）以C++為編程語言，以Visual Studio 2019 為開發環境，在 Intel Core i7-7700HQ、內存為 8GB的筆記本計算機上運行。元啟發式算法參數設置直接影響算法的收斂速度、解的質量和算法的穩定性。本文通過正交試驗設定IJA的種群數目為50，路徑重連中對應的相關個體選擇的參數設定為α1=D（Xi，Xbest）/10，β1=max{D（Xi，Xbest）/6，2}，α2=D（Xi，Xwst）/5，β2=max{D（Xi， Xwst）/3，4}，禁忌搜索中禁忌表的長度為n，最大的迭代次數為100n。算法的終止條件為100代內不更新解或運行時間達到1 h。

為了驗證算法的有效性，首先選擇Carlier和Neron中24個經典較難測試集［26］與可有效求解HFSP的改進離散人工蜂群算法（improved discrete artificial bee colony algorithm， IDABC）［27］、之前刷新最優解的改進候鳥算法（improved migrating birds optimization algorithm， IMBO）［19］、最近的改進果蠅算法（improved fruit fly optimization algorithm， IFOA）［28］、改進灰狼算法（improved grey wolf optimization， IGWO）［10］、標準Jaya算法［15］為參考對照。測試集的名稱中“j”后面的數字表示工件數，第二個字母“c”后面的數字表示階段數，第三個字母和數字不唯一，用來表示并行機的布局方式及不同測試集。為了更好地衡量各種算法在不同數據集中的差距，定義偏差Deviation=（T1-T2）/T2，其中T1為該算法對此測試實例的最長完工時間（makespan），T2為目前該測試實例的下界。下界是該測試集的理論最低值，任何算法包括精確算法都無法在該測試集取得比下界更優的結果，各算法的具體結果見表1。

可以看出，在選擇的所有24個較難的測試集中，IJA算法與最近提出的IMBO、IFOA算法均獲得了18個實例的下界，而FF-IGWO及IDABC算法只得到17個實例的下界，標準Jaya算法只達到3個實例的下界。IJA算法能取得所有未到達下界的測試實例中目前的最優解。

使用IJA算法求解Fernandez-viagas測試集［29］，進一步驗證所提算法的有效性和優越性。該測試集提出于2019年，其中具體數據集“instancia_10_5_1”中第一個數字10代表工件的數量，第二個數字5代表階段數，第三個數字1代表數據集的編號，其他數據集以此類推。選取工件規模的范圍為{10，15，20}、階段數分別為{5，10，15，20}的數據集，對比作者給出各個數據集的上界值（upper bound，UB）進行驗證。在所選擇測試的120個數據集中，對比2019年4月公布的上界，IJA算法更新了其中的68個結果，并且在其他的測試集中，IJA算法都達到了作者公布的上界，驗證了所提算法的尋優能力，具體結果見表2。

為了進一步驗證IJA算法求解較大規模HFSP問題的優越性，在 LIAO等［9］提出的工件數為30的10個大規模標準數據集上進行測試，對比的算法為前述的IMBO、IDABC，之前刷新過最優解的迭代貪婪算法（iterative greedy algorithm，IGT）［30］，以及目前解決HFSP問題最優算法——綜合進化算法和禁忌搜索優勢的混合進化算法（hybrid evolutionary algorithm，HEA）［20］，具體求解結果見表3。表3給出了不同算法針對不同測試實例的平均相對誤差（mean relative error， MRE）， MRE為相對百分比偏差Deviation的平均值，用于衡量算法的整體性能。在表3的計算結果中，在10個大規模測試集中HEA、IGT、IMBO、IDABC分別有1個、3個、5個、4個實例的計算結果不如本文提出的IJA算法；MRE值分別為0.02、0.07、0.14、0.14，也不如本文提出的IJA算法。因此，對比其他算法，IJA算法得到的結果在5個算法中均為最優。由表3可以看出，其他算法在求解小規模問題時表現良好，算法的差異性不大，但是面對大規模問題時，其求解質量不及IJA算法。這是由于IJA算法在設計時兼顧了全局搜索和局部搜索的能力，通過路徑重連保證了種群的多樣性，擴大了迭代更新時能夠探索到的區域，同時采用的全階段編碼方式可以無需解碼及再編碼過程即可在禁忌搜索階段通過基于關鍵路徑的鄰域結構高效深入搜索解空間，增大了尋優概率。此外，IJA算法在實例j30c5e4中獲得完工時間為562的新最優解，這一結果在目前其他所有算法中是無法達到的。所提算法得到j30c5e4實例最優解的甘特圖見圖6。

4 結語

本文提出了一種改進Jaya算法用于求解混合流水車間調度問題。所提算法結合了Jaya算法和禁忌搜索各自的優勢，應用的編碼方式能夠避免以往算法解碼過程中的質量損失，基于路徑重連的離散更新迭代方式能夠探索到一些傳統更新機制難以找到的調度方案，相似度計算方式能更好地保持種群多樣性，提高了尋找到更好解的概率。基于關鍵路徑的鄰域結構能夠使局部搜索過程更加集中和高效，更好地探索解空間中具有潛在改進空間的區域。所提算法在不同工件規模和階段數的基準測試集上獲得了各實例的當前最優解，在經典大規模實例中獲得了新的最優解，所得到的結果質量優于目前文獻中其他算法。未來的研究可以考慮進一步探索這種改進Jaya算法在其他類型的調度問題上的應用，或者進一步開發有關多條關鍵路徑的鄰域結構，嘗試求得更優的解。

參考文獻：

［1］ 李穎俐， 李新宇， 高亮. 混合流水車間調度問題研究綜述［J］. 中國機械工程， 2020， 31（23）：2798-2813.

LI Yingli， LI Xinyu， GAO Liang. Review on Hybrid Flow Shop Scheduling Problems［J］. China Mechanical Engineering， 2020， 31（23）：2798-2813.

［2］ 張超勇. 基于自然啟發式算法的作業車間調度問題理論與應用研究［D］. 武漢：華中科技大學， 2007.

ZHANG Chaoyong. Research on the Shop Scheduling Problem with Naturally-inspired Heuristic Algorithms［D］. Wuhan：Huazhong University of Science and Technology， 2007.

［3］ RUIZ R， VZQUEZ-RODRGUEZ J A. The Hybrid Flow Shop Scheduling Problem［J］. European Journal of Operational Research， 2010， 205（1）：1-18.

［4］ MENG Leilei， ZHANG Chaoyong， SHAO Xinyu， et al. More MILP Models for Hybrid Flow Shop Scheduling Problem and Its Extended Problems［J］. International Journal of Production Research， 2020， 58（13）：3905-3930.

［5］ MISSAOUI A， RUIZ R. A Parameter-less Iterated Greedy Method for the Hybrid Flowshop Scheduling Problem with Setup Times and Due Date Windows［J］. European Journal of Operational Research， 2022， 303（1）：99-113.

［6］ 鄭堃， 練志偉， 顧新艷， 等. 采用改進兩點交叉算子的改進自適應遺傳算法求解不相關并行機混合流水車間調度問題［J］. 中國機械工程， 2023， 34（14）：1647-1658.

ZHENG Kun， LIAN Zhiwei， GU Xinyan， et al. Hybrid Flow Shop Scheduling Problems with Unrelated Parallel Machine Solved by Improved Adaptive Genetic Algorithm（IAGA） with ITPX［J］. China Mechanical Engineering， 2023， 34（14）：1647-1658.

［7］ PAN Quanke， WANG Ling， LI Junqing， et al. A Novel Discrete Artificial Bee Colony Algorithm for the Hybrid Flowshop Scheduling Problem with Makespan Minimisation［J］. Omega， 2014， 45：42-56.

［8］ 張源， 陶翼飛， 王加冕. 改進差分進化算法求解混合流水車間調度問題［J］. 中國機械工程， 2021， 32（6）：714-720.

ZHANG Yuan， TAO Yifei， WANG Jiamian. An Improved DE Algorithm for Solving Hybrid Flow-shop Scheduling Problems［J］. China Mechanical Engineering， 2021， 32（6）：714-720.

［9］ LIAO C J， TJANDRADJAJA E， CHUNG T P. An Approach Using Particle Swarm Optimization and Bottleneck Heuristic to Solve Hybrid Flow Shop Scheduling Problem［J］. Applied Soft Computing Journal， 2012， 12（6）：1755-1764.

［10］ 時維國， 宋存利. 求解混合流水車間調度問題的改進灰狼算法［J］. 計算機集成制造系統， 2021， 27（11）：3196-3208.

SHI Weiguo， SONG Cunli. Improved Grey Wolf Optimization for Solving Hybrid Flow Shop Scheduling Problem［J］. Computer Integrated Manufacturing Systems， 2021， 27（11）：3196-3208.

［11］ 杜利珍， 王震， 柯善富， 等. 混合流水車間調度問題的果蠅優化算法求解［J］. 中國機械工程， 2019， 30（12）：1480-1485.

DU Lizhen， WANG Zhen， KE Shanfu， et al. Fruit Fly Optimization Algorithm for Solving Hybrid Flow-shop Scheduling Problems［J］. China Mechanical Engineering， 2019， 30（12）：1480-1485.

［12］ WANG Shijin， LIU Ming. Two-stage Hybrid Flow Shop Scheduling with Preventive Maintenance Using Multi-objective Tabu Search Method［J］. International Journal of Production Research， 2014， 52（5）：1495-1508.

［13］ PENG Bo， LYU Zhipeng， CHENG T C E. A Tabu Search/Path Relinking Algorithm to Solve the Job Shop Scheduling Problem［J］. Computers amp; Operations Research， 2015， 53：154-164.

［14］ RAO R V. Jaya：a Simple and New Optimization Algorithm for Solving Constrained and Unconstrained Optimization Problems［J］. International Journal of Industrial Engineering Computations， 2016：19-34.

［15］ BUDDALA R， MAHAPATRA S S. Improved Teaching-Learning-based and JAYA Optimization Algorithms for Solving Flexible Flow Shop Scheduling Problems［J］. Journal of Industrial Engineering International， 2018， 14（3）：555-570.

［16］ 連裕翔， 張超勇， 孟磊磊， 等. 基于改進Jaya算法的柔性作業車間調度問題［J］. 計算機集成制造系統， 2021， 27（11）：3172-3184.

LIAN Yuxiang， ZHANG Chaoyong， MENG Leilei， et al. Improved Jaya Algorithm and Tabu Search for Flexile Job Shop Scheduling Problem［J］. Computer Integrated Manufacturing Systems， 2021， 27（11）：3172-3184.

［17］ AMIRTEIMOORI A， MAHDAVI I， SOLIMANPUR M， et al. A Parallel Hybrid PSO-GA Algorithm for the Flexible Flow-shop Scheduling with Transportation［J］. Computers amp; Industrial Engineering， 2022， 173：108672.

［18］ FERNANDEZ-VIAGAS V， PEREZ-GONZALEZ P， FRAMINAN J M. Efficiency of the Solution Representations for the Hybrid Flow Shop Scheduling Problem with Makespan Objective［J］. Computers amp; Operations Research， 2019， 109：77-88.

［19］ 任彩樂， 張超勇， 孟磊磊， 等. 基于改進候鳥優化算法的混合流水車間調度問題［J］. 計算機集成制造系統， 2019， 25（3）：643-653.

REN Caile， ZHANG Chaoyong， MENG Leilei， et al. Hybrid Flow-shop Scheduling Problems Based on Improved Migrating Birds Optimization Algorithm［J］. Computer Integrated Manufacturing Systems， 2019， 25（3）：643-653.

［20］ FAN Jiaxin， LI Yingli， XIE Jin， et al. A Hybrid Evolutionary Algorithm Using Two Solution Representations for Hybrid Flow-shop Scheduling Problem［J］. IEEE Transactions on Cybernetics， 2023， 53（3）：1752-1764.

［21］ FERNANDEZ-VIAGAS V. A Speed-up Procedure for the Hybrid Flow Shop Scheduling Problem［J］. Expert Systems with Applications， 2022， 187：115903.

［22］ URLINGS T， RUIZ R， STTZLE T. Shifting Representation Search for Hybrid Flexible Flowline Problems［J］. European Journal of Operational Research， 2010， 207（2）：1086-1095.

［23］ GUINET A， SOLOMON M M， KEDIA P K， et al. A Computational Study of Heuristics for Two-stage Flexible Flowshops［J］. International Journal of Production Research， 1996， 34（5）：1399-1415.

［24］ ZHANG Chaoyong， LI Peigen， GUAN Zailin， et al. A Tabu Search Algorithm with a New Neighborhood Structure for the Job Shop Scheduling Problem［J］. Computers amp; Operations Research， 2007， 34（11）：3229-3242.

［25］ MASTROLILLI M， GAMBARDELLA L M. Effective Neighbourhood Functions for the Flexible Job Shop Problem［J］. Journal of Scheduling， 2000， 3（1）：3-20.

［26］ CARLIER J， NERON E. An Exact Method for Solving the Multi-processor Flow-shop［J］. RAIRO-Operations Research， 2000， 34（1）：1-25.

［27］ CUI Zhe， GU Xingsheng. An Improved Discrete Artificial Bee Colony Algorithm to Minimize the Makespan on Hybrid Flow Shop Problems［J］. Neurocomputing， 2015， 148：248-259.

［28］ 周永強， 王翠雨， 李穎俐， 等. 改進果蠅算法求解混合流水車間調度問題［J］. 控制理論與應用， 2023， 40（4）：597-606.

ZHOU Yongqiang， WANG Cuiyu， LI Yingli， et al. Improved Fruit Fly Optimization Algorithm for Solving the Hybrid Flow Shop Scheduling Problem［J］. Control Theory amp; Applications， 2023， 40（4）：597-606.

［29］ FERNANDEZ-VIAGAS V， FRAMINAN J M. Design of a Testbed for Hybrid Flow Shop Scheduling with Identical Machines［J］. Computers amp; Industrial Engineering， 2020， 141：106288.

［30］ ZTOP H， TASGETIREN M， ELIIYI D， et al. Metaheuristic Algorithms for the Hybrid Flowshop Scheduling Problem［J］. Computers amp; Operations Research， 2019， 111：177-196.

（編輯 陳 勇）