基于能耗預測的空調測試任務調度問題研究*

張 恪，賴信君，黎展滔※，林深和，陳慶新，毛 寧，李 鑫

（1.廣東工業大學機電工程學院，廣州 510006；2.珠海城建智慧能源有限公司，廣東珠海 519070）

0 引言

全球能源消耗與碳排放總量逐年增長，嚴重威脅著人類社會的可持續發展。中國是一個空調生產大國，焓差實驗是空調性能測試和能效標定的主要手段，其通過冷熱平衡來達到實驗室內空氣高精度的溫度和濕度，因此試驗過程需要消耗大量的電力。以江蘇省某亞太地區空調測試企業龍頭為例，其每年的測試任務耗電量為1.9億kW·h，按當地電價，耗電費用高達1.95億元，具有極大的能耗優化空間。

通過調研發現，大部分進行焓差實驗的空調測試企業沒有充分利用分時電價政策實現電費成本優化。焓差實驗的準備（“打工況”）時間及能耗難以確定，是其中主要的原因；此外，測試任務順序的改變，也會對測試任務“打工況”的時間及能耗產生較大影響。這也是大量高能耗企業在生產調度過程中，因準備時間及能耗不確定且具有任務順序相關性，而難以充分利用分時電價實現成本優化的原因。

國內外文獻有較多關于分時電價下的任務調度研究，耿凱峰等[1]針對多目標綠色可重入混合流水車間調度問題的特點，在機器分配和工序排序的基礎上引入分時電價機制，構建了以最小化最大完工時間、總能耗成本和碳排放為目標的綠色調度優化模型，提出了一種改進的多目標文化基因算法來求解該問題；Ding JY[2]、Che A[3]研究了在使用分時段電價計劃和無關并行機器調度問題背景下，均改進了基于連續時間間隔的混合整數線性規劃公式并分別提出了一種列生成啟發式算法和一種兩階段的啟發式方法。目前，分時電價調度問題中機器設置時間一般會默認設置為服從某種特定分布進行求解，而本文中測試任務“打工況”時間與耗電率的變化很難用特定的分布函數去描述，需要收集多種傳感器數據及數據預測手段進行解決。其中，選擇一種合適的預測算法是其中的關鍵。丁飛鴻等[4]和閆軍威等[5]研究顯示，集成學習方法如隨機森林、xgboost等算法通過集成多個弱學習器，能以較低的計算開銷顯著提高模型的預測能力，適合應用于本研究。

任務調度問題是經典的NP-Hard問題，目前求解方法主要有精確算法和啟發式算法等。其中精確算法經常使用混合整數規劃（Mixed Integer Programming，MIP）模型、分枝定界[6]等方法對問題求最優解，但求解過程耗時較長，且隨著問題規模擴大求解時間和難度也進一步增強，而遺傳算法（Genetic Algorithm，GA）作為一種群智能優化的啟發式算法[7]，在高原等[8]最近研究中顯示，其在收斂性、魯棒性、通用性和擴展性等方面都具有優異的表現，被廣泛應用于在組合優化問題求解過程之中。其中，李書全等[9]研究顯示傳統的交叉算子如PMX、OX等算子重組是隨機的，不能夠大概率地生成優于父代的子代個體，搜索速度較慢，故本文采用Inver-over算子通過倒置操作可以有效的引導交叉子代大概率向最優解的方向進化，適合應用于本研究。

如何有效地運用數據預測方法解決數學規劃中參數（其變化曲線不能用常規分布描述）不確定性問題，是近年來的熱點。較多的研究及應用大多把預測及優化設置為兩個單獨模塊，如王犇[10]和井華等[11]首先對需求及環境變量進行預測，再進行任務調度；劉民等[12-13]在求解大規模復雜色織生產調度問題時，首先對整經軸數進行預測，繼而作為優化模型的輸入。其求解思路均為先完成預測，再進行優化，兩個階段之間較少關聯。而在本問題中，若采用GA算法對調度問題進行求解，假設每一條染色體代表一種任務順序，則不同的序列將對任務的打工況時間及能耗產生影響，這導致GA在迭代過程中需要對任務打工況時間進行多次預測。該情況在已有文獻中較少討論，如何實現機器學習算法與GA算法的有機結合，是本研究的難點。

