柔性車間調(diào)度問題的協(xié)作混合帝國算法

呂 聰，魏康林

(三峽大學(xué) 電氣與新能源學(xué)院，湖北 宜昌 443002)(*通信作者電子郵箱zeyuanwei@163.com)

0 引言

柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem， FJSP)是傳統(tǒng)作業(yè)車間調(diào)度問題(Job-shop Scheduling Problem， JSP)的拓展，即多工件工序排列在多機(jī)器加工的高維規(guī)劃問題，由Bruker等[1]于1990年首次提出。FJSP與JSP不同的是采用多機(jī)器并行生產(chǎn)加工模式，可選擇加工路徑增多，已被證明是一個NP完全問題，理論上更符合實(shí)際工業(yè)調(diào)度要求，因此柔性車間調(diào)度問題的研究具有重要的理論意義和實(shí)際應(yīng)用價(jià)值。

目前，國內(nèi)外相關(guān)學(xué)者對柔性車間調(diào)度問題已經(jīng)進(jìn)行了大量研究。Gao等[2]在混合多微型鳥群算法中，提出自適應(yīng)多種交叉策略，但收斂速度較慢。Zuo等[3]在自適應(yīng)無功優(yōu)化多模算法中，提出多種局部搜索方法和特有的鄰域結(jié)構(gòu)，但是全局搜索能力下降。Sreekara等[4]在社會網(wǎng)絡(luò)方法中，分析協(xié)作網(wǎng)絡(luò)評估功能屬性，且融入遺傳算法，但鄰域搜索能力下降。張潔等[5]在兩階段蟻群算法中，建立調(diào)度模型與蟻群搜索的映射關(guān)系，為任務(wù)分派與排序分別設(shè)計(jì)蟻群優(yōu)化算法，但求解質(zhì)量不穩(wěn)定?；谏鲜鏊惴ǖ膬?yōu)勢和缺陷，采用一種新的啟發(fā)式算法，Atashpaz-Gargari[6]在2007年受帝國競爭行為啟發(fā)提出帝國競爭算法(Imperialist Competitive Algorithm， ICA)。該算法具有收斂速度快、收斂效果好、全局搜索能力強(qiáng)的優(yōu)點(diǎn)，對于相對簡單的JSP已有較好的優(yōu)化效果[7]。因此，本文根據(jù)柔性車間調(diào)度的特性改進(jìn)帝國競爭算法，引入帝國殖民地雙變異多改革策略和自適應(yīng)參數(shù)，引入大陸間優(yōu)秀帝國的政治交流機(jī)制，減少了早熟現(xiàn)象的發(fā)生，提高了尋優(yōu)精度，得到了較好的調(diào)度方案。

1 柔性車間調(diào)度問題

1.1 問題描述

柔性車間調(diào)度是約束工件工序的調(diào)度問題，通常描述[8-9]為：某工廠需要加工多個不同工件，每個工件擁有長短不同的加工工序，各個工序可以選擇不同的機(jī)器作為加工路線，且不同機(jī)器針對某個工件工序的加工時(shí)間存在差異。關(guān)鍵就是調(diào)整工序順序以及安排合理機(jī)器加工，使最大完工時(shí)間最優(yōu)化。為了更加接近實(shí)際工廠操作效果，針對工件加工過程作出如下規(guī)定：

1)每個工序都具有預(yù)先可用的加工機(jī)器以及加工時(shí)間——作為實(shí)際調(diào)度前提。

2)任意工件的工序可以預(yù)先設(shè)定機(jī)器隨機(jī)選取加工——符合實(shí)際調(diào)度的目的意義。

3)工件準(zhǔn)備時(shí)間和等待時(shí)間都記錄在加工時(shí)間內(nèi)——注重整體的調(diào)度規(guī)劃結(jié)果。

4)允許工件的不同工序之間存在等待——考慮實(shí)際生產(chǎn)多任務(wù)分配優(yōu)化。

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

針對柔性車間調(diào)度問題的研究，定義參數(shù)如下:C表示所有工件加工結(jié)束花費(fèi)時(shí)間;g表示加工的總工序;N表示待加工的工件總數(shù);M表示可運(yùn)行的機(jī)器總數(shù);Pi表示工件i，i∈[1,N];Jk表示第k號機(jī)器,k∈[1,M];Pij表示工件i的第j個工序;Tijk表示Pij的工序在機(jī)器k上工作時(shí)間長度;Sijk表示Pij的工序在機(jī)器k上開始加工時(shí)間;Eijk表示Pij的工序在機(jī)器k上加工結(jié)束時(shí)間。

1.3 建立數(shù)學(xué)模型

