基于開關機控制的流水車間節能調度問題研究

馬子飛，王昭，趙子杰

（中國航空工業集團公司西安航空計算技術研究所，陜西西安，710065）

0 引言

研究表明，在豐田汽車生產車間，約82%的能耗用于機器無加工任務且空轉運行的過程中，只有不到12%的能耗用于有效加工過程中。Kordonowy通過研究銑削機、機床、注塑機等機器的加工能耗，發現有30%的電能消耗在裝錠、工件給進、冷卻泵和風扇運轉等后臺輔助加工過程。G. Mouzon等通過研究一臺CNC機床8個小時的加工過程，發現機床有30%的時間處于空閑等待狀態。這就表明：在生產過程中，當機器無加工任務時將其關閉，有加工任務時將其啟動，能大大降低能耗。

本文將流水車間作為研究對象，提出基于開關機控制的節能調度問題，使用混合整數規劃法建立節能調度模型并設計模型求解算法。基于開關機控制的節能調度問題，就是在傳統生產調度問題中加入開關機控制，即當機器無加工任務時將其關閉，有加工任務時啟動加工。加入開關機控制需考慮兩個問題：一是機器是否需要進行開關機操作；二是若進行開關機操作，就要確定關機時長，合理的關機時間不僅不會影響產出和效益，而且能最大程度的降低生產能耗。節能調度問題的研究內容以優化生產總能耗為目標，在滿足生產約束和關機約束的條件下，尋找最優的調度方案，使得生產能耗最低。其中調度方案包括五部分：工件的加工順序、工件各工序的加工時間、工件各工序的加工設備的分配、開關機時間和關機時長，如圖1所示。

圖1 節能調度問題

1 流水車間節能調度建模

1.1 模型描述

流水車間調度問題（Flow Shop Scheduling Problem，FSP）是許多實際流水線生產調度問題的簡化模型，也是一個典型的NP-hard問題。本研究的流水車間節能調度問題可描述為：N個工件在M臺機器上加工，每個工件有M道工序，工件的加工順序完全一致，即均為 M1→ M2→ M3…Mm，機器每加工完一個工件后可選擇關機也可繼續空轉等待。優化目標就是求取工件的最優加工順序和工件各工序的加工時間，以及機器最佳的開關機時間和停機時長，使得生產總能耗最優化

1.2 混合整數規劃模型

1.2.1 模型參數

TPi,m——工件i在m機器加工用時，i∈[1 ,N],m∈[1,M]

Ri——工件i準備時間或到達時間，i∈[1,N]

Di——工件i交貨期，i ∈ [1,N]

PWm——機器m加工功耗，m ∈ [1,M]

PIm——機器m空閑功耗，m ∈ [1,M]

PSm——機器m待機功耗，m ∈ [1,M]

PXm——機器m關機操作后統一功耗，若采用完全開關機控制模式則為0，若為部分開關機控制模式則為 P Smm∈[1,M]

PEi——工件i超期懲罰功耗，i ∈[1,N]

1.2.2 決策變量

Ck,m——機器m上第k個工件的完成時間，k ∈[1 ,N], m∈ [1,m]

xi,k——工件i在某加工順序π中的位置

TBk,m——機器m上第k個工件加工完成后停機時長，k∈[1,N], m∈[1,M]

1.2.3 約束條件

（1）唯一性約束，式（1）表示，任意工件i在加工順序π中只能出現一次；式（2）表示，加工順序π中第k個位置只能有一個工件

（2）順序約束，任意工件i不能同時由多臺機器加工，即只能在上道工序加工完成后才能開始下一道工序的加工。

（3）占用約束，任意機器m在同一時刻只能加工某個工件的某道工序

（4）初始加工約束，任意工件i的首道工序必須在工件到達或準備好后方可開始加工。

（5）決策變量范圍約束

1.2.4 目標函數

節能調度問題的優化目標為生產總能耗ET，由于靜態確定性調度問題中不存在工件等待，所以生產能耗主要由加工能耗，機器空閑能耗，開關機能耗，超期能耗四部分組成。

