基于改進帝國競爭算法的柔性作業車間機器故障重調度

張國輝，陸熙熙，胡一凡，孫靖賀

（鄭州航空工業管理學院管理工程學院，鄭州 450015）

0 引言

作業車間調度問題一直是制造業中的重點關注對象，車間調度的主要目的是節省產品的生產時間，讓生產資源的利用率發揮最大作用，最后通過對資源的恰當分配讓柔性作業車間的生產效率更高。柔性作業車間調度問題（Flexible Jobshop Scheduling Problem，FJSP）是經典車間調度的延伸，擴展了每道工序的機器柔性，相對經典車間調度來說較為繁雜。在實際的生產制造過程中，車間環境是動態變化的，會出現各種各樣的問題，比如緊急插單、機器故障等不確定性因素，要充分考慮到當前工作環境及系統的狀態，及時作出正確合理的調度方案，因此就出現了柔性作業車間動態重調度問題。在1977年，Nelson等［1］對于動態調度問題，提出了將動態問題轉化為多個連續的靜態區間，對每個區間進行優化，以達到總體最優。柴永生等［2］根據動態調度問題提出了免疫遺傳算法，即對進化種群進行免疫操作，有效地解決了搜索效率低的問題。孟冠軍等［3］在求解多目標柔性作業車間調度問題上設計了改進混合人工蜂群算法，即在不同的階段采用不同的搜索機制，并且為了提高得到最優解的概率，將禁忌搜索與改進的混合人工蜂群算法結合。Shahrabi等［4］針對考慮隨機作業到達和機器故障的動態作業車間調度問題，提出了一種基于變量鄰域搜索的調度方法，結合事件驅動策略，為了在任意重調度點獲得合適的參數，采用了基于Q因子算法的強化學習算法，并通過模擬作業車間實驗結果表明該方法的性能明顯優于常用調度規則和一般可變鄰域搜索。He等［5］在研究機器故障狀態下的動態調度問題時，為了提高調度的魯棒性和穩定性，首先提出了一種新的空閑時間插入策略，其次提出了加工路線變更策略和右移策略相結合的策略，在這兩種策略的基礎上，提出了一種多策略調度算法。鄒攀等［6］提出一種基于分層蟻群遺傳算法的車間資源驅動的多目標調度方法，適用于車間資源變化、任務執行情況變化、緊急任務插入等不確定情況下的動態調度。吳正佳等［7］在研究機器發生故障的柔性作業車間動態調度問題時，提出了兩種重調度策略即插入重調度和完全重調度，并結合改進遺傳算法（Genetic Algorithm，GA）進行求解，將機器故障產生的影響降到最低。孫麗珍等［8］采用改進遺傳算法結合啟發式規則求解柔性作業車間問題；針對工件加入和機器故障的動態調度，提出了加入多約束的貪婪插入空隙法的解碼方式的改進遺傳算法。Nouiri等［9］以最小最大完工時間和魯棒性為目標，在求解機器故障下柔性作業車間調度問題上，提出了一種兩階段粒子群優化算法，實驗部分與Al-hinai等［10］提出的混合遺傳算法進行比較，結果表明該優化算法具有更好的魯棒性和穩定性。近年來，隨著可持續發展戰略的提出，越來越多的生產企業開始轉向綠色制造，降低能源消耗已經成了焦點問題。Nouiri等［11］在解決機器故障下的動態柔性作業車間調度問題時，以最大完工時間最小、全局能耗最小為目標，提出了一種基于粒子群優化方法的綠色重調度方法，可以最大限度地減少時間和降低能耗。包哲人等［12］面向考慮能耗的柔性作業車間調度問題提出了改進離散蝙蝠算法，為避免算法早熟收斂設計了一種具有記憶能力的粒子變異操作，同時為了算法的搜索能力加入慣性權重策略，通過生產實例驗證了算法的有效性。陳超等［13］以平均流經時間和能耗為目標建立柔性作業車間模型，針對此模型提出了遺傳算法與模擬退火混合算法（Genetic and Simulated Annealing Algorithm，GASA），采用滾動窗口技術結合GASA來求解機器故障的動態調度問題并驗證了算法的有效性。曹慶奎等［14］針對在機器故障情況下，同時考慮能耗和交貨期的柔性作業車間動態調度問題，采用GASA進行求解，以最大完工時間最小、能耗最小、客戶滿意度最大為目標驗證了其算法的有效性。李明等［15］針對考慮準備時間的低碳FJSP，提出了新型帝國競爭算法（Imperialist Competitive Algorithm，ICA），采用一種全新的同化方法和歸一化總成本新定義，在優化關鍵目標的同時持續改進非關鍵目標總能耗。呂聰等［16］提出協作混合帝國算法，改進了自適應參數，提高了算法的收斂速度，并對不同階段采用多變異改革策略以提高算法的局部搜索效率，以及協作交流機制來提高算法的全局搜索能力，表明了協作混合帝國算法在求解柔性車間調度問題上的穩定性和優越性。以上針對動態調度問題的研究，在國內外學者的努力下研究成果豐富，但是針對機器故障重調度，并同時考慮能耗的研究相對較少。機器故障在實際車間生產過程中是很常見的動態事件，在發生故障后找到合適的重調度方案是非常重要的。本文主要研究機器故障的柔性作業車間重調度問題，對帝國競爭算法進行改進，在同化和革命操作之后加入一個輪盤賭的選擇機制，對同化和革命后的個體重新進行選擇，并結合事件驅動策略對此類重調度問題進行求解，驗證算法的有效性。

