夏霖輝，吳瑤，周學良，王海林

（湖北汽車工業(yè)學院機械工程學院，湖北十堰 442002）

網(wǎng)絡環(huán)境下協(xié)同制造能最大限度調動社會優(yōu)質資源，發(fā)揮制造優(yōu)勢，高效、快速、低成本地完成客戶個性化訂單的生產制造任務。傳統(tǒng)單工廠訂單制造模式將逐漸被多工廠協(xié)同制造模式取代［1］，分布式多工廠生產制造是發(fā)展趨勢。流水車間是車間加工設備的主要組織形式，分布式置換流水車間調度問題是企業(yè)協(xié)同制造過程中需要解決的關鍵問題［2］，成為調度領域新的研究熱點。文獻［3-10］通過設計不同的優(yōu)化算法對分布式置換流水車間調度問題進行研究，文獻［11-16］研究了考慮運輸時間的生產調度優(yōu)化問題，但主要針對單工廠內工序間的加工轉運以及單工序工件在多工廠間的運輸。多工序工件在并行工廠加工完成后的交付轉運對工件的加工分配和完工交付有重要影響，文中以最小化最大工件交付時間為目標，建立考慮運輸時間的分布式置換流水車間調度問題的數(shù)學規(guī)劃模型，采用灰狼優(yōu)化算法的計算框架，結合問題的結構特點，設計基于工件加工位置的隨機鍵編碼方式和局部搜索策略以提高算法的性能。

1 問題描述與模型建立

考慮運輸時間的分布式置換流水車間調度問題描述如下：有n個待加工工件需要在分布于不同地區(qū)的F間工廠進行加工，各工廠擁有1條相同的由m臺機器串行構成的流水生產線，分配至各工廠的待加工工件需按照相同加工路徑在m臺機器上依次加工，同工廠的所有工件加工完畢后由運輸車輛統(tǒng)一運至客戶。已知工件在每臺機器上的加工時間和各工廠至客戶的運輸時間。調度決策需要研究如何聯(lián)合多工廠協(xié)同完成工件加工任務，降低工件交付時間，優(yōu)化目標為最小化最大工件交付時間，即工件完工時間與工件運輸時間之和。調度決策內容如下：1）待加工工件如何在各工廠分配；2）分配至各工廠的工件的加工排序。

為方便建立模型，作如下假設：1）不同流水車間的加工工藝相同，相應工序的機器性能相同；2）任一待加工工件可在任意流水車間內加工，同車間內的所有工件都完工后經同批次運輸至客戶；3）同車間內各臺機器上的工件加工排序相同，任一機器同時刻只能加工1個工件，任一工件同時刻只能在1臺機器上加工。目標函數(shù)為

約束條件為

變量說明如表1所示。

表1 變量說明

2 改進灰狼算法

灰狼算法（grey wolf optimization，GWO）是受灰狼捕食行為啟發(fā)所提出的新型群體智能優(yōu)化算法［17］，采用實數(shù)編碼機制，應用于求解連續(xù)優(yōu)化問題。有學者通過嘗試改進灰狼算法將其應用于車間調度等典型的離散型優(yōu)化問題，并取得良好的效果。文中基于GWO 的計算框架，提出改進灰狼算法（improved grey wolf optimization，IGWO）求解考慮運輸時間的分布式置換流水車間調度問題。鑒于算法在表達離散變量時存在編碼表示和迭代更新困難，設計隨機鍵編碼機制，將連續(xù)編碼映射為離散碼值，同時引入局部搜索策略以改進算法最優(yōu)解，提高算法的收斂速度。

2.1 GWO基本原理

GWO通過模擬灰狼群的嚴格等級制度和灰狼追蹤、包圍、攻擊獵物的行為過程，構建解的更新機制。算法將第1～3 階級灰狼分別表示為α、β、δ，群體中其他個體為第4階級，用ω表示。不失一般性，前3階級各有1只灰狼，依次對應灰狼群中適應度好的前3 個解?；依侨褐姓急茸畲蟮摩乇仨毻耆摩痢ⅵ潞挺?，因而灰狼群的解更新過程主要由α, β和δ進行引導和指示。在支配性灰狼引導下灰狼位置更新數(shù)學模型表示如下：

式中：X(t)為當前灰狼的位置向量；t為當前迭代次數(shù)；Xp為支配性灰狼（獵物）的位置向量；D為距離向量；A和C為協(xié)同系數(shù)向量；a為參數(shù)，隨迭代次數(shù)的增加從2 逐漸降低到0；r1和r2為0～1 隨機向量。模擬灰狼攻擊獵物行為，在α、β、δ的同時引導下，X(t)更新數(shù)學模型表示如下：

2.2 IGWO設計

基于GWO 基本原理設計IGWO，如圖1 所示，主要包括編碼與解碼、生成初始灰狼群、解評價與更新機制以及局部搜索等算子。

圖1 改進灰狼算法流程圖

2.2.1 編碼與解碼

采用基于隨機鍵編碼的最大順序值規(guī)則（larg?est order value,LOV）［17］，將灰狼位置坐標的連續(xù)數(shù)值映射為離散數(shù)值。

編碼過程如下：根據(jù)車間數(shù)量，生成含F(xiàn)個片段且長度為n的隨機向量，如編碼串{π1,π2,…,πθ1,|,…,|,πθF-1+1,…,πn}，“ |”為分配到不同車間工件之間的分隔符，工廠f分配的工件數(shù)為

解碼過程如下：對編碼數(shù)組

中的數(shù)值作降序排列，然后將相應數(shù)值轉換為排列順序的離散值，得到中間數(shù)組：

