考慮調整時間的綠色柔性作業車間調度研究*

衛少鵬，王 婷，2*，周 彤

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

0 引 言

綠色車間調度作為綠色制造的重要依托技術，通過合理分配資源、調整加工順序，達到節能減排、降低成本的目標。在實際生產過程中，裝夾、對刀等輔助操作所消耗的時間和能量占據較大比例，探明調整環節在綠色作業車間調度中對完工時間和能耗的影響具有重要意義，能夠更加有效地指導柔性作業車間的綠色生產。

在模型建立層面，綠色車間調度模型在保證經濟指標正常運行的同時，還要兼顧綠色指標的優化約束，屬于多目標優化模型。根據處理方法的不同，模型可以分為兩類：加權優化模型和帕累托優化模型。

(1)在加權模型的研究中，DAI等[1]考慮到生產對環境的影響，選取能耗和完工時間作為優化指標，利用加權法將兩個指標合并為單個指標，采用單目標算法對模型進行了求解；解瀟晗等[2]針對柔性作業車間的節能調度問題，選取能耗作為綠色指標，降低了運行過程中的切削能耗、負載能耗等；王建華等[3]針對具有機器柔性和折舊特性的調度問題，同時考慮機器啟動、負載、空轉、停止環節消耗的能耗，通過為工序匹配相對節能的機器，降低了生產過程中的能耗。

(2)在帕累托模型的研究中，張斯琪等[4]以完工時間為經濟指標，以能耗浪費和噪音污染為綠色指標，建立了綠色車間調度模型；ZHANG等[5]以最大完工時間、相鄰工件完工時間間隔、機器負載和碳排放量優化指標，并考慮了機器加工、輔助材料、工具磨損和運輸過程的碳排放；吳秀麗等[6]從考慮機器轉速的角度進行了節能調度研究，構建了帶有多機器轉速的生產模型。

綜上所述，大多數研究集中在加工環節，如：時間、能耗、噪音、機器負載、機器轉速等因素，較少考慮到加工輔助環節，如：機器調整、物料運輸、生產準備等工藝過程，尤其機器調整環節的裝夾、定位、對刀、測量等輔助操作，消耗了大量的時間、能源和人資，對綠色生產具有較大影響。因此，對此進行深入研究能夠更好地發掘制造企業節能減排的潛力。

在算法設計層面，目前對經典智能算法的引用和改進較為普遍。其中，裴小兵等[7]提出了基于三方博弈的改進遺傳算法，通過完工時間、總機器負荷和臨界機器負荷3個目標間的博弈得到了帕累托最優解；楊振泰等[8]設計了融合Powell搜索法的遺傳算法，有效加強了遺傳算法的局部搜索能力；張于賢等[9]針對蟻群算法收斂速度慢且易陷入局部最優解的問題，加入了基于生物記憶曲線原理的信息素更新規則，驗證了改進算法的優勢；劉洪銘等[10]為了避免粒子群算法易早熟的問題，利用自適應權重和混沌方法改進了粒子群算法，提高了粒子的利用率，平衡了全局和局部搜索能力；趙敏等[11]為了改善人工魚群算法在搜索后期盲目性大、精度低等問題，加入了步長參數分解和柔性參數設置等策略,并在算法后期加強了局部搜索能力。此外，還有其他改進遺傳算法[12-14]、改進蟻群算法[15，16]、改進粒子群算法[17-19]、改進魚群算法[20]等。

綜上所述，經典智能算法的研究和應用已趨于成熟，性能提升難。同時，在處理大規模的組合優化問題時，傳統算法具有明顯局限性，難以獲得滿意的求解精度和速度；而新型群智能優化算法融合了群體優化方法和數據挖掘方法，在求解復雜問題時表現出較大優勢，是智能算法未來的發展趨勢[21]，對其進行探索研究具有更大的意義。

