考慮多時間因素的綠色柔性作業車間動態調度*

衛少鵬，王 婷，2，周 彤

(1.貴州大學管理學院，貴陽 550025；2.貴州省互聯網+協同智能制造重點實驗室，貴陽 550025)

0 引言

隨著精益生產的盛行，制造業在生產過程中對質檢的應用越來越廣泛。為了減少殘次品的數量，綠色柔性作業車間調度需要對關鍵工件的特殊工序穿插質檢環節。質檢環節使得緊鄰工序間隙較大，造成機器空轉能耗較高，尤其是返修、報廢等問題的存在，嚴重影響了生產過程的流暢性，極大擾動了原始生產計劃。綠色動態車間調度基于事件驅動的重調度策略，通過重新調整工件的加工順序，同時匹配高效率、低能耗的加工機器，從而達到節能減排、按時交貨的雙重目標。

當前，國內外學者對柔性作業車間動態調度的研究成果較為豐富。Nouiri M等[1]針對機器故障問題提出了一種動態節能調度；張守京等[2]針對重調度問題提出了免疫度概念；成榮榮等[3]基于完工時間和總成本指標進行建模，分別對4類動態事件設計了重調度策略；孫麗珍等[4]針對工件批量加入和機器故障問題的重調度問題采取了改進的遺傳算法進行求解；Liu B等[5]設計了一種快速分布估計算法帶有模糊時間的柔性作業車間動態調度問題；李聰波等[6]建立了多目標重調度節能優化模型，引入多目標引力搜索算法進行求解；王雷等[7]引入了可變重調度區間策略，避免了重調度和原調度方案差別過大；陳超等[8]提出了一種退火遺傳算法求解動態節能調度問題；劉燚等[9]將事件驅動策略和滾動窗口技術應用于動態調度問題。

綜上所述，以往的動態調度研究僅關注加工環節的相關指標優化，較少考慮到輔助加工時間的影響，如：調整時間、質檢時間。輔助環節對生產系統的效率和能耗均有較大影響，探明其影響機理極其重要。鑒于此，以下動態車間調度選取最大完工時間和機器總能耗為優化指標，同時考慮機床輔助環節的調整時間和質檢時間，建立了綠色動態車間調度模型，用線性加權法將多目標轉化為單目標。采用新型群體智能算法—頭腦風暴算法進行求解，對編碼環節進行改進，引進了轉換機制，設計了多層編碼方式，有效提高了最優解的收斂速度和精度。

1 問題描述與數學建模

1.1 問題描述

考慮多時間因素的柔性作業車間綠色動態調度描述如下：假設n個工件在m臺機器上加工，每個工件有h道工序，所有工序按照固定的工藝路線在柔性機器上完成操作。其中，所有工序Ojh在加工之前要考慮調整時間，部分關鍵工序在加工前要同時考慮調整時間和質檢時間。

在生產過程中，機器的能耗可以分為兩部分：加工能耗和等待能耗。加工能耗指的是機器在加工各道工序時產生的必要能耗；等待能耗指的是機器處于調整時間、質檢時間以及空閑時間時產生的非必要能耗，這部分能耗在保證工藝質量的前提下，應盡可能減少。結合實際情況，質檢過程處理結果分為兩種：合格和返修。若該工序的質檢結果為合格，則直接進入下一道工序的加工；若結果為返修，則需要返回到有問題的指定工序進行加工，再以指定工序為起始工序直至完成加工任務。此外，調度過程需滿足以下假設條件：①所有工件均可在0時刻進行加工；②每臺機器在同一時刻只能加工一個工件；③所有工序一旦開始就不能中止；④同一工件的加工工序分先后順序；⑤質檢時間和調整時間之間不分先后順序，可以同時并行；⑥不考慮機器故障問題。圖1為不考慮質檢擾動的原始調度甘特圖。

圖1 未考慮質檢時間的動態調度甘特圖

