基于機器故障的車間調度研究

靳彬鋒，畢 利，李 浩

（寧夏大學 信息工程學院，銀川 750021）

0 引言

柔性作業車間調度問題（flexible job-shop scheduling problem，FJSP）考慮了工件工序調度和機器選擇的問題，貼近現實的生產過程，有著重要的應用意義和研究價值[1～5]。在實際的工業生產中，不可預知的事件隨時有可能發生，比如緊急插入新的加工工件、原材料短缺或加工機器故障等事件，均會影響生產調度的結果。本文針對加工過程中的機器故障問題，給出了一種基于粒子群算法（particle swarm optimization，PSO）的優化策略。

近些年來，動態的FJSP引起眾多學者的關注。高俊宇等[5]就動態車間調度與靜態車間調度進行比較，列出動態車間調度問題的干擾種類。陳勇等[6]考慮到加工參數的非確定性和動態擾動等因素，將模糊概念引入到調度模型中，并利用GA算法進行求解。李平等[7]結合工序碼和機器碼構造了一種雙層染色體編碼的遺傳算法用于解決三種常見擾動類型的動態車間調度問題。李素粉等[8]針對流水車間調度問題的三種情況進行研究，通過預測機器的期望故障來進行計算。Maroua Nouiri等[9]提出了用兩階段粒子群算法求解動態柔性車間調度問題。劉愛軍等[10]將動態調度分為基于周期的調度、基于事件的調度和基于周期和事件的混合調度。

上述文獻都對車間調度中加工機器故障的問題提供了解決方法，但研究重新調度方法的執行效率和對機器發生故障的概率預期還很少，即加工過程中機器發生故障的概率，以及故障發生時，對相應故障機器上待加工工件的重新調度安排效率的評價。本文設置了穩定性指標對重調度方法的效率進行評價，穩定值越高，說明重新調度的安排對初始化調度的安排影響越小，對優化目標的影響越小，調度效果越好。同時計算加工機器發生故障的概率，對于概率值越大的機器，被選擇的概率越低，以保證調度的順利進行。粒子群算法根據自己的速度來決定搜索位置，收斂速度快[11]。但也具有容易陷入局部最優和早熟問題的缺點，本文提出“淘汰”機制，將部分位置較差的粒子淘汰掉并重新生成相同數量的粒子作為補充，避免了算法陷入局部最優和早熟的問題。

1 柔性作業車間調度問題

1.1 FJSP的數學描述

FJSP可描述為：一組工件序列job={job1，job2，…，jobn}在一組機器序列machine={m1，m2，…，mm}上進行加工。其中每個工件jobi有多步工序。初始化調度的目標就是將工件的工序合理的分配到各個機器上去，在滿足相關前提條件下使得目標函數達到最優。具體的假設如下所示：

1）調度開始時，每臺機器都可以被使用，即當時間t=0時，每臺機器都可以被使用。

2）調度開始時，任一待加工工件的第一步工序都可以被加工，即當t=0時，每個工件都可被加工。

3）每種待加工工件的任一工序在可用機器上的加工時間是確定的。

4）同一待加工工件的所屬工序是有先后順序約束的。

5）工件的加工時間應當包括該工件在機器上的準備時間和加工時間。

6）在相同時間內，每個待加工工件能且僅能在一臺可用機器上加工。

7）在相同時間內，可用機器最多只能加工待加工工件的一道工序。

8）從前一個加工機器運輸到下一個加工機器的運輸時間是確定的。

1.2 符號說明

i：工序的自變量；

j：工件的自變量；

k：機器的自變量；

n：工件的數量；

nj：工件j的工序的數量；

m：機器的數量；

cj：工件j的完工時間；

Oij：工件j的第i道工序；

tijk：工序Oij在機器k上的加工時間；

Xijk：如果工序Oij在機器k上加工，則Xijk=1，否則0；

Sijk：工序Oij在機器k上的開始加工時間；

Eijk：工序Oij在機器k上的完成時間；

