機器故障的柔性加工與裝配作業車間分批聯合調度算法

柳冬，宋豫川，楊云帆，雷琦

（重慶大學 機械傳動國家重點實驗室，重慶 400044）

作業車間調度問題(job-shop scheduling problem,JSP)最早由GAREY 提出，并被證明是一個NP-Hard 問題[1]。柔性作業車間調度問題(flexible job-shop scheduling problem,FJSP)是JSP 的拓展問題，不同于JSP，FJSP 中一道工序可在多臺機器上加工，也已經被證明為NP-Hard 問題[2]。因其復雜性、不確定性和多約束性等特點，學者一般會選用智能優化算法來求解車間調度問題，例如遺傳算法[3]、灰狼算法[4]、蟻群算法[5]等。

近年來，大量學者對FJSP 進行了深入的研究，比如石小秋等[6]以最小化完工時間為優化目標，提出一種自適應變級遺傳雜草算法求解FJSP。李明等[7]針對具有順序準備時間(sequence dependent setup time,SDST)和關鍵目標的低碳FJSP，給出了一種有效策略加強對關鍵目標優化的同時兼顧非關鍵目標的持續改進，提出了一種新型帝國競爭算法求解該問題。但是上述文獻沒有考慮到工件的批次和批量，引入批次和批量之后的FJSP 更加貼近實際，有著重大研究價值。徐本柱等[8]提出了基于工序分批調度的概念，建立了以關鍵路徑工序為中心的分批調度模型并證明了該模型的有效性。李聰波等[9]以車間總能耗最低和完工時間最小為優化目標建立了多工藝路線柔性作業車間分批優化調度模型，并采用多目標模擬退火算法對模型進行優化求解。

在實際生產中，工件的加工是制造過程的最底層，加工完成的工件需要組裝為組件再由組件組裝為成品，而無論是組件或者成品都有其物料清單(bill of material,BOM)需求。因此，把裝配過程考慮到調度問題中是有必要的。柔性裝配作業車間調度問題(flexible assembly job shop scheduling problem,FAJSP)是在FJSP 的基礎上考慮工件的裝配關系約束的更為復雜和常見的問題。在FJSP 中完工時間是指最后一個工件的最后一道工序的加工完成時間，而在FAJSP 中完工時間是指最后一個成品的裝配工序的完工時間。學者Nourali 等[10-11]最早建立了FAJSP 的混合整數規劃數學模型，并在靜態環境中以makespan 為優化目標提出一種粒子群算法進行求解。但是其并沒有考慮到動態環境因素，相比于靜態車間調度問題，動態車間調度問題(dynamic job-shop scheduling problem,DJSP)與實際的生產環境更為相似。DJSP 在靜態調度的基礎上需要考慮各種突發事件，比如機器損壞、緊急插單、工件交貨期改變或者物料延遲等，其中機器損壞是動態事件中常見的事件之一，也是本文主要研究的動態事件。針對動態調度，Zhang 等[12]提出了一種名為混合多智能體/蟻群算法(hybrid MAS/ACO,HMA)的結合了多智能體系統協商和蟻群優化的方法，并利用實驗證明了該方法在求解DFJSP 上的有效性和可行性；劉愛軍等[13]對遺傳算法進行改進并結合滾動窗口再調度技術，設計了基于事件和周期驅動的重調度策略用于解決DFJSP；Baykaso?lu等[14]利用貪婪隨機自適應搜索算法，給出了一種具有機器容量約束和建立次數依賴于序列的FJSP和DFJSP 的求解算法并驗證了其適用性。針對FAJSP 的動態調度，楊小佳等[15]考慮現實生產中存在的隨機擾動，采用了完全反應式與預測?反應式兩類動態調度策略，并提出了相應的優先度規則算法和周期性滾動遺傳算法用于求解該問題。

