考慮機器非加工狀態的作業車間節能調度

吳正佳 華 露 白煒鋮 涂晶鑫 劉秀鳳 徐 崢

(三峽大學 機械與動力學院， 湖北 宜昌 443002)

考慮機器非加工狀態的作業車間節能調度

吳正佳 華 露 白煒鋮 涂晶鑫 劉秀鳳 徐 崢

(三峽大學 機械與動力學院， 湖北 宜昌 443002)

為了減少機器在非加工狀態時的能耗，采用機器關閉再開啟的決策方案來實現此目的．首先建立目標為總能耗和最大完工時間最小化的車間節能調度模型，并將此決策方案抽象為約束條件，然后提出一種基于混合元胞遺傳模擬退火算法的求解方法，引入插入式貪婪解碼算法進行解碼，基于同步機制的遺傳操作更新種群，增加模擬退火操作與收斂準則實現進一步優化．最后通過案例驗證了該模型與算法的有效性與實用性，結果表明運用該模型可達到很好的節能優化效果．

節能； 多目標； 作業車間調度； 混合元胞遺傳模擬退火算法

機器在不同狀態下會產生不同的能耗，且不同的運行狀態對生產任務總能耗具有不同的影響，還會影響到機器的能量利用率．因此在研究作業車間節能調度問題時，機器非加工狀態下的能耗也是需要考慮的部分，不可忽略．

車間調度問題屬于NP-hard問題，許多學者對其求解算法進行了大量研究，其中遺傳算法是研究最為熱門的一個分支[1-2]．雖然傳統遺傳算法能夠獲得較滿意的調度方案，但在解決調度問題時存在明顯不足，即容易在收斂過程中得到局部最優解，形成早熟現象[3]．元胞遺傳算法(cellular genetic algorithm，CGA)將元胞自動機與遺傳算法有機結合，具有收斂快、多樣性好的特點，在一定程度上改善了遺傳算法局部搜索能力問題，但仍有可能陷入局部最優的情況[4]．模擬退火算法(simulated annealing algorithm，SA)是以隨機搜索技術從概率意義上找出目標函數的全局最優點，具有強大局部搜索能力[5]．根據這兩種優化算法各自的特點，取長補短進行結合，構造混合優化算法，能夠發揮兩種算法的優點，進而改進常規單一優化算法的性能．

本文在已有的研究基礎上，詳細分析機器不同狀態下的能耗特征，以總能耗和最大完工時間為優化目標，將非加工狀態下機器采取關閉再開啟的決策方案抽象為約束條件，建立作業車間下考慮機器非加工狀態下決策的多目標節能調度數學模型，然后提出混合元胞遺傳模擬退火算法對其求解，并運用Pareto優化獲得Pareto解集，最后通過實例驗證該模型．

1 節能調度模型的建立

1.1 作業車間下機器能耗的狀態變化

根據文獻，可將機器的運行狀態分為3種，即加工、關閉和空閑．其中，機器的加工狀態能直接對工件創造價值，而關閉和空閑狀態沒有貢獻任何形式的價值，故應盡量避免非加工狀態的能耗或使其最小化．

在作業車間環境下，考慮到工件后一個工序階段受到前一個工序階段的時間約束，機器在加工完一個工件后，很有可能進入待機空閑狀態，等待后一個工件的到達，此時，機器的空閑狀態仍需要一定的能量消耗來維持機器運轉，長時間待機仍然消耗大量能量．本文提出采用機器關閉再開啟的決策方法解決此問題，具體步驟如下：設機器關閉再開啟的能耗為Eon-off，機器空閑等待的能耗為Eidle，其中空閑能耗為機器待機功率pidle與機器待機時間tidle(刀具或工件的安裝時間)的乘積[6]．

(1)當Eon-off

(2)當Eon-off>Eidle=pidletidle時，機器選擇空閑等待.

其中，定義TB為決策方案的臨界時間，Yildirim[7]等研究表明：

圖1為采用該方法前后能耗示意圖，由圖1可知采取上述決策能有效減少能量消耗．

圖1 采取停機在開啟方案前后的能耗示意圖

1.2 考慮機器非加工狀態的作業車間節能調度的問題定義

JSP問題描述如下：M臺機器上有N個工件加工，已知各操作的加工時間和各工件在各機器上的加工次序約束，要求確定機器上各工件加工先后順序，使加工性能指標達到最優．本文提出以總能耗E和最大完工時間T為目標的節能調度模型，結合機器停機再開啟的決策方法，最終得到性能指標較優的調度方案[4-5]．

1.3 模型建立

1.3.1 模型目標分析

本文針對作業車間節能優化問題，為了減小機器總能耗的同時保證完成時間，提出了以總能耗E和最大完工時間T為目標的節能調度模型．

1)機器總能耗E