T*：最優調度方案的最大完工時間；

MBk：第k臺機器的動態（工作狀態）損耗率；

MFk：第k臺機器的靜態（閑置狀態）損耗率。

1.3 約束條件

1.3.1 時間約束

cj＞0。工件j的加工時間必須大于0。

tijk＞0。工序Oij在機器k上的加工時間必須大于0。

S0jk≥0并且Sijk≥0。工件j在機器k上開始加工第一道工序O0j時，S0jk不能為負數，同時工件j在機器k上開始加工Oij時，Sijk必大于0。

Eijk≤F1。工件j在機器k上完成加工工序Oij時，Eijk小于等于F1。

1.3.2 資源約束

式(1)表示工序Oij在機器序列1，2，…，m中有且只有一次被選中的機會，同時每一次選中的總和即為工件j的工序數量nj。

1.3.3 費用約束

MBk＞0并且MFk＞0。機器損耗必須大于0。

1.4 目標函數

本文選取的三個目標為：最小化最大完工時間，最小成本和機器最大負荷。具體如下：

1）最大完工時間：

2）最低成本:

3）機器最大負荷：

2 面向機器故障的重新調度方法

2.1 關于FJSP的機器故障描述

面向機器故障的重新調度方法是在初始化調度的基礎之上，考慮到機器在長時間的使用過程中發生故障的可能性較高一些，因此將機器故障作為擾動因素（不可預知發生時間）。重新調度方法需要對這種突發事件具有較好的優化處理能力。本文主要研究機器發生故障時，通過重新調度方法盡量減少故障對生產調度過程的影響。

假設在加工過程中，時間為t時某機器發生故障，則對應的最大完工時間如式(8)和式(9)所示：

式(9)中r表示發生故障的機器個數。

對應的加工成本如式(10)、式(11)和式(12)所示：

2.2 基于機器故障的重新調度策略

在柔性車間調度中，每一道工序可以由多個機器進行加工。因此當某臺機器發生故障時，首先將故障機器的修復時間與重調度時間進行比較，如果機器的修復時間小于重調度時間則等待機器的修復然后繼續執行之前所做的初始化調度表。如果修復時間大于重調度的時間，那么運用改進的粒子群優化算法對所有受影響的工序進行重排列（故障節點之后的所有未加工的工序）。故障修復時間是從機器發生故障時的時刻t1開始到該機器修好加入調度時刻t2的時間間隔T1。重新調度時間是從機器發生故障時的時刻t1到調度計劃重新排程完畢的時刻t3的時間間隔T2。具體流程圖如圖1所示。

圖1 重新調度策略流程圖

2.3 穩定性指標

其中robustness指的是穩定性。Freschedule為機器發生故障時重調度所花費的時間，Fschedule為初始化調度所花費的時間，robustness的值越大則說明重調度的效果越好。

2.4 機器發生故障的概率

車間調度過程中機器發生故障的概率Mfr由品牌參數、機器使用率和使用年限共同決定。

式(14)中，γ1（γ1＞1）表示品牌參數，即機器所屬制造商的品質信譽，值越大表示該機器的品質信譽越好。γ2（0 ＜γ2＜ 1）表示機器使用率的權值，機器使用率是某單一機器在整個調度過程中的工作時間占全部調度時間的比例。γ3（0 ＜γ3＜ 1）表示機器使用年限Y的權值，即機器按照使用年限進行相應的比率折舊。

3 改進的粒子群優化算法

3.1 粒子編碼

算法采用整數編碼對所有粒子進行離散化表述。粒子的編碼長度由兩部分組成，分別是待加工工件的工序編碼部分和加工機器編碼。工序編碼的長度取決于工件的種類以及每種工件的所屬工序數量。如果有p種待加工工件，每個工件有nj個工序，則工序編碼的長度為：

加工機器編碼的長度與工序編碼的長度一致且與工序編碼的位置一一對應，即粒子的長度為length×2。