目前DFJSP 已有大量研究，但是考慮到工件批量和裝配因素的研究卻十分匱乏?；谏鲜龇治隹芍?，綜合考慮批量加工與裝配聯合調度的FAJSP 具有重大的研究價值，本文將該問題描述為：柔性加工與裝配作業車間分批聯合調度問題。本文以最小化最大完工時間為優化目標，在考慮機器故障的基礎上，建立了柔性加工與裝配作業車間動態調度模型，并利用改進遺傳算法進行求解。

1 問題描述與數學模型

1.1 問題描述

本文研究的是柔性加工與裝配作業車間分批聯合調度問題，包括靜態、動態調度問題，其中靜態調度問題可以描述為：給定一組待生產的產品，其裝配結構已知，同一車間中有m臺不同的加工機器用來加工工件，am臺不同的裝配設備用來裝配工件，n種工件在m臺加工機器上加工，各工件包含多道工序且工序順序固定不變，每道工序可在多臺不同的機器上加工，各道工序在不同機器上的加工時間可能不同。完成加工的工件均由裝配設備裝配，這里本文提出裝配柔性，類推工件加工柔性，即同一組件可選擇不同的裝配設備進行裝配，在不同設備上的裝配時間可能不同。調度的目標是為每一道加工工序和裝配工序分配機器與設備，使成品的最終完工時間最小。

動態調度在靜態調度的基礎上考慮到車間緊急事件的影響，系統對該事件做出應急反應。針對動態調度問題的研究來分類，可將其分為3 類：周期性重調度、事件驅動重調度以及周期性和事件驅動混合重調度[16]。本文考慮機器故障，為了及時響應動態事件，采用基于事件的重調度策略。

1.2 數學模型

本文將在以下假設說明的前提下建立上述問題的數學模型：

1)本文采用等量一致分批策略[17]；

2)一道裝配工序同一時刻只能在一臺裝配設備上進行裝配；

3)在整個調度作業過程中最多只有一臺機器發生故障；

4)機器故障后可以經過維修時長Lt后繼續投入使用；

5)機器故障時加工到一半的工件視為廢品，應取出一個新的備用工件重新加工；

6)各種工件、組件最終組裝成同一種成品。

①相關符號定義

i：工件號，i=1,2···,n。

k：加工機器號，k=1,2,···,m。

Bi：工件i的總批量。

b：加工批次號。

Bib：工件i的b批次的批量。

Oi：工件i的工序數。

j：加工工序號，j=1,2,···,Oi。

Pibj：工件i的b批次的第j道加工工序。

u：裝配設備號，u=1,2,···,am。

z：組件號，z=1,2,···,d。

c：成品號，c=1,2,···,f。

RZz、RCc：當前預組裝件z和成品c的數量。

Azu、Acu：組件z和成品c在裝配設備u上的裝配工序。

②約束條件

式(1)為目標函數，即最小化成品的最大完工時間：

式中：Cmax為最大完工時間；為成品在裝配設備u上的裝配完工時間。

式(2)為各工件各批次的加工工序之間的約束關系：

式(3)表示加工工序Pibj在同一時刻只能在一臺加工機器上加工：

式中Xkibj取值為0 或1，若Pibj在機器k上加工，Xkibj=1，否則Xkibj=0。

式(4)為劃分批次后的總工序數，pi為共件i的批次數。

式(5)表示同一時刻一臺加工機器只能加工一道工序：

式(6)表示同一時刻一臺裝配設備只能進行一道組件或成品的裝配工序：

式中：R代表 RZz或者 RCc；若裝配設備u上的A1(Azu或者Acu)先于A2加工，=1，否則=0；為工序A1的單件裝配時間。

式(7)、(8)、(9)為加工工序與裝配工序的開始時間與結束時間的計算式。

2 算法設計

遺傳算法原理簡單，通用性強，不受限制條件的約束，具有隱含并行性和全局解空間搜索能力[18]，但其缺點是容易早熟收斂。本文選用改進過后的遺傳算法解決上述NP-hard 問題，輔以鄰域搜索來增強局部搜索能力。針對本文問題特性設計出鄰域結構N1，給出一種混合型解碼方式進行求解，并在機器故障時提出相應調度策略。