機器總能耗包括加工能耗和非加工能耗，表達式為

其中切削能耗Ecutting表達式[8]為

式中，f為切削比能(W.s/mm3)，與工件硬度和機器屬性相關，v表示材料去除率(cm3/s)，tcutting表示切削時間．

min{Eon-off，Eidle}表示機器非加工狀態時選擇能耗最小的方案，即

2)最大完工時間T

1.3.2 數學模型

在上述數學模型中，式(9)表示總能耗最小和最大完工時間最小兩個目標函數；式(10)表示工件各操作的先后順序；式(11)表示各機器加工各工件的先后順序；式(12)表示機器在非加工狀態的決策約束；式(13)表示各工序在各臺機器上的加工時間與加工結束時間的范圍約束；式(14)表示工件和機器的數量約束．

2 模型求解

2.1 求解方法概述

如前所述的多目標問題中兩個目標函數優化時存在沖突，且兩個目標的量綱不同，因此本文利用Pareto優化思想進行求解來獲得各目標相對折中的解(即本文所提出的Pareto最優解)．為解決本文提出的考慮機器非加工狀態的作業車間節能調度模型，提出了一種混合元胞遺傳模擬退火算法(cellular genetic algorithm-simulated annealing algorithm，CGA-SA)，即先利用CGA的搜索能力對整個解空間進行全局搜索，確定最有可能搜索出的最優解的區域，再利用SA的局部搜索能力對各個區域進行優化，從而發揮兩種算法的優點．

在算法操作細節上，本文在CGA中引入一種插入式貪婪解碼算法進行解碼，以確保染色體經解碼后能產生主動調度，然后采用同步機制進行遺傳操作，進而增加記憶功能的模擬退火操作與收斂準則，這樣既防止算法求解時陷入局部最優解，又提高了算法的優化效率以及魯棒性．

1)插入式貪婪解碼

將染色體作為工序的有序序列，根據工序在該序列上的順序進行解碼，序列上第1道工序安排加工，取序列的第2道工序插入到對應機器上最佳可行的加工時刻安排加工，以此方式直到所有序列上所有工序都安排在其最佳可行位置[9]．

2)評價函數

由于本文數學模型為多約束多目標優化問題，且總能耗最小的目標函數E與最大完工時間最小的目標函數T是相互沖突的兩個目標，因此本文采用加權求和方法將兩個目標構成一個單目標函數，由此用來評價每組優化解集并確定最優解[10]，即

其中，Emax(t)和Emin(t)為第t次迭代中的總能耗的最大值和最小值，Tmax(t)和Tmin(t)為第t次迭代中的最大完工時間的最大值和最小值．

2.2 CGA-SA算法步驟

在借鑒前人的研究成果基礎上，本文提出的CGA-SA混合算法具體步驟如下：

Step 1：初始化群體Q，規模為N，將其分布在m×n元胞空間中，N=m×n，則群體個體以矩陣表示；

Step 2：基于插入式貪婪解碼算法，評價群體個體的適應度F(Qij)；

Step 3：采用同步機制對分布于元胞空間的所有個體進行相關遺傳操作[4]：

選擇：以確定的元胞空間位置的個體為中心元胞Qcenter=Qij，從此中心元胞領域內個體集QNij中選擇一個個體QNij=max(F(QNij))，若中心元胞個體處于元胞空間邊緣情況，且其鄰居個體不在元胞空間內，則以另一邊緣個體作為鄰居個體；

交叉：以中心元胞個體Qcenter和領域內QNij中選一個個體進行交叉操作，本文選擇兩點交叉方法生成新個體Onew；

Step 4：選擇優秀個體作為SA的初始解，并對其種群中的各個個體均進行定步長抽樣的模擬退火操作，定義在溫度tk下，為新產生的種群個體S*與當前種群個體S的增量，若ΔF(Qij<0)，則接收S*并判斷F(S*)0，則以概率min(1，exp(-ΔF(Qij)/tk))接收S*為當前種群個體，且及時更新最優調度；

Step 5：判斷是否達到算法終止條件，如果沒有達到，迭代次數加1，并利用tk=αtk-1，α∈(0，1)進行降溫操作，返回步驟(2)；如果達到終止條件，則把當前最優解輸出，算法結束．

CGA-SA算法流程圖如圖2所示．

圖2 CGA-SA算法流程圖

3 實例分析

3.1 CGA-SA性能分析

為驗證CGA-SA算法的可行性和有效性，采用標準測試案例FT06、FT10、FT20、LA06、LA11、LA21和LA31為測試基準，將CGA-SA算法與CGA算法進行比較，結果見表1．其中C**為算例的基準最優解，C*為算法最優解，Dmax為仿真20次得到的最大值與該算例已知最優值的相對偏差，Dmin為仿真20次得到的最小值與該算例已知最優值的相對偏差，Dave為仿真20次的平均值與該算例已知最優值的相對偏差．算法參數設置如下：種群規模200，最大遺傳代數100，交叉概率0.5，變異概率0.9，降溫速率0.9．

