吳昌錢,黃 銳,羅志偉

(1.閩南科技學(xué)院計算機信息學(xué)院,福建 泉州 366200)(2.北京理工大學(xué)計算機學(xué)院,北京 100081)(3.廈門大學(xué)機電學(xué)院,福建 廈門 361000)

隨著我國科技的迅速發(fā)展,帶動了高端制造業(yè)市場,相關(guān)設(shè)施裝備的需求量也逐漸擴大. 先進(jìn)的大型機械設(shè)備由各個重要的構(gòu)件組成,這些構(gòu)件的制造工藝復(fù)雜且加工精度非常高,因此,構(gòu)件的制造過程是高端制造業(yè)的關(guān)鍵之處.

精密復(fù)雜構(gòu)件的生產(chǎn)模式特點是典型的生產(chǎn)品種多,每種品種加工數(shù)量較少,交貨周期長,成本高. 而且,精密復(fù)雜構(gòu)件的制造工藝較為復(fù)雜,且加工的精度較高,加工工序不同,并且工件間無約束,但同一工件的工序有順序[1]. 由此可見,制造車間調(diào)度問題(Aviation Manufacturing Job Shop Scheduling Problem,AMJSP)的特點與作業(yè)車間調(diào)度問題(Job Shop Scheduling Problem,JSP)的特點近似相等,因此,本文將AMJSP考慮為JSP. JSP對高端制造業(yè)的發(fā)展和進(jìn)步的作用至關(guān)重要,如今的科技已較為發(fā)達(dá),從而車間調(diào)度問題也逐漸復(fù)雜化,而傳統(tǒng)模式車間調(diào)度方案已經(jīng)無法高效解決JSP問題,因此相應(yīng)的各種求解車間調(diào)度問題的智能算法應(yīng)運而生,例如遺傳算法(Genetic Algorithm,GA)、粒子群算法(Particle Swarm Optimization,PSO)等.

崔琪等[2]為了求解混合流水車間調(diào)度問題,提出了利用變鄰域搜索的方式來改進(jìn)GA,該方案可有效求解車間調(diào)度問題,但其收斂速度較慢. 劉洪銘等[3]提出了一種改進(jìn)PSO算法的方案,該算法基于自適應(yīng)權(quán)重,提高了粒子利用率,加入了混沌以平衡全局與局部,但其容易丟失種群多樣性. 劉勝輝等[4]提出了一種雙禁忌表禁忌搜索算法,該算法避免了在搜索中容易出現(xiàn)循環(huán)的情況,提高了尋優(yōu)能力. 黃海松等[5]提出了一種改進(jìn)模擬退火算法以求解雙目標(biāo)柔性JSP,該算法融合搜索與編碼方法提高了運行速度,避免了傳統(tǒng)的模擬退火算法陷入早熟,提高了算法的全局尋優(yōu)能力. 施文章等[6]提出一種退火下布谷鳥算法求解JSP問題方案,該方案改善了種群的多樣性. 上述智能算法各有各的特點,以不同程度的效率解決JSP問題,但是隨著車間調(diào)度問題的復(fù)雜化加上算法的某些局限性,還需進(jìn)一步對算法進(jìn)行優(yōu)化.

綜上所述,本文根據(jù)復(fù)雜構(gòu)件制造車間的特點,結(jié)合量子計算和蟻群算法提出一種基于量子蟻群算法的智能制造車間調(diào)度問題方案,該方案保留了量子計算的高效性,提高了蟻群全局尋優(yōu)能力,避免了螞蟻易陷局部最優(yōu)解問題.

1 車間調(diào)度問題描述及數(shù)學(xué)模型

1.1 智能制造作業(yè)車間調(diào)度問題描述

在智能制造作業(yè)車間調(diào)度問題AMJSP當(dāng)中,根據(jù)每個工件和每臺機器的信息特點,研究如何安排n個工件在m臺機器上的加工的順序,使得最大完工時間最小. 其加工過程中的基本假設(shè)和約束條件為:

