考慮工件分批的混合流水車間節能調度研究＊

張中偉 孟 亞 李 藝 李元生 胡文博 惠延波

（河南工業大學機電工程學院，河南 鄭州 450001）

在強國戰略和“碳達峰、碳中和”背景下，制造企業積極推進節能減排是提高自身競爭力，實現可持續發展的重要因素之一。圍繞節能制造系統，目前主要從兩方面開展研究，一是在工序層面利用高效機床、優化加工工藝參數等；二是在制造系統層面從生產組織運行優化角度開展能耗優化[1]。對于后者，最具代表性的節能方法就是生產調度，其具有硬件成本投入低、適應性強的優勢，目前已得到廣泛地推廣應用。

混合流水車間涉及汽車生產、半導體封裝等國民經濟關鍵行業，混合流水車間調度問題（hybrid flow-shop scheduling problem，HFSP）在流水車間調度問題（flow-shop scheduling problem，FSP）的基礎上，在所有或部分加工階段引入多臺可選擇的并行機器。并行機的引入提高了車間生產能力和柔性，HFSP 亦被稱為柔性FSP。目前，針對HFSP 研究取得的成果眾多，在考慮工件分批的HFSP 研究方面：Zhong W 等[2]研究了考慮階段間作業分批運輸，以最大完工時間為優化目標的的兩階段HFSP，提出一種快速啟發式算法求解；王文艷等[3]研究了帶批處理的混合流水車間批量流調度問題，提出一種可變分批方法，并以最小化完工時間為目標建立了調度模型，進而提出了一種離散水波優化算法求解模型；張彪等[4]在考慮運輸和啟動作業的基礎上，研究了以最大完工時間和子批總數為優化目標的多目標變分批HFSP，建立了相應的混合整數規劃模型，進而采用自動算法設計方法來構造高性能的多目標進化算法求解模型。從工件分批的角度來看，這些研究主要考慮均等分批和可變分批兩種形式，且表明工件分批會影響調度性能指標。然而，目前考慮工件分批的HFSP 研究大都以時間、成本為性能指標[5-6]，對能耗或能耗相關指標考慮不足。

隨著制造業對節能減排和可持續發展的關注，以能耗為優化目標或約束條件的HFSP 研究逐漸成為車間調度領域研究熱點，代表性的如：張立萍[7]建立了以機器能耗為優化指標，并行機調度作業中工藝約束、資源約束等為約束條件的節能HFSP 模型，并采用混合差分進化算法求解；Dai M 等[8]考慮了不同并行機主軸轉速對能耗的影響，建立了具有能量意識的HFSP 模型，并利用遺傳-模擬退火算法求解模型；Li J 等[9]提出了一種能量感知多目標優化算法求解考慮工件裝夾準備能耗的HFSP；任彩樂等[10]面向節能的不相關并行機HFSP，基于Wagner 建模思想提出了一種以最小化能耗為目標的混合整數線性規劃模型，并采用改進的候鳥優化算法進行求解；雷德明等[11]提出了一種新型蛙跳算法求解以總加工能耗和總延遲時間為目標的低碳HFSP。這些研究提出的各種節能/低碳HFSP 模型和求解方法對后續相關研究有較強的借鑒意義，且研究表明：（1）在節能生產調度方法基礎上集成一些單機設備能效提升方法，如“關機/重啟”策略（即如果機床待機能耗大于將機床關閉，再重新啟動的能耗，允許將待機狀態下的機床關閉一段時間后重新啟動）、工藝參數優化，可進一步提升制造系統節能潛力；（2）開展節能生產調度時考慮實際加工過程中工件運輸、工件裝夾等因素對能耗的影響，有助于在保證車間生產節能效果的同時提升節能調度方案的實際可執行性。然而，目前開展的節能/低碳HFSP 研究主要面向多品種單件產品，而車間實際生產過程中為了便于物料準備與追蹤，質量管控與回溯，常進行分批生產，因此面向混合流水車間，在生產調度時進行工件分批是否有助于提升制造系統節能潛力以及如何合理設置工件批量以獲得較優的節能效果是現有研究缺失和有待進一步探索的地方。