基于以上綜述：第一，本文通過引入機器學習算法，實現分時電價政策下更精細化的任務調度問題分析。第二，提出一種RF-GA混合算法求解思路，適用于分析因任務順序改變而產生的準備時間及能耗未知的問題。區別于以往數據挖掘及數學規劃結合中往往兩個模塊相互獨立的情況，本研究進一步探索兩種方法的深度及有機結合，以獲得更貼近實際、更可行的方案。第三，根據本文特點，挑選一種合適的編碼方式及交叉算子應用到GA算法中。最后，通過實驗及實際應用檢驗所提出RF-GA混合算法求解思路的實用性及優越性。

1 分時電價調度模型

如圖1所示，該問題可以描述為：有N個空調的測試任務在J個相互獨立的實驗臺進行測試，其中每個任務集的特征包括1個安裝任務、S個測試任務以及每個任務相對應的時長及耗電率；每個測試任務又分為實驗臺“打工況”和空調測試兩部分；其中空調測試時間有相關工藝要求，“打工況”時間主要依賴于上一次測試任務的環境溫度/濕度與當前測試任務環境溫度/濕度差值。

圖1 問題描述

本文中電價遵循分時段定價方案，即該企業所在城市的電價會在一天內進行變化。在分時段電價方案中，時間范圍分為K個時段，其中每個時段的電價為Ck。

本文的目標為將I個任務分配到J個相互獨立的實驗臺的可用時段進行測試，在保證任務不拖期的情況下，最大程度的降低實驗臺電費。

在對實驗臺和測試任務進行分配時需嚴格遵循該企業實際情況：（1）實驗臺數量、任務集數量及測試任務數量已知且確定；（2）每個實驗臺同一時刻一次只能進行一項測試任務；（3）每個實驗臺具備測試所有任務的能力；（4）每項測試任務的測試要求已知且確定；（5）測試任務一旦開始，不能半途停止；（6）測試開始時就可以使用所有實驗臺及進行所有測試任務。基于以上條件，構建關于測試任務的分時電價模型，其相關符號、變量如表1所示。

表1 模型參數符號及其說明

具體數學模型如下：

其中，式（1）為目標函數表示在任務不拖期的情況下使得實驗臺耗電費用最低；式（2）為任務分配到實驗臺j上的各個時段時長之和等于分配到實驗臺j上的任務時長；式（3）為任務分配到實驗臺j上時段k的時長小于等于分配到實驗臺j上的任務時長；式（4）確保任務分配到實驗臺j上時段k的所有任務時長之和一定小于該時段的時長；式（5）～（6）保證任務連續完成不會中斷；式（7）確保任務跨越電價的最大時段數與該任務分配到實驗臺j的不同電價時段k的和相等；式（8）保證每個任務只能分給一個實驗臺；式（9）保證組裝任務與測試任務均在相同實驗臺上進行；式（10）為組裝任務結束后才可以進行測試任務；式（11）～（12）為實驗臺進行一次完整實驗與分別進行打工況、測試任務參數之間的等式約束；式（13）～（15）為決策變量的取值約束。

2 RF-GA混合算法求解思路

本文中實驗臺及測試任務調度問題具有較高的復雜性，需要考慮分時段電價特點和各項測試任務“打工況”時間和耗電率未知且隨測試順序變化的情況。根據此情況，如果采用先預測再進行優化的傳統方法，則需要預測出全部測試順序下任務“打工況”時間和耗電率，不僅增大任務計算量還使得問題變的更加復雜。因此，如圖2所示，針對該問題，本文提出一種RF-GA混合算法求解思路，該求解思路主要分為兩個模塊，即數據預測模塊和算法求解模塊。兩模塊之間不是簡單的獨立關系，而是數學優化方法與數據挖掘技術深度結合：調度模型中任務“打工況”時間與耗電率為未知量，需要利用機器學習算法對其進行預測；而模型的輸出結果為測試任務順序，其決定了當前測試任務開始前的測試環境所處狀態，即預測模型的輸入變量，于是在算法每一次迭代過程中，RF算法與GA算法采用并行處理方式對任務測試順序進行求解，提高了模型的求解效率。

