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

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

關(guān)鍵詞：無等待流水調(diào)度；候鳥優(yōu)化算法；量子旋轉(zhuǎn)門；最大完工時間；變鄰域搜索

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

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

開放科學（資源服務(wù)）標識碼（OSID）

0 引言

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

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

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

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

1 問題描述

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

設(shè)工件數(shù)為{1，2，...，n}和機器數(shù)為{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調(diào)度甘特圖。

2 量子候鳥協(xié)同優(yōu)化算法（CQMB）

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

2.1 量子雙鏈編碼和解碼

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

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

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

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

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

2.2 算法描述

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

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

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

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

步驟4：對[初始解π']執(zhí)行變異的FL算法及VNS算法進行優(yōu)化。

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

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

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

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

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

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

步驟11：隨機使用[Swap（）]和[Insert（）]的方法生成[Lp[m]]的[Cnum-Snum]個鄰域解，然后和[Sn_L[]]合并構(gòu)成[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]，進行右邊跟飛鳥的優(yōu)化。

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

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

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

步驟16：對當前解執(zhí)行[VNS]優(yōu)化，增強局部搜索能力，并通過根據(jù)當前最優(yōu)解變化自適應(yīng)調(diào)整旋轉(zhuǎn)角[Δθ]，若更優(yōu)則替換領(lǐng)飛鳥的解。

步驟17：輸出最優(yōu)解及對應(yīng)的工件加工序列。

步驟18：循環(huán)至[imax]時算法結(jié)束，否則返回步驟[5]進行迭代。

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

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

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

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

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

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

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

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

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

3.2 性能比較

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

以Ta044為例，本文算法求解得到的最小完工時間為4 399，而DWWO算法卻為4 407。得到最優(yōu)解的序列為：{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}，括號中的數(shù)字代表工件的序號，該序列代表了工件的加工順序。

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

4 結(jié)論

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

參考文獻：

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

[2] 鄭堃，練志偉，王玉國，等.改進激素算法求解置換流水車間調(diào)度問題[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] 錢潔，鄭建國，張超群，等.量子進化算法研究現(xiàn)狀綜述[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.

【通聯(lián)編輯：唐一東】