再根據(jù)式（14）將中間數(shù)組映射為加工排序向量。

為清晰說明解碼過程，以含有5個工件的單個車間調度問題為例。隨機生成灰狼個體向量Xi為［0.62,0.46,0.81,0.31,0.13］，如圖2 所示。依編碼序列的數(shù)值大小對不同編碼位置依次分配2、3、1、4和5，得到中間序列φi為［2,3,1,4,5］，通過式（14）可得：當k為1 時，φi,1為2，πi,2為1；當k為2 時，φi,2為3，πi,3為2；當k為3時，φi,3為1，πi,1為3；當k為4時，φi,4為4，πi,4為4；當k為5時，φi,5為5，πi,5為5。進而獲得解碼后的工件加工序列：

圖2 隨機向量解碼過程示例

以2個工廠、10個具有2道工序的工件加工調度為例，設灰狼編碼向量為［0.12,0.94,0.64,0.56,0.91|0.78,0.71,0.32,0.51,0.19］。第1個編碼向量片段［0.12,0.94,0.64,0.56,0.91］，解碼后獲得的加工順序為［2,5,6,7,3］；另一工廠編碼向量片段為［0.78,0.71,0.32,0.51,0.19］，解碼后獲得的加工順序為［4,9,8,10,1］，2個工廠對應的加工調度方案的甘特圖如圖3所示。

圖3 實例甘特圖

2.2.2 灰狼群初始化

隨機生成N個灰狼個體，構造初始灰狼群。任意灰狼位置編碼Xi為[xi,1,xi,2,…,xi,n]，其中xi,j為向量的第j維取值，得：

式中：ju和jl分別為第j元素的上界和下界；n為工件總數(shù)；R為0～1隨機數(shù)。

2.2.3 評價和更新機制

基于問題目標，將灰狼個體適應度函數(shù)定義為

計算每個灰狼的適應度，并按照適應度從大到小的順序排列，進而確定α、β和δ。

在灰狼群迭代更新過程中，為了避免種群退化，采用精英保留策略，將適應度最好的3 個個體α、β和δ直接保留至下一代，其他灰狼個體的位置按照式（9）的更新機制進行，即以α、β和δ的位置指引其他灰狼向獵物方向搜索。

2.2.4 局部搜索

工件交付時間為加工工廠的完工時間與運輸時間之和，而后者為固定值，因而目標函數(shù)值取決于工件交付時間最長的工廠l的完工時間。為縮短工廠l的工件交付時間，改變工件數(shù)量、類型和加工順序，提出3種基于工件分配方案和加工順序變動的局部搜索策略，具體操作如下：

1）工廠間工件交換。將交付時間最長的工廠l與其他任意工廠l′的1個工件交換，若交換后最大交付時間減小，則更新最優(yōu)解。

2）工廠間工件插入。任選交付時間最長的工廠l的1個工件插入交付時間最短工廠l′的加工序列，若變換后的最大交付時間減小，則更新最優(yōu)解。

3）工廠內工件移位。任選交付時間最長的工廠l的1個工件，將其插入加工序列的其他位置，若工件移位后的最大交付時間減小，則更新最優(yōu)解。

3 實驗結果與分析

考慮運輸時間對分布式置換流水車間調度問題的影響，對文獻［6］中32 組算例進行改進，增加各工廠至客戶的運輸時間。對于含2 個工廠的算例，假設各工廠到客戶的運輸時間分別為120 min和180 min；對于含3個工廠的算例，假設各工廠到客戶的運輸時間分別為120 min、150 min和180 min?；谏鲜鏊憷?，采用MATLAB2016a，Windows10，Intel i5 2.5GHz，RAM 8GB 的運算測試環(huán)境，使用IGWO GWO 和GA（遺傳算法）求解，算法參數(shù)設置參考文獻［17］。將3 種算法的種群規(guī)模均設置為100，最大迭代次數(shù)設置為200。GA 的交叉概率為0.4，變異概率為0.08。

3種算法對各測試算例分別運行40次，求解每次運算的C。基于運算結果的最小值Cmin、平均值Cave、平均相對誤差Eare來比較3 種算法的求解質量［18］。Eare表示為

式中：C?為目前已知的下界值。

3 種算法對算例的計算結果如表2～4 所示，可以看出，采用IGWO求得的Cmin、Cave均不低于GWO和GA，Eare也優(yōu)于GWO 和GA。這是因為GWO 在求解離散流水車間調度收斂速度慢，后期容易陷入局部收斂；GA因為隨機生成初始種群，生成的個體適應度較低，影響種群的收斂速度和最終解的質量。由此可見，IGWO對求解文中問題有更好的效果，提出的局部搜索算子能有效提升求解質量。

表2 IGWO仿真結果

表3 GWO仿真結果

表4 GA仿真結果

4 結論

針對考慮運輸時間的分布式置換流水車間調度問題，建立以最小化最大交付時間為目標的數(shù)學模型，采用改進的灰狼算法對問題進行求解，并在優(yōu)化過程中加入局部搜索算子，更好地平衡算法的全局探索與局部開發(fā)最優(yōu)解的能力，通過MATLAB對大量算例進行仿真計算，與傳統(tǒng)遺傳算法和灰狼算法進行比較，證明改進的灰狼算法對研究問題的求解具有優(yōu)越性。文中針對分布式置換流水車間環(huán)境，僅考慮了交付時間對訂單分配和加工排序的影響，未考慮訂單交付期約束以及工件裝配調度過程，后續(xù)可在考慮這些因素情況下進行擴展研究。