圖2 RF-GA混合算法求解思路

2.1 隨機森林預測模型構建

隨機森林RF（Random Forest）算法是一種基于決策樹的集成學習算法，通過對分類回歸樹CART（Classification and Regression Tree）的集成來提高預測精度，是一種著名的集成學習算法[14-15]。本文采用隨機森林回歸RFR（Random Forest Regressor）方法對測試任務打工況時間和耗電率進行預測，RFR是RF理論的重要應用，即取所有決策樹的預測均值作為預測結果。在實際應用中，需要結合企業實際傳感數據對模型進行訓練。

隨機森林回歸模型構建過程如下所示：（1）利用Bootstrap抽樣從測試任務“打工況”時間/耗電率歷史數據集中抽取z個訓練樣本集；（2）構建決策樹時，隨機抽取一定數量的候選屬性，從中選擇最合適屬性作為分裂節點；（3）設定樹的棵數ntree值，作為決策樹生長的終止條件；（4）生成的z≤ntree棵決策樹組成隨機森林回歸模型，將每一棵決策樹輸出的均值作為最終預測結果。

2.2 遺傳算法編碼設計

有效的編碼可以在不產生非法解的情況下能表達出個體與可行解的關系。本文問題包含2個子問題：實驗臺分配和任務集任務排序。因此，本文采用兩段式編碼方式，將2個子問題編碼到一條染色體上，用來表示本問題的一個可行解[16]。假設有4臺被測空調（A～D）在2個實驗臺進行測試，4個空調的測試任務數量分別為8、8、6、7，染色體編碼方式如圖3所示。實驗臺分配的編碼方式為插入式編碼，4個任務集隨機排序后在中間任意位置插入一個字符E即可將4個任務集分配到2個實驗臺上。每一個任務集代表一臺被測空調，根據實際情況，每臺被測空調分配到相應實驗臺后不可進行更換，只能在當前實驗臺完成全部測試任務，所以任務集之間采取分段編碼，測試任務編碼采用整數編碼，每一個測試任務代表一個數字。如任務集1中包含8個測試任務，將該基因片段編碼為1～8的數字組合。

圖3 染色體的編碼方式

2.3 交叉操作

本文采用一種Inver-over算子，該算子運用倒置操作不僅可以使生成的新基因片段中各基因之間相對順序保持不變——即染色體上的重要基因更加緊湊，更不容易被分裂；還可以使那些在父代中離得很遠的基因位在后代中緊靠在一起，提高了算法的種群多樣性和全局搜索能力。

該算子較好地利用了種群中獲得的信息來指引個體進行交叉操作使交叉子代大概率向最優解的方向進化，其具體步驟如下：（1）設定一個交叉概率λ，在父代染色體A中隨機選擇一個起始點，比如起始點值為2；（2）產生一個0～1的隨機小數，若小于λ，則在剛才選中父代染色體A中隨機選擇另一個終止位置點，比如終止位置點的值為7，然后將起始點與終止點位置之間的部分倒置（不包括起始與終止位置）；（3）產生一個0～1的隨機小數，若大于λ，則從種群中任意在選擇一條父代染色體B，找到父代A中起始點值所在的位置，即父代染色體B中值為2的位置在首位，然后選擇其下一個位置的值等于7，返回到父代A找到值為7所在的位置，即父代A倒數第二位作為終止點，將父代A起始點與終止點之間的部分倒置（不包括起始與終止位置）；具體過程如圖4所示。

圖4 Inver-over算子操作

2.4 變異操作

本文采用兩點互換變異操作，在相應部分任意選擇兩個互換點，然后互換對應位置的編碼，此變異操作方法可以保證編碼的合法性。具體過程如圖5所示。

圖5 變異操作

3 實驗及分析

3.1 預測結果對比

