基于量子計算和威布爾分布的混合CHIO算法求解JSP 問題*

亓祥波 趙品威 王 潤

（沈陽大學(xué)機械工程學(xué)院，遼寧 沈陽 110044）

在制造業(yè)中，作業(yè)車間調(diào)度問題（job-shop scheduling problem，JSP）被證明是一種極具挑戰(zhàn)性的約束組合優(yōu)化問題，也是一個典型的NP-hard 問題。這類問題的特點是，無法找到一種有效的算法在多項式時間內(nèi)準(zhǔn)確地求解其最優(yōu)解[1]。它涉及如何合理地安排工作流程和資源分配，以最大化生產(chǎn)效率和利潤。隨著全球制造業(yè)的發(fā)展和競爭的加劇，對調(diào)度的優(yōu)化變得越來越重要，設(shè)計科學(xué)合理的調(diào)度方案可以提高生產(chǎn)效率和經(jīng)濟效益，因此，對調(diào)度優(yōu)化算法的研究成為調(diào)度領(lǐng)域研究熱點之一。

近年來，受自然界各種生物群體行為、物理現(xiàn)象和自然現(xiàn)象等啟發(fā)設(shè)計出來各種智能優(yōu)化算法，因其具有較強的全局搜索能力、自適應(yīng)性、魯棒性、并行計算能力以及易實現(xiàn)等優(yōu)點而被廣泛應(yīng)用于離散調(diào)度的問題求解中。劉麗娜等提出了一種改進(jìn)麻雀算法（ISSA）[2]，通過引入高斯變異擾動、正余弦搜索等策略提高了麻雀算法對離散調(diào)度問題的求解精度。為了解決狀態(tài)轉(zhuǎn)移算法在過分依賴初值、局部搜索能力差、收斂速度慢等方面存在的不足，吳貝貝等提出了一種量子狀態(tài)轉(zhuǎn)移算法（QSTA）[3]，該算法引入了量子旋轉(zhuǎn)門的思想，通過將最小化最大完工時間作為目標(biāo)函數(shù)來解決離散調(diào)度問題，最后通過試驗驗證了該算法能夠有效地求解離散調(diào)度問題。陳斌等提出了一種多策略引導(dǎo)的電磁場優(yōu)化算法（MGEFO）[4]，該算法通過引入了自適應(yīng)電磁移動系數(shù)，并采用不同的引導(dǎo)策略來動態(tài)調(diào)整粒子間的正電距離和負(fù)電距離，通過實驗結(jié)果驗證了該算法在解決離散調(diào)度問題方面的可行性。亓祥波等針對離散調(diào)度問題的特性提出了一種基于交叉選擇的變鄰域蜂群算法（VABC）[5]，增強了人工蜂群算法在離散調(diào)度問題上的搜索能力。

以上針對調(diào)度問題設(shè)計的改進(jìn)算法在一定程度上取得了成果，為進(jìn)一步研究提供了參考。然而，這些改進(jìn)算法大多是對較為傳統(tǒng)的優(yōu)化算法的改良和設(shè)計，很少嘗試使用新型智能優(yōu)化算法進(jìn)行對調(diào)度問題進(jìn)行求解。冠狀病毒群免疫優(yōu)化算法[6]是2020 年Al-Betar M A 等提出的一種新的元啟發(fā)式優(yōu)化算法，靈感來源于造成世界性傳播的新冠病毒，該算法模仿了群體免疫策略和社會距離概念，其基于3 種類型的個體病例用于群體免疫：易感、感染和免疫。每個易感人群與感染個體接觸而感染病毒，再通過個體是否免疫而更新引導(dǎo)群體免疫以達(dá)到算法收斂。

針對CHIO 后期搜索能力差、收斂精度低等缺點，已有不少學(xué)者對其進(jìn)行了改進(jìn)并應(yīng)用在不同實際問題上，例如路徑規(guī)劃[7]、醫(yī)療檢測[8]和設(shè)計優(yōu)化[9]等，但對于離散調(diào)度問題應(yīng)用相對較少。本文以CHIO 為基礎(chǔ)并對其進(jìn)行了改進(jìn)將其應(yīng)用到車間調(diào)度問題上，與其他幾種改進(jìn)的優(yōu)化算法進(jìn)行了仿真對比實驗，證明了算法在求解JSP 方面有較強的能力。最后，將提出算法應(yīng)用到發(fā)動機生產(chǎn)調(diào)度實例上，進(jìn)一步驗證了所提出算法的可行性和優(yōu)越性。