1 問題描述

柔性作業車間調度問題可以描述為：將1到n個工件合理安排到m臺機器上進行加工，每個工件有多道工序，其中每道工序都可以選擇不同的機器進行加工，各工序所選機器不同，所需加工時長也不相同。在實際生產過程中存在一些不確定性因素，導致會出現各種動態事件，本文考慮的是機器故障的動態事件。柔性作業車間動態重調度研究存在以下幾個假設條件：

1）同一個工件在同一時刻只能由一臺機器進行加工，一臺機器在同一時刻只允許有一個工件在該機器上加工。

2）每一道工序可以選擇由可加工機器集中的機器進行加工，但是同一時刻只允許在一臺機器上加工。

3）每一個工件對于每道工序的加工有先后順序要求，只有某工件的前道工序加工完成后才能對該道工序進行加工。

4）當原調度已經對工件的前幾道工序加工完成，再調度時只需加工該工件的后續工序。

柔性作業車間機器故障重調度問題是在給出相關變量和決策變量，滿足約束條件和目標函數的情況下，生成一個初始調度，在機器發生故障后，初始調度方案便不可行，此時應重新調整調度方案，結合重調度策略生成重調度方案。

1.1 變量定義

本文的相關變量符號及定義如表1所示。

表1 變量描述Tab.1 Variables description

本文的決策變量有?ijk和δijhdk，其中，?ijk用于確定工序與機床的選擇關系；δijhdk用于確定工序在機器上的優先加工順序。

1.2 約束條件

柔性作業車間調度問題要滿足工件約束和機器約束：

式（1）表示一道工序只能在一臺機器上加工；式（2）表示同一工件只能在前一道工序加工完才能加工后一道工序；式（3）表示一臺機器在同一時刻只能加工一道工序。

1.3 目標函數

本文主要研究的調度目標為最小化最大完工時間（makespan）、最小能耗以及最小總延遲時間，如下所示：1）最小化最大完工時間。

2）最小能耗。

采用文獻［13］中的加工能耗E的表示方法，每臺機器上的第一個工件的開始加工時刻就是該臺機器的開工時刻，機器一直保持著耗能狀態，直到該機器上所有工件都加工完畢，因此能耗的數學模型為式（5）所示：

3）最小總延遲時間。

本文總延遲時間主要是計算機器故障前后，兩次調度的最小化最大完工時間差，總延遲時間的數學模型如式（6）所示：

由于三個目標的量綱不統一，需要進行歸一化處理，將各目標數據轉換到［0，1］內，計算過程如式（7）所示：

其中：x*表示歸一化之后的目標值，x為當前目標值，xmax為全局目標最大值，xmin為全局目標最小值。

對本文的三個目標進行歸一化處理后，再采用線性加權和法，將三個目標優化問題轉變成單目標優化問題，如式（8）所示：