2.1 編碼與初始化

染色體的編碼是遺傳算法的關鍵，良好的編碼方式會提高執行效率。本文采用MSOS 編碼方式[19]。染色體總長度為總工序數E，如圖1 所示，由兩部分組成，第一部分為基于工序的編碼，用來確定各工件各批次各工序的加工順序，從左往右第一個21 表示工件2 第1 批次的第1 道工序，以此類推；第二部分為基于加工機器的編碼，用來確定加工各道工序的加工機器。由于裝配階段的獨特性，編碼中沒有給出裝配設備號。

圖1 編碼Fig.1 Encoding

初始解的質量對算法的求解速度和質量極為重要，為提高初始解在機器選擇部分中的質量和初始種群的多樣性，使用GLR 初始化方法[20]。設置全局選擇、局部選擇和隨機選擇的比例分別為0.6、0.3 和0.1。

2.2 遺傳算子設計

2.2.1 選擇

選擇是為了使質量高的個體能以更高的幾率生存，避免有效基因的損失，從而加快全局收斂性，提高計算效率。本文使用錦標賽選擇并輔以精英保留策略，錦標賽選擇的操作方法為每次從種群中選出3 個個體進行適應度的比較，將適應度高的個體插入到交叉池，如此循環，直到填滿交叉池為止。

2.2.2 交叉

交叉是主要的遺傳操作，利用父代個體產生適應度更高的新個體，有效增加種群多樣性以保證算法的全局搜索能力。交叉的方式有很多，為避免產生非法解，工序部分采用基于工件優先順序的交叉算子[21]，基于加工機器的編碼則采用兩點交叉[22]。

2.2.3 變異

變異通過隨機改變染色體的某些基因來生成新的個體，增加種群多樣性，在一定程度上影響著遺傳算法的局部搜索能力。本文采用兩種變異算子，基于工序的編碼采用交換變異算子，即從染色體中隨機選擇兩個位置的基因，然后將它們進行位置交換；基于加工機器的編碼則采用單點變異算子，隨機選擇一個基因位置，然后生成一個不大于該位置工序可選加工機器總數的隨機整數，并將其填入所選的基因位置。

2.2.4 鄰域搜索

遺傳算法作為一種群優化算法，存在早熟和局部搜索能力差的問題。變鄰域搜索算法通過不同鄰域結構間的系統化切換，可以防止搜索陷入局部最優，增強局部搜索能力[23]。在柔性加工與裝配作業車間分批聯合調度問題中，最大完工時間為最終成品的組裝完成時間，而組件和成品的組裝開始時刻又受到零件最后一道工序完工時間的影響?；诖颂攸c，本文設計了一種針對該問題的工件末工序前移的鄰域結構N1和一種隨機的鄰域結構N2。

N1：在染色體中找到工件i的第b批次的最后一道工序，并將其向前移動到之間隨機一個位置。對所有工件的所有批次的最后一道工序都執行上述操作，便可提前進行裝配操作從而縮減最大完工時間。例如圖2 中，假設染色體c為某完整染色體片段，工件1 和工件3 的工序數均為3，將工序11 和23 的最后一道工序向前移動至其可移動范圍，則c'為移動后的一種情況。

圖2 N1 鄰域結構Fig.2 Neighborhood structure of N1

N2：隨機選擇某個零件i總數基因10%的基因，為這些基因重新分配加工機器。

2.3 基于裝配設備負載均衡的混合貪婪解碼

車間調度領域的解碼方式可以分為三大類：半主動解碼、主動解碼和全主動解碼[24]，比如傳統的貪婪解碼屬于主動解碼。由于考慮到批量裝配，而裝配設備號未編入編碼，所以單一的貪婪解碼并不適用于此問題。考慮該問題的特性并希望快速和有效的完成解碼，本文設計了一種基于裝配設備負載均衡的混合貪婪解碼，流程圖如圖3所示。

