無等待流水調度量子候鳥協同優化算法

陳林烽 王永錄 楊浩 黃重春 汪峰坤 鄧春紅

摘要：文章提出了一種新穎的量子候鳥協同優化（CQMB） 算法，求解無等待流水調度問題（NWFSP）最小化最大完工時間。算法首先采用量子雙鏈編碼方案擴大解空間；全局使用候鳥優化 （MBO）算法進行迭代并與量子旋轉門相結合，實現較差個體的改進以及劣勢個體與優勢個體之間的信息交換，從而提高解的質量；采用變鄰域搜索（VNS）策略加速種群收斂并跳出局部最優；測試了基準實例Ta001-Ta090，將CQMB與目前較優算法DWWO比較，DWWO獲得較優解的個數為57，而CQMB則為75個。實驗結果證明了所提算法具有較強的優化能力，能夠有效地求解中小規模無等待流水調度問題。

關鍵詞：無等待流水調度；候鳥優化算法；量子旋轉門；最大完工時間；變鄰域搜索

中圖分類號：TP301.16? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2023）31-0009-05

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

0 引言

無等待流水調度問題（No-wait flow-shop scheduling problem， NWFSP） 是一類重要組合優化問題，廣泛存在于煉鋼、食品加工、化工制造等工業領域[1]。由于在調度過程中，工件加工受到設備、工藝等約束，一旦開始加工就不能中斷，直至最后所有加工操作全部完成才得以結束，因此當加工機器m≥3時，NWFSP被證明是一類NP-hard問題[2]。

近年來，許多研究學者將智能優化算法用于求解NWFSP。W. Bozejko等[3]以makespan為目標設計了自我調整混合遺傳算法（Hybrid Genetic Algorithm， HGA），實驗結果證明HGA算法在求解質量上優于TS（Tabu Search），GASA（Genetic Algorithm and Simulated Annealing Algorithm）算法。D Davendra等[4]針對makespan提出了一種具有自我組織的離散遷徙算法（Discrete Migrating Algorithm，DMA），利用Taillard基準測試實例[5]仿真，實驗結果表明DMA的高效性。朱海紅等[6]以makespan為指標采用了新穎的量子布谷鳥協同搜索算法（Quantum-inspired Cuckoo Co-search Algorithm， QCCS），并利用基準測試實例Rec仿真，結果證明QCCS算法在求解質量上均優于GA-VNS（Genetic Algorithm and Variable Neighborhood Search），HGA，TS-PSO，TMIIG（Tabu-Mechanism Improved Iterated Greedy）算法。Fuqing Zhao等[7]以makespan為指標采用了新穎的離散水紋優化算法（Discrete Water Wave Optimization，DWWO），通過與TMIIG，IIGA（Improved Iterated Greedy Algorithm），DPSOVND相比可知該算法在中小規模數據集Rec與Ta上取得較優解。

以上算法在求解NWFSP上的成功應用，顯示了啟發式算法和智能優化算法的優越性。但目前的研究大多基于單一算法，對智能混合優化算法的研究相對較少。量子進化算法（Quantum-inspired Evolutionary Algorithm， QEA）作為新興智能優化算法，近年來在工程領域掀起了一股熱潮[8]。候鳥優化（Migrating Birds Optimization， MBO）算法[9]是一種基于鄰域搜索技術的算法，優化思想簡單、收斂速度快、較優魯棒性，在實際應用中已被證明是一種有效的優化方法。

MBO算法目前主要用于求解連續空間優化問題，對于NWFSP這類組合優化問題只有較少的研究。為彌補這一缺陷，本文提出了一種量子候鳥協同優化（Co-optimizate Quantum-inspired Migrating Birds， CQMB）算法嘗試求解無等待流水調度中最小化最大完工時間問題。算法采用量子雙鏈編碼方案，并使用FL[10]算法產生初始解。引入量子旋轉門的概念，即根據當前最優解變化自適應調整旋轉角，增加種群多樣性，進一步提高解的質量。全局使用MBO算法進行種群迭代，利用量子旋轉門，實現劣勢個體的自我改進以及劣勢個體與優勢個體的信息交換，同時引入VNS（Variable Neighborhood Search）[11]算法進一步提高算法的局部搜索能力。本文采用基準測試實例進行實驗仿真并與目前較優的智能優化算法作比較，實驗結果表明所提算法可以很好地解決組合優化NWFSP，尤其在中小規模下求解最小化最大完工時間問題優化效果顯著。