1 作業(yè)車間調(diào)度模型

1.1 JSP 問題的描述

JSP 問題可以理解為在具有特定工序的n個工件在m臺機器上進(jìn)行加工。每個工序的加工機器以及加工每道工序所需的時間都是已知的。調(diào)度的目標(biāo)是安排每臺機器上工件的加工順序，根據(jù)排序確定每個工序的開始和結(jié)束時間，以實現(xiàn)最小的完工時間。JSP 問題滿足以下假設(shè)：

①機器是獨立的。

② 加工準(zhǔn)備時間已被計入加工時間。

③所有機器從0 時刻開始可用。

④ 各工件加工的優(yōu)先級相同，同一工件不同工序之間存在先后約束。

⑤ 每道工序在同一時刻只能由一臺機器進(jìn)行加工。

⑥ 加工過程中沒有缺料或機器故障的情況。

1.2 作業(yè)車間調(diào)度的數(shù)學(xué)模型

本文使用整數(shù)規(guī)劃模型[10]對JSP 進(jìn)行描述，其模型如下：

其中：式（1）為最小化最大完工時間的目標(biāo)函數(shù)；式（2）為工藝約束；式（3）為機器約束；cik為工件i在機器k上的完成時間；pik為工件i在機器k上的加工時間；M是一個充分大的正數(shù)；xihk是指示系數(shù)，xijk是指示變量，其含義為

1.3 基于工序的編碼

選擇恰當(dāng)?shù)木幋a規(guī)則對于獲得優(yōu)秀的調(diào)度方案至關(guān)重要，尤其是在表示JSP 的解時。本文采用基于工序的編碼方式來實現(xiàn)這一目的。工序編碼由工件號組成，編碼的總長度等于任務(wù)的總加工工序數(shù)。在解碼過程中，按照從左到右的順序?qū)ば蚓幋a進(jìn)行安排加工。當(dāng)一個工件號第一次出現(xiàn)時，表示該工件正在進(jìn)行第一道工序的加工；當(dāng)同一個工件號第二次出現(xiàn)時，表示該工件正在進(jìn)行第二道工序的加工；以此類推，直到所有工序都被安排完成。以一個3×2 規(guī)模問題為例，具體見表1。

表1 編碼對應(yīng)規(guī)則

對離散變量除以機器總數(shù)向上取整，即得到基于工序的編碼[1,3,3,2,1,2]。

2 量子混合CHIO

2.1 標(biāo)準(zhǔn)CHIO 算法

在CHIO 算法中，有3 種類型的個體病例：易感、感染和免疫。傳播冠狀病毒的速度取決于感染者如何與其他社會成員直接接觸。群體免疫是當(dāng)大多數(shù)群體具有免疫力時，群體達(dá)到的一種狀態(tài)，這種狀態(tài)可以防止疾病的傳播。這些概念是根據(jù)優(yōu)化概念建模的，既模仿群體免疫策略，又模仿社會距離概念。CHIO 對群體免疫策略進(jìn)行了建模：在初始化種群HIP 后，隨機產(chǎn)生與HIS一樣多的一組病例（即個體）。生成的病例以二維矩陣n×HIS形式存儲，且每個個體均對應(yīng)一個狀態(tài)向量Si和年齡向量Aj，HIP 為

式中：HIS為種群個數(shù)；n為問題維度。

在算法迭代過程中，xi病例的j基因要么保持不變，要么受到社會距離的影響，其影響根據(jù)基本繁殖率BRr，取值為0.05，見式（8）。

式中：r表示(0,1)的隨機數(shù)；(t+1) 表示(t)更新后的基因值。

式中：r表示(0,1)的隨機數(shù)；(t)表示從易感個體中選擇的個體，此時m={i|Si=0}。

式中：r表示(0,1)的隨機數(shù)；(t)表示從免疫個體中選擇的最好的個體，此時v={i|Si=2}。