2 FJSP動態重調度策略

動態重調度策略，是指在系統生產過程突發情況下將采取應對措施來解決發生的異常事件。一般用到的策略方法有三種，分為事件驅動、周期驅動和周期與事件的混合驅動，本文采用事件驅動策略。

當機器出現故障時，確定機器修復時間T，故障點前已經加工過的工序保持不動，找出故障點后未加工的工序，并對其用帝國競爭算法進行重新調度，故障機器的開工時間為修復后的時間，即故障時刻加上故障時長，其余機器的開工時間為當前正在加工工序的完成時間。機器發生故障后，在該機器上未進行加工的工件將被分配到其他機器上進行加工。機器故障重調度的具體流程如圖1所示。

圖1 機器故障重調度流程Fig.1 Flow of reschedulingwith machinebreakdown

3 算法設計

3.1 基本帝國競爭算法

帝國競爭算法是一種受帝國競爭行為啟發的新的智能優化算法，它與粒子群優化（Particle Swarm Optimization，PSO）算法、蟻群優化（Ant Colony Optimization，ACO）算法等一樣，都屬于基于群體的隨機優化搜索算法。帝國競爭算法比PSO和GA收斂速度快，具有較強的全局收斂性，并且同化和革命步驟又保證了算法的局部搜索能力，因此在求解柔性作業車間調度問題上有一定的優勢。帝國競爭算法在解決各種實際的優化問題上具有廣泛應用，本文將其應用在解決機器故障重調度問題上。

ICA的基本過程為：產生初始帝國、同化、革命、帝國競爭和帝國消亡。ICA的流程如圖2所示，具體步驟為：

圖2 ICA流程Fig.2 Flowchart of ICA

步驟1 將隨機產生的Npop個初始解作為初始國家，并計算每個國家的成本cn。

步驟2 構建初始帝國。選擇成本較小的Nimp個國家作為殖民國家imp，剩余的作為殖民地Col，殖民地的個數NCol與殖民國家個數Nimp之和等于初始解的個數Npop。確定殖民國家所能分到的殖民地數量，隨機分配殖民地給各殖民國家，此時各殖民國家與其殖民地組成初始帝國PEmp。殖民國家所擁有的殖民地數量與其勢力成正比，因此要先計算每個殖民國家的標準化成本Cn，如式（9）所示：

殖民國家的成本越小，勢力就越大，每個殖民國家的標準化勢力pn如式（10）所示：

第n個殖民國家所擁有的初始殖民地數量NCn如式（11）所示：

其中round是將小數四舍五入成整數的函數。

步驟3 同化和革命。將殖民地向其所在殖民國家移動，即殖民地都趨向于殖民國家這個最優解；革命的目的是防止同化后的算法過早收斂。同化操作分為機器的選擇和工序排序兩部分，機器的選擇部分采用多點交叉變異的方法，具體操作為：隨機選取r個位置，將殖民國家的r個位置的信息替換到殖民地中的對應位置，其余位置信息保持不變；工序排序部分采用工件交換的方式，將殖民地的加工工序部分與殖民國家的加工工序部分進行信息交換，更新殖民地的加工工序部分。革命操作同樣分為機器的選擇部分和工序排序部分，在機器選擇部分，隨機選取某個加工機器，然后選擇對應機器集中的其他任一機器代替它；在工序排序部分，隨機選擇兩個位置上的工序進行信息交換。同化和革命后的新帝國為SEmp。

步驟4 殖民國家更新。當殖民地經過同化和革命后，將殖民國家和所有殖民地的成本進行比較：若有殖民地的成本比殖民國家要小，則該殖民地替代殖民國家成為該帝國內新的殖民國家；否則，殖民國家不發生變化，更新后的帝國為Emp。

步驟5 帝國競爭。計算所有帝國的總成本，較弱帝國需選出一個最弱殖民地，較強帝國可以來爭奪殖民地，帝國越強獲得該殖民地的概率越大。每個帝國的總成本TCn計算如式（12）所示，將每個帝國的總成本進行標準化處理，如式（13）所示，每個帝國占有弱殖民地的概率Pn計算如式（14）所示：