鑒于此，本研究以完工時間和機器總能耗作為優化指標，綜合考慮機器調整環節的完工時間和總能耗，建立帶有調整時間的綠色車間調度模型，運用加權歸一方式對兩個指標的量綱進行統一，依據指標的賦值特點，將生產分為3種不同的模式；采用頭腦風暴優化算法對綠色調度模型進行求解；算法融合群體智能優化方法和數據挖掘策略，可實現滿意解的快速收斂。

1 綠色柔性作業車間調度模型

1.1 問題描述

考慮調整時間的綠色柔性作業車間調度問題(以下簡稱GFJSP)描述如下：n個工件在m臺機器上加工，每個工件有多道加工工序，所有工序在加工前均需進行調整操作；調整操作和加工操作之間沒有等待時間，且調整操作只能在加工操作之前；只考慮機器加工的柔性，不考慮工件工序的柔性，即工件的工序順序是確定的；工件的加工時間和調整時間的長度取決于所選機器的加工特點和性能。工件n的第h道工序的Ojh具有可選擇的機器數mjh(mjh

綠色調度就是在滿足工藝加工的前提下，通過為每個工件分配高效或節能的加工機器、確定不同工序間的最佳排序，達到綠色環保、按期交貨的優化目標。

為了便于理解，筆者給出2個工件在3臺機器上加工的簡單實例。

2×3 GFJSP問題加工和調整時間表如表1所示。

表1 2×3 GFJSP問題加工和調整時間表

表1可以描述為2個工件在3臺機器上進行加工，調整時間和加工時間用“/”隔開，“-”表示該工序不能用上面的機器進行加工，其他工序均可。

柔性作業車間生產流程圖如圖1所示。

圖1 柔性作業車間生產流程圖O—加工時間；A—調整時間；連線—工序可用的加工機器

1.2 考慮調整時間的綠色調度模型

從生產效率和生態環境的角度出發，調度指標選取最大完工時間和機床總能耗。

(1)最小化最大完工時間?？s短工件的生產周期，保障企業能夠準時交貨，是調度研究中最根本的優化指標。

Cmax=min(max(Cj))

(1)

式中：Cmax—最大完工時間；Cj—工件的完工時間；n—工件總數；j—機器序列，j=1,2,3…n。

(2)最小化總能耗。主要的節能減排方式，企業降低成本、保護環境。

E=E1+E2

(2)

式中：E—機床總能耗；E1—機床加工狀態的能耗和；E2—機床空轉狀態的能耗和。

E1=∑mYm1∑i,jxijh×Pijh

(3)

式中：xijh—0-1變量；Ym1—機器加工功率；m—機器總數；Pijh—第j個工件的第h道工序在機器i上加工時間。

其中：xijh是0-1變量，如果工序Ojh選擇機器i，xijh值為1，否則為0；i=1,2,3…m。

(4)

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

將式(3，4)代入式(2)得：

(5)

綠色調度模型受到的約束如下：

Cjh-Sjh=Vijh+Pijh

(6)

式中：Sjh—第j個工件的第h道工序調整開始時間；Vijh—第j個工件的第h道工序在機器i上調整時間。

Sjh+Vijh≤Hjh

(7)

式中：Hjh—第j個工件的第h道工序加工開始時間。

Sjh+xijh×(Vijh+Pijh)≤Cjh

(8)

式中：Cjh—第j個工件的第h道工序加工完成時間。

Cjh≤Sj(h+1)

(9)

式中：Sj(h+1)—第j個工件的第h+1道工序調整開始時間。

Cjhj≤Cmax

(10)

式中：Cjhj—所有工件的完工時間。

Sjh+Vijh+Pijh≤Skl+L(1-yijhkl)

(11)

式中：L—工序序號；yijhkl—0-1變量。

其中：yijhkl是0-1變量，如果工序Oijh先于Oikl加工,yijhkl值為1，否則為0；L=1,2,3…hj。

Cjh≤Sj(h+1)+L(1-yiklj(h+1))

(12)

式中：yiklj(h+1)—0-1變量，k=1,2,3…n。

(13)

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

(14)

式中：hj—第j個工件的工序總數；xikl—0-1變量。

(15)

式中：hk—第k個工件的工序總數；xijh—0-1變量。

Sjh≥0,Cjh≥0

(16)

式中：Sjh—第j個工件的第h道工序調整開始時間；Cjh—第j個工件的第h道工序加工完成時間。

式(6)表示工序的加工時間和調整時間之間沒有間隔時間；式(7)表示工序的調整時間在加工時間之前；式(8，9)屬于工件約束，表示每個工件的工序的先后順序約束；式(10)表示所有工件的完工時間不能超過最大完工時間；式(11,12)表示同一時刻同臺機器只能加工一道工序；式(13)表示同一時刻同一道工序能且只能被一臺機器加工；式(14,15)表示每臺機器存在循環操作；式(16)表示每個參數變量均為正數。

為了便于決策者調整能耗和時間的目標權重以適應不斷變化的環境，筆者采用歸一法消除不同目標之間的量綱，再用加權法將多個目標合并，處理后的目標函數表達式如下：

(17)

式中：α—完工時間權值；β—能耗權值；Cmax—最大化完工時間值；Cmin—最小化完工時間值；C—當前完工時間值；Emax—最大能耗值；Emin—最小能耗值；E—當前能耗值。

其中：α+β=1。

2 頭腦風暴優化算法

史玉回教授[22]2011年提出了頭腦風暴優化算法。算法的核心思想是：不斷在他人方案的基礎上提出新方案，對比后保留較好方案，并重復這一過程，最終得到最佳方案。

2.1 BSO編碼與解碼

2.1.1BSO的編碼方案

改進BSO算法的單一編碼方式為多層編碼方式。相較于單層編碼方式，多層編碼方式更能準確表達解。編碼分為兩層，分別是工序層和機器層，用集合S、M表示。為了便于理解，給出1個具體的編碼實例：{34125/32213}，工序層S={3,4,1,2,5}，機器層M={3,2,2,1,3}。

工序層中的數字代表工件，工件編號出現的次數對應該工件的第幾道工序，表中所有工件編號都只出現了1次，所以都是相應工件的第1道工序。

(1)工序層編碼方案

工序層編碼是1個集合S。初始得到隨機排序集合S0的位置矢量，依據位置矢量大小重排后，得到優化后工序優先度排序S。個體位置矢量向工序排序轉換如表2所示。

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

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

(2)機器層編碼方案

機器層編碼為工序指派機器的集合M，其基因是工序所選擇的可用機器。首先，初始得到隨機指派集合M0的位置矢量，若位置矢量不是整數，則屬于無效編碼。當出現無效編碼時，對位置矢量的大小向下取整，得到工序要指派的機器集合M。

個體位置矢量向指派機器轉換如表3所示。

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

最后，將編碼S和M組合在一起，代表優化后的1個可行解:{3412532213}。為了避免第1層(工序)基因對應的第2層(機床)基因超出工序可用機床范圍，即產生非法染色體，第2層編碼對應指派工序的機器為該工序的“第幾個”可用機器，而不是全部機器，有效避免了非法染色體的產生。

2.1.2BSO的解碼方案

(1)編碼意義。以上實例中的決策編碼G={3,4,1,2,5/3,2,2,1,3}，工序解碼得到U={3,4,1,2,5/3,2,2,1,3}，拆分后得到工序編碼S={3,4,1,2,5}和機器編碼M={3,2,2,1,3}。

S={3,4,1,2,5}表示的意義為：第1位的3表示工件3的第1個工序；第2位的4表示工件4的第1個工序；第3位的1表示工件1的第1個工序；第4位的2表示工件2的第1個工序；第5位的5表示工件5的第1個工序。

M={3,2,2,1,3}表示的意義為：第1位的3表示工件3的第1個工序用它的第3個可用機器加工；第2位的2表示工件4的第1個工序用它的第2個可用機器加工；第3位的2表示工件1的第1個工序用它的第2個可用機器加工；第4位的1表示工件2的第1個工序用它的第1個可用機器加工；第5位的3表示工件5的第1個工序用它的第3個可用機器加工。

(2)解碼過程。從S的第1個編號開始，第1位的3表示工件3的第1個工序被先加工，然后根據機器編碼找到其工序對應的是第3個可用機器。其全部可用機器集合為{2,3,5}，故第3個可用機器是機器5，即在機器5上開始加工，得到開始時刻和結束時刻。

依次可知S的第2個編號，代表工件2的第1個工序。工件2的第1個工序對應機器集合為{4,5,6}，根據機器編碼，它的加工機器是第2個可用機器，也即5號機器，則5號機器要等前1道工序加工完成后才能開始加工本工序，即本工序開始加工時刻等于5號機器上1個工序完成的時刻；以此類推完成整個調度。

2.2 BSO解的聚類

BSO的聚類算子是決定優化效果的關鍵因素，作用是將相似個體歸為同組。采用k-means聚類算法，以N個數據點作為輸入，把點的相似度作為分類標準，將N個點歸類到不同組別。通過k-means操作，不斷把更好的解挑選出來，最后將挑選后的所有解聚集在一個較小的解空間里。pclustering是隨機解替換聚類中心的概率參數，能夠避免算法早熟收斂，幫助算法跳出局部最優解。

其具體的實現步驟如下：

(1)聚類操作將n個解分為m個簇；

(2)確定簇心計算每個簇中所有個體的適應度值，將最優個體作為簇心；

(3)設置數值設定值pclustering，隨機生成rclustering值，p、r∈[0,1)；

(4)替換簇心當r

2.3 BSO解的分類

BSO的分類算子對結果的影響也很重要，其作用是基于舊解來產生新解。分類操作采用高斯變異方式，即：

(18)

其中：w1+w2+…wn=1。

(19)

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

其具體的實現步驟如下：

(1)確定rgeneration。生成一個區間在[0,1)的隨機數rgeneration；

(2)比較rgeneration和pgeneration大小。pgeneration為預先設定好的參數值；

(3)若rgenerationpgeneration時,將普通解加上隨機值得到新個體；

(4)若rgeneration>pgeneration,則隨機選擇2個簇，步驟可類比(3)；

(5)通過設定參數來保持上述4種方式產生的新個體的比例在新個體產生后，與舊個體進行比較，較優的個體將會被保留并作為新一代中的個體。

2.4 適應度值

綠色車間調度要同時優化完工時間和能耗指標，適應度函數選式(17)。式中，α、β分別為完工時間和能耗的權重，指標權重越高代表重要程度越高，在同等條件下，迭代優化時會優先處理權重高的指標。

2.5 BSO新解選擇及算法流程圖

新解選擇保證了種群的多樣性，操作是基于數據分析的保留策略將適應度更高的新解替換舊解，將個體逐一進行更新，直到達到最大更新代數。

頭腦風暴算法流程圖如圖2所示。

圖2 頭腦風暴算法流程圖

2.6 性能測試

2.6.1 實驗1

為了測試IBSO算法的性能，實驗1選取較為相近的標桿文獻[23]算例進行測試。算例為10×6的實際生產數據，以最小化最大完工時間為優化指標，終止條件為最大迭代代數到達100代，算法參數設置與文獻相同?？紤]調整時間的甘特圖如圖3所示。