隨后更新群體免疫群體，計算新個體xi(t+1)的免疫率（即適應(yīng)度值），如果f(xi(t+1))>f(xi(t))，則xi(t+1) 取代xi(t)。且如果該個體為感染個體，則年齡向量Aj增加1。其中個體對應(yīng)狀態(tài)向量Si也隨著適應(yīng)度值改變，見式（12）。

式中：?f(x) 表示當(dāng)前種群的平均免疫率；is_Corona表示當(dāng)前個體是否繼承過感染個體基因。如果繼承過感染個體的基因、當(dāng)前個體為易感人群且免疫率小于平均免疫率，則該個體感染病毒，此時該個體的 Si=1；如果當(dāng)前個體免疫率大于平均免疫率且當(dāng)前個體為感染個體，則該個體為免疫個體，此時該個體的 Si=2。

最后，當(dāng)個體年齡大于最大年齡后，該個體將重置：

式中：ub、lb分別表示問題的上下界；rand表示(0,1)的隨機數(shù)。

2.2 QCHIO 算法

2.2.1 量子計算

由于CHIO 在求解JSP 時存在收斂精度低、尋優(yōu)能力差等缺點，因此將量子計算[11]的思想引入到CHIO 算法。其中單量子比特的疊加狀態(tài)為

在量子計算中，實現(xiàn)邏輯變換的基礎(chǔ)是量子邏輯門。這些門操作主要用于改變量子態(tài)的性質(zhì)。常見的幾種量子門包括Hadamard 門、相位門和量子旋轉(zhuǎn)門等。量子旋轉(zhuǎn)門表達(dá)式為

量子旋轉(zhuǎn)門的更新表達(dá)式如下：

在更新過程中對工序序列進(jìn)行量子優(yōu)化，則工序序列經(jīng)過單鏈編碼量子旋轉(zhuǎn)門變換后表達(dá)式為

式中：Qxi表示xi通過量子計算產(chǎn)生的新個體。

2.2.2 威布爾分布變異

威布爾分布又稱為韋伯分布、韋氏分布，是一種連續(xù)概率分布，一般用于工業(yè)制造、預(yù)測天氣、可靠性和失效分析、量化壽險模型的重復(fù)索賠等。其概率密度函數(shù)（probability density function，PDF）為

式中：A為尺度參數(shù)，表示函數(shù)的走勢；B為形狀參數(shù)，表示函數(shù)的形狀。圖1 表示尺度為A、形狀為B的威布爾分布的PDF。Sahoo S K 等[12]將威布爾分布算子應(yīng)用到飛蛾撲火算法上證實了其可以當(dāng)前位置搜索到有用的信息，因此將改進(jìn)威布爾分布算子引入CHIO 以增加算法的多樣性，通過改進(jìn)威布爾分布算子的大步長和小步長來平衡算法的局部搜索和全局開發(fā)能力，以增強算法的收斂精度。具體實現(xiàn)見式（21）～式（23）。

圖1 威布爾分布示意圖

式中：S TEP表 示大步長，step表 示小步長，sign(rand-0.5) 表示隨機取得的-1 或1 的向量，wbl(1,1)表示A、B均為1 時生成的威布爾分布的隨機數(shù)，norm為范數(shù)函數(shù)，j表示個體的第j維，xi表示第i個個體，xbest表示當(dāng)前種群中最優(yōu)個體，xnew表示xi生成的新個體。

2.2.3 β-登山局部搜索

登山（hill climbing，HC）算法是一種簡單的貪心鄰域搜索算法。該算法每次從當(dāng)前解的臨近解空間中選擇一個最優(yōu)解作為當(dāng)前解，直到達(dá)到一個局部最優(yōu)解。但其主要缺點是易陷入局部最優(yōu)解。為克服該缺點，Al-Betar M A 等提出了一種 β-登山算法[13]。在CHIO 中引入了 β-登山算子以平衡局部搜索和全局開發(fā)，從而提高CHIO 的收斂精度。具體實現(xiàn)見式（24）和式（25）。

式中：xj表 示當(dāng)前個體的第j維，j是從當(dāng)前個體 中隨機選擇的一個維度；r1表示(0,1)的隨機數(shù)；表示一個常數(shù)，取值為0.001。

式 中：xi表示當(dāng)前個體的第i維，lbj、ubj分別表示問題求解范圍的下界和上界在第j維的位置，r2和R均表示(0,1)的隨機數(shù)。最后采用貪婪選擇，如新個體的適應(yīng)度值大于原個體，則新個體取代原個體。

