劉道興

（山東科技大學，山東 青島 266590）

0 引言

車間調(diào)度問題最早是由JOHNSON 在20 世紀50 年代提出的[1]，到了20 世紀90 年代BRUCKER 擴展了車間調(diào)度理論，提出柔性作業(yè)車間調(diào)度（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）[2]，隨后眾多學者又在FJSP 問題上加入了動態(tài)擾動，研究在擾動條件下的車間調(diào)度問題。

隨著計算機技術(shù)的快速發(fā)展，啟發(fā)式算法為解決FJSP問題提供了更好的思路，也逐漸取代了傳統(tǒng)的調(diào)度規(guī)則和數(shù)學類方法。陳鴻海等[3]、尹愛軍等[4]、景志強等[5]、曾強等[6]對非支配排序遺傳算法進行改進研究，解決了相關(guān)的車間調(diào)度問題，并證明各自的改進在解決調(diào)度問題上的可行性。陳魁等[7]利用小生境粒子群優(yōu)化算法解決了考慮工件運輸時間的多目標FJSP 問題。趙博選等[8]使用基于多策略融合的Pareto 人工蜂群算法求解多目標的FJSP 問題。

該文將機器故障下的柔性作業(yè)車間調(diào)度問題分為2 個階段：首先，采用智能算法求解出靜態(tài)預(yù)調(diào)度方案。其次，在靜態(tài)調(diào)度方案基礎(chǔ)上提出了基于2 種重調(diào)度策略的組合重調(diào)度策略，并驗證了該策略在解決機器故障下的FJSP 問題的可行性。

1 問題描述

該文將考慮機器故障的FJSP 問題分為2 個過程，首先是傳統(tǒng)的靜態(tài)FJSP 問題，其次是在靜態(tài)調(diào)度方案基礎(chǔ)上發(fā)生機器故障后的重調(diào)度。

FJSP 問題的具體描述如下：有n個工件在m臺機器上加工，工件的工序數(shù)和加工工藝已經(jīng)確定無法改變，并且所有工序在可選機器上的加工時間是確定的，選擇不同機器的加工時間也不盡相同。調(diào)度的目的就是通過調(diào)整工序的加工順序和選擇加工機器找到更優(yōu)的加工方案，以實現(xiàn)各項優(yōu)化目標，所有工件生產(chǎn)完成后即調(diào)度結(jié)束。

研究FJSP 問題時要與實際生產(chǎn)狀態(tài)相匹配，需要提出以下假設(shè)條件：第一，開始時，所有的機器都處于待機狀態(tài)，且工件加工只能選擇一臺機器。第二，工藝順序為確定順序，在加工時不能發(fā)生改變，該工件的前道工序加工完成后才能對后道工序進行加工。第三，出現(xiàn)設(shè)備故障時，受到影響的機器停止加工，未受到影響的機器繼續(xù)加工。第四，發(fā)生設(shè)備故障時，故障在一定時間內(nèi)可以維修恢復(fù)。第五，工序時間包括加工時間和工作準備時間。第六，工件能在可加工機器上任意切換。第七，前、后工件之間沒有約束關(guān)系。

2 模型建立

從最小加工總時間、最小機器總能耗、最小機器總負載3 個角度建立柔性作業(yè)車間調(diào)度優(yōu)化模型。

2.1 最小加工總時間

最小加工總時間指的是最后一道工序加工完成后花費的總時間最短，是調(diào)度方案效率最直接的體現(xiàn)，如公式（1）所示。

式中：i為工件號；ti為工件i的加工時間。

2.2 最小機器總能耗

最小機器總能耗指的是從加工開始到所有工件加工完成機器所消耗的能源最小（包括空載與負載），如公式（2）所示。

式中：j為工序號；qi為工序數(shù)；z為機器號；m為機器數(shù)；Tijz為工件oij在機器z上的加工時間；oij為工件i的第j道工序；Xijz為決策變量，當工件i在機器z上加工為1，否則為0；Lz、ULz分別為機器z在負載下的能耗與空載下的能耗；CTz為oij在機器z上的完工時間。

2.3 最小機器總負載

總負載最小是指工件在機器上的加工時間最小，其計算如公式（3）所示。

3 問題求解

3.1 靜態(tài)FJSP 問題求解