由江蘇某大型空調測試實驗中心提供的5 600多條具有代表性的實際空調測試數據對模型進行訓練。該企業對實驗臺內部布置了多種傳感設備，共能收集約26種數據。對數據進行清洗、探索性、相關性及顯著性分析后，結合預測任務及企業實際業務可行性分析后，最終得到一個9維的輸入自變量，分別為“打工況”前內干球溫度r1、“打工況”前內濕球溫度r2、“打工況”前外干球溫度r3、“打工況”前外濕球溫度r4、測試內干球溫度r5、測試內濕球溫度r6、測試外干球溫度r7、測試外濕球溫度r8、實驗臺制冷量r9。

為了對照分析證明隨機森林預測模型性能的優良性，本文采用了多元線性回歸（Multiple Linear Regression，MLR）、MLP深層感知機、支持向量機回歸（Support Vector Regression，SVR）和貝葉斯嶺回歸（Bayes Ridge Regression，BRR）模型對相同樣本數據進行了分析和研究，將均方誤差（Mean Square Error，MSE）和平均絕對誤差（Mean Absolute Error，MAE）作為評估標準。

比較結果如表2所示，RFR算法在預測打工況時間和實驗臺耗電率兩項的MSE、MAE值最小要遠優于其他機器學習算法，且耗時較短，能夠很好的滿足模型在迭代求解過程中對于預測模型的在運算時間和預測精度兩方面的要求，適合與GA算法進行深度結合。

表2 不同數據預測算法預測結果對比

3.2 測試算例與實驗環境設定

為了測試本文所提出Inver-over算子性能的優良性，以該實驗中心日常測試數據為基礎，分析提取其所具備的特征，引入DURASEVIC[17]實驗設計的思想，隨機生成72組具有該實驗中心實際測試案例特征的測試算例，算例命名格式為α-β-γ-ε-δ。其中參數α為實驗臺數量，參數β為任務集數量，參數γ為測試集任務數量，二者共同決定測試規模大小，參數ε和δ分別代表測試集任務中最大溫度/濕度差，可以用來體現溫度變化范圍大小，算例實驗詳細參數如表3所示。

表3 測試算例參數表

在英特爾酷睿i7處理器及Windows10系統下，算法采用Matlab R2016b編程實現。

3.3 各種算法性能比較

為了驗證本文所提出Inver-over算子性能的優良性，實驗中將以SA算法、6種采用常規交叉算子操作的GA算法作為比較對象。其中GA算法種群選擇操作采用輪盤賭[18]方法，其他參數設置如下：種群大小為100，代溝為0.8，遺傳算法交叉率λ＝0.8，變異率θ＝0.05；其他算法中SA初始溫度100，冷卻系數0.99。所有算法皆隨機初始化初始種群，為了保證公平起見且滿足企業實際需求，這里以迭代次數作為算法的終止條件。當β=3且γ＝2時，將任務規模定義為大規模測試算例，迭代終止次數為500次，其余實驗迭代次數為300次。8種算法將在每個算例組合下分別進行5次獨立實驗，將實驗臺總耗電費用求均值，作為算法評估的觀察指標。表4所示為8種算法在各個算例組合下的測試結果，測試結果中每種算法的性能分布與該實驗中心實際測試案例進行計算得到的性能分布類似，說明運用該方法生成的隨機測試數據具有一定的可用性。由表4可得如下結論。

表4 不同算法實驗統計結果

（1）應用遺傳算法求解該企業問題的結果要優于使用模擬退火算法；而對于同樣應用遺傳算法求解時，使用不同遺傳算法在不同性質的測試環境下求解性能也不盡相同。總體來看，本文所應用的Inver-over算子在大部分測試環境下具有良好的求解性能；循環交叉算子（Cycle Crossover，CX）和部分匹配交叉算子（Partially-matched crossover，PMX）在少部分測試環境下具有良好的求解性能；而應用其他交叉算子的遺傳算法只在極少數特定環境下的結果較優，總體而言優化效果較差。