由圖3可知：IBSO算法的最大完工時間為47 min，而文獻中IGA的最優解為55 min，最大完工時間縮短了8 min，效率提升14.5%。

圖3 考慮調整時間的甘特圖

考慮調整時間的收斂曲線如圖4所示。

圖4 考慮調整時間的收斂曲線

由圖4可知：IBSO的初始解66 min與IGA的初始解70 min基本相同；約經過10代的迭代之后，IBSO的解穩定在51 min左右，而IGA的解穩定在58 min左右，此時BSO的解已經優于IGA算法迭代終止的最優解；在迭代次數達到60代后，IBSO已經找到了最優解47 min，IGA則在90代之后找到了最優解55 min。IBSO在開始階段就快速收斂，之后收斂速度逐漸降低，驗證了IBSO的初始解集的質量較高，具有良好的全局搜索能力。

測試結果表明，IBSO算法優于IGA算法。

2.6.2 實驗2

實驗2的8×6的工件測試數據來自文獻[24]，由6個工件、8臺機器、26道工序組成。為了測試IBSO算法性能，目標函數選取最小化最大完工時間，算法初始參數設置相同。

實驗2收斂曲線圖如圖5所示。

圖5 實驗2收斂曲線

由圖5可知：IBSO算法的最優解為58 min。IBSO算法迭代到約80代時，已達到TLPSO 算法的最優值60 min，再經過30代迭代，達到最優值58 min，并一直穩定于該值。測試文獻中，普通粒子群算法(PSO)、雙層粒子群算法(TLPSO)、改進的雙層粒子群算法(ITLPSO)的最優解分別為71 min、66 min、60 min，IBSO求解的最大完工時間均有所減少，尤其比PSO算法降低了13 min。

