基于量子蟻群算法的智能制造調(diào)度問(wèn)題研究

吳昌錢,黃 銳,羅志偉

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

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

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

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

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

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

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

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

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

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

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

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

(5)一個(gè)機(jī)器同時(shí)只對(duì)一個(gè)工件的一道工序且該工序只能由該機(jī)器完成.

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

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

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

(1)

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

(2)

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

(3)

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

min[max(Tx)].

(4)

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

Cij-Kij-tij=0,

(5)

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

Kij+tij≤Ki(j+1),

(6)

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

Kijq+tij≤Kweq,

(7)

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

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

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

2.1 量子計(jì)算

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

(8)

2.2 量子蟻群算法基本思想

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

(9)

圖1 量子蟻群算法流程圖

信息素強(qiáng)度更新方程為:

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

(10)

(11)

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

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

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

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

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

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

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

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

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

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

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

(12)

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

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

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

步驟2:在開(kāi)始處放入n個(gè)螞蟻,最終螞蟻向結(jié)束節(jié)點(diǎn)移動(dòng).節(jié)點(diǎn)移動(dòng)的概率為式(9).

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

步驟4:如果螞蟻?zhàn)咄晁泄?jié)點(diǎn),則計(jì)算出該螞蟻的目標(biāo)函數(shù)值即最短完工時(shí)間,記錄當(dāng)前最低值,否則,執(zhí)行步驟2.

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

表2 實(shí)驗(yàn)參數(shù)

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

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

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

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

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

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

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

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

5 結(jié)論

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