為此，本文結合生產實際，開展考慮運輸時間、換刀時間約束，面向分批生產的混合流水車間節能生產調度研究，構建了以能耗和最大完工時間為優化目標，集成“關機/重啟”節能策略的混合流水車間節能調度（energy-efficient hybrid flow-shop scheduling，EHFS）模型。進而，利用非支配排序遺傳算法（nondominated sorting genetic algorithm-II，NSGA-II）求解模型，并結合實際案例進行模型節能效果和求解方法有效性的驗證。

1 問題描述與建模

1.1 問題描述與建模假設

EHFS 涉及n類工件，第i類工件的總加工批量為DMi，i=1,2,···,n。每類工件均有u道工序，第k道工序存在mk臺并行機，k=1,2,···,u，共涉及w臺機床，。考慮到生產過程均衡性，設定每類工件在相鄰兩加工階段間的轉移時間T相同，且為常量。假設采用均等分批，第i類工件的平均批量為ABi，其可劃分的批次數BNi=ceil(DMi/ABi)，ceil表示返回大于或等于輸入變量的最小整數的函數，則對于第j個批次的批量Bij，j=1,2,···,BNi，存在Bij≤ABi。對于機床m，m=1,2,···,w，加工每類工件i使用的刀具不同，所需換刀時間（含換刀后的對刀調整時間）TCim不相同。此外，本文在能耗優化時僅考慮機床能耗，忽略加工所用刀具、工件毛坯、切削液等物料的蘊含能和維持照明、通風、溫度、濕度等加工環境的能耗[12-13]。

進而，EHFS 以所有工件的加工總能耗（Etotal，J）和最大完工時間（Tmakespan，s）為優化目標，針對各類工件，合理劃分加工批次，并為各工件批次工序選擇合適的加工機床，合理安排各機床上工件批次工序的加工順序和應用“關機/重啟”節能策略，得出最優的調度方案。建模所需假設條件如下：

（1）所有機床零時刻可用，配套的加工刀具未經加工磨損，所有加工任務零時刻下達。

（2）任意工件批次工序一旦開始加工就不允許中斷，直到加工完成。

（3）每臺機床在任意時刻只能加工一個工件批次工序。

（4）各工件批次在其每個加工階段只能選擇一臺該階段的并行機加工。

（5）不考慮各工件批次初始加工階段之前和加工完成后的運輸。

（6）每臺機床加工第一個工件批次工序前不考慮換刀。

（7）各工件批次間無優先級關系。

（8）各類工件在相關并行機加工的工藝規程和參數已預置給定。

1.2 模型表示

結合問題描述和建模假設，表示EHFS 模型時所需的主要參數和決策變量分別如表1 和表2 所示。

表1 模型參數定義

表2 決策變量定義

根據機床執行加工任務的活動狀態，Etotal由加工能耗Ec、換刀能耗Etc和待機能耗Es組成。

Ec和Etc可一步表示為

Es指機床因等待作業任務閑置階段消耗的能量。對于機床m，其在加工第c和第c+1 個工件批次工序間的理論待機能耗可表示為

當相鄰工件批次工序間隔較長采用“關機/重啟”策略后，Es可表示為

進而，EHFS 模型目標函數為

約束條件：

式（8）表示基于刀具磨鈍標準的工件均等分批批量設置范圍，且各類工件平均批量確定后，所分批次數目隨之而定。式（9）表示每類工件的加工總量等于所分各批次批量之和。式（10）表示各工件批次工序只能選擇一臺機床加工。式（11）表示每類工件各批次工序在分配機床上的加工開始時刻和完成時刻之間的間隔為其加工時間。式（12）表示分配至同一機床加工的工件批次工序不允許加工時間重疊，且各工件批次工序的加工開始時刻受換刀因素約束。式（13）表示同一工件批次存在工序順序約束和運輸時間約束。式（14）表示各工件批次工序的加工開始時間非負。式（15）表示機床加工工件批次工序的換刀約束。式（16）表示機床待機狀態下應用“關機/重啟”節能策略的約束。

2 模型求解