圖3 基于裝配設備負載均衡的混合貪婪解碼Fig.3 Hybrid greed decoding based on load balancing of assembly equipment

在工件加工的部分采用貪婪解碼，在裝配部分提出一種基于裝配設備負載均衡的裝配設備選擇策略，該策略步驟如下：

1)得到當前需要進行組裝的工序Azu(或者Acu)信息；

2)列出此工序所有可用裝配設備u；

3)選擇可選設備中完成該裝配工序時刻早的設備進行裝配，即u為使(或者)取得最小值的設備。

融合上述策略后，基于裝配設備負載均衡的混合貪婪解碼具體步驟為：

1)初始化參數，令基因位置g=1；

2)判斷當前基因代表的工序是否為某一工件i的最后一步工序，若是則更新工件i的完工數，寫入矩陣Gjn(i,1)，Gjn(i,1)為n×1矩陣，記錄各個工件當前已完成加工而未參與組裝的數目；更新記錄完工時間，寫入矩陣Gjt(i,b)，Gjt(i,b)為n×pi矩陣，記錄各個工件各批次加工完成的時間；否則，令g=g+1并重復步驟2)；

3)根據BOM 結構圖判斷更新完成的工件數量是否能組裝成組件z，若能則為此道裝配工序分配機器進行組裝并更新已完成的組件數，寫入矩陣Zjn(z,1)，Zjn(z,1)為d×1矩陣，記錄現有各個組件的數目，同時更新Gjn；否則直接轉步驟4)。更新Zjn和Gjn具體方法為：假設某BOM 結構如圖4，圖中括號里的數字代表組成單件成品或組件需要的組件或者工件的數量，則式(10)、(11)為更新表達式，為方便描述，用M代表括號中的數字。

圖4 BOM 結構Fig.4 BOM structure

式中RZ矩陣為對應的預裝組件數矩陣，比如在BOM 結構的前提下，式(10)中RZ與Gjn相對應，為。

4)根據BOM 結構判斷更新完成后的工件數量和組件數量是否能組裝成為成品，若能則為此道工序分配設備進行組裝并更新已完成成品數量，同時按照式(10)、(12)更新Gjn和Zjn；否則令g=g+1轉步驟2)。

式(10)、(11)、(12)中M表示一個可變參數，與參與計算的工件或者組件有關，比如Gjn(1,1)=Gjn(1,1)?中M與工件i1相關，則M=2，而Zjn(1,1)=Zjn(1,1)+中M與組件z1相關，則M=1。

2.4 機器故障發生后的調度策略

2.4.1 裝配設備發生故障

與FJSP 中的機器損壞不完全一樣，在柔性加工與裝配作業車間中除了工件加工機器可能會發生故障，用于裝配的裝配設備也存在著發生故障的可能性。由于本文引入了柔性裝配，若裝配設備發生故障，便不必停工等待設備修理，可以進行重調度，選擇其他的裝配設備進行裝配作業，盡可能縮短最大完工時間。

2.4.2 加工機器發生故障

加工機器發生故障時會面臨兩種情況：

情況一：故障時此機器處于空閑狀態；

情況二：故障時此機器正在加工某一批零件。

若為情況一，則根據靜態調度的結果，記錄當前還未完成加工的工序，在機器損壞時進行完全重調度。

若為情況二，機器損壞時正在被此機器加工的Pibj將會被分成兩個批次，一批為已經完成了此道工序加工的工件，另外一批為還未來得及完成此道加工工序的工件。此時，由于工件i的批次和批量都發生了改變，原來的染色體便不再合法，因此無法直接進行重調度。需要對染色體進行調整，加入新的基因，使重調度能夠順利進行，關于染色體的調整將結合算例1 進行具體說明，算法總流程圖如圖5 所示。

圖5 改進遺傳算法總流程Fig.5 Improved general flow of genetic algorithm

綜上，機器故障發生后的調度策略具體步驟為：

1)判斷在Ts時刻發生故障的機器類型，若是裝配設備u故障則轉至步驟2)；若是加工機器k則轉至步驟3)；

