基于量子狀態轉移算法的作業車間調度問題

吳貝貝 李 喆

1(新疆大學電氣工程學院 新疆 烏魯木齊 830047) 2(新疆大學網絡與信息技術中心 新疆 烏魯木齊 830046)

Tolerance mechanism

0 引 言

作業車間調度問題(Job-shop Scheduling Problem,JSP)是一類組合最優化問題，其實質就是要解決如何合理地安排工件的加工順序，將有限的人力物力資源分配給不同的工作任務，使預定的目標最優化的問題。研究該問題，對于在現有的資源條件下提高工作效率和經濟效益有十分重要的作用。目前國內外學者已經用多種智能優化算法對JSP問題進行了研究。劉洪銘等[1]提出一種改進粒子群算法，將自適應權重及混沌策略相融合，有效地提升了粒子的利用率，提高了算法的全局和局部搜索能力。孫在省等[2]針對特定的可重入JSP問題，提出一種基于塊結構性質的花粉算法用于最小化總加權延誤時間，該算法能夠在可行解空間區域內進行全局搜索，從而發現較優解所在的區域。張垚等[3]提出了一種新型遺傳鄰域萬有引力算法，并以此定義了一種新的交叉策略，可有效解決某類大規模JSP問題。Dao等[4]提出了一種基于并行式的蝙蝠算法，采用隨機鍵編碼方式，以最大完工時間為優化目標求解JSP問題，實驗表明該方案可有效提升算法的收斂性及平穩性能。上述優化算法可有效彌補傳統算法所存在的不足，并且為求解JSP問題擴展了新的方向。

Zhou等[5]于2012年提出狀態轉移算法(State transition algorithm,STA)，這是一種新型的隨機性全局優化方法，因其結構簡單、參數少、尋優效率高，得到廣泛的應用。王聰等[6]提出了結合正交學習機制和原對偶學習策略的狀態轉移算法[7]用于分數階多渦卷混沌系統的辨識。陽春華等[8]提出了一種離散狀態轉移算法用于求解旅行商問題。王正元等[9]提出了一種基于狀態轉移算法的組合優化方案，該策略融合了近似方法、下界算法、降維方法及精確求解的方法。董天雪等[10]在一次狀態轉移的基礎上提出了二次狀態轉移的概念，豐富了解的多樣性，使算法跳出局部最優。

量子計算作為突破當前計算極限的重要技術，也成為各國專家學者密切關注的前沿學科之一[11]。量子計算是將量子理論及智能計算二者相融合，并應用量子并行計算特性，能夠彌補傳統優化算法中的不足，避免算法陷入局部最優，提高算法的收斂速度。對此國內外學者做了大量的研究工作。黃力明等[12]提出了一種新的量子旋轉門調整策略，確保當前解無論處于何種狀態都能收斂到一個更優的染色體，即最優解染色體。解平等[13]為保證可行解向最優解方向搜索，在量子旋轉門更新的基礎上同時引入局部更新操作。閆旭等[14]采用量子計算和量子優化的思想提出了一種量子鯨魚優化算法,可有效解決算法出現的收斂精度低、易早熟的問題。高輝等[15]通過嘗試不同的初始旋轉角度來進行算例的仿真實驗，并探討分析了初始旋轉角對算法性能所產生的影響。Salido等[16]提出了一些分析公式來估計能效、魯棒性和最大完工時間這些參數之間的比率關系。

本文針對群智能優化算法在求解作業車間調度問題時過分依賴初值、局部搜索能力差、收斂速度慢等不足，提出了量子狀態轉移算法(Quantum state transition algorithm,QSTA)，將量子計算與優化的思想引入狀態轉移算法構成量子狀態轉移算法，以最大完工時間最小為目標函數，來求解JSP問題。

1 作業車間調度問題的數學描述

1.1 問題描述

JSP問題一般被描述為：假定有n個工件，它們要經過m臺機器加工，每個工件在特定的機器設備上進行加工被稱為一道“工序”，每道工序的加工時間是事先確定的。每個工件的加工工藝過程是事先給定的，因此，一個工件可看作一列工序的組成部分。所以調度需處理的問題就是要安排一種合理的工件加工順序及開始加工的時間，以滿足某種性能指標的最優。本文所求解的性能指標為“最小化最大完工時間”，并且在求解該問題時必須滿足以下約束條件：

(1) 機器不存在故障，工件從t=0時刻開始加工。

