改進粒子群算法求解分布式柔性車間調度問題

陳 強，王宇嘉，林煒星，陳萬芬

(上海工程技術大學 電子電氣工程學院,上海 201620)

隨著經濟全球化的不斷加深和市場競爭的日益嚴峻，傳統的單一車間制造模式已經無法滿足我國制造業的生產需求，分布式生產制造模式已經成為企業提高生產競爭力的重要手段。由于不同工廠之間存在著技術水平、機器數量、物料運輸等無法避免的差異，采用有效的分工協作方式使企業高效地生產出高質量產品成為當前的研究熱點。

分布式柔性車間調度問題(Distributed Flexible Job-shop Scheduling Problem，DFJSP)是車間調度問題的一種特例。由于在工件分配過程中，要同時考慮到工件到不同工廠之間的分配以及工序在加工機器之間的分配，因此其具有更高的復雜度和求解難度。

DFJSP的概念于2006年被文獻[1]提出，該研究使用基于支配基因策略的遺傳算法求解最小化最大完工時間(Makespan)。文獻[2]以最小化最大完工時間為調度目標，提出一種遺傳算法來求解DFJSP，在選擇階段對個體進行基于完成工期的排序，然后選取應用于交叉階段的染色體。文獻[3]提出了一種混合遺傳算法求解DFJSP，同樣以最小化最大完工時間為調度目標。文獻[4]提出了一種改進的人工蜂群算法來求解DFJSP，其編碼方案采用了三維向量編碼即工序排列向量、柔性加工單元(Flexible Manufacturing Unit，FMU)選擇向量和加工設備選擇向量，在跟隨蜂的操作中，引入了基于關鍵路徑的局部搜索算子。文獻[5]在解決DFJSP時，提出了一種新型的編碼方式，將一維染色體轉換成精確的三維解，有效減少了計算量。文獻[6]在解決DFJSP時，將K-means和混合蛙跳算法同蟻群算法相結合，通過判斷蟻群所處的狀態，動態調整蟻群的參數。文獻[7]將組合拍賣機制與蟻群算法相結合來求解DFJSP，提高了工件的生產效率。

目前，對于DFJSP的研究相對較少，大部分研究者都是采用的遺傳算法或蟻群算法來解決該問題。然而該類算法參數設置復雜且容易陷入局部最優，導致無法得到一組較滿意的結果，因此本文提出一種更高效的優化算法來解決復雜的DFJSP。其次，在構建DFJSP數學模型時，大部分文獻都將其簡化為一個以Makespan為調度目標的單目標優化問題。然而，將該問題過于簡單化并不能很好地描述出實際生產情況。粒子群算法(Particle Swarm Optimization，PSO)[8]是通過研究鳥群覓食規律而發展起來的一種群智能優化算法，其結構簡單、收斂速度快、精度高，被廣泛應用于各個領域[9-11]。粒子群算法也同時被成功地應用到車間調度問題中[12]。因此，本文采用一種改進粒子群算法IMPSO(Improved Particle Swarm Optimization)求解DFJSP。

1 分布式柔性車間調度問題

在DFJSP中，有n件工件、m臺機器和s間分布式工廠。每件工件都有自己的預定義和確定性處理工序，這些工序構造了工件一組操作。在對每一件工件分配過程中，第一個階段是將工件分配給某間工廠。在分配了某間工廠之后，工件通過預定義的階段進行處理。在每個預處理階段，都有一組用于加工工件的候選機器，這是該問題的第二個階段，即為每件工件從候選機器中選擇合適的機器。在為每件工件分配了合適的機器之后，第三個階段是在每間工廠分配的機器上調度相關工件的工序。因此，DFJSP的關鍵問題如下：(1)工件分配合適的工廠；(2)工件分配合適的機器；(3)在合適的機器上確定所有工序的加工順序。

調度過程中遵循的分配原則如下：(1)每臺機器每次只能處理一道工序；(2)每道工序只能在其前一道工序處理完成之后才能處理；(3)每道工序只能在一臺機器上處理；(4)任意一件工件分配到某一工廠時，其所有工序只能在這同一工廠內加工處理；(5)所有工序要全部加工完成后，生產活動才能停止；(6)工件在工廠內部的運輸時間忽略不計；(7)機器的加工時間是連續的。

為了方便表述DFJSP，表1給出了構建數學模型所用的符號及其定義。

表1 符號及其定義