2.2.4 多鄰域搜索

在優(yōu)化算法中，鄰域搜索是一種通過使用鄰域函數(shù)來創(chuàng)建解的鄰域，并在鄰域中找到比當(dāng)前解更優(yōu)的解來進(jìn)行替換的方法。在本文中，經(jīng)過迭代過程后，對種群中的最優(yōu)個體依次進(jìn)行了交換、倒置和倒序操作。每次操作都會保留適應(yīng)度值較優(yōu)的個體，以增強算法的挖掘能力。

具體的多鄰域搜索方法如下。

（1）交換操作：假設(shè)加工任務(wù)總加工工序數(shù)為N，在1～N中隨機選擇兩個不同的位置，然后交換這兩個位置的加工工序。

（2）倒置操作：假設(shè)加工任務(wù)總加工工序數(shù)為N，在1～N中隨機選擇一個位置Oa，然后將該位置與其后面的工序位置Oa+1進(jìn)行交換。如果選擇的位置是最后一個位置，則將該位置的工序與工序列表中的第1 個位置的工序進(jìn)行交換。

（3）倒序操作：假設(shè)加工任務(wù)總加工工序數(shù)為N，在1～N中隨機選擇兩個不同的整數(shù)為a和a+p，假設(shè)未進(jìn)行倒序操作前的工序編碼為O＝[O1,O2,O3,···,Oa,Oa＋p,···,ON]，則執(zhí)行倒序操作后的序編碼為Onew＝[O1,O2,···,Oa＋p,Oa+p-1,···,Oa,···,ON]。

2.3 QCHIO 算法的流程

QCHIO 的流程圖如圖2 所示。

圖2 QCHIO 流程圖

3 實驗驗證與結(jié)果分析

為了驗證所提出算法QCHIO 的性能，采用了車間調(diào)度上典型的FT 算例與LA 算例進(jìn)行仿真測試。實驗PC 設(shè)備參數(shù)為：CPU 為AMD Ryzen7 5700U、主頻為1.8 GHz、運行內(nèi)存為16 GB、操作系統(tǒng)為Windows 11。編程環(huán)境為Matlab 2018b。

3.1 對比算法及參數(shù)設(shè)置

為了便于對比分析，選取了幾種較為先進(jìn)的算法作為對比算法，其中有改進(jìn)麻雀算法（ISSA）[2]、量子狀態(tài)轉(zhuǎn)移算法（QSTA）[3]、多策略引導(dǎo)的電磁優(yōu)化算法（MGEFO）[4]、標(biāo)準(zhǔn)CHIO[6]算法。為了驗證改進(jìn)策略的有效性，對算法進(jìn)行了消融實驗，見表2，其中ICHIO1、ICHIO2、ICHIO3、ICIO4 分別表示在QCHIO 的基礎(chǔ)上無量子計算算子、無威布爾分布算子、無 β-登山算子、無多鄰域搜索算子。為了便于對比，將實驗參數(shù)均設(shè)置種群個數(shù)為50，最大迭代次數(shù)為500，算法獨立運行30 次，記錄其平均值（avg）、最優(yōu)值（best）作為實驗結(jié)果，結(jié)果見表3，QCHIO 相對于對比算法的改進(jìn)提升水平見表4，同時選取了幾個具有代表性的算例給出了平均迭代曲線和甘特圖，如圖3 和圖4 所示。

圖3 在部分算例上的平均迭代曲線

圖4 在部分算例上的甘特圖

表2 消融實驗結(jié)果

表3 QCHIO 與部分改進(jìn)算法在算例上的對比（%）

表4 QCHIO 相對于CHIO、ISSA、QSTA、MGEFO 的提升水平（%）

3.2 仿真結(jié)果