(2) 每臺機器在任一時刻最多加工一道工序。

(3) 作業的加工路線必須嚴格遵守，一旦開始加工不得中途停止，直至這道工序被加工完。

(4) 每個作業的加工工藝固定，不允許改變。

1.2 數學模型建立

求解JSP問題的實質是指在滿足上述約束條件的情況下，找到一組可行解(可行的加工工序)并令所要求的目標函數達到最優。實現最小化最大完工時間，可有效提高車間的生產效率，降低企業的生產成本，因此將最大完工時間最小化作為目標函數進行求解具有一定的現實意義。

由于本文求解的決策變量(機器數、工件數)均為正整數，因此利用整數規劃模型對JSP問題的數學模型進行描述：

優化目標如下：

(1)

約束條件如下：

Cjk-tik+M(1-aihk)≥Cih

(2)

Cjk-Cik+M(1-xihk)≥tjk

(3)

Cik≥0

(4)

aihk,xijk=0,1

(5)

i,j=1,2,…,nh,k=1,2,…,m

(6)

式中：tik和Cik表示第i個工件在第k臺機器上的加工時間以及完工時間；M是一個極大的正數；aihk=1表示機器h比機器k優先加工工件i；xijk=1表示工件i比工件j優先在機器k上加工；反之，二者皆為0。

式(1)為目標函數，表示最大完工時間最小；則式(2)表示當前工序與上道工序之間的約束關系；式(3)表示工序之間是非阻塞約束關系；式(4)表示各工件的完工時間必須大于零；式(5)表示工序、機器約束；式(6)表示各下標變量的取值范圍。

2 算法描述

2.1 量子比特位編碼

量子計算[17](Quantum computation,QC)首次于1982年提出，現今已成為國內外專家學者所密切關注的前沿問題。進行量子計算時運用量子比特表示信息,采用|0〉與|1〉代替微觀粒子所存在的兩種基本狀態,記號“|〉”稱為Dirac記號,在量子力學中表示狀態。除了|0〉和|1〉之外,量子比特還可以是疊加態,即這兩種狀態之間的中間狀態：|φ〉=α|0〉+β|1〉,參數α、β代表一對復數,是指量子態的概率幅,即量子態|φ〉以|α2|的概率坍縮到|0〉或以|β2|的概率坍縮到|1〉,且滿足：

(7)

量子邏輯門是指對量子狀態采用邏輯變換所生成的量子裝置，它是量子計算可以實現的基礎。

2.2 解空間映射方法

解空間映射是將量子比特位編碼應用于JSP的關鍵環節。編碼時一定要考慮狀態的可行性、有效性和對問題解空間表征的完備性。在求解車間調度問題時，可行解就是工件的排列順序，所以必須將量子位的概率幅轉變成工件的加工工序編碼。

在JSP問題中，從一組可行解上進行有限次位置變換生成的解仍然是可行的，本文采用基于移位解碼的編碼方式和基于實數的交換位編碼方式。這兩種編碼方式均是在一組可行解基礎上進行有限次位置交換從而生成新的加工序列，這保證了狀態的可行性和有效性，同時兩種編碼方式對解空間表征的完備性具有互補作用，詳細論述如下。

1) 基于移位解碼的編碼方式是以父代工件的加工工序作為參考模板，根據某一個二進制串進行移位解碼從而得到子代工件工序的編碼轉換方式[18]。定義二進制串中數值0取當前父代序列的第一位值，數值1取當前父代序列的第二位值，以此策略，順次從父代個體中取出其值組成子代個體，隨后將取出的值從父代中刪除，方便選取下一位值，其具體說明如圖1所示。運用此方法對序列進行重新排序，有助于增加序列的多樣性，并提高算法全局搜索的能力。

圖1 移位解碼

2) 為了使加工序列發生微小變化，引起序列更新，本文提出一種基于實數的交換位編碼方式。通過交換加工序列中任意兩位置的值，從而產生新的加工序列。每一個序列有兩個量子串控制其交換位，將量子串轉換為二進制數，再換算成十進制編碼，進而將加工序列中對應位置的值進行交換。

對于有N個工件M個機器的JSP問題，采用兩個最小能表示N×M對應的二進制位數個量子位，一個量子串對應加工序列中的一個待交換位置。例如6個工件6臺機器需要6個量子位來描述其工作序列中的位置，量子串被表示為：

(8)