4種算法的最大完工時間及迭代次數如表4所示。

表4 對比4種算法的最大完工時間及迭代次數

由表4可知：IBSO算法在收斂速度和精度方面均優于實驗2文獻的3種算法。

2.6.3 實驗3

實驗3的6×6工件測試數據來自文獻[25]，包含6個工件、6臺機器和15道工序。算法的目標函數和參數設置與文獻一致。

實驗3調度甘特圖如圖6所示。

圖6 實驗3調度甘特圖

由圖6可知：IBSO算法的最優解為10。文獻中CE-MOFJSP算法的最優解為11 min，最大完工時間縮短了1 min。IBSO算法迭代到70代時已達到CE-MOFJSP的最優解11 min，到80代時達到最優解10 min，而CE-MOFJSP算法在100代到達最優解11 min，收斂速度略快于文獻算法。

對比2種算法帕累托最優解和平均值如表5所示。

表5 對比2種算法的帕累托最優解

由表5可知：IBSO算法對應的帕累托解集均優于CE-MOFJSP，帕累托解平均值減少1.67 min，優化效率平均提高13.9%。該結果表明：IBSO算法優于CE-MOFJSP算法。

3 實驗與結果分析

某制造企業的零件加工車間屬于典型的柔性作業車間，每個工件在機床上加工時，都需要進行安裝、定位、對刀或測量等調整操作，調整時間的長短由機床特性和工人熟練程度決定。在保證質量和工藝的前提下，筆者通過制定適宜的調度方案來盡可能降低最大完工時間和機床總能耗。