(1)加工時,不考慮員工、機器、用電等意外因素;

(2)計算加工時間,不加入材料運輸、工件設(shè)備安裝拆卸等時間;

(3)工件的設(shè)計工藝都是提前確定好的,都是零時刻到達(dá);

(4)工件工序按照工序順序加工且過程不中斷,對應(yīng)的機器都是提前確定好的;

(5)一個機器同時只對一個工件的一道工序且該工序只能由該機器完成.

1.2 數(shù)學(xué)模型

基于上述問題描述和約束條件,建立JSP的數(shù)學(xué)模型,并構(gòu)造相應(yīng)的矩陣. 從上述描述可知,一般概括有n個工件,m臺機器,每個工件最多有m道工序,則對JSP問題的參數(shù)的集合分別有:

(1)n個工件的工序集合為J=(J1,J2,…,Jn)T,其中Ji=(ji1,ji2,…,jik,…,jnm)T,i∈[1,n],k∈[1,m],jik表示第i個工件的第k道工序.相應(yīng)地,工件的工序排列矩陣J:

(1)

(2)n個工件加工使用的機器集合為M=(M1,M2,…,Mn)T,其中Mi=(mi1,mi2,…,mik,…,mnm),i∈[1,n],k∈[1,m],mik表示為第i個工件的第k道工序所加工的機器.相應(yīng)地,工序所需機器的加工機器矩陣MJ為:

(2)

(3)n個工件的各個工序加工時間的集合為:T=(T1,T2,…,Tn)T,其中Ti=(ti1,ti2,…,tik,…,tnm),i∈[1,n],k∈[1,m],tik表示第i個工件的第k道工序加工所需要的時間.相應(yīng)地,工序的加工時間矩陣TJ為:

(3)

綜上所述,在智能制造車間調(diào)度問題中,給定工件的工序矩陣和相應(yīng)的生產(chǎn)時間矩陣,求出最短生產(chǎn)時間的目標(biāo)函數(shù)公式定義為:

min[max(Tx)].

(4)

根據(jù)上述的約束條件和矩陣,可得出相應(yīng)的約束公式為:

Cij-Kij-tij=0,

(5)

式中,1≤i≤n,1≤j≤m.式(5)對應(yīng)的約束條件是工件工序?qū)?yīng)的機器是確定的,按照工序順序加工且過程不中斷.Cij是指工件的完工時間.

Kij+tij≤Ki(j+1),

(6)

式中,1≤i≤n,1≤j≤m.式(6)對應(yīng)的約束條件是加工的工序按著一定的順序開始進(jìn)行.

Kijq+tij≤Kweq,

(7)

式中,1≤i≤n,1≤j≤m.式(7)對應(yīng)的約束條件是一個機器同時只能進(jìn)行一個工件的一道工序且該工序只能由該機器完成.Kweq是指加工w工件的第e道工序在機器q上的進(jìn)行生產(chǎn)的開始時間.

2 量子蟻群算法的優(yōu)化機理

量子蟻群算法(Quantum Ant Colony Algorithm,QACA)是由量子計算和蟻群算法結(jié)合而成的,以量子計算[7-9]為基礎(chǔ),可以提高蟻群全局尋優(yōu)能力,避免螞蟻易陷局部最優(yōu)解問題.

2.1 量子計算

在QACA中,量子比特對信息素進(jìn)行編碼,它是一個二維復(fù)向量空間中由標(biāo)準(zhǔn)正交基{|0〉,|1〉}所組成的向量單位,其狀態(tài)可表示為|ψ〉=|α〉+|β〉,其中α和β滿足|α|2+|β|2=1,表示|0〉和|1〉的概率幅.通過利用量子旋轉(zhuǎn)門來改變相位可以實現(xiàn)對量子比特的狀態(tài)改變,其表示式為(8):

(8)

2.2 量子蟻群算法基本思想