通過以上信息，建立如下的3目標數學模型：

(1)最大完工時間(Makespan)，該目標保證了加工所有工件總的用時最短

f(1)=max(Cp|p=1, 2, …,n)

(1)

(2)機器最大負載，該目標強調了機器之間要保持負載平衡

f(2)=max(wk|k=1, 2, …,m)

(2)

(3)機器總負載，該目標保證了所有機器總的負載量要小

f(3)=T

(3)

綜上所述，DFJSP的數學優化模型如式(4)所示。

min(F)=min(f(1),f(2),f(3))

(4)

2 任務分配策略的粒子群算法

2.1 粒子的編碼與解碼

DFJSP是離散優化問題，而PSO算法一般解決的是連續優化問題，因此在求解之前要確定粒子的編碼與解碼方案。

操作向量(OS)為基于工序的編碼，用來確定工序Opj的先后加工順序。

機器向量(MA)為基于機器的編碼，用來確定每道工序分配的加工機器。

表2給出了一個可行的粒子編碼的表達式。

表2 粒子編碼的表達式實例

其中，該實例共有兩個工廠，且每個工廠含有3臺機器。從表2中可以看出粒子的維度為2×l=22，粒子位置可表示為(OS,MA)，OS可以解釋為工序的加工順序為(O21→O41→O11→O31→O42→O32→O12→O22→

M12→M21)。

種群粒子在迭代過程中，根據速度更新式和位置更新式，生成新的粒子。然而新粒子的位置不一定是有效的整數。因此需要對新粒子的位置進行調整。首先對粒子位置進行四舍五入和邊界限制，使新生成的粒子轉換為有效的整數。然后，判斷粒子的OS值，對所有的工序進行多余和缺失的查找，并將多余的工序轉變為缺失的工序。接著遵循以下原則對粒子中的MA進行調整：(1)少數服從多數原則。當某工件被不同的工廠加工時，分別計算不同工廠中加工該工件的工序個數，通過該原則將該工件中的工序從較少的工廠中轉移到較多的工廠；(2)當不滿足上條原則時，采用后到服從先來原則，即當某工件的工序平均被不同的工廠加工，則排位靠后的工序要轉移到前面工序所在的工廠中。通過上述的兩個原則可將新粒子中多余的部分轉化成缺少的部分。最后，判斷所有工序是否在可行的機器上被加工，若不在，則隨機從該工廠選取可行的機器作為該工序的加工機器。通過以上所有操作，新粒子就轉換成得到一組可行解。

2.2 任務分配策略

粒子的任務分配策略使用文獻[13]給出的計算方法。

勘探任務：在勘探過程中，粒子的速度和位置的更新式如式(5)和式(6)所示。

vid(t+1)=ωvid(t)+c1r1(Xid-xid(t))+c2r2(Xgd(t)-xid(t))

(5)

xid(t+1)=xid(t)+vid(t+1)

(6)

式中，ω表示權重向量；c1和c2表示學習因子；r1和r2表示(0,1)的隨機數；Xid和Xgd分別表示個體最優位置和群體最優位置。

開采任務：反向學習是一種區間收斂的算法，將其應用到開采任務中，可以更好地發揮種群精確收斂的作用。本文應用文獻[14]給出的反向學習策略作為粒子的更新策略，計算式為

(7)

2.3 改進擁擠距離

對于傳統的擁擠距離，僅僅能夠計算某點到上下兩點之間的歐式距離，無法區分該點的位置關系。如圖1所示，數字表示位置，字母表示粒子，在圖1(a)和圖1(b)中，根據原有擁擠距離計算可得B點的擁擠距離相等。然而，圖1(a)的B點位置的分布性劣于圖1(b)中的B。因此，本文采用式(8)計算擁擠距離

(8)

式中，distanceid表示第i粒子的第d維擁擠距離；disd表示在第d維上第i-1和i+1兩粒子之間的歐式距離；d1和d2分別表示第i-1和i+1兩粒子分別到第i個粒子之間的歐式距離。從圖1可以進一步看出，圖1(a)中B點的擁擠距離小于圖1(b)中B點的擁擠距離。對比圖1(a)中B和圖1(c)中的B，通過式(8)可得，圖1(c)中B的擁擠距離好于圖1(a)中的B。從中也可以看出，對于距離大但分布性不好的個體，其擁擠距離仍有可能小于距離小但分布性好的個體。