如表1所示，比較CGA和CGA-SA所得的7個算例的最優解C*可知，對于FT06和LA06小規模算例，兩種算法均能獲得基準最優解，而對于其他算例，其難度較大，CGA-SA所得最優解與CGA相比更接近基準最優解，說明加入SA后，最優解質量提高很多．比較7個算例的最大偏差Dmax、最小偏差Dmin和平均偏差Dave可知，CGA-SA算法所求的偏差值均明顯低于CGA的偏差值，說明CGA-SA求解結果與CGA相比更為穩定，這是因為CGA在對整個解空間進行全局搜索來確定最優解區域時，存在局部過早收斂的情況，增加SA算法后，對各個區域進行局部搜索，能有效提高收斂精度，進而提高算法的求解能力，因此CGA-SA在全局尋優和收斂精度上都有了顯著提高，具有較強的搜索能力．

表1 CGA-SA算法與CGA算法對比

3.2 CGA-SA的應用

選取某機械加工車間的加工任務進行調度試驗．已知車間包含6個工件、6道工序和6臺設備，其具體的機床編號，工件加工時間和加工功率見表2、表3，機床待機功率、關閉再開啟的能耗和時間見表4．隨著加工任務的標準化，可確定工件加工的進給量與切削速度，則由文獻[11]可確定工件加工的切削比能f=2.840 J/mm3，材料去除率v=7.344 cm3/s．

表2 機床編號與對應的工件加工時間(單位：h)

表3 機床在不同工件工序的加工功率(單位：kW)

表4 機床待機功率、關閉再開啟的能耗和時間

為驗證本文所提出模型的優勢，設定3種情況進行測試．方案1：機器在非加工狀態選擇等待或關閉再開啟，調度目標為總能耗E和完工時間T，即本文提出的調度模型；方案2：在方案1的基礎上，調度目標為單目標E或T；方案3：在方案1的基礎上，機器在非加工狀態僅考慮等待時的能耗情況，調度目標為E和T．

3.2.1 方案1的分析

根據本文的CGA-SA算法繪出以總能耗和完工時間為優化目標的Pareto最優解集形成的Pareto前沿，如圖3所示，任務加工總能耗范圍為3 007.28～3 335.39 kW·h，完工時間為58～65 h，根據式(15)中的評價函數可得方案1最優解的能耗為3 037.07 kW·h，最大完工時間為63 h，調度方案的甘特圖如圖4所示，紅色區域表示機床在非加工狀態選擇關閉再開啟，此時對應的生產調度節能數據見表5．

圖3 方案1的Pareto前沿曲線

圖4 方案1的甘特圖

閑置機床編號等待時間/h停機啟動時間/h待機功率/kW停機啟動能耗/(kw·h)節能比/%M2150．150．903．3475．26M3290．271．112．0293．72M4180．211．951．4295．95

由表5可知，閑置機床在非加工狀態采取關閉再開啟的措施可節能75%以上，使機床總的空閑能耗降至21.72 kW·h，占總能耗的比例降至0.72%，因此執行關閉再啟動的措施能夠實現有效節能．

3.2.2 方案1與方案2的對比分析

方案1與方案2的區別是調度目標不同，根據本文算法分別求出總能耗最小(方案2a)，完工時間最小(方案2b)時的最優解，與方案1的結果對比如圖5所示．

圖5 方案1與方案2的結果對比

由圖5可知，總能耗與完工時間這兩個優化目標具有矛盾性，方案1與方案2a相比，能耗增加了197.79 kW·h，但完工時間減少了12 h，與方案2b相比，雖然完工時間增加了8 h，但總能耗減少了746.47 kW·h，故方案1的最優解介于方案2a與方案2b兩者之間，且與各方案的最優值相距較小，因此方案1能綜合優化兩個目標，使各個優化目標更加平衡，進而獲得兩目標都較優的調度方案．

3.2.3 方案1與方案3的對比分析

方案3與方案1的區別是在機床非加工狀態是否考慮關閉再開啟的情況．根據本文算法求出方案3的Pareto最優解集，將調度完工時間為63 h時的總能耗以及空閑能耗與方案1對比結果見表6．由表6可知，方案1與方案3相比，在完工時間相同的情況下，總能耗節省了9.69%，其中空閑能耗節省了80.37%，因此方案1在機床非加工狀態執行關閉再開啟的措施具有更顯著的節能效果．

表6 方案1與方案3的結果對比