1 問題描述

NWFSP可描述為：n個工件在m臺機器上加工，每個工件加工順序和時間給定，要求連續加工，即一旦開始加工便不能被中斷；且每個工件只允許被一臺機器加工，每臺機器只加工一個工件。本文優化目標是求出n個工件的一個加工順序，使其最大完工時間最小，該問題記為Fm|nwt|Cmax。數學模型如下：

設工件數為{1，2，...，n}和機器數為{1，2，...，m}，Pu，v為工件u在機器v上的加工時間，u?{1，2，...，n}，v?{1，2，...，m}；Ck，i為機器i上第k個工件的完工時間，k?{1，2，...，n}；π為工件按照一定加工次序形成的序列，π={[π1，π2，...，πk]}，[k=2，...，n] 。由于受到工件加工過程無等待的約束，相鄰的工件[πk-1]和[πk]之間存在一個開工時間差，記為[Dπk-1，πk]，其計算公式[10]為：

[Dπk-1，πk=max1≤i≤mj=1iPπk-1，j-j=2iPπk，j-1 ，]

[? ? ? ? ?k= 2，...，n? ? ? ? ? ? ? ? ? ? ? ]? ? （1）

則最大完工時間Cmax（π）為：

[Cmax（π）=k=2nDπk-1，πk+j=1mPπn，j]? ? ? ? （2）

圖1為3個工件在3臺機器上的Fm|nwt|Cmax調度甘特圖。

2 量子候鳥協同優化算法（CQMB）

CQMB算法采用候鳥優化算法對種群進行迭代，設計了量子編碼、量子旋轉門方案，用于優化NWFSP。其基本思想是：首先采用量子雙鏈編碼候鳥種群并使用FL算法及VNS 算法產生初始解，在迭代過程中應用候鳥優化算法產生初始候鳥群體，模仿其遷徙過程中V形編隊排列，隨后進行領飛鳥進化及跟飛鳥進化并采用量子旋轉角更新種群，迭代此過程直至滿足停止條件。算法基本框架如圖2所示。

2.1 量子雙鏈編碼和解碼

流水調度問題中的解為所有可能形式的作業排列，量子個體中的每個量子位可代表一個作業，且[φ]的概率符用量子角形式表示，即：

[φ=[α，β]T=[cos（θ），sin（θ）]T]? ? ? ? ? ?（3）

因此，量子比特可以由圓上的一點[P（cos（θ），sin（θ））] 描述，如圖3所示。長度為n的量子個體q由n個量子位組成，應用至此環境中q即為種群個體，可描述為：

[q=cos（θ1）sin（θ1）cos（θ2）sin（θ2）……cosθnsinθn]? ? ? （4）

群體初始化時，量子角[θj] （1≤j≤n）在[0，2π]內隨機生成。量子個體的解碼過程如下：令q的第j個量子位的概率幅[αj]表示為當前調度序列第j個作業在區間[0，1]的映射值，相應產生[α1，α2，...，αn]解向量，采用LOV（largest-order-value）規則[10]生成一組調度作業[π1，π2，...，πn]。

2.2 算法描述

為了解決Fm|nwt|Cmax問題，采用量子雙鏈編碼方案，候鳥優化算法，變鄰域搜索算法和量子旋轉門策略。具體描述如下：

步驟1：初始化各參數，包括種群大小[ps]，最大迭代次數[imax]，鄰域大小[Cnum]，分享鄰域大小[Snum]，巡回次數K，數組Lp[[]]、Rp[[]]、[Sn_L[]]和[Sn_R[]]等。

步驟2：初始化種群，隨機生成[ps]個個體[{x1，x2，...，xps}]。

步驟3：執行量子編碼種群[{x1，x2，...，xps}←Encoding（）]，生成ps個調度序列π，調用Min函數生成初始解π'。