（1）加工能耗EP

（2）機器空閑能耗EI

（3）機器開關機能耗ETO

（4）超期懲罰能耗ED

則目標函數：

1.3 模型求解

本文采用分支定界法作為節能調度問題的求解算法，分支定界法（Branch and Bound，B&B）本質上是一種改進的枚舉法，是解決整數線性規劃問題的一種有效工具。其基本原理是通過松弛原問題中離散的整數變量，將問題轉化為連續變量的優化問題。分支定界法求解基于混合整數規的節能調度問題的步驟為:（1）松弛 ；（2）松弛問題求解 ；（3）分支 ；（4）定界 ；（5）剪支 ；（6）收斂判據，待分支隊列為空，即所有的子問題求解完畢，則可退出分支定界過程。

2 實例分析

選取10組工件5臺機器，構成（10×5）的調度案例，假設機器開關模型為理想開關，且選擇完全開關機控制模式，即機器可以完全關閉且關機和開機過程中無能損無遲滯。節能調度模型參數如表1和表2所示。

表1 工件在各個機器上的加工時間（單位：秒）

Job9 11 63 24 16 89 Job10 87 52 43 10 26

表2 機器各運行狀態下的功率

求解過程借助優化建模軟件LINGO，LINGO是專門用于求解最優化問題的一款軟件，可以用于求解線性規劃、非線性規劃、整數規劃、混合整數規劃等多種優化問題。為了驗證基于開關機控制的流水車間節能調度模型的有效性，本文選取傳統的最優Makespan調度模型作為比較對象，最優Makespan調度問題以所有工件的最大完成時間作為優化目標，將二者在LINGO中求所求數值解繪制成調度甘特圖，如圖2和圖3所示，可以直觀的顯示加工過程。

圖2 節能調度甘特圖

圖3 最優Makespan調度甘特圖

由調度甘特圖中可以看出，二者工件加工順序和加工時間均不同。在節能調度方案中，關機操作比較多，加工密度相對較小，無空閑時間；而最優Makespan調度方案中，加工密度較大，中間留有空閑時間。二者在最大完成時間（Cmax）、空閑能耗（EI）、總能耗以及節能效率（η）等方面的對比如表3中所示。

表3 流水車間節能調度方案與最優Makespan調度方案對比

由表中對比數據可知，節能調度方案比傳統的最優Makespan調度方案在生產能耗方面優勢明顯。在最大完成時間方面，節能調度模型求解過程中設置整批工件交貨期為1300s，而實際完成時間為1292s，未超出交貨期。由此可知，節能調度方案的原理是在不超出交貨期的前提下，通過最大限度的增加機器停機時間，而降低空閑時間，從而達到節能降耗的目的。

3 結束語

本文以流水車間生產為研究對象，圍繞基于開關機控制節能調度問題展開，主要研究了節能調度問題建模以及模型求解算法兩個問題。本文創新之處在于：一，建立了基于混合整數規劃法的節能調度模型，以生產總能耗為優化目標，以工件工序、機器占用、開關機操作等作為約束條件，以工件分配、加工時間、機器是否停機和停機時長等作為決策變量，建立節能調度問題模型。二，給出了節能調度問題的求解算法，對于規模較小的節能調度問題，本文采用采用分支定界法求解，得到全局最優精確解。通過實例分析與對比驗證，證明了基于開關機控制的節能調度模型的合理性和有效性，同時也證明了通過開關機控制，能達到節能降耗的目的。

參考文獻

[1]Mouzon G, Yildirim MB. A framework to minimise total energy consumption and total tardiness on a single machine[J]. International Journal of Sustainable Engineering, 2008, 1 (2): 105-116.

[2]王凌.車間調度及其遺傳算法[J].工業工程與管理,2004,(1)：78-78．

[3]劉霞,高岳林.整數二次規劃問題的一種新型分支定界算法[J].中北大學學報:自然科學版,2015,(4):412-417．

[4]王偉．面向能耗優化的車間調度方法研究及其應用環境開發[D]：哈爾濱工業大學，2011．