根據(jù)柔性車間調(diào)度問題，建立數(shù)學(xué)模型[10]如下：

(1)

Si(j+1)k≥Eijk

(2)

Eijk-Sijk=Tijk

(3)

(4)

其中：式(1)就是本文研究FJSP的目標(biāo)函數(shù)最小化最大完成時(shí)間；式(2)代表工件的工藝約束，任何一個工件必須嚴(yán)格按照加工順序進(jìn)行加工，即只有在前一道工序完成后才能進(jìn)入下一道工序加工；式(3)代表工件加工約束，一個工序只允許在一臺機(jī)器上加工，一旦開始加工，不允許中斷加工過程；式(4)代表機(jī)器資源約束，機(jī)器對某一工序加工完成后可立即加工其他工件，中間可以不設(shè)等待時(shí)限，同時(shí)限制一臺機(jī)器同一時(shí)間只允許操作一個工件。

2 協(xié)作混合帝國算法

2.1 帝國競爭算法

帝國競爭算法(ICA)是通過模擬帝國殖民競爭機(jī)制而建立智能算法，本質(zhì)上是群體隨機(jī)優(yōu)化搜索方法。ICA基本流程[11]為：產(chǎn)生初始帝國，同化殖民地，帝國之間競爭，帝國消亡。

2.1.1 產(chǎn)生初始帝國

ICA與其他智能尋優(yōu)算法初始化相同，隨機(jī)產(chǎn)生的個體并稱為國家。在FJSP中，采用雙層編碼機(jī)制，前g個表示工件工序，確定工序加工順序，后面代表各工序?qū)?yīng)加工機(jī)器，則一個國家表示為式(5)：

Country=[P1,P2,P3,…,Pg,J1,J2,J3,…,Jg]

(5)

將隨機(jī)產(chǎn)生的國家編碼代入式(6)中的fitness函數(shù)計(jì)算其調(diào)度時(shí)間。根據(jù)調(diào)度時(shí)間對每個國家進(jìn)行強(qiáng)弱估值，即時(shí)間越小國家勢力越大。

Cost=fitness(Country)

(6)

根據(jù)式(7)、(8)，選擇勢力較大的Nimp作為帝國競爭算法中的帝國，剩余的國家為殖民地。Nimp個數(shù)會對算法求解結(jié)果產(chǎn)生影響，Nimp較大時(shí)，各個帝國分配較少的殖民地，收斂趨勢分散，影響收斂速度；Nimp較小時(shí)，帝國擁有較多殖民地，趨勢收斂單一，容易陷入早熟和局部收斂。

Cm=K×max{Costimp}-Costimp

(7)

(8)

其中：Cm為帝國分配殖民地的修正值；K是修正系數(shù)，1≤K≤2；Numi為第i個帝國所分殖民地的個數(shù)，以帝國的勢力決定擁有殖民地?cái)?shù)量。

2.1.2 同化殖民地

18世紀(jì)中期，世界帝國主義不斷瓜分掠奪殖民地。為了更好地管轄殖民地，強(qiáng)大的帝國將風(fēng)俗文化和政治思想在殖民地進(jìn)行推廣，ICA的同化操作就是模仿這一過程。

同化操作相當(dāng)于群體智能算法中的尋優(yōu)過程，重在保證算法區(qū)域搜索能力。ICA優(yōu)勢在于：所有殖民地群體向多個優(yōu)秀個體進(jìn)行遷移，增強(qiáng)群體中個體區(qū)域搜索能力。其同化式與粒子群的進(jìn)化式相似：

PNewcol=k1×Poldcol+k2×Pimp

(9)

其中：PNewcol為同化重新生成的殖民地；Poldcol為原始的殖民地；Pimp為殖民地所對應(yīng)的帝國。k1和k2為控制參數(shù)，且k1+k2=1。k1可以體現(xiàn)殖民地本體繼承和鄰域搜索能力，k2可以體現(xiàn)帝國對殖民的控制約束。本文采用工序、機(jī)器雙層編碼，同化只針對工件工序排列組合，如圖1所示。

圖1 帝國同化殖民地

簡單交換會出現(xiàn)沖突，圖1中以帝國基因?yàn)榛A(chǔ)，采用部分映射的方法消除沖突。新產(chǎn)生的殖民地可能會超越原有對應(yīng)的帝國勢力大小，像當(dāng)年英國和美國關(guān)系一樣，所以需要目標(biāo)函數(shù)對其進(jìn)行強(qiáng)弱估值。如果出現(xiàn)殖民地比帝國強(qiáng)大，將該殖民地與其對應(yīng)帝國進(jìn)行角色替換，該殖民地成為帝國，原來的帝國依附這個新的帝國。