HFSP 是典型的NP-hard 問題，一般很難求其精確最優解，而啟發式算法和智能優化算法求解此類問題近似最優解的有效性和實用性已被許多研究證實[14]。EHFS 亦是多目標優化問題，在眾多求解此類問題的智能優化算法中，NSGA-II 具有運行速度快，解集收斂性好的優點，常被選作評估其他多目標優化算法性能的基準，因此本文利用NSGA-II求解EHFS 模型。

2.1 編碼與解碼

應用智能算法時，反映問題解的個體編碼方案設計會影響算法效率和求解質量。針對EHFS，節能調度方案的確定取決于決策變量的取值，因此個體編碼要能夠反映它們的信息。為此，設計個體采用兩段實數編碼的形式。第一段染色體基因長度為n，其中第i個基因位的基因值對應ABi。第二段染色體采用基因分層編碼，染色體長度取決于各類工件的分批批次BNi，為。第二段染色體編碼類似于基于工序的編碼方法，各基因位分別代表一個工件批次工序，編碼形式為（i,j,m），其中第一層編碼表示第i類工件信息，第二層編碼表示第i類工件第j個批次，進而第k次出現的前兩層編碼值均相同的基因代表Oijk；第三層編碼表示Oijk選擇機床m加工，進而可確定Xijkm的值。以某3×3 調度為例，一個可行的個體編碼如圖1 所示。

圖1 個體編碼示例

決策變量Sijk和值的確定，以及優化目標Etotal和Tmakespan的計算均依賴個體解碼。對任一合法個體，按照以下步驟解碼。

步驟1：提取長度為n的第一段染色體，根據各基因位的基因值直接確定ABi。

步驟2：從左到右掃描個體第二段染色體基因，提取各類工件劃分的批次、各批次工序加工選擇的機床、以及各機床執行的工件批次工序集合Km和順序，根據約束式（10）確定Xijkm的值。

步驟3：從左到右依次提取個體第二段染色體基因，確定各基因位代表的工件批次工序的加工開始和結束時刻，以代表Oijk的基因（i,j,m）為例：

步驟4：判斷個體第二段染色體基因是否分析完成，如果未完成，返回步驟3。

步驟5：根據Xijkm、Sijk和Cijk，提取各機床的全部待機時間間隔，進而根據約束式（16）判斷各機床在其各待機時間段能否應用“關機/重啟”節能策略，確定的值。

步驟6：結合初始參數和解碼得到的決策變量值，根據式（1）和式（2）分別求出Etotal和Tmakespan。

2.2 種群個體初始化

首先，根據約束式（8）為每類工件i隨機選取分批的平均批量ABi，得出各類工件的分批批次BNi，確定個體染色體總長為。然后，初始化個體第一段染色體，將ABi賦給第i個基因位。最后，初始化個體第二段染色體，對于第i類工件，其存在BNi個批次，將u×BNi個工件類型編碼i隨機分布在各基因位工件種類層；再次，對于第i類工件，表示批次的整數（即1 至BNi）分別有u個，將表示批次的全部數字隨機分布在工件種類層已經賦值為i的各基因位工件批次層；進而，從左向右順序訪問個體第二段染色體基因位，工件種類層和工件批次層賦值均相等的基因代表了同一工件批次的不同加工工序，為每個工序從其并行機中隨機選擇一臺機床，將機床編號值賦給對應基因位的機床層。

2.3 交叉和變異

交叉是為了增加種群的多樣性，基于個體編碼方案設計的交叉算子偽代碼如圖2 所示。需要注意，父代個體進行第二段染色體交叉時可能產生非法個體，需對其基因編碼進行合法性調整，具體調整過程的偽代碼如圖3 所示。

圖2 交叉算子偽代碼

圖3 個體合法性調整偽代碼

對于變異操作，研究提出了3 種變異算子，其特性如表3 所示。各變異算子被選用的機會均等，種群個體變異操作過程偽代碼如圖4 所示。

需要注意，在執行變異算子1 時，改變ABi可能會改變第i類工件的分批批次，此時還需對個體第二段染色體基因編碼進行合法性調整，具體調整過程可參考圖4 所示偽代碼。

圖4 變異算子偽代碼