對上述兩個量子位串進行觀測，如圖2所示，若得到二進制串[0 0 1 0 0 0]、[0 1 0 0 1 1]，則換算成十進制為[8]、[19]，將序列中對應位置的值交換。這種編碼方式可以對加工序列進行微調，通過加工序列局部變化引起其序列的更新。

圖2 交換位解碼

3.3 量子狀態轉移算法

根據量子的疊加特性及變遷理論，應用量子旋轉門變換更新產生新的編碼。量子旋轉門構造如下:

(9)

(10)

采用狀態轉移算法作為旋轉角搜索策略，同時結合量子旋轉門操作提升算法的全局搜索能力。使用狀態轉移算法中產生候選旋轉角的統一框架可以描述如下：

(11)

式中：θk,θk+1∈Rn分別表示旋轉角的當前狀態與更新后的狀態，當前狀態對應優化問題的一個解，經過一次算子變換產生的θk+1將構成一個候選解集；Ak,Bk∈Rn×n為狀態轉移矩陣；uk是關于狀態sk及歷史狀態的一個函數表達式；f(θk+1)表示狀態更新后的目標函數值。

為了使QSTA求解問題時量子旋轉角狀態轉移過程具有可控性，依據傳統狀態轉移算法設計了四種量子旋轉角狀態更新算子。

1) 量子旋轉算子：

(12)

2) 量子平移算子:

(13)

式中：β是正常數，稱為平移因子；Rt∈R是一個服從[0,1]均勻分布的隨機變量。

3) 量子伸縮算子:

θk+1=θk+γReθk

(14)

式中：γ是正常數，稱為伸縮因子；Re∈Rn×n是一個服從高斯分布的隨機矩陣；該算子主要起到在整個解空間內進行全局搜索的作用。

4) 量子坐標變換算子:

θk+1=θk+δRaθk

(15)

式中：δ是正常數，稱為坐標因子；Ra∈Rn×n是一個服從高斯分布的隨機對角稀疏矩陣。坐標算子有利于增強單維搜索能力。

對以上四種算子計算出的旋轉角分別通過量子旋轉門更新量子位，通過量子坍縮操作對量子位進行觀測，生成二進制串通過相應的編碼方式將其映射到解空間中，可有效增加解的多樣性并避免非法解的產生。

2.4 容忍非局部最優解機制

基礎的狀態轉移算法每次迭代過程只考慮當前最優解，在其基礎上進行狀態轉移，然而應用狀態轉移算法處理JSP問題時容易陷入局部最優，因此本文提出一種對非局部最優解的容忍機制，如圖3所示，能夠有效避免加工序列處于局部最優狀態無法收斂的情況。

圖3 容忍非局部最優解機制

本文考慮單次序列的局部變化，可能不會使新序列獲得更好的適應度值，但對同一序列的連續局部變化形成的新序列也有可能導致更好的結果，因此設置非局部最優狀態下的容忍次數，允許非局部最優解獲得連續的狀態變化，以此增加解的多樣性，同時有效避免了某一加工序列陷入局部最優。

2.5 QSTA算法流程

量子狀態轉移算法是在原有狀態轉移算法(STA)的基礎上引入量子旋轉門操作以豐富工序的多樣性。通過狀態轉移算法的不同操作更新旋轉門所需的旋轉角，進行量子旋轉門操作。對量子位串觀測引起坍縮，生成二進制狀態，通過此狀態獲得不同的加工序列，計算加工工序的總完工時間，進而選出最短完工時間對應的加工序列作為當前最優工序。

QSTA流程如圖4所示。

圖4 量子狀態轉移算法流程

QSTA的優化步驟如下：

Step2生成二進制移位編碼。隨機生成移位編碼的旋轉角，通過量子旋轉門對移位編碼的量子位串執行量子旋轉門操作，對此量子位串進行觀測，獲得二進制移位編碼，使用此編碼對全局最優加工序列進行重新排序，然后進行適應度計算，保存最優適應度結果。

Step3對非最優解的容忍操作。對Step 2中所產生的加工序列根據容忍次數連續調整加工序列的不同位置，并對其進行適應度值計算，保存最優適應度結果。

Step4采用量子狀態轉移算子生成位置交換編碼。采用量子旋轉、量子伸縮、量子坐標變換操作對旋轉角進行更新，通過量子旋轉門對交換位編碼的量子位串執行量子旋轉門操作，對此量子位串對進行觀測，獲得二進制編碼，將其轉換成十進制交換位編碼，使用此編碼對全局最優加工序列中的兩個位置進行交換，然后進行適應度計算，保存最優適應度結果。