步驟4：對[初始解π']執行變異的FL算法及VNS算法進行優化。

步驟5：令[i=1，2，...，imax]，開始進入循環操作。

步驟6：[令j=1，2，...，K]，開始進入循環操作。

步驟7：令經過步驟4優化后的初始解[π'']為領飛鳥的解，并用IG算法生成領飛鳥的[Cnum]個鄰域解[LBc]，其中，[LBc[]=N1，N2，...NCnum，Nbest=Min{N1，N2，...，NCnum}]。

步驟8：將[Nbest]與[領飛鳥的解π']比較目標值[Cmax，]若小則替換。

步驟9：將[LBc[]]中未被使用的[Cmax]最佳的[2Snum]個鄰域解隨機填入[Sn_L[]]和[Sn_R[]]，使得兩個數組都包含[Snum]個解。

步驟10：對于[m=1，2，...，（ps-1）/2]，進行左邊跟飛鳥的優化。

步驟11：隨機使用[Swap（）]和[Insert（）]的方法生成[Lp[m]]的[Cnum-Snum]個鄰域解，然后和[Sn_L[]]合并構成[Lp[m]]的鄰域解集合[FBc[m]]。[令Nbest=Min（Cmax（FBc[]））]，若[Cmax]（[Nbest]） < [CmaxLpm，] 則將[Nbest賦值給Lp[m]]，并將[FBc[]]中未被使用的[Cmax]最佳的[Snum]個鄰域解填入[Sn_L[]]。

步驟12：對于m = [1，2，...，（ps-1）/2]，進行右邊跟飛鳥的優化。

步驟13：隨機使用[Swap（）]和[Insert（）]的方法生成[Rp[m]]的[Cnum-Snum]個鄰域解，然后和[Sn_R[]]合并構成[Rp[m]]的鄰域解集合[FBc[m]]。[令Nbest=Min（Cmax（FBc[]））]，若[Cmax]（[Nbest]） < [CmaxRpm] 則將[Nbest賦值給Rp[m]]，并將[FBc[]]中未被使用的[Cmax]最佳的[Snum]個鄰域解填入[Sn_R[]]。

步驟14：循環至K次進行步驟15操作，否則返回步驟6。

步驟15：將左右兩翼的第一個解[Lp[1]]和[Rp[1]]相比較，其目標值將較小者作為領飛鳥，舊的領飛鳥自動回至所在翼的尾部。

步驟16：對當前解執行[VNS]優化，增強局部搜索能力，并通過根據當前最優解變化自適應調整旋轉角[Δθ]，若更優則替換領飛鳥的解。

步驟17：輸出最優解及對應的工件加工序列。

步驟18：循環至[imax]時算法結束，否則返回步驟[5]進行迭代。

CQMB算法的時間開銷主要集中在步驟4、5、16優化階段，步驟4、16的時間復雜度為O（mn4），步驟5的時間復雜度為O（[imax]），若每次運行k次，則CQMB時間復雜度為O（km[imaxn]4）。

3 仿真實驗與算法性能評價

3.1 參數設置

本文所提出算法是針對Fm|nwt|Cmax問題，采用基準測試實例Rec、Car與Ta進行性能評估。按問題規模Car數據集11×5到8×8的8組，每組1個實例；Rec數據集20×5到75×20的7組，每組3個實例；Ta數據集20×5到100×20的9組，每組10個實例；每個實例重復計算30次。算法采用Visual Studio實現，在CPU 2.83GHz、RAM 4GB的PC機上運行。設置工件數n，m為機器數。其他參數各數值采用正交實驗設計方法，表1是每個參數因素及其對應的水平值。

其中imax表示最大迭代次數，ps是種群大小，Cnum、Snum、K和d分別表示鄰域大小、分享鄰域大小、巡回次數和IG算法中序列的刪減個數。

從表1的5因素3水平表可知，正交表可安排18組試驗，即L18（37），將最后兩列設置為空置列，如表2所示。以50×10中一個實例為實驗數據，采用Taguchi實驗[12]方法，計算每組實驗的信噪比（S/N ratio）。實驗結果分析時， S/N ratio值的計算能夠很好地保護目標函數值。在大多數情況下，每個水平對應的目標函數值互相都非常接近，因此S/N ratio的影響非常重要。S/N ratio 計算公式如下：

[SN ratio=-10log10f（S）2]? ? ? ? ? ?（7）

其中，f（S）是目標函數值，即最大完工時間，圖4為各因素水平與平均S/N ratio關系圖。

在CQMB算法中，S/N ratio取較大值較好。由圖4可得，（imax， ps）、Cnum、Snum、K 和d分別在水平1、1、3、3、3值較大，因此可得出參數imax =90、ps=71、Cnum=3、Snum=1、K=8、d=8。

3.2 性能比較

Ta數據集上的性能測試。為了更加全面地體現算法尋優能力，采用基準測試實例Ta數據集測試，并與當前較優算法DWWO比較，比較結果如表3所示。由表3可以看出，在n=20、m=5、10和20時，本文算法與DWWO算法全部達到最優。在n=50、100，m=5時，除Ta70與DWWO優化結果相同外，所提算法均優于DWWO算法；在n=50、100，m=10時，CQMB達到較優解的個數為15，而DWWO僅有10個。在n=50、m=20時，CQMB得到10個較優解，而DWWO僅有6個。在n=100、m=20時，所提算法優化效果不是特別明顯。從算法總體求解質量看，在中小規模問題中本文所提算法優于所比較的算法。

以Ta044為例，本文算法求解得到的最小完工時間為4 399，而DWWO算法卻為4 407。得到最優解的序列為：{20，10，19，9，44，29，46，34，13，28，5，8，22，17，14，25，12，26，45，41，38，36，35，30，21，1，37，2，11，6，49，15，47，43，24，50，32，4，23，18，40，16，39，31，48，3，27，7，33，42}，括號中的數字代表工件的序號，該序列代表了工件的加工順序。

為了體現算法的收斂性，圖5給出了算法求解Ta044實例的收斂曲線，由圖5可以看出，算法在最初具有很快的收斂速度，但隨著迭代次數的增加，算法的收斂性變緩，甚至出現局部收斂，但算法具有跳出局部最優的能力最終得到較好的解。

4 結論

本文針對Fm|nwt|Cmax問題提出了一種新穎高效的CQMB算法。該算法模擬候鳥遷徙與跟飛鳥替換領飛鳥過程，智能達到一種高效的尋優模式；算法采用量子雙鏈編碼方案擴大解空間，并引入量子旋轉門對當前最優解變化自適應調整旋轉角，增加種群多樣性，進一步提高解的質量并使用變鄰域算法（VNS） 加速種群收斂并跳出局部最優。通過選取不同規模Benchmark問題算例測試，并與目前較優的幾種算法相比較。結果表明，所提算法在求解中小規模Fm|nwt|Cmax問題均優于其他算法。

參考文獻：

[1] 張梓琪，錢斌，胡蓉.混合交叉熵算法求解復雜零等待流水線調度問題[J].控制理論與應用， 2021， 38（12）：16.

[2] 鄭堃，練志偉，王玉國，等.改進激素算法求解置換流水車間調度問題[J].電子科技大學學報，2022，51（6）：890-903.

[3] BO?EJKO W，Makuchowski M.Solving the no-wait job-shop problem by using genetic algorithm with automatic adjustment[J].The International Journal of Advanced Manufacturing Technology，2011，57（5/6/7/8）：735-752.

[4] DAVENDRA D，ZELINKA I，BIALIC-DAVENDRA M，et al.Discrete self-organising migrating algorithm for flow-shop scheduling with no-wait makespan[J].Mathematical and Computer Modelling，2013，57（1/2）：100-110.

[5] TAILLARD E.Benchmarks for basic scheduling problems[J].European Journal of Operational Research，1993，64（2）：278-285.

[6] ZHU H H，QI X M，CHEN F L，et al.Quantum-inspired cuckoo co-search algorithm for no-wait flow shop scheduling[J].Applied Intelligence，2019，49（2）：791-803.

[7] ZHAO F Q，LIU H A，ZHANG Y，et al.A discrete Water Wave Optimization algorithm for no-wait flow shop scheduling problem[J].Expert Systems With Applications，2018（91）：347-363.

[8] 錢潔，鄭建國，張超群，等.量子進化算法研究現狀綜述[J].控制與決策，2011，26（3）：321-326，331.

[9] DUMAN E，UYSAL M，ALKAYA A F.Migrating Birds Optimization：a new metaheuristic approach and its performance on quadratic assignment problem[J].Information Sciences，2012（217）：65-77.

[10] FRAMINAN J M，LEISTEN R.An efficient constructive heuristic for flowtime minimisation in permutation flow shops[J].Omega，2003，31（4）：311-317.

[11] MLADENOVI? N，TODOSIJEVI? R，URO?EVI? D，et al.Solving the Capacitated Dispersion Problem with variable neighborhood search approaches：from basic to skewed VNS[J].Computers & Operations Research，2022（139）：105622.

[12] DAO T P，HUANG S C，THANG P T.Hybrid Taguchi-cuckoo search algorithm for optimization of a compliant focus positioning platform[J].Applied Soft Computing，2017（57）：526-538.

【通聯編輯：唐一東】