NSGA-II 二元錦標賽法選擇個體、非支配排序、擁擠度計算等關鍵過程可參考文獻[15]，此處不再贅述。

3 案例研究

3.1 模型節能效果驗證

為驗證EHFS 模型節能效果，結合上海某制造企業的萬向聯軸器生產車間進行案例研究。該車間符合混合流水車間類型，生產的萬向聯軸器主要有5 種規格，它們的機械加工工藝路線基本相同。車間現已應用能源管理系統，在每個工位上都裝有智能數字電表，能夠采集各工位上機床的用電數據。

以該車間計劃生產的5 類聯軸器（加工總量分別為100、150、120、150 和200 件）為例，結合企業工時定額管理系統和采集的生產能耗歷史數據，得出各類工件的工藝基礎信息如表4 所示。各機床的能耗特性信息如表5 所示。

表5 機床能耗特性信息

EHFS 模型求解算法用Matlab 語言在配置為Window10 操作系統、i5-1400H 2.7 GHz CPU、16GB RAM 的PC 上實現，關鍵參數設置如表6 所示。

首先，在作業分批的前提下進行4 種調度模式下的優化結果對比。模式1 僅關注Tmakespan，模式2僅關注Etotal，模式3 對應建立的EHFS 模型，同時關注Tmakespan和Etotal，模式4 相當于不采用“關機/重啟”節能策略下的模式3，即此時恒為0。模式1 和2 屬于單目標優化問題，采用遺傳算法（genetic algorithm，GA）求解，個體編碼以及交叉、變異算子與本文NSGA-II 一致，選擇操作采用輪盤賭法，且算法參數設置同表6。4 種模式下分別運行算法10 次，其中模式3、模式4 下得到的Pareto 最優解分布情況如圖5 所示。顯然，能耗和最大完工時間是兩個相互獨立的優化目標。

圖5 中兩個虛線框內的Pareto 最優解與其他兩種模式下搜索得到的最優解之間的對比如表7 所示。

圖5 EHFS 模型的Pareto 最優解分布情況

由表7 可知，4 種模式下，加工能耗均是總能耗的主體，具體地：

表7 4 種調度模式下的優化結果對比

（1）與模式2 相比，模式1 下Tmakespan降低了33.26%。主要因為模式1 下為了縮短Tmakespan，調度時工件除傾向于選擇加工時間較短的機床還兼顧了不同機床間利用率的平衡，有效縮短了各工件批次工序的加工等待時間。

（2）與模式1 相比，模式2 下Etotal降低了4.38%。因為模式2 下為了降低Etotal，各工件批次工序傾向于選擇加工能耗較低的機床，使得同類工件選擇的加工機床相對集中，機床換刀能耗和待機能耗也隨之降低。

（3）與模式1 相比，模式3 下Tmakespan升高了0.78%，但Etotal降低了4.29%；與模式2 相比，模式3 下Etotal升高了0.09%，但Tmakespan降低了32.74%，說明模式3 綜合權衡了兩個優化目標，工件批次工序在選擇機床時兼顧了加工時間和加工能耗的平衡。

（4）對比模式4 與模式1、2 得到的最優解，可以發現模式4 也綜合權衡了兩個優化目標。然而，根據圖5，模式3 比模式4 下求解EHFS 模型得到的Pareto 前沿靠外，說明在生產調度過程中集成“關機/重啟”節能策略有助于提升制造過程節能潛力。

圖5 中虛線框內模式3 下的Pareto 最優解對應的調度方案明細如圖6 所示，其中各工件批次工序表示為“工件類型-工件批次-工件批量”形式。

圖6 模式3 下求解EHFS 模型得到的一個最優調度方案