2.1.3 帝國競爭機(jī)制

ICA通過競爭機(jī)制，迫使勢力弱的帝國割舍殖民地給勢力較強(qiáng)的帝國，不斷蠶食勢力弱的帝國，實(shí)現(xiàn)帝國的統(tǒng)一或少數(shù)帝國并立的結(jié)局。其算法關(guān)鍵在于弱勢殖民地可以向其他帝國移動，不在局限于一個帝國內(nèi)部搜索，在一定程度上增加了群體多樣性，體現(xiàn)全局“勘探”能力。競爭機(jī)制要求根據(jù)各個帝國的勢力大小選擇最弱的帝國中最弱的殖民地作為一個競爭對象，轉(zhuǎn)讓給勢力較大的帝國。帝國勢力計(jì)算公式如下：

(10)

式(10)表示帝國與殖民地都會對其勢力產(chǎn)生影響，其中α決定了殖民地對整個帝國的影響程度，一般取0.2。

2.2 帝國競爭算法的改進(jìn)

2.2.1 自適應(yīng)參數(shù)改進(jìn)

在帝國競爭算法的同化操作和競爭規(guī)則中，固定參數(shù)設(shè)置會影響算法的局部“開采”和全局“勘探”能力，因此設(shè)計(jì)自適應(yīng)優(yōu)化參數(shù)[12]，使算法更好地求解車間調(diào)度問題。

帝國同化殖民地操作中，式(9)的k1和k2影響帝國對殖民地的同化。迭代初始階段，為保證群體基因的多樣性，設(shè)置參數(shù)k1較大，有助于殖民地進(jìn)行區(qū)域搜索。隨著迭代次數(shù)的增加，為保證收斂速度，使參數(shù)k2變大，有助于群體全局搜索。

帝國競爭過程中，通常設(shè)置一個競爭概率μ(0<μ<1)，然后由代碼中的rands函數(shù)產(chǎn)生一個隨機(jī)數(shù)與其比較，當(dāng)隨機(jī)數(shù)小于μ時(shí)才進(jìn)行帝國競爭。μ的大小取值對算法的收斂速度和尋優(yōu)搜索能力有很大影響：如果μ取值過大，則帝國競爭激烈，弱勢帝國迅速減弱直至消亡，結(jié)果會導(dǎo)致帝國個數(shù)減少，算法的收斂速度過快，群體多樣性降低，容易陷入局部最優(yōu)；如果μ取值過小，則帝國競爭相對緩和，各帝國之間交流少，全局搜索能力下降，難以體現(xiàn)帝國競爭算法的關(guān)鍵核心。所以，算法對μ進(jìn)行自適應(yīng)調(diào)節(jié)設(shè)置：即迭代初期μ取值較小，削弱帝國競爭，提高鄰域搜索能力；迭代中后期，μ不斷增大直至為0.5，增加帝國之間交流并加速迭代收斂。

2.2.2 多變異改革策略

柔性車間問題具有高維復(fù)雜性，為防止ICA陷入局部最優(yōu)，基于生物進(jìn)化思想提出殖民地與帝國雙改革的優(yōu)化，針對車間調(diào)度編碼特性提出多種改革方案[13]。為保證基本ICA流程中的同化與競爭機(jī)制，設(shè)計(jì)的雙改革在競爭機(jī)制之后，且只保留優(yōu)秀個體。

兩種工件工序排列改革：

A1 隨機(jī)選取一段工序，重新分配工序順序；

A2 隨機(jī)選取x個位置，交換位置基因。

結(jié)合雙層編碼結(jié)構(gòu)，針對不同F(xiàn)JSP側(cè)重點(diǎn)，提出三種使用機(jī)器基因的改革：

B1 完全繼承原始使用機(jī)器基因；

B2 所有機(jī)器基因全部重新分配；

B3 被調(diào)整的工序的機(jī)器基因重新分配。

上述變異可產(chǎn)生6種改革方案：在算法初始階段波動大，需要對其全局“勘探”能力優(yōu)化，殖民地和帝國imp采用A1與B2/B3結(jié)合的改革方案；在迭代中期為加速收斂和提高搜索能力，采用A1/A2與B2/B3的改革方案；迭代后期，帝國與殖民地相似程度高，變異改革幅度與對結(jié)果影響成反比采取A2與B1/B3方案，加強(qiáng)局部“開采”能力，保證最優(yōu)解的相對穩(wěn)定性。

2.2.3 協(xié)作帝國算法