針對靜態(tài)的多目標FJSP 問題，該文采用改進的灰狼優(yōu)化算法進行求解。狼優(yōu)化算法（GWO）是2014 年由澳大利亞學者提出的一個群智能優(yōu)化算法[9]，其主要是模擬狼群的捕獵過程，具有收斂性強、參數(shù)少和易實現(xiàn)的特點，在求解車間調(diào)度問題上具有很大優(yōu)勢。但是該算法本身也存在一定缺陷。首先，GWO 作為非精確算法，在求解迭代過程中需要挑選一個或多個優(yōu)秀個體去引導目標優(yōu)化的方向，而FJSP問題涉及目標較多，個體優(yōu)劣判斷較難，會直接影響算法性能，因此需要采用孫新宇等[10]提出的方法，即引入非支配排序及擁擠度計算，以此來判斷算法中的個體優(yōu)劣。其次，針對GWO 線性收斂易造成局部最優(yōu)解的問題，在孫新宇法改進的基礎(chǔ)上，該文采用了一種非線性收斂因子，避免算法出現(xiàn)局部最優(yōu)解的問題。

3.1.1 非支配排序及擁擠度計算

采用孫新宇提出的方法，引入非支配排序及擁擠度計算，經(jīng)過快速非支配排序和擁擠度計算，得到種群中每個個體的非支配序和擁擠度，當且僅當個體i的非支配序大于等于個體j且個體i的擁擠度大于個體j，可得個體i優(yōu)于個體j。

3.1.2 改進非線性收斂因子

作為群體智能算法，GWO 法有全局搜索和局部搜索2個過程，二者的平衡關(guān)乎算法收斂速度，進而影響算法求解的性能。在GWO 中，收斂因子a決定了算法是實現(xiàn)全局搜索還是局部搜索。傳統(tǒng)的GWO 中，a隨迭代從2 線性遞減至0，但實際求解問題時算法的迭代常常不是呈線性的。在迭代初期，收斂因子a應(yīng)當緩慢衰減，以保證算法實現(xiàn)全局搜索，找到更好的全局解。到了算法迭代后期，收斂因子a應(yīng)當快速衰減，以保證算法在局部搜索，進而更加準確地找到局部內(nèi)的最優(yōu)解。此情況下的a線性收斂策略將無法滿足算法迭代規(guī)律[11]，因此該文改進了收斂因子a的收斂方式，采用一種非線性收斂方式，如公式（4）所示。

式中：e 為自然數(shù)；t為迭代次數(shù)；tmax為最大迭代次數(shù)。

3.1.3 算法流程

改進后的灰狼優(yōu)化算法步驟如下。步驟1：設(shè)置種群數(shù)量、算法參數(shù)以及種群迭代次數(shù)；步驟2：初始化種群；步驟3：解碼得到優(yōu)化目標的參數(shù)；步驟4：根據(jù)得到的優(yōu)化目標參數(shù)進行非支配排序和擁擠度計算；步驟5：計算后用灰狼算子更新種群；步驟6：計算個體的適應(yīng)度，最優(yōu)的3個為α、β、δ三只狼；步驟7：判斷算法是否達到最大迭代次數(shù)，是則輸出結(jié)果，否則轉(zhuǎn)到步驟4。

3.2 機器故障下的重調(diào)度求解

在靜態(tài)預(yù)調(diào)度方案的基礎(chǔ)上，當發(fā)生機器故障時，需要及時調(diào)整調(diào)度策略，以保證生產(chǎn)的穩(wěn)定進行。該文針對機器故障下的調(diào)度策略的調(diào)整，采用重調(diào)度策略代替單一重調(diào)度策略，并結(jié)合2 種調(diào)整策略的特點，保證在不同情況下重調(diào)度策略的適用性。

3.2.1 右移重調(diào)度策略

發(fā)生機器故障后，直接調(diào)整故障機器上正在加工的工序或者將要在故障機器上加工的工序，直到機器可以加工工件，即為右移重調(diào)度策略。具體步驟如下：首先，確定故障機器、故障發(fā)生時間和故障修復(fù)時間。其次，分析確定出預(yù)調(diào)度中在故障機器上直接加工或者將要加工的工序集合。最后，根據(jù)故障的修復(fù)時間，將受到影響的工序右移，直到故障修復(fù)，滿足工件的加工條件后開始加工，形成右移重調(diào)度方案。

3.2.2 完全重調(diào)度策略

當機器發(fā)生故障時，將方案切分，故障前的加工工序不變，將故障后所有機器待加工的工件完全重組，重新編碼解碼，得到新的調(diào)度方案，即為完全重調(diào)度策略。具體步驟如下：首先，找到故障發(fā)生時間進行切分，確定未開始的需要重新調(diào)度的工序集合，其中包括中斷的工序和沒有開始加工的工序。其次，確定所有機器的開工時間，機器的開工時間為故障發(fā)生后的最早空閑時間。最后，采用智能算法對確定好的工序合集進行編碼解碼，得到新的調(diào)度方案，與切分的調(diào)度前半部分方案組合即為故障發(fā)生后的完全重調(diào)度方案。