通過上述3種案例的對比分析可知，本文提出的考慮機床非加工狀態并以總能耗E和完工時間T為目標的節能調度模型能夠有效平衡優化目標，在任務加工完成時間較小的情況下，總能耗也相對較小．在機床非加工狀態下采取關閉再開啟措施后，進一步減少了能耗，實現了有效節能．因此本文所提出的模型能夠獲得較好的加工生產方案，具有較好的節能優化效果，并且提出的CGA-SA算法能獲得Pareto最優解集．

4 結 論

本文基于作業車間環境，考慮到機器在非加工狀態下仍存在大量能耗，提出了機器關閉再開啟的決策方法來達到節能優化的效果．

1)建立了以總能耗和最大完工時間為目標的節能調度模型，定義決策方案的臨界時間，并將此決策方案抽象為約束條件．這樣綜合了兩個優化目標，在滿足完工時間的同時可減少能耗，另外采取機器關閉再開啟的決策方法能進一步減少能耗，實現更有效的節能．

2)提出了CGA-SA混合算法，在算法操作細節上，引入插入式貪婪解碼算法進行解碼，然后采用同步機制進行遺傳操作，進而增加記憶功能的模擬退火操作與收斂準則．這樣既防止算法求解時陷入局部最優解，又提高了算法的優化效率以及魯棒性．

3)通過性能測試驗證了CGA-SA混合算法的求解質量優于其他算法，且具有較好的優化性能與魯棒性．結果表明，本文提出的節能調度模型能夠有效平衡優化目標，具有顯著的節能效果．

因此，本文提出的考慮機器非加工狀態的多目標節能調度模型，通過采用CGA-SA混合算法能獲得較好的加工生產方案，同時實現設備的有效節能．

[1] 王萬亮，吳啟迪. 生產調度智能算法及其應用[M]．北京：科學出版社，2007．

[2] 王宇平. 進化計算理論和方法[M]．北京：科學出版社，2011．

[3] 朱鳳龍. 遺傳算法“早熟”現象的探究及改進策略[D]．成都：西南大學, 2010．

[4] 魯宇明. 元胞遺傳算法研究及應用[D]．南京：南京航空航天大學,2013．

[5] 趙 衛. 模擬退火遺傳算法在車間作業調度中的應用[J]．計算機仿真，2011，28(7)：361-364．

[6] Rajemi M F, Mativenga P T, Aramcharoen A. Sustainable machining: selection of optimumturning conditions based on minimum energy considerations[J]． Journal of Cleaner Production,2010,18(10):1059-1065．

[7] Yildirim M B, Mouzon G. Single-machine Sustainable Production Planning to Minimize Total Energy Consumption and Total Completion Time Using a Multiple Objective Genetic Algorithm[J]．IEEE Transactions on Engineering Management,2012,59(4):585-597．

[8] Gutowski T, Murphy C, Allen D, et al. Environmentally benign manufacturing: observationsfrom Japan, Europe and the United States[J]． Journal of Cleaner Production, 2005,13(1):1-17．

[9] 楊宏安，孫啟峰，李錦遠. 求解作業車間提前/拖期調度問題的一種新解碼方法[J]．計算機集成制造系統，2011，17(12)：2652-2659．

[10] He Y, Li Y, Wu T, et al. An energy-responsive optimization method for machine tool selection and operation sequence in flexible machining job shops[J]．Journal of Cleaner Production,2015,87(1):245-254．

[11] 張洪潮，孔露露，李 濤，等. 切削比能模型的建立及參數影響分析[J]．中國機械工程，2015，26(8)：1098-1104．

Jop-shopEnergySavingSchedulingunderMachineNon-workingCondition

Wu Zhengjia Hua Lu Bai Weicheng Tu Jingxin Liu Xiufeng Xu Zheng

(College of Mechanical & Power Engineering, China Three Gorges Univ., Yichang 443002, China)

To reduce energy consumption under machine non-working condition, the decision method of machine is closed and then opened to achieve this goal. First, a multiobjective jop-shop optimization model based on this decision method is put forward, in which the energy consumption and makespan are considered. Then, a cellular genetic algorithm-simulating annealing algorithm (CGA-SA) is designed, with using insert greedy decoding algorithm, updating population by genetic operation based on synchronization, increasing simulated annealing and convergence criterion to improve searching performance. Finally, the effectiveness and practicability of model and algorithm are verified by case study. The results show that the model can achieve a good energy saving effect.

energy saving; multiobjective; jop-shop scheduling; cellular genetic algorithm-simulated annealing algorithm

10.13393/j.cnki.issn.1672-948X.2017.05.020

2016-12-23

湖北省自然科學基金資助項目(2014CFB686)

吳正佳(1964-)，男，教授，博士，研究方向為先進制造企業信息系統分析與集成、智能算法理論、設備綜合管理與檢測．E-mail： zjwu@ctgu.edu.cn

TH166

A

1672-948X(2017)05-0100-06

[責任編輯張 莉]