以表1所示的一個加工序列為例。

表1 3×3的調度問題

從表1中我們可以得到待加工工件序列、加工機器序列和每個待加工工件的工序，其中待加工工件序列為J=[J1、J2、J3]和可供選擇的加工機器組M=[M1、M2、M3]。第一行第一列的M1/M2表示工件J1的工序1只能在機器M1和M2上進行加工，然后根據機器發生故障的概率進行選擇。由此，我們可以得到一個初始解即一個粒子的編碼：

X=[1 2 1 3 2 3 1 3 2 2 3 1 3 2 2 3 1 1]

該粒子的長度為18，然后對該粒子進行拆分，前一部分即從第一位到第九位為待加工工件的工序編碼，后一部分即從第十位到第十八位為加工機器的編碼。具體如下所示：

工件的工序編碼： Xi= [1 2 1 3 2 3 1 3 2]

加工機器編碼： Xm =[2 3 1 3 2 2 3 1 1]

解碼過程分別對應工序和機器。首先看待加工工件的工序編碼序列Xi，“1”、“2”、“3”分別出現了三次，表示待加工工件J1、J2和J3的加工工序都有三步。以J1舉例說明，“1”出現的第一次表示待加工工件J1的第一道工序，“2”出現的第一次表示待加工工件J2的第一道工序，“1”出現的第二次表示待加工工件J1的第二道工序。以此類推即可得到所有相對應的操作序列。

再看加工機器編碼序列Xm，“1”、“2”、“3”分別出現了三次，表示加工機器M1、M2和M3各被使用了三次。以M1舉例說明，“1”出現的第一次表示待加工工件J1的第二道工序在加工機器M1上加工，“1”出現的第二次表示待加工工件J3的第三道工序在加工機器M1上加工，“1”出現的第三次表示待加工工件J2的第三道工序在加工機器M1上加工。以此類推即可知道“2”和“3”所代表的實際意義。

3.2 粒子位置和速度的更新

在標準的粒子群算法中，粒子在空間中搜索的速度和位置的更新公式如下：

其中w為慣性常數；r1、r2為加速常數（或者加速因子）用來調節學習的步長，r1為自我學習因子，r2為群體學習因子；為區間[0,1]上均勻分布的隨機數；是粒子i在第k次迭代中的第d維的位置；是粒子i在第k次迭代中的第d維的個體最優的位置，是群體在第d維的全局最優的位置。是為防止粒子飛出解空間，需要限制

3.3 算法的改進

粒子群算法的位置更新是通過粒子的慣性、全局搜索能力和個體記憶三部分組成，分別由慣性常數w，自我學習因子r1和群體學習因子r2三種參數共同來影響。因為慣性常數w的存在，粒子可以搜索未知的區域。算法開始時粒子具有較快的收斂速度，隨著迭代的進行，部分粒子進入局部最優解，其他粒子可能會受到影響從而導致解集收斂至局部最優的位置。另外，粒子在最優解附近時，若“速度”過快會導致粒子在最優解附近震蕩，使得收斂速度過慢或無法收斂。基于以上兩點不足，本文引入“淘汰”機制，經過每一次迭代，將位置較差的粒子淘汰掉用以保持種群整體的優越性，每輪迭代淘汰10%的粒子。同時為了保證種群的規模，每次淘汰結束以后都會加入等量的新生成的粒子。針對最大完工時間最小化的目標，算法描述如圖2～圖7所示。

圖2 種群初始狀態

圖3 種群迭代變化

圖4 淘汰粒子

圖5 插入粒子

圖6 種群迭代變化

圖7 最終結果