柔性車間調(diào)度是非線性多局部極值的問題，為此提出協(xié)作混合帝國競爭算法[14-15]。相當(dāng)于幾個大陸內(nèi)部帝國不斷競爭，大陸之間某些帝國簽訂一份公約，它們相互幫助共同獲利。單獨(dú)的大陸的內(nèi)部帝國競爭隨著迭代次數(shù)增加會喪失部分“勘探”能力，大陸公約制度會傳遞一些交流因子——優(yōu)秀的帝國編碼基因，帝國會與另一個大陸上的勢力弱些的帝國進(jìn)行交叉變異，或者取代實(shí)力最弱的帝國。對多個大陸之間全局最優(yōu)進(jìn)行比較，并根據(jù)目標(biāo)函數(shù)去保留優(yōu)秀的基因。這種交流機(jī)制能有效地促進(jìn)算法的尋優(yōu)，從而使各個大陸上的帝國相互協(xié)助，共同進(jìn)化。

2.2.4 協(xié)作混合帝國算法流程

以最大完工時(shí)間最小化為目標(biāo)值，結(jié)合上述對帝國算法的3種改進(jìn)優(yōu)化，算法最終流程如圖2所示。

圖2 協(xié)作混合帝國算法流程

圖2中需要指出的是，在理想情況下，經(jīng)過若干次迭代，各大陸統(tǒng)一，即各大陸僅存在一個帝國，此時(shí)算法達(dá)到終止條件。而在實(shí)際應(yīng)用中，帝國之間不斷競爭會導(dǎo)致幾個國家勢力相近，并始終存在直至達(dá)到規(guī)定的迭代次數(shù)才結(jié)束算法。

3 調(diào)度實(shí)例仿真

為驗(yàn)證本文提出的協(xié)作混合帝國算法對柔性車間調(diào)度的有效性和優(yōu)越性，選取側(cè)重點(diǎn)不同的6個FJSP實(shí)例運(yùn)用Matlab工具進(jìn)行實(shí)驗(yàn)研究。實(shí)驗(yàn)平臺為：Windows 7系統(tǒng)，內(nèi)存4 GB，處理器i5-CPU 3.3 GHz。

3.1 針對自適應(yīng)參數(shù)的結(jié)果改進(jìn)對比

選取車間實(shí)例模型為：10臺機(jī)器，6個工件，每個工件6個工序，共36個工序。該FJSP側(cè)重工件工序排列。表1為工件工序?qū)?yīng)可以使用的機(jī)器；表2為工件工序?qū)?yīng)使用的機(jī)器花費(fèi)時(shí)長。

自適應(yīng)參數(shù)ICA與一般ICA和改進(jìn)遺傳算法比較。實(shí)驗(yàn)參數(shù)：國家(種群)規(guī)模為100，帝國個數(shù)為10，帝國同化率為0.8，迭代次數(shù)為300。自適應(yīng)參數(shù)設(shè)置為：第1～50次，k1=0.9，k2=0.1，μ=0.1；第51～100次，k1=0.8，k2=0.2，μ=0.2；第101～150次，k1=0.7，k2=0.3，μ=0.3；第151～300次，k1=0.6，k2=0.4，μ=0.5。實(shí)驗(yàn)獨(dú)立運(yùn)行10次。記錄算法最優(yōu)值(Best)、平均值(Mean)和標(biāo)準(zhǔn)偏差(STDEVP)。

表1 工件工序?qū)?yīng)使用機(jī)器

表2 工件工序?qū)?yīng)的機(jī)器工作時(shí)間

由表3得出，對于6×10問題，3種方法均可以求出最優(yōu)解；但是從平均值和標(biāo)準(zhǔn)偏差的數(shù)據(jù)看，相比標(biāo)準(zhǔn)ICA和GA，自適應(yīng)參數(shù)改進(jìn)的ICA的平均值更好，穩(wěn)定性更高，由此證明自適應(yīng)參數(shù)改進(jìn)對柔性車間調(diào)度有較好的影響。其中：t指的是所有工件工序加工完成后的總時(shí)間(無實(shí)際單位)。圖3為此6×10調(diào)度的甘特圖。

表3 自適應(yīng)ICA與其他算法測試結(jié)果比較

3.2 針對多變異改革改進(jìn)的結(jié)果對比

由文獻(xiàn)[16-19]提出的4個實(shí)例：4×6、8×8、10×10和15×10，該類FJSP側(cè)重工件工序使用機(jī)器的選取。設(shè)置算法基本參數(shù)為：國家(種群)是100，迭代300次。多變異改革策略設(shè)置如表4所示。

