柔性車間調度問題的協作混合帝國算法

呂 聰，魏康林

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

0 引言

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

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

1 柔性車間調度問題

1.1 問題描述

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

1)每個工序都具有預先可用的加工機器以及加工時間——作為實際調度前提。

2)任意工件的工序可以預先設定機器隨機選取加工——符合實際調度的目的意義。

3)工件準備時間和等待時間都記錄在加工時間內——注重整體的調度規劃結果。

4)允許工件的不同工序之間存在等待——考慮實際生產多任務分配優化。

1.2 參數設置

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

1.3 建立數學模型

根據柔性車間調度問題，建立數學模型[10]如下：

(1)

Si(j+1)k≥Eijk

(2)

Eijk-Sijk=Tijk

(3)

(4)

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

2 協作混合帝國算法

2.1 帝國競爭算法

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

2.1.1 產生初始帝國

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

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

(5)

將隨機產生的國家編碼代入式(6)中的fitness函數計算其調度時間。根據調度時間對每個國家進行強弱估值，即時間越小國家勢力越大。

Cost=fitness(Country)

(6)

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

Cm=K×max{Costimp}-Costimp

(7)

(8)

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

2.1.2 同化殖民地

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

同化操作相當于群體智能算法中的尋優過程，重在保證算法區域搜索能力。ICA優勢在于：所有殖民地群體向多個優秀個體進行遷移，增強群體中個體區域搜索能力。其同化式與粒子群的進化式相似：

PNewcol=k1×Poldcol+k2×Pimp

(9)

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

圖1 帝國同化殖民地

簡單交換會出現沖突，圖1中以帝國基因為基礎，采用部分映射的方法消除沖突。新產生的殖民地可能會超越原有對應的帝國勢力大小，像當年英國和美國關系一樣，所以需要目標函數對其進行強弱估值。如果出現殖民地比帝國強大，將該殖民地與其對應帝國進行角色替換，該殖民地成為帝國，原來的帝國依附這個新的帝國。

2.1.3 帝國競爭機制

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

(10)

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

2.2 帝國競爭算法的改進

2.2.1 自適應參數改進

在帝國競爭算法的同化操作和競爭規則中，固定參數設置會影響算法的局部“開采”和全局“勘探”能力，因此設計自適應優化參數[12]，使算法更好地求解車間調度問題。

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

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

2.2.2 多變異改革策略

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

兩種工件工序排列改革：

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

A2 隨機選取x個位置，交換位置基因。

結合雙層編碼結構，針對不同FJSP側重點，提出三種使用機器基因的改革：

B1 完全繼承原始使用機器基因；

B2 所有機器基因全部重新分配；

B3 被調整的工序的機器基因重新分配。

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

2.2.3 協作帝國算法

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

2.2.4 協作混合帝國算法流程

以最大完工時間最小化為目標值，結合上述對帝國算法的3種改進優化，算法最終流程如圖2所示。

圖2 協作混合帝國算法流程

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

3 調度實例仿真

為驗證本文提出的協作混合帝國算法對柔性車間調度的有效性和優越性，選取側重點不同的6個FJSP實例運用Matlab工具進行實驗研究。實驗平臺為：Windows 7系統，內存4 GB，處理器i5-CPU 3.3 GHz。

3.1 針對自適應參數的結果改進對比

選取車間實例模型為：10臺機器，6個工件，每個工件6個工序，共36個工序。該FJSP側重工件工序排列。表1為工件工序對應可以使用的機器；表2為工件工序對應使用的機器花費時長。

自適應參數ICA與一般ICA和改進遺傳算法比較。實驗參數：國家(種群)規模為100，帝國個數為10，帝國同化率為0.8，迭代次數為300。自適應參數設置為：第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。實驗獨立運行10次。記錄算法最優值(Best)、平均值(Mean)和標準偏差(STDEVP)。

表1 工件工序對應使用機器

表2 工件工序對應的機器工作時間

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

表3 自適應ICA與其他算法測試結果比較

3.2 針對多變異改革改進的結果對比

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

實驗獨立運行10次，將變異改革策略ICA與文獻[16]的改進蟻群、文獻[17]的兩級遺傳算法、文獻[18]的IPSO(Improved Particle Swarm Optimization)和文獻[19]的多規則遺傳進行比較，結果記錄于表5(最優值/平均值)。

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

圖3 6×10算例甘特圖

Tab. 4 Multi-mutation reform strategy

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

3.3 協作混合帝國算法

前面提到的5個實例，FJSP的側重點不同，相對應的改進也不同。為了進一步貼合實際驗證提出的協作混合帝國算法求解FJSP的有效性和穩定性，采用文獻[20]的車間實例模型：8臺機器6個工件，共26道工序。基礎參數與其保持一致，即：種群總規模為100，并設置15個帝國。

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

表6 協作混合帝國算法與其他算法測試結果比較

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

圖4 4個實例的甘特圖

圖5 協作混合帝國算法的平均結果收斂曲線

4 結語

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

圖6 車間實例[20]模型調度甘特圖