（2）由圖6可知，在測試任務集數量小的時候，Inver-over算子、PMX、OX算子等能夠在基因片段長度較短的情況下對基因進行較大程度重組的算法相對于其它算法的算例最優次數較多；而隨著測試任務集數量增加，Inver-over算子在性能上出現一定劣化但是劣化趨勢較為緩和；而CX算子隨著基因片段長度增加，染色體片段大幅度改變的機會增加，于是在性能上實現了較大飛躍。

圖6 測試任務集數量變化

（3）由圖7～8可知，無論在實驗臺和被測空調數量規模處于什么情況，Inver-over算子均能取得相對于其它算法更少的耗電費用，隨著實驗臺數量和被測空調規模的增加，Inver-over算子求解效果有所降低但是相比其他遺傳算法仍然具有一定優勢，而PMX、CX等能夠實現區域重組交叉的算子相比于OBX和SEC等選擇多基因位的交叉算子能夠進行更廣范圍的搜索，能夠更好地對實驗臺和測空調進行合理的分配。

圖7 實驗臺數量變化

圖8 被測空調數量變化

（4）由圖9可知，隨著空調內外機溫度濕度變化增大，Inver-over算子在算例求解最優的次數上與其他算法拉開很大距離；這是由于隨著溫度、濕度范圍變化增大，測試順序發生變化后相鄰兩項各個測試項之間環境變化程度也會發生較大的改變，而Inver-over算子采用的倒置操作可以保證相鄰測試項之間的環境參數不發生改變，使得種群大概率向最優解的方向進化。

圖9 空調環境參數變化

在該企業實際測試案例中，新空調測試大多需要實現測試環境在溫度、濕度方面較大范圍的變化，而Inver-over算子在這方面表現突出，且在其他方面相對于其他算子也具有一定的優勢，于是綜合上述內容選擇該算子用于本文的模型求解。

3.4 算法應用及方案對比

圖10所示為針對該實驗中心測試任務實行安排的3種應用方案，本文隨機選取10個實際案例分別計算其相對應實驗臺電費圖。其中方案1是該企業日常空調測試安排方案，由于員工上班時長限制，該企業對任務安排的時間段沒有考慮分時段電價特點，而且測試任務的順序都是按照測試人員的經驗判斷，測試順序無法達到最優，每個測試任務的“打工況”時間普遍較長，導致整個實驗臺耗費較高；電費成本曲線在中間位置的為方案2，一般是該企業任務加急時的方案安排，即實驗臺不間斷進行任務測試，但測試順序仍然是由測試人員經驗判斷，測試任務“打工況”時長依然沒有得到優化；如圖10所示，方案3電費成本曲線最優，該方案是本文針對以上2種方案進行改進后提出的RF-GA混合算法求解思路，其不僅充分利用分時段電價的特點，還由于應用該求解思路后任務“打工況”時長明顯縮短，使得實驗臺電費得到了進一步優化。

圖10 3種任務安排方案相應電費

4 結束語

本文針對空調測試實驗中心在空調測試任務安排時多憑工人經驗、測試任務打工況時長及耗電率未知等情形，造成該企業能源消耗過多和電費支出過高的現象，以最小化實驗臺總電費為目標，提出了一種數據預測與智能算法深度融合的RF-GA混合算法求解思路。該求解思路不僅可以為每一臺被測空調安排合理的測試順序，使其能夠充分利用分時段電價的特點；而且在空調測試順序得到優化后，相應的測試任務參數也可以得到進一步優化（比如任務打工況時間縮短），從而使得實驗臺總電費在兩個方面都得到了大幅度的降低。除此之外，為了滿足該企業的實際測試需要，本文的預測模型和智能算法分別采用隨機森林算法與Inver-over算子的遺傳算法，通過該企業實際測試數據和各種具有該企業實際數據特征的測試算例中與其他算法進行比較，說明兩種算法的有效性與優越性；最后通過對該企業日常任務安排方案與應用本文所提出RF-GA混合算法求解思路的方案對比，說明了本文求解方案的優越性。未來的研究包括將進一步深化GA算子與集成學習方法的結合，并進一步考慮符合人員排班后對總成本的最優化求解。