3.2.3 重調(diào)度流程

在重調(diào)度階段，為了探究在不同情況下如何選擇重調(diào)度策略，并探究組合重調(diào)度策略是否優(yōu)于單一重調(diào)度策略，對2 種重調(diào)度策略分別進行求解試驗。然后將結(jié)果進行對比，選取較優(yōu)的方案作為最終的重調(diào)度方案。

4 仿真結(jié)果與分析

為了驗證方案求解機器故障下FJSP 問題的可行性，采用標準車間調(diào)度數(shù)據(jù)MK01。該算例是一個工件數(shù)為10、機器數(shù)為6 的10×6 算例。

4.1 靜態(tài)預(yù)調(diào)度方案

仿真試驗的運行環(huán)境為Intel Core i7 CPU，主頻2.60GHz，內(nèi)存16GB，Windows 11，64 位操作系統(tǒng)，試驗仿真軟件為Python3.6.5，種群大小為100，進行150 次迭代，得到的預(yù)調(diào)度結(jié)果圖如圖1 所示，排產(chǎn)的甘特圖如圖2 所示。

圖1 改進灰狼優(yōu)化算法目標函數(shù)結(jié)果圖

圖2 中的矩形方塊代表算法中工件的解碼，即工件加工的順序，其中的數(shù)字代表工件號，某工件按照時間順序出現(xiàn)的次數(shù)代表該工件的第幾道工序。部分加工順序的舉例如圖3 所示。機器3 中第一個矩形方塊中的數(shù)字1 代表工件1 的第一道工序，機器6 中第一個矩形方塊10 則為工件10 的第一道工序，而機器3 第2 個方塊中的10 為第二次出現(xiàn)，則為工件10 的第二道工序。依此類推，解碼得到排產(chǎn)的加工順序，即為可行的靜態(tài)調(diào)度方案，具體如下。

圖2 改進灰狼優(yōu)化算法MK01 甘特圖

圖3 排產(chǎn)甘特圖（局部）

預(yù)調(diào)度工序集：

預(yù)調(diào)度工序集對應(yīng)機器集：

預(yù)調(diào)度工序集對應(yīng)機器加工時間集：

4.2 重調(diào)度方案

為驗證加工機器對加工的影響，本試驗在預(yù)調(diào)度的方案基礎(chǔ)上選取機器3 在第15min 發(fā)生故障，故障持續(xù)時間為6min，在不同的重調(diào)度策略下得到的排產(chǎn)甘特圖如圖4、圖5所示。

圖4 機器3 故障下右移重調(diào)度甘特圖

圖5 機器3 故障下完全重調(diào)度甘特圖

從重調(diào)度排產(chǎn)甘特圖可得，當故障發(fā)生在對后續(xù)工件加工影響較大的機器3 上時，完全重調(diào)度策略要優(yōu)于右移重調(diào)度策略。采取同樣的調(diào)度策略，當故障發(fā)生在機器5 對工件加工影響較小的機器且故障持續(xù)時間依舊為6min 時，右移重調(diào)度策略的完工時間為51min，而完全重調(diào)度策略的完工時間為54min，此時右移重調(diào)度策略要優(yōu)于完全重調(diào)度策略。

綜上所述，進行重調(diào)度時，如果只采用某一種重調(diào)度策略，可能在不同條件下會缺乏適應(yīng)性，因此采用2 種重調(diào)度的組合策略，在不同條件下選擇不同策略進行重調(diào)度，才能保證生產(chǎn)的高效進行。

5 結(jié)語

該文將機器故障下柔性作業(yè)車間調(diào)度問題分為靜態(tài)預(yù)調(diào)度和機器故障下的重調(diào)度2 個部分。首先，采用了改進的灰狼優(yōu)化算法，計算得到靜態(tài)預(yù)調(diào)度方案。其次，基于右移重調(diào)度策略和完全重調(diào)度策略的特點，提出了一種組合重調(diào)度策略，驗證了其比單一重調(diào)度策略在解決生產(chǎn)調(diào)度問題上更具適應(yīng)性。

目前該文只考慮了2 種重調(diào)度策略，下一步工作需要挖掘更加完善的重調(diào)度策略，以提高重調(diào)度方案在解決動態(tài)調(diào)度方面的適應(yīng)性。