其中：f（impn）表示第n個帝國的殖民國家的成本，f（Coli）表示第i個殖民地的成本，α為殖民地影響因子，0<α<1，NTCn表示第n個帝國的標準化成本。

步驟6 帝國消亡。當某個帝國沒有任何殖民地時，此時該帝國消亡。

步驟7 若終止條件成立，則算法結束；否則回到步驟3。

3.2 編碼和解碼

在ICA中，每一個國家代表一組柔性作業車間動態調度問題的可行方案，結合柔性作業車間調度問題特點設計兩段式實數編碼方式對國家個體進行編輯。

以圖3為例，每個個體為一串整數，總長度為2L，L為所有工序的個數，Oi表示工件i的工序數。左半部分為加工機器的選擇，按照工件1、工件2和工件3的工序順序進行排列，每個整數表示對應工序可選加工機器的排列序號，第一個整數3為工序O11可選機器集｛M2，M3，M4｝的第3個機器即M4。右半部分為加工工序的排序，每個整數代表工件號，第1次出現表示該工件的第1道工序，第2次出現表示該工件的第2道工序，以此類推，圖3中加工工序所表示的工序順序為（O21，O11，O31，O12，O32，O22）。

圖3 編碼表達示意圖Fig.3 Schematic diagram of codingexpression

對國家個體進行解碼操作時，首先對個體的前半部分即機器部分從左到右依次進行解碼，轉成對應的機器并確定各工序在對應機器上的加工時間，然后對個體的后半部分即工序部分進行解碼，解碼成活動調度。

3.3 改進ICA

帝國競爭算法中的同化是通過殖民地向殖民國家的移動來實現，相當于是一個尋優過程增強了算法的局部搜索能力，但是在傳統的帝國競爭算法中并沒有物競天擇的進化規律，在ICA求解調度時為了能夠提高求解質量、提高算法的尋優能力，因此本文參照遺傳算法中的遺傳和變異對帝國競爭算法進行改進，在初始帝國進行同化和革命之后增加一個選擇機制的步驟，可以使初始帝國中的優秀基因得以保留，更新后的帝國質量更優，更加貼近最優解。選擇機制的具體操作如下：

步驟1 首先將初始帝國PEmp中的第一個帝國PEmp（1）的所有個體與其同化和改革后的SEmp中對應的第一個帝國SEmp（1）中的所有個體放在一起。

步驟2 采用輪盤賭的方法從合并的帝國中選出一半數量的個體，將其作為一個新的帝國Emp（1）。本文采用輪盤賭的個體概率值為各個國家的成本值的倒數，成本值越小則被選到的概率越大，否則概率越小。

步驟3 從新帝國中選出成本值最低的國家作為殖民國家，剩余的國家則淪為該殖民國家的殖民地。

步驟4 接著轉到步驟1進行初始帝國PEmp中的第二個帝國PEmp（2）和同化和改革后的SEmp中對應的第二個帝國SEmp（2）的合并，以此類推，直到所有帝國全部選擇完成，最終生成新的帝國Emp，此時選擇機制結束。

改進帝國競爭算法選擇機制的示意圖如圖4所示。

圖4 選擇機制示意圖Fig.4 Schematic diagram of selection mechanism

改進后的帝國競爭算法的流程如圖5所示。

圖5 改進ICA流程Fig.5 Flow of improved ICA

4 仿真結果與分析

采用改進ICA對柔性作業車間機器故障重調度算例進行仿真實驗，并隨機假設三種機器發生故障的場景，得出最佳調度方案，驗證該算法求解柔性作業車間機器故障重調度問題的有效性。

4.1 參數設置

本文的實驗算例來自洛陽某鋼具廠生產車間，經過簡化為8×8的柔性作業調度問題，如表2所示，有8個工件，8臺機器。表3為每臺機器的加工能耗，表4為假設的三種機器故障場景，這三種場景分別獨立發生。

表2 仿真實例數據Tab.2 Dataof simulation examples

表3 機器能耗Tab.3 Machineenergy consumption

表4 三種機器故障場景Tab.4 Three scenarios of machinebreakdowns