考慮質檢擾動的重調度甘特圖如圖2所示。

圖2 考慮質檢時間的動態調度甘特圖

圖中紅色方格和綠色方格表示質檢工序的時間，紅色方格表示工件的工藝加工質量不達標，需重新加工；綠色方格表示檢驗合格，直接加工下一道工序。調整時間和質檢時間不分先后，可同時進行。

1.2 能耗模型

(1)加工能耗：機器對工件進行車、銑、磨等工藝加工時，所消耗的能量。這部分能耗可通過二次多項式擬合曲線求得，公式為：

(1)

式中，E1為加工能耗；α1、α2是二次多項式的擬合曲線系數；xijh為0-1變量；Ym1為機器加工功率；m為機器總數；Pijh為第j個工件的第h道工序在機器i上加工時間。

(2)空轉能耗：機器在等待加工的過程中消耗的能量，包括：工件等待時間、機器調整時間、工件質檢時間，公式為：

(2)

式中，E2為空轉能耗；xijh為0-1變量；Ym2為機器空轉功率；Cjh為第j個工件的第h道工序加工完成時間。

綜上所述，能夠得到所有機器的綜合能量消耗表達式為：

(3)

式中，E為機床總能耗。

1.3 綠色動態調度模型

綠色柔性作業車間動態調度模型，同時兼顧經濟指標和綠色指標，即最大完工時間和機器總能耗。模型函數和約束條件為：

(4)

式中，Cmax為最大完工時間。其中，Cmax=min(max(Cj))為最大完工時間的計算公式。約束條件為：

Hijh=Cj(h-1)+Vijh

(5)

式中，Hijh為工件j的第h道工序在機器i上的允許開始加工時間；Vijh為工件j的第h道工序在機器i上的調整時間。

Hijk=Cj(k-1)+Rijh

(6)

式中，Rij為工件j的第h道工序在機器i上的質檢時間。

Hijh′=max(Hijh,Hijk)

(7)

式中，Hijh′為工件j的第h道工序在機器i上的實際開始加工時間。

Cjh=Hijh′+Pijh

(8)

式中，Cjh為工件j的第h道工序的完工時間

(9)

式中，mjh為第j個工件的第h道工序的可選加工機器數；xijh為0-1變量。

式(5)表示調整時間約束；式 (6)質檢時間約束；式(7)表示質檢時間與機器調整時間中的較大者；式(8)表示同一時刻同臺機器只能加工一道工序；式(9)屬于機器約束，表示同一時刻同一道工序能且只能被一臺機器加工。

多目標優化模型的求解大致可分為兩類：加權優化模型和帕累托優化模型。為了便于決策者調節指標權重，尋找更有針對性的調度方案，選取加權優化模型進行求解。采用加權歸一的方式，將多個目標的量綱進行統一，式(4)可進一步描述為：

(10)

2 頭腦風暴算法

頭腦風暴算法是一種模擬人類群體決策過程的群體智能優化算法。采用文獻[10]的頭腦風暴算法流程框架，在單目標算法的基礎上引進能耗指標，設計了多目標頭腦風暴優化算法。通過k-means聚類方法，不斷把解集里的較好解挑選出來并聚集在一個較小的解空間里，提高了全局搜索能力；在舊解的基礎上產生新解的迭代方式保證了種群的多樣性，增強了局部搜索能力。

2.1 編碼

編碼是頭腦風暴算法的關鍵環節，能夠保證算法的收斂速度。為了避免單一編碼方式導致解的表達不清楚，采用文獻[11]設計的多層編碼方式。每個個體分為兩層{工序層S ,機器層M }，采用整數編碼方式。如：{31232 / 31213}，工序層數字代表工件編號，數字重復出現的次數表示工件的某道工序，即第4位的3表示工件3的第二道工序；機器層數字代表機器編號。

2.2 重調度種群初始化