圖中，中心的小圓圈的范圍是所要求的最優解集的邊界范圍；橢圓形是淘汰適應度值低于要求的解的邊界范圍，隨著迭代次數的增加，該范圍會逐步縮小；矩形框為所求問題的邊界范圍。圖2為種群的初始狀態，所有的個體都隨機分布在矩形范圍之內，每個個體都有速度慣性、個體最優（pbest）和全局最優（gbest），所有的粒子根據適應度來改變自己的位置，一次迭代后如圖3所示，將所有在橢圓形范圍之外的個體全部淘汰掉，如圖4所示，以保證種群的優越性。同時，為了保證粒子的多樣性，避免粒子都被淘汰掉，在每一次迭代過程中重新生成與淘汰數量相同的粒子并將其加入種群中，如圖5所示。再次根據適應度的值改變每個個體的位置并將橢圓形外的那些位置較差的粒子淘汰掉，如圖6所示，反復進行淘汰、生成和加入，直至達到最大迭代次數，將中心的圓形范圍內的粒子取出即為所求問題的最優解集，如圖7所示。

3.4 算法流程圖及步驟

改進的算法流程圖如圖8所示。

圖8 改進的粒子群算法的流程圖

具體步驟如下：

Step1：初始化粒子群種群；

Step2：得到初始粒子群的適應度以及個體最優pbest和全局最優gbest；

Step3：對粒子的位置和速度更新；

Step4：計算該粒子的適應度；

Step5：判斷所有的粒子是否完成更新操作，若完成則進行Step6，否則返回step2；

Step6：更新個體最優解和全局最優解；

Step7：將位置較差的粒子淘汰，并將新產生的粒子加入種群中；

Step8：判斷是否滿足終止條件，若滿足則終止算法，gbest為最優解，若不滿足則返回Step2。

4 實驗結果

本文使用的計算機操作系統為Windows 7，處理器為Intel（R） Core（TM） i7-3632QM，內存為8G。利用Matlab2014b仿真平臺對改進的粒子群算法進行仿真模擬實驗，結果如下：

本文分別使用3×4、8×8和10×15三種不同規模的FJSP進行仿真實驗。算法參數經梯度下降法[12]實驗后設置為：種群數量200，迭代次數200次，速度范圍設置v=[-2,2]，慣性常數w=0.15，r1=0.5，r2= 0.7。實驗獨立運行20次取平均值，結果如表2所示。

表2 算法實驗比較

從表2中可以看出，針對不同規模的FJSP，改進的粒子群算法和標準的粒子群算法相比，目標函數求解均有提升。得到的非劣解集仿真結果如圖9～圖10所示。

圖9 標準PSO的非劣解集

圖10 改進的PSO的非劣解集

本文選擇8×8的調度問題進行求解，其中每個工件有3個工序，如表3所示，其中“-”表示該道工序在該機器上無法進行加工。

表3 實驗的原始數據

根據表3提供的數據，采用改進的粒子群優化算法進行初始化調度，得到的甘特圖如圖11所示，最大加工完成時間為42個時間單位。

圖11 改進PSO求解所得甘特圖

現在假設機器3在時間點為16時刻時發生故障。得到的傳統解決機器故障的重調度甘特圖如圖12所示。

圖12 傳統機器故障調度甘特圖

圖12中，機器故障的持續時間為51個單位時間，最大加工完成時間由初始化調度的42個時間單位增加到86個時間單位。

同時對受影響的工序利用改進的粒子群算法進行重新調度，得到的甘特圖如圖13所示。

圖13 改進PSO求解機器故障甘特圖

圖13中，最大加工完成時間從86個時間單位縮短到36個時間單位，優化效果明顯。

5 結束語

應用PSO算法求解含有機器故障的FJSP，首先在粒子群算法中引入“淘汰”機制來彌補粒子迭代過程中容易陷入局部最優和早熟的不足，然后根據重新調度方法對加工過程中的機器故障問題進行優化處理。最后通過仿真實驗對比，證明了改進的粒子群優化算法求解柔性車間調度問題的優越性，對實際生產具有一定的理論意義。同時通過進行故障模擬實驗，結果表明本文提出的重新調度策略可以有效的解決具有機器故障的柔性車間調度問題。

由于數據的有限性，還不足以對機器的各類參數進行細化，需要在今后的研究中進行優化。