2)判斷設備u在故障時刻是否正在組裝工件，若是則記錄此工序完成組裝的組件或者成品個數，轉至步驟5)；否則直接轉至步驟5)；

3)判斷機器k的當前情況，若是情況1 則轉至步驟5)；若是情況2，即工序Pibj正在被此機器加工，則轉至步驟4)；

4)將Bib個工件i劃分成已經完成此道工序加工的Bib1件和未完成加工的Bib2件兩個批次，將新的基因考慮到動態染色體中；

5)記錄現有的已完工工件數、組件數、成品數和所有機器的可開工時間；

6)根據當前已完成加工的工序和最優靜態甘特圖得到還未加工的工序，將其考慮到動態染色體中；

7)初始化動態染色體開始重調度，獲得最優方案。

3 算例分析

為了驗證本文算法以及動態調度策略的有效性，以下設計了兩個算例進行說明。在MATLAB 2016a 上進行算例測試，運行環境為：Windows 10操作系統，3.00 GHz，8 GB RAM。設置算法相關參數：靜態初始種群規模為400，動態初始種群規模為200，交叉率為0.8，變異率為0.2，迭代次數為120 次。

3.1 算例1

算例1 選用文獻[25]中提出的問題并適當拓展修改。5 種工件的批量分別為20、10、10、30、20，共有10 臺零件加工機器，3 臺裝配設備。最后組裝成一種成品，BOM 結構如圖4，裝配工序信息如表1。

表1 裝配工序信息Table 1 Assembly process information min

為與文獻[25]進行對比，在不同的分批原則上利用本文算法求解該問題，以最小化最大完工時間為優化目標得到的結果如表2。

表2 算例1 結果比較Table 2 Comparison of results of example 1 min

從表2 可以看出，除了在等分2 批的情況下本文的最優值與文獻[25]相同，在等分3 批和等分4 批的情況下本文的最優值均優于文獻[25]，驗證了本文算法的整體有效性，等分4 批時本文最優解甘特圖如圖6 所示。

圖6 等分4 批時本文最優解甘特圖Fig.6 Optimal solution of Gantt chart with four equal batches

為了說明本文所提算法和解碼在處理機器故障時的可行性，對該算例進行了適當拓展。不失一般性，在等分4 批的情況下隨機選擇機器故障時間Ts∈[55,75]，隨機選擇故障機器k∈[1,10]。假設損壞情況為4 號機器在Ts=68 min 時發生故障，故障時長Lt=10 min，即4 號機器在78 min 時可以正常運轉。利用本文算法求解得動態調度后的最優解，給出機器4 在Ts時刻故障后的重調度甘特圖(如圖7)，可見其在Ts時刻之前(紅色線條左邊)的調度順序與靜態甘特圖6 一致。

圖7 加工機器4 故障后的動態最優解(算例1)Fig.7 Dynamic optimal solution after machine four failure (example 1)

結合圖例簡單說明解碼機器故障時染色體的更改原則：進行重調度之前首先判斷在Ts時刻機器k上工件的加工情況。例如：由圖7 可知，在68 min 時機器4 正在加工工件4 的第4 批次的第二道工序(圖7 中紫紅色方塊)，此道工序中有3 件工件完成了加工，有6 件未完成加工，因此工件4 在后續加工中由4 個批次（批量分別為7、7、7、9）變成5 個批次（批量分別為7、7、7、3、6）。進而重調度時需要將基因45 也考慮進入染色體編碼當中，由于45 并未完成第二道工序加工，因此45 剩4 道工序(綠色方塊)在重調度后進行，44 則剩3 道工序(黃色方塊)在重調度后進行。

3.2 算例2

在FAJSP 的問題模型下引入批量和動態元素后的問題十分復雜而且本文提出了裝配柔性，故而目前暫未尋得相關算例也沒有基準測試算例集。在此生成一個參數隨機的算例并完成靜態與動態調度，用于說明本文所提算法和策略的有效性與可行性。算例2 的BOM 結構依舊采用圖4，分批原則采用等分4 批，其他模型參數設置如表3所示。加工工序信息和裝配工序信息分別見表4和表5。