仿真平臺選取MATLAB2018a，運行環境及配置為Intel Corei5-4210 2.6 GHz CPU、4.00 RAM、Windows 10 64位操作系統。參數設置為：最大迭代數為500；種群大小為50；選擇一個簇形成新個體的可能性Pclustering=0.8;選擇一個簇中心以替換為隨機生成的中心的概率Pgenetation=0.2。優化結果如表5所示。

實例中有8個工件，8臺機器。車間工件能耗與時間信息如表6所示。

表6 車間工件能耗與時間信息

為了說明數據的含義，筆者以表中工件1的第1道工序為例：工件J1的工序O11選擇M1加工時，加工時間為4 min，調整時間為1.5 min，加工功率為1 278 W，空轉功率為370 W，所有工件所有工序均依次類推即可。

筆者將指標間的權重系數組合分為10組，每組均在MATLAB環境下運算20次，再求出完工時間和能耗的平均值。

3種模式下的實驗結果如表7所示。

表7 3種模式下的實驗結果

由表7可知：根據指標權重的賦值特點，可將生產分為3種典型模式：綠色模式、綜合模式、高效模式。從表中可以看出，完工時間和能耗兩個指標在優化過程中的關系是相互沖突的，無法同時得到兩者的最優解，只能通過調整指標權重得到一組pareto最優解。整體來看，機器空轉能耗較高，總空轉能耗占總加工能能耗的21.36%；結合典型指標來看，當α=0，β=1時，最大完工時間為41.7 min，總能耗為156 252 J；當時，最大完工時間為34.2 min，總能耗為216 265 J。