根據(jù)文獻(xiàn)[10-12]提出的基于蟻群的啟發(fā)式進(jìn)化算法,可得螞蟻k轉(zhuǎn)移相鄰節(jié)點的概率為式(9):

(9)

圖1 量子蟻群算法流程圖

信息素強度更新方程為:

τij(new)=(1-ρ)τij(old)+Δτij(k),

(10)

(11)

式中,τij(new)表示螞蟻移動的下一個節(jié)點;ρ為信息素的揮發(fā)性,0≤ρ<1;τij(old)表示螞蟻所在當(dāng)前的節(jié)點;Q為常數(shù).

綜上所述,量子蟻群算法流程為:

步驟1:螞蟻利用轉(zhuǎn)移概率移動節(jié)點;

步驟2:計算各個螞蟻目標(biāo)函數(shù)最優(yōu)值;

朗讀能夠訓(xùn)練普通話的發(fā)音技巧。學(xué)生在一定的量的朗讀訓(xùn)練之后可以達(dá)到吐字清晰，語音響亮，瑯瑯上口，悅耳動聽；能通過語音傳達(dá)出文章所表達(dá)的感情。

步驟3:利用量子旋轉(zhuǎn)門、信息素強度方程式更新;

步驟4:若當(dāng)前滿足迭代次數(shù),則輸出最優(yōu)解,否則返回步驟1.

3 基于量子蟻群算法的制造車間調(diào)度問題求解

將量子蟻群算法(Quantum Ant Colony Algorithm,QACA)應(yīng)用到求解制造車間調(diào)度問題當(dāng)中,根據(jù)工件的工序的加工時間矩陣TJ,可構(gòu)造一個有向圖,如圖2所示.在圖2中,螞蟻從左邊的開始處開始向ti1移動,下一個移動節(jié)點為tij(new),其可移動節(jié)點集合表示為:

圖2 基于量子螞蟻的AMJSP有向圖

tij(new)={tpq||i≠p}.

(12)

螞蟻橫向移動時,只能向相鄰的右節(jié)點進(jìn)行移動,向其他節(jié)點移動時,移動到的節(jié)點不約束.直至螞蟻移動到結(jié)束.其中,螞蟻移動過的節(jié)點不可能重復(fù)移動.

其算法實現(xiàn)步驟如下.

步驟1:初始化,設(shè)置各個參數(shù)值,其中,螞蟻數(shù)與機器數(shù)m相同,最大迭代次數(shù)DDmax,信息素τij(0)=1,螞蟻量子信息素編碼所有αij和βij初始值都設(shè)置為2-1/2.設(shè)置基于量子螞蟻的AMJSP有向圖,共n×m個節(jié)點.

步驟2:在開始處放入n個螞蟻,最終螞蟻向結(jié)束節(jié)點移動.節(jié)點移動的概率為式(9).

步驟3:設(shè)置每個螞蟻所走的節(jié)點數(shù)組Ak[n×m],即第k個螞蟻所走的節(jié)點放入數(shù)組中.根據(jù)式(9)和式(12)設(shè)置可選節(jié)點數(shù)組Kk[n×m],即第k個螞蟻還未走過的路徑節(jié)點的集合.

步驟4:如果螞蟻走完所有節(jié)點,則計算出該螞蟻的目標(biāo)函數(shù)值即最短完工時間,記錄當(dāng)前最低值,否則,執(zhí)行步驟2.

步驟5:根據(jù)式(8)改變量子信息、式(10)和式(11)改變軌跡信息素強度.

步驟6:若當(dāng)前滿足迭代次數(shù)DDmax,則輸出最優(yōu)解,否則執(zhí)行步驟2.

4 實驗結(jié)果與分析

關(guān)于JSP求解若干典型問題,國內(nèi)外學(xué)者專家設(shè)計了不同參數(shù),以便測試比較各自的優(yōu)化性能[13],如表1所示.

表1 不同參數(shù)的JSP調(diào)度案例