Step5根據容忍次數連續調整Step 4中所產生的加工序列的不同位置，并對其進行適應度值計算，保存最優適應度結果。

Step6判斷是否滿足終止條件，若滿足則結束搜索，否則返回Step 2。

3 實 驗

本實驗選用MATLAB R2015b編程語言實現，運行環境為:處理器1.60 GHz，處理器速度1 800 MHz，物理環境3 993 MB，Windows 10操作系統。為驗證本文算法解決作業車間調度問題的高效性，采用QSTA方法對作業車間調度標準測試問題庫中的12個測試問題進行求解并與其他算法相比較。上述12種算例分別為文獻[19]提出的實例FT06、FT10、FT20和Lawrence等[20]提出的實例LA01、LA06、LA11、LA16、LA21、LA26、LA31、LA36、LA40。

3.1 STA、PSO和GA的仿真對比

狀態轉移算法的參數選擇：搜索規模SE=100，旋轉因子的最大值αmax=1，最小值為αmin=1e-4，旋轉因子α=1，平移因子β=1，伸縮因子γ=1，坐標系數δ=1，迭代次數M=500。為了更準確地與PSO和GA就JSP問題進行比較，將各個參數設置與STA保持一致，即種群規模NIND=100，最大迭代次數M=500。各個算法單獨運行20次，所得到的結果如表1所示。

表1 三種算法(STA、GA、PSO)的比較

續表1

可以看出，在搜索規模、迭代次數和獨立運行次數皆相同的情況下，STA、PSO和GA在FT06、LA01、LA06、LA11等問題中均能收斂到當前已知最優解。在尋最優解個數上STA算法要優于PSO和GA。在計算大規模問題算例時GA要優于STA，從最優解、平均值方面可以得出，STA優于PSO，但部分劣于GA。

仿真結果表明，STA雖能有效解決JSP，但對比PSO及GA來說并無明顯優越性，因此還需對基本STA做進一步的改進，本文采用QSTA繼續對以上算例進行求解。QSTA求解的部分甘特圖如圖5所示。

(a) FT06甘特圖(makespan=55/min)

(b) FT10甘特圖(makespan=960/min)

(c) LA01甘特圖(makespan=666/min)

(d) LA16甘特圖(makespan=945/min)圖5 部分調度問題甘特圖

3.2 QSTA與STA的對比

利用量子狀態轉移算法繼續對上述問題進行求解，將算法的搜索規模設置為SE=100，最大迭代次數M=500，獨立運行20次，量子旋轉角設置為rand×2×π。運算結果如表2所示，尋優成功率的計算方法為：最優解個數/獨立運行總次數。

通過QSTA與STA算法就求解作業車間調度問題的比較結果可知，量子狀態轉移優化算法在算法的尋優成功率方面有很大的提升，在LA06、LA11問題上的尋優成功率的值均在100%,且在LA31中QSTA可以搜索到已知最優解。結合圖6所示的尋優曲線對比可知，采用QSTA可有效解決JSP問題，QSTA搜索得到的最優解及平均值皆明顯優于STA，且收斂速度及收斂精度也明顯優于STA、PSO和GA。綜上所述，QSTA可有效求解JSP問題，與STA相比其收斂精度更高、收斂速度更快。因此，改進后的量子狀態轉移算法可有效避免算法陷入早熟，增強算法的求解精度并提高算法的收斂速度。

表2 QSTA與STA算法的比較

(a) FT06收斂曲線

(b) FT10收斂曲線

(c) LA16收斂曲線

(d) LA31收斂曲線圖6 部分測試問題尋優曲線對比

4 結 語

本文針對傳統群智能算法求解JSP時存在的算法易早熟、后期收斂速度慢和全局搜索能力差的問題，提出了量子狀態轉移算法來求解JSP問題。首先，驗證了STA在解決JSP時具有可行性，并發現了STA在解決JSP時存在缺陷；為提升STA搜索可行解的多樣性及收斂精度，采用移位解碼和交換位編碼兩種編碼方式，結合量子計算的優點提出QSTA；在此基礎上又提出一種容忍非最優解機制，對其進行仿真實驗。通過對比發現，QSTA在解決JSP時可有效彌補傳統算法的不足，具有迭代次數少、收斂速度快、全局搜索能力強等優點。