為了提高初始化種群的質量，依據種群個體的位置矢量向工序排序轉換。首先，得到隨機排序的工序層集合S0的位置矢量，按照位置矢量大小重排后，得到優化后的集合S。

表1 個體位置矢量向工序排序轉換

由表2可知：解碼后的工序優先度為O21→O31→O32→O11→O22。

(2)機器層編碼方案

機器層編碼為工序指派機器的集合M，其基因是工序所選擇的可用機器。首先，得到隨機指派集合M0的位置矢量，若位置矢量是整數則為有效編碼，即為指派機器編碼；否則屬于無效編碼，對位置矢量的大小向下取整，待指派的機器集合M。個體位置矢量向指派機器轉換如表2所示。

表2 個體位置矢量向指派機器轉換

最后，將編碼工序層和機器層編碼組合在一起，表示優化后的1個可行解: {31 232 / 31 213}。為了避免非法染色體的產生，第2層編碼對應指派工序的機器為該工序的“第幾個”可用機器，而不是全部機器。

2.3 適應度函數

在頭腦風暴算法迭代的過程中，適應度值越高，被保留的概率就越大。以下研究的適應度函數設置為式(10)。

2.4 BSO解的分類和聚類

BSO的聚類過程是決定優化效果的關鍵步驟，主要作用是將不同的個體分類，讓相似個體處于同一個類中。由于k-means聚類算法具有運算速度快、簡單等優點，故采用k-means不斷把較好解挑選出來，并聚集在一個較小的解空間里。

BSO的分類操作是基于已有的舊解來產生新解。分類操作采用高斯變異方式：

(11)

其中，w1+w2+wn=1。

(12)

式中，T為最大迭代數；t為當前迭代數；k為控制搜索步長的調整系數，作用是平衡算法的收斂速度；rand()為隨機函數。

2.5 算法測試

為了驗證算法的性能，選取3個標桿案例[12-14]中的算法與當前算法進行對比，指標選取最大完工時間，參數設置和標桿文獻相同。標桿文獻的算例規模分別為：6×6、8×6、10×6，結果如表3所示。

表3 不同規模問題的算法對比

從表中可以看出，IBSO算法的收斂速度和精度均優于其他算法，驗證了算法的可行性和高效性。在6×6的實例中，IBSO稍稍優于CE-MOFJSP；在8×6的實例中，IBSO算法的性能最大提高了18.3%，且迭代次數遠遠低于標桿文獻的迭代次數，優化效果最為明顯；在10×6的實例中，性能也提高了14.5%。

3 實驗與結果分析

用Matlab2018a軟件進行程序編譯，實驗環境配置如下：Intel Core i5-4210 2.6GHz CPU、4.00RAM、Windows 10 64位操作系統。參數設置為：終止迭代數500；種群規模50；Pclustering=0.8;Pgenetation=0.2。為了衡量原始調度和重調度的偏離度，采用相對偏差來表示原始調度和重調度間的完工時間和能耗偏差，公式如下：

(13)

(14)

因為當前沒有綠色柔性作業車間動態調度的標準實例，所以機器的加工數據采用來自文獻[15]的10×10測試數據，而測試數據不包含調整時間，將工序對應的調整時間設定為不超過4的隨機數，質檢時間和擾動工序為隨機生成。機器能耗的設置參考文獻[16] ，機器的額定功率和空載功率設置如表4所示。

表4 所有機器的加工功率 (kW)

算例為10個工件在10臺機器上加工，共有30道工序。需要質檢的工序為：1-1、3-1、4-1、6-1，對應的質檢時間為：4.8 min、5 min、6.3 min、5.5 min。質檢時間是固定的，不隨機器的不同而改變。運算結果如表5所示。

表5 數值計算結果

從表5可以看出，完工時間指標和能耗指標是互斥的。原始調度和重調度方案隨著α值的升高，完工時間逐漸縮短，而能耗不斷增加。根據指標權重的特點將生產模式分為三類，便于企業決策者挑選適合的最優解。