在眾多案例中,關(guān)于JSP運用最多的是LA類和FT類,因此,本文選擇該兩類數(shù)據(jù)案例對基于量子蟻群算法的求解制造車間調(diào)度問題進(jìn)行性能測試. 為了更好的評估,實驗平臺為Windows 10,CPU i7,8G內(nèi)存,Matlab R2018b仿真軟件,其他實驗仿真環(huán)境相關(guān)參數(shù)如表2所示.

表2 實驗參數(shù)

首先對FT06案例進(jìn)行調(diào)度尋優(yōu),將所提方案對其進(jìn)行求解得到的最優(yōu)解,如圖3所示. 可以看出,基于量子蟻群算法的FT06尋優(yōu)效率比較快,在執(zhí)行4次后就可得到最優(yōu)解,在執(zhí)行5次的時候就可得到平均解,從此可見,量子蟻群算法在制造車間調(diào)度的收斂性能上有優(yōu)勢,最優(yōu)解為55.

圖3 基于QACA-AMJSP的FT06尋優(yōu)解過程

將QACA-AMJSP與GA方案[14-15]、PSO算法方案[16-18]在FT06案例上進(jìn)行對比,如圖4所示. 可以看出,GA方案的收斂速度較慢且低于PSO方案的收斂速度,而QACA-AMJSP方案的算法收斂速度最快. QACA-AMJSP方案在執(zhí)行4次時,達(dá)到了最優(yōu)解55. GA在執(zhí)行6次的時候,達(dá)到了最優(yōu)解58,PSO方案在執(zhí)行次數(shù)到7次時,最優(yōu)解也達(dá)到了55,但總體而言,與GA和PSO方案相比,QACA-AMJSP方案的全局尋優(yōu)能力較強,收斂速度較快.

圖4 與其他方案的FT06最優(yōu)解對比圖

然后對LA36案例進(jìn)行調(diào)度尋優(yōu),將所提方案對其進(jìn)行求解得到的最優(yōu)解,如圖5所示. 可以看出,基于量子蟻群算法的LA36尋優(yōu)效率比較快,在執(zhí)行23次后就可得到最優(yōu)解,在執(zhí)行24次的時候就可得到平均解,由此可見,量子蟻群算法在制造車間調(diào)度的收斂性能上有優(yōu)勢,最優(yōu)解為1 268.

圖5 基于QACA-AMJSP的LA36尋優(yōu)解過程

將QACA-AMJSP與GA方案、PSO方案在LA36案例上進(jìn)行對比,如圖6所示. 可以看出,GA方案的收斂速度較慢,遠(yuǎn)低于PSO方案的收斂速度,而QACA-AMJSP方案的算法收斂速度最快. GA在執(zhí)行24次的時候,達(dá)到了最優(yōu)解1 574,QACA-AMJSP方案在執(zhí)行23次時最優(yōu)解達(dá)到了1 268,PSO方案在執(zhí)行次數(shù)到24次時,最優(yōu)解也達(dá)到了1268,但總體而言,與GA和PSO方案相比,QACA-AMJSP方案的全局尋優(yōu)能力較強,收斂速度較快.

圖6 與其他方案的LA36最優(yōu)解對比圖

5 結(jié)論

提出量子計算與模擬自然界蟻群行為的蟻群算法相結(jié)合求解智能制造車間調(diào)度問題. 根據(jù)智能制造車間的特點,構(gòu)建了相應(yīng)的車間調(diào)度數(shù)學(xué)模型. 然后利用量子蟻群算法求解AMJSP,提高了蟻群全局尋優(yōu)能力,避免了螞蟻易陷局部最優(yōu)解問題. 實驗結(jié)果表明,相比GA和PSO,量子蟻群算法對解決智能制造車間調(diào)度問題具有較高的搜索效率和較快的收斂速度. 但是未來智能制造車間會逐漸復(fù)雜化,復(fù)雜構(gòu)件的加工精度會越來越細(xì),還需要人工全程參與,因此,下一步研究將人員因素考慮到智能制造車間調(diào)度問題中進(jìn)行求解.