表3 模型參數設置Table 3 Model parameter setting

表4 加工工序信息Table 4 Process information min

續表 4

表5 裝配工序信息Table 5 Assembly process information min

靜態調度情況：為驗證鄰域結構N1在柔性加工與裝配作業車間分批聯合調度問題中的有效性。分2 種情況各獨立運行程序20 次得到的結果如表6。

表6 不同鄰域情況下的結果比較Table 6 Comparison of results under different neighborhood structures min

可見同時采用N1和N2時的最優值和均值均比單獨采用N2時更好，驗證了N1鄰域結構在考慮批量裝配問題上的有效性，在一定程度上提高了算法的局部搜索能力和整體性能。利用本文算法多次運行后得到的最優解甘特圖如圖8 所示。

圖8 靜態調度最優解對應的甘特圖Fig.8 Gantt chart corresponding to the optimal solution of static scheduling

動態調度情況：

1)工件加工機器發生故障：隨機選擇機器故障時間Ts∈[55,100]，隨機選擇故障機器k∈[1,8]，設置故障時長Lt=10 min。隨機抽取兩種情況并利用本文算法解得對應靜態調度最優解圖8 的動態調度甘特圖如圖9、圖10 所示。

圖9 加工機器4 故障后的動態最優解(算例2)Fig.9 Dynamic optimal solution after machine four failure (example 2)

圖10 加工機器7 故障后的動態最優解Fig.10 Dynamic optimal solution after machine seven failure

①情況1：Ts=88,k=4。

②情況2：Ts=93,k=7。

圖9 和圖10 中的綠色方塊均為重調度后產生的工件的第5 批次，紅色方塊為機器故障時刻正在被加工的工序。由于在機器損壞時，工件4 的第3 批次還未完成一道工序的加工，因此圖9中Ts時刻重調度后將沒有43 工序塊。

2)裝配設備發生故障：隨機選擇機器故障時間Ts∈[110,160]，隨機選擇故障機器u∈[1,4]，設置故障時長Lt=10 min。隨機抽取兩種情況并利用本文算法解得對應靜態調度最優解圖8 的動態調度甘特圖，如圖11、圖12 所示：

圖11 裝配設備1 故障后的動態最優解Fig.11 Dynamic optimal solution after assembly device one failure

圖12 裝配設備3 故障后的動態最優解Fig.12 Dynamic optimal solution after assembly device three failure

①情況1：Ts=126,u=1。

②情況2：Ts=135,u=3。

4 結束語

本文針對考慮機器故障的柔性加工與裝配作業車間分批聯合調度問題進行了研究，以成品的最終組裝完成時間為優化目標，引入裝配柔性，在遺傳算法的基礎上進行了改進后求解，并得出了以下結論：

1)設計了一種針對該問題的工件末工序前移的鄰域結構N1，通過算例結果分析可知N1鄰域結構的采用使本文算法的局部搜索能力得到提高，求解質量得到改善。

2)針對工件加工和組件裝配兩種不同類型的工序不能單一采用貪婪解碼的問題，提出了一種基于裝配設備負載均衡的混合貪婪解碼，在裝配解碼部分融入一種基于裝配設備負載均衡的裝配設備選擇策略，成功地解決了本文所研究的調度問題。

3)針對工件加工機器和裝配設備故障問題，提出了相應的調度策略和染色體更改規則用于處理機器故障動態事件。

4)通過對已有算例和本文自編算例的測試，驗證了本文所提算法在處理柔性加工與裝配作業車間分批聯合調度問題上的可行性和有效性。

針對柔性加工與裝配作業車間分批聯合調度問題，本文提出了相關解碼和策略，但在分批原則上采用的是等量一致分批，動態事件只是考慮了一種。多樣的分批原則和其他動態事件的考慮都是進一步研究的方向和要點。