使用Matlab 2017b對該算例進行仿真實驗，本文提出的算法參數設定為：最大迭代次數為50，國家個數為100，帝國個數為10，a、b、c分別設為0.3、0.3、0.4。針對同化系數、革命概率和競爭概率三個參數，采用田口方法以及Minitab軟件進行多因子正交實驗，正交表如表5所示，每個參數有3個水平，共有9種不同的組合，對該正交表進行田口分析得到的均值主效應圖如圖6所示，最后得出同化系數、革命概率和競爭概率的參數分別為0.7、0.05、1。

表5 正交表Tab.5 Orthogonal table

圖6 參數均值主效應圖Fig.6 Main effect plots of parameter means

4.2 實驗結果

首先在初始時刻采用改進ICA對問題進行調度，得到初始方案，如圖7所示為迭代最優解的甘特圖，最大完工時間為26 min，能耗為624.3 J。圖7中相同顏色代表同一工件，其中顏色塊上的數字表示為：第一個數字是工件號，后兩位數字表示工序號，如“101”表示工件1的第一道工序，“402”表示工件4的第二道工序。

圖7 初始調度方案甘特圖Fig.7 Gantt chart of initial scheduling scheme

場景1是機器3在0時刻發生故障，故障修復時刻為15，進行重調度后的甘特圖如圖8所示，最大完工時間為27 min，總延遲時間為1 min，能耗為722.8 J。圖8中數字表示工件號，相同顏色代表同一工件，機器3上，［0，15］時間段為故障區間。

圖8 機器3發生故障后的重調度甘特圖Fig.8 Gantt chart of rescheduling after machine 3 breakdown

場景2是機器6在5時刻發生故障，故障修復時刻為10，進行重調度后的甘特圖如圖9所示，最大完工時間為27 min，總延遲時間為1 min，能耗為757.6 J。圖9中標有數字的白色部分表示機器發生故障時刻之前的工序保持原調度不變，有顏色的部分表示機器發生故障后重新進行調度的工序。

圖9 機器6發生故障后的重調度甘特圖Fig.9 Gantt chart of reschedulingafter machine6 breakdown

場景3是機器7在10時刻發生故障，故障修復時刻為25，重調度后的甘特圖如圖10所示，最大完工時間為27 min，總延遲時間為1 min，能耗為707.3 J。

為進一步驗證改進ICA的有效性，假設機器2、機器5和機器6分別在0時刻發生故障，并且短時間內無法修復，針對該三種機器故障情況采用GASA［13］、改進GA［8］和改進ICA分別進行求解并對比，三種算法求出的三種優化目標數據如表6所示，從表中可以看出該改進ICA與其他兩種算法相比實驗結果更好，驗證了該算法的有效性。

表6 實驗數據對比Tab.6 Comparison of experimental data

故障機器D/min 2 5 6算法GASA改進GA改進ICA GASA改進GA改進ICA GASA改進GA改進ICA C max/min 28 31 27 30 30 27 29 32 29 E/J 786.1 792.5 712.2 807.9 833.9 740.6 780.4 817.9 723.6 251441363

為了驗證算法求解的穩定性，分別采用三種算法對上述機器2發生故障的情況進行求解，表7為三種算法運行10次的各優化目標的平均值和方差，從表7中可以看出，改進ICA與GASA、改進GA相比各優化目標的方差最小，表明該改進ICA求解的穩定性最好。

表7 三種算法的性能對比Tab.7 Performance comparison of threealgorithms

針對上述假設的機器故障情況的實驗研究以及與遺傳算法進行比較，可以得出的結論是，故障后的重調度方案的最大完工時間、總延遲時間以及能耗都控制在一個較好的范圍之內，符合實際生產需要。

5 結語

本文針對柔性作業車間機器故障的動態事件，對帝國競爭算法進行改進，加入選擇機制操作，結合事件驅動策略以及最大完工時間、能耗和總延遲時間三個目標函數，對該類動態問題進行求解。對提出的三種不同機器故障的場景進行實驗仿真分析，得出的結果較為符合實際生產需要，并將改進ICA與兩種不同的算法進行比較，驗證了該算法的有效性和可行性。

柔性作業車間生產過程中容易受到各種復雜因素的影響，下一步將繼續對帝國競爭算法進行改進，并運用到其他類型的動態調度中，如插入緊急訂單、工件延誤等動態事件。