圖1 擁擠距離示意圖

對于邊界粒子，設置擁擠距離為無限大。

通過上述分析可以看出，本文提出改進的擁擠距離可以有效地克服傳統擁擠距離無法解決的問題。

3 算法流程

圖2 IMPSO算法流程圖

下面為算法詳細步驟：

步驟1參數設置，依據調度規則，種群初始化；

步驟2根據粒子的編碼與解碼方式，計算初始化種群的適應度值，同時根據Pareto支配策略產生非支配解。若非支配解的個數大于外部檔案的大小，則通過改進擁擠距離從非支配解中選出部分非支配解存入外部檔案中，否則直接將非支配解存入外部檔案；

步驟3更新個體最優粒子和全局最優粒子，隨機從外部文檔選取全局最優粒子；

步驟4粒子執行任務分配策略，并對新生成的粒子進行編碼與解碼，計算適應度值，更新個體最優粒子和全局最優粒子；

步驟5選取部分粒子執行多項式變異操作；

步驟6對變異后的粒子進行編碼與解碼操作，更新種群個體；

步驟7將外部文檔粒子與種群粒子合并，通過Pareto支配選取非支配解，若非支配解的個數大于外部檔案的大小，則通過改進擁擠距離從非支配解中選出部分非支配解存入外部檔案中，否則直接將非支配解存入外部檔案；

步驟8判斷算法是否滿足停止條件，若條件滿足，算法停止迭代，否則轉到步驟4。

4 實驗結果與分析

4.1 測試算例

目前對于分布式柔性車間調度問題，仍沒有標準的測試算例，因此本文使用的算例DMK01-DMK10是通過經典的柔性車間調度算例MK01-MK10[15]改進而來的。所有的測試算例分別在2工廠和3工廠下完成生產。算例的生成規則如表3所示。

表3 算例參數

以DMK01為例，總的工件個數n表示在該算例中，需要被加工的工件。工序數量z是表示每件工件中包含的數量，其取值范圍是[5,6]中的隨機取值。機器數量m是指每個工廠中的機器數量，從[4,6]中隨機取值。可用機器數量Av是指在同一個工廠內，每道工序可使用的機器的數量。加工時間PT是指每道工序的加工時間，其取值是從[1,10]中隨機選取。運輸時間TT是指每件工件從原料產地運輸到加工工廠所花費的時間，從[5,10]中隨機選取。以上的隨機取值都取整數。

4.2 性能指標

為了測試所提算法在解決分布式柔性車間調度問題的性能，采用文獻[16]給出的平均Pareto距離Dp來評價算法的性能。其中，設S*為一組參考點，該參考點是通過所有對比算法運行3 000次迭代得到的所有非支配解個體組成的。平均Pareto距離Dp越小，算法的性能越好。性能指標的計算過程請參考上述文獻。

4.3 參數設置

將本文所得結果與NSGA-II[17]和IGASA[18]進行對比。表4給出了算法在求解該問題上的參數設置。所有算法的種群大小都為25，外部文檔大小為25，迭代次數為1 000，取平均值。

表4 參數設置

4.4 結果分析

表5 平均Pareto距離

表6給出了IMPSO算法在DMK01測試算例下得到的分配數據，在2工廠的情況下，工件4、5、7和9在工廠1被加工，工件1、2、3、6、8和10在工廠2被加工，所有工件的最小化完成時間為52，最小化機器總負載為189，最小化機器負載為34。在3工廠的情況下，工件3、5和9被工廠1加工，工件4、6和10被工廠2加工，工件1、2、7和8被工廠3加工，所有工件的最小化完成時間為40，最小化機器總負載為196，最小化機器負載為18。

表6 IMPSO在DMK01測試算例下得到的分配數據

5 結束語

本文將任務分配策略、反向學習和改進擁擠距離相結合，提出了一種改進的粒子群算法。實驗結果表明，在解決分布式柔性車間調度問題時，該算法能夠有效地提高解的收斂性和分布性。目前，隨著科技的不斷進步，制造業也在相應地發展，這就意味著分布式柔性作業車間調度問題會越來越復雜，對于該問題的研究也需要更加深入。因此，在未來的課題中將會對實際生產問題進行深入分析，從離線性問題向實時性問題轉變，建立更實用的多目標約束的數學模型。將本文所提算法應用到更復雜的車間調度問題上也將是下一步的研究重點。