從表2 可以看出，QCHIO 相對于CHIO 在所有算例上無論是最優(yōu)值還是平均值都得到了較大程度的提升，相較于ICHIO1、ICHIO2、ICHIO3、ICHIO4 也得到了不同程度的提升，從而證明了改進(jìn)策略的有效性。其中相較于ICHIO1，QCHIO 在最優(yōu)值上的提升大于平均值的提升，由此可以推斷加入量子計算算子有助于提升算法的全局開發(fā)能力。相較于CHIO2，QCHIO 在大規(guī)模問題的LA21、LA26、LA31、LA36 上均得到了較大的提升，由此推斷威布爾分布算子在求解大規(guī)模問題上具備一定優(yōu)勢。文獻(xiàn)[14]指出全局最優(yōu)解是在所有鄰域結(jié)構(gòu)中的局部最優(yōu)解中找到的，并且某種鄰域結(jié)構(gòu)的局部最優(yōu)解通常接近于另一種鄰域結(jié)構(gòu)的局部最優(yōu)解。相對于ICHIO3、ICHIO4，QCHIO 分別在當(dāng)前最優(yōu)解和全局最優(yōu)解附近進(jìn)行了鄰域搜索，基于實驗結(jié)果也同樣可得出，算法在最優(yōu)解附近確實可以搜索到有用的信息，從而提升算法的局部搜索能力。

在表3 中，CHIO(50,500) 意為種群大小為50，總迭代次數(shù)為500，例如ISSA(100,500)表示在原文中種群大小為100，總迭代次數(shù)為500。在表4 中，?best表示QCHIO 相較于其他算法最優(yōu)值的提升率，?avg表示相較于其他算法平均值的提升率，“－”表示無提升，以QCHIO 相對于CHIO 的提升水平為 例，?best=(CHIObest-QCHIObest)/ CHIObest,?avg=(CHIOavg-QCHIOavg)/ CHIOavg。

由表3 和表4 可知，QCHIO 相較于CHIO，最優(yōu)值和平均值均得到了較大提升，尤其是在大規(guī)模問題上均取得了10% 左右的提升。相較于ISSA，雖然其設(shè)置了更大的種群規(guī)模，但QCHIO 在平均值上有7 個算例上均具有不同程度的提升，說明了QCHIO 在一定程度較ISSA 更穩(wěn)定。相較于QSTA，QCHIO 與其實驗參數(shù)設(shè)置均保持了一致，從平均值角度看，QCHIO 在9 個算例上得到了提升，在最優(yōu)值上有4 個算例得到提升，3 個算例保持一致，由此得出引入了量子計算和威布爾分布算子的QCHIO 在解決調(diào)度問題上相較于QSTA 具有更強的全局尋優(yōu)能力和穩(wěn)定性。與MGEFO 相比，該算法總迭代次數(shù)為QCHIO 的2 倍，但在10 個算例的最優(yōu)值上QCHIO 有5 個算例得到提升，3 個算例保持一致，平均值上有9 個算例得到提升，由此可以推斷出QCHIO 較于MGEFO 在求解JSP 問題上更具優(yōu)越性。

3.3 統(tǒng)計學(xué)分析

為了進(jìn)一步驗證本文算法與其他算法在仿真結(jié)果在統(tǒng)計學(xué)上是否存在顯著性差異，通過使用95%置信度的配對t檢驗對各算法在10 個算例上的平均值進(jìn)行試驗并記錄其實驗結(jié)果，見表5。在四組配對數(shù)據(jù)中顯著性水平p均小于0.05，另外，Cohen's d 值是用來衡量效應(yīng)量大小的，即算法之間差異的幅度大小。當(dāng)Cohen's d 值越大時，說明算法之間的差異越大。根據(jù)常用的分級標(biāo)準(zhǔn)，效應(yīng)量可分為小、中、大三個等級，對應(yīng)的臨界點分別是0.2、0.5 和0.8。根據(jù)表中的數(shù)據(jù)可知，4 組數(shù)據(jù)的Cohen's d 值均大于0.8，表示算法之間存在較大的差異性。因此可以得出結(jié)論，QCHIO 與所有對比算法在統(tǒng)計學(xué)上均存在顯著性差異。

表5 各算法配對t 檢驗結(jié)果

4 實例驗證

為了進(jìn)一步驗證QCHIO 求解車間調(diào)度問題JSP 的可行性和有效性，本文在某公司汽車發(fā)動機生產(chǎn)的作業(yè)排產(chǎn)問題上進(jìn)行了例證，根據(jù)文獻(xiàn)[15]整理了某型號的發(fā)動機的生產(chǎn)工件工藝和數(shù)據(jù)，各工件的加工順序見表6，加工時長見表7。

表6 各工件加工工藝

表7 各工件加工時長 min