兩種方案在生產效率和綠色環保方面表現出的優劣勢較為明顯，因此企業應結合具體面臨的生產情境，確定相應的生產模式，得到更有針對性的調度方案。筆者從3種模式中各選取1個代表方案，進行對比研究。

(1)綜合模式。企業在生產過程中，既有生產效率的壓力，又有綠色環保的規制，該情境適合采取綜合模式。取α=0.5，β=0.5時，最大完工時間為36 min，總能耗為176 719 J。

綜合模式下的甘特圖如圖7所示。

圖7 綜合模式下的甘特圖

由圖7可知：由于完工時間指標和能耗指標的權重相同，加工時間和加工能耗差異不大的機器所表現出的適應度值基本相同，故工件可選擇的機器數增加，工件在機床上的分布也較為均勻。機器8因為設備老化、維保不足等問題，各道工序加工能耗較高。由于能耗指標的限制，機器8未被安排加工任務。

(2)綠色模式。企業在面臨嚴格的環保規劃，或者客戶對訂單的交貨期要求比較寬松的情況下，可以采取綠色環保的生產模式，將能耗水平降至最低。取α=0.2、β=0.8時，最大完工時間為38.5 min，總能耗為156 670 J。

綠色模式下的甘特圖如圖8所示。

由圖8可知：機器3加工負荷最大。通過查找表6的工件能耗信息可知，機器3在加工O62、O12、O54工序時，相比所有可用機器，消耗的能量是最低的；在加工O41、O14工序時，也較為節能。多道工序在綠色模式下流向機器2，造成機器2的高負荷。同理，指派機器1加工O31、O23、O43工序，以及工序O71、O34在機器2上加工，都是最佳的節能機器匹配。機器8節能屬性較差，在該模式下不安排加工任務。

圖8 綠色模式下的甘特圖

(3)高效模式。當企業的生產訂單對時間因素較為敏感和嚴格的情況下，決策者可以采取高效生產模式。取α=0.8、β=0.2時，最大完工時間為35.3 min，總能耗為193 707 J。

高效模式下的甘特圖如圖9所示。

圖9 高效模式下的甘特圖

由圖9可知：在高效模式下，為了保證生產速度，工件主要選擇那些加工速度快的機器，并不注重加工能耗的高低，故能耗高的機器和能耗低的機器同時開始運行，使得工件的分布最為均勻。此時，機器8承擔了4道加工工序。相比與所有可用機器，機器8加工O12和O84時速度最快，加工O12和O84時速度次最快。

4 結束語

以往的綠色車間調度文獻沒有考慮機床調整時間及其能耗，導致調度方案和實際差別較大。針對這一不足，本文構建了帶有調整時間的綠色車間調度模型，在模型中綜合考慮了設備的調整和加工環節所產生的時間和能耗，并依據指標權重的特點將生產模式劃分為3類，使調度方案更加科學有效；在單層編碼頭腦風暴算法的基礎上，設計了多層編碼頭腦風暴優化算法，在搜索操作中應用群智能優化方法和數據挖掘策略，提高了求解的精度和速度；通過對標桿算例和生產實例進行仿真，驗證了本研究的模型和算法的有效性，實現了綠色車間調度。

針對未來的研究，筆者還會將車間生產的運輸環節和機器故障環節等多個生產過程進行集成后建模，融合其他智能算法，采用混合頭腦風暴算法進行求解，使綠色車間調度更完善、更高效。