為了反映重調度和原始調度的偏差變化情況，繪制了完工時間和能耗的偏差變化趨勢，如圖3所示。

圖3 完工時間和能耗的偏差變化趨勢

從圖3可知，隨著完工時間指標權重的增大，RT1直線的波動較小。這是因為原始調度和重調度完工時間的偏差值始終穩定在8附近，帶入完工時間偏差式(13)后，結果變化不大；RT2直線波動較大，由最大值0.45降至0.2，能耗擾動偏差降低了55.6%。由于重調度方案的加工工序變多，必要的等待能耗和加工能耗增大，致使算法的搜索迭代空間更大，能耗結果的分布更加離散。隨著能耗指標的增大，搜索強度提高，使得能耗偏差逐漸縮小至一定范圍內。圖4為原始調度和重調度的最優前沿分布圖。

圖4 原始調度和重調度的最優前沿分布

由圖4可以看出原始調度和重調度的帕累托解均勻、全面地分布在最優前沿上，驗證了算法和模型的有效性和可行性。原始調度方案和對應的重調度方案，其完工時間偏差值和能耗偏差值較為穩定，表明基于以上模型和算法的調度方案可有效將質檢工序帶來的完工時間擾動和能耗擾動控制在一定范圍內，保障了生產過程的穩定性和高效性。由于篇幅有限，僅展示重調度之后的甘特圖。

根據企業面臨的實際情景，以速度為導向規則的重調度甘特圖如圖5所示，完工時間為28.2 min，能耗為1 064 kJ。

圖5 速度導向下的重調度甘特圖

圖中，紅色和綠色方格表示質檢時間，紅色表示需要返工，綠色表示質檢合格；質檢時間上方的條紋方格，表示調整時間，且調整操作和質檢操作可以同時進行。黑色方格表示工件返工后被重新調度后所進行的安排。從圖中可以看出，所有工序在各機床的分配較為均勻，機器負載也更為合理。

不同模式下的原始調度方案不同，故對應的重調度方案也不同。當企業需要推行綠色生產，則以能耗為導向規則進行重調度，甘特圖如圖6所示，完工時間為44 min，能耗為859 kJ。

圖6 能耗導向下的重調度甘特圖

圖中，機器3、6、9承擔了較多的加工任務，且每道工序的加工時間也較長。通過分析機器的加工特性可知，機器3、6、9的節能屬性較好，加工功率較低，故工件都傾向于流向這幾臺機器。機器8在加工各工件的功率只有3 kJ，而流向該機器的只有工序3-1，這是由于機器8的整體加工時間過長，限制了更多的工序流向該機器。

兩種規則導向所產生的實際效應差異較大。速度相差15.8 min，速度導向下的調度方案速度提高了35.9%；能耗相差205 kJ,能耗導向下的調度方案可以節省能耗19.3%。企業決策者根據生產的實際需要，可靈活選擇不同的方案，保障企業效益最大化。

4 結論

以綠色柔性作業車間為研究對象，針對質檢擾動引起的完工時間長和能耗高的問題，對綠色動態調度優化問題進行了研究，得出以下結論：

(1)建立節能調度數學模型，采用改進的頭腦風暴算法進行求解，可有效將質檢擾動的影響控制在一定范圍內，保證了生產的穩定性和流暢性。用算例進行檢驗，原始調度和重調度的帕累托最優解集的分布較為均勻、全面，驗證了模型和算法的有效性

(2)改進了頭腦風暴算法，提高了最優解的收斂速度和精度。在編碼環節引進了轉換機制和多層編碼策略，有效提高了初始種群的質量。通過與其他算法作對比，驗證了算法的可行性與高效性。

(3)決策者根據生產情境選擇恰當的綠色柔性作業車間動態調度方案，在保障交付期的前提下，將生產能耗降至最低，有利于企業降低生產成本、推行可持續發展戰略。