實(shí)驗(yàn)獨(dú)立運(yùn)行10次，將變異改革策略ICA與文獻(xiàn)[16]的改進(jìn)蟻群、文獻(xiàn)[17]的兩級遺傳算法、文獻(xiàn)[18]的IPSO(Improved Particle Swarm Optimization)和文獻(xiàn)[19]的多規(guī)則遺傳進(jìn)行比較，結(jié)果記錄于表5(最優(yōu)值/平均值)。

由表5得出，算法對于4個柔性車間調(diào)度均可以取得最優(yōu)值；但是由于4個實(shí)例中對工序機(jī)器選擇權(quán)有較大范圍，一般的種群變異不能有效尋求到最合適的使用機(jī)器，導(dǎo)致求解質(zhì)量下降。而本文提出的變異改革策略針對ICA和車間調(diào)度流程設(shè)計(jì)，可以進(jìn)行高效區(qū)域搜索，從表5中結(jié)果也可以看出其求解質(zhì)量穩(wěn)定性較高。圖4為以上4個柔性車間問題的最優(yōu)調(diào)度甘特圖。

圖3 6×10算例甘特圖

Tab. 4 Multi-mutation reform strategy

表5 多變異改革ICA與其他算法測試結(jié)果比較

3.3 協(xié)作混合帝國算法

前面提到的5個實(shí)例，F(xiàn)JSP的側(cè)重點(diǎn)不同，相對應(yīng)的改進(jìn)也不同。為了進(jìn)一步貼合實(shí)際驗(yàn)證提出的協(xié)作混合帝國算法求解FJSP的有效性和穩(wěn)定性，采用文獻(xiàn)[20]的車間實(shí)例模型：8臺機(jī)器6個工件，共26道工序?；A(chǔ)參數(shù)與其保持一致，即：種群總規(guī)模為100，并設(shè)置15個帝國。

為體現(xiàn)協(xié)作混合帝國算法的優(yōu)越性，按照文獻(xiàn)[20]要求將協(xié)作混合帝國算法獨(dú)立運(yùn)行30次，并與文獻(xiàn)[21]的改進(jìn)雙層粒子群優(yōu)化(Improved Two-Layer Particle Swarm Optimization, ITLPSO)算法、文獻(xiàn)[22]的改進(jìn)量子粒子群優(yōu)化(Opposition-Based Learning Quantum-behaved Particle Swarm Optimization with Bounded mutation, OBL-QPSOB)算法、文獻(xiàn)[20]的骨干雙粒子群優(yōu)化(Double Bare Bones Particle Swarm Optimization, DBBPSO)算法進(jìn)行比較。圖5為協(xié)作混合帝國算法的30次收斂曲線。表6為測試結(jié)果記錄算法最優(yōu)值(Best)、平均值(Mean)。

表6 協(xié)作混合帝國算法與其他算法測試結(jié)果比較

由文獻(xiàn)[20]得知3種改進(jìn)粒子群算法每次迭代4 000次，且只有DBBPSO存在解收斂于最佳值53。對比圖5協(xié)作混合帝國算法的30次平均結(jié)果收斂圖，其具有較高的收斂速，(迭代1 000次后不會出現(xiàn)明顯變異，即本算法只迭代1 000次)，而且多數(shù)平均值都收斂于最優(yōu)值附近，具有較高收斂精度和穩(wěn)定性。同時(shí)表6中數(shù)據(jù)也可以表明協(xié)作混合帝國算法求解結(jié)果的質(zhì)量和穩(wěn)定性均為最優(yōu)。圖6顯示一組最優(yōu)解對應(yīng)調(diào)度甘特圖。

圖4 4個實(shí)例的甘特圖

圖5 協(xié)作混合帝國算法的平均結(jié)果收斂曲線

4 結(jié)語

針對求解柔性車間調(diào)度(FJSP)算法的易早熟與波動性大的問題，提出一種協(xié)作混合帝國算法。該算法為增強(qiáng)全局“勘探”能力和局部“開采”能力，提出自適應(yīng)參數(shù)、多變異改革策略和協(xié)作交流機(jī)制3種改進(jìn)方式。通過對6個柔性車間調(diào)度實(shí)例仿真對比，結(jié)果可以證明所提改進(jìn)算法具有區(qū)域探索能力強(qiáng)易于尋最優(yōu)值、收斂速度快、求解結(jié)果穩(wěn)定性高的特點(diǎn)，對實(shí)際調(diào)度生產(chǎn)問題具有一定指導(dǎo)作用；但是，本文僅探究單目標(biāo)的FJSP求解，后續(xù)工作將會運(yùn)用協(xié)作混合帝國算法求解多目標(biāo)FJSP。

圖6 車間實(shí)例[20]模型調(diào)度甘特圖