根據(jù)表6 可以看出需要排產(chǎn)的發(fā)動機的工件生產(chǎn)過程需要10 個工件，每個工件需要6 道工序，為10×6 規(guī)模的問題，解集規(guī)模為(10!)6。目前該公司所采用的人工經(jīng)驗調(diào)度方式的原則為：優(yōu)先加工總時長最短的工件，同時在整個調(diào)度中盡可能將總加工時長相對較短的工件先加工，同時盡可能保證在調(diào)度中排在前面的加工機器能夠連續(xù)工作，不出現(xiàn)空閑狀況，即優(yōu)先保證粗加工車M1 優(yōu)先加工，所得到的該型號發(fā)動機的主要10 個工件總工時為199 min。

運用本文所提算法QCHIO 對其進(jìn)行求解，設(shè)置種群規(guī)模為100，最大迭代次數(shù)為100，算法獨立運行10 次，所得結(jié)果見表8。最優(yōu)加工方案甘特圖如圖5 所示。

圖5 最優(yōu)加工方案甘特圖

表8 實例求解結(jié)果

所得最優(yōu)加工方案為[3,3,9,10,3,5,9,3,5,4,10,9,7,9,5,6,4,9,10,1,5,1,4,9,7,2,3,10,8,4,6,1,1,5,10,4,7,7,3,8,1 0,5,6,2,8,2,1,4,6,1,8,7,2,6,8,7,2,6,8,2]，加工總時長為122 min。較原始人工調(diào)度方法提升了38.7%，較原文提出算法DFACO 提升了10.3%。盡管只是對工件加工工時進(jìn)行初步改善，但這是在該公司所生產(chǎn)的發(fā)動機的其中一種型號，對10 個工件進(jìn)行的一次10×6 規(guī)模的調(diào)度優(yōu)化。考慮到整個公司的產(chǎn)品種類和數(shù)量較多，每年實際的生產(chǎn)成品量巨大，并且包括單獨外售的零部件，所以從整體上看，這種改善效果和產(chǎn)生的效益是較為可觀的。

5 結(jié)語

隨著全球制造業(yè)的發(fā)展和競爭的加劇，車間調(diào)度作為提高生產(chǎn)車間效率的關(guān)鍵，不斷對其進(jìn)行優(yōu)化變得越來越重要。本文針對最小化最大完工時間為求解JSP 目標(biāo)，提出QCHIO 算法，并通過在10個算例進(jìn)行仿真實驗和消融實驗，與其他幾種算法上進(jìn)行了對比分析，并對結(jié)果進(jìn)行了顯著性分析，最后將其應(yīng)到一個實際生產(chǎn)案例上，得出了以下結(jié)論：

通過對10 個算例的消融結(jié)果進(jìn)行分析，驗證了所提算法QCHIO 在改進(jìn)策略的有效性。通過對算例仿真結(jié)果的分析得出QCHIO 具有較強的全局搜索能力，收斂精度較高等特點。引入量子計算算子，通過量子相關(guān)性實現(xiàn)全局搜索和快速收斂的目標(biāo)，增強了算法的全局開發(fā)能力，威布爾分布算子進(jìn)一步增加了算法的多樣性和搜索能力，在搜索空間的尾部有更好的擬合性能，能夠更好地探索整個搜索空間。β-登山算子和多鄰域搜索算子是針對局部最優(yōu)解問題的改進(jìn)措施。這兩種策略的引入有效地避免了算法陷入局部最優(yōu)解而無法跳出的問題，提高了算法的局部搜索能力。通過對實例結(jié)果分析進(jìn)一步驗證了所提算法的可行性和優(yōu)越性。

本文的研究對象主要為調(diào)度問題中JSP 問題，作為實際生產(chǎn)的簡化模型，除了本文應(yīng)用求解的發(fā)動機生產(chǎn)，金屬沖壓件和彈簧[16]等生產(chǎn)都符合JSP的生產(chǎn)特點，由此看出本文的研究具有一定的代表性，所提算法也可為求解調(diào)度問題提供一種思路。但隨著綠色制造的提出，越來越多的企業(yè)重視企業(yè)生產(chǎn)能耗，以求由此來降低成本，因此在同時考慮最大完工時間和能耗的多目標(biāo)問題上有待進(jìn)一步研究。