進而，針對本案例，同時考慮兩個優化目標，進行作業分批和不分批（此時滿足ABi=DMi）兩種情形下的EHFS 模型求解結果對比。分別運行算法10 次，得到兩種情形下的Pareto 最優解分布情況如圖7 所示。就節能效果而言，兩種情形下得到的最小Etotal極為相近（相差在0.24%以內），但作業不分批情形下得到的Etotal更小。分析相關Pareto 最優解對應的調度方案，發現這是因為作業不分批時，工件工序傾向于選擇加工能耗較低的機床加工，此時機床換刀次數主要受刀具磨鈍標準制約；而作業分批后，機床因前后加工工序不屬于同類工件引起的換刀次數顯著增加，導致換刀能耗增大，最終影響了Etotal的優化結果。然而，車間實際生產往往考慮多個目標，由圖7 可知，在Etotal相近的情況下，作業分批能夠顯著縮短Tmakespan，說明分批調度比不分批調度更能均衡不同目標的優化空間。

圖7 作業分批和不分批兩種情形下的案例優化結果對比

3.2 算法有效性驗證

算法有效性驗證主要從兩方面進行：

（1）利用現有HFSP 研究案例，驗證本文NSGA-II 個體編碼方案和遺傳算子的有效性。

（2）針對3.1 節案例，利用另一代表性多目標優化算法-基于分解的多目標進化算法（multiobjective evolutionary algorithm based on decomposition，MOEA/D）[16]求解，并與本文NSGA-II 的求解效果對比。

文獻綜述發現目前鮮有考慮作業分批，面向節能生產的HFSP 研究案例與EHFS 模型嚴格一致。然而，如果EHFS 模型參數中各類工件數目均為1，則EHFS 問題將退化為常見的面向單件生產的HFSP。此時應用本文算法求解時，只需將個體第一段染色體各基因位的基因值均置為1，即本文算法及其個體編碼方案應仍適用于求解HFSP。

為此，選擇兩個現有文獻中的HFSP 案例利用本文NSGA-II 求解驗證。案例1[17]以生產時間和費用為優化目標，采用本文NSGA-II 求解時，參數設置與文獻中一致，求解得到兩個Pareto 最優解，對應 優 化 目 標 值（12 min，2 600 元）和（16 min，2 575 元）。顯然，前者支配文獻中利用結合小生境技術的GA 得到的最優解（對應優化目標值分別為13 min 和2 760 元），其對應的調度方案甘特圖如圖8 所示。

圖8 求解案例1 得到的最優解對應的調度方案

案例2[18]以總加工能耗和最大完工時間為優化目標。當采用本文算法參數設置，利用NSGA-II 求解該案例得到的Pareto 最優解分布情況如圖9 所示。對比發現，文獻中利用結合局部搜索的多種群GA得到的最優解恰好位于利用NSGA-II 搜索出的Pareto 前沿。從能耗優化的角度來看，利用NSGAII 搜索得到了能耗更低的最優解，其對應的調度方案甘特圖如圖10 所示。根據兩個現有案例的求解結果，本文提出的算法個體編碼方案和遺傳算子是有效的。

圖10 求解案例2 得到的能耗最低最優解對應的調度方案

進而，采用MOEA/D 求解3.1 節案例。在同一PC 上使用Matlab 語言實現利用切比雪夫分解策略的MOEA/D，采用本文提出的個體編碼方案和交叉算子，參數設置為：種群規模100、循環代數500、權重向量個數100、鄰域個數15。運行MOEA/D 10次，其與使用NSGA-II 得到的Pareto 最優解對比如圖11 所示。

圖11 NSGA-II 和MOEA/D 求解結果對比

由圖11 可知，應用MOEA/D 得到的Pareto 前沿的解的分布性較好，但是應用NSGA-II 比應用MOEA/D 得到的Pareto 前沿比更靠外，搜索的優化解更好。此外，NSGA-II 的平均運行用時（623 s）小于MOEA/D 的（1 741 s）。因此，本文采用的NSGAII 在求解EHSP 模型方面是有效的。

4 結語

針對混合流水車間的節能生產需求，考慮工件運輸、機床換刀約束，綜合基于刀具磨鈍標準的工件分批方法和“關機/重啟”節能策略，建立了以能耗和最大完工時間為優化目標的EHFS 模型，并采用NSGA-II 對其求解，實現了最優工件分批方案和節能生產調度方案的同時生成。案例研究驗證了所提模型的節能效果和求解方法有效性，后續將進行考慮動態不確定事件（機床故障、緊急插件和訂單隨機到達等）的混合流水車間節能調度研究。