考慮能耗與工時惡化作用下的并行機調度優化①

薛 聰,郭 鵬,陳 宓,王麗敏

1(西南交通大學 機械工程學院,成都 610031)

2(軌道交通運維技術與裝備四川省重點實驗室,成都 610031)

尿素造粒塔是尿素生產中的重要設備,也是尿素生產流程中最后一個生產環節[1].其造粒原理是將成批次放置的滿足加工溫度要求的熔融尿素使用泵通過管道打到塔頂后噴出,從而形成高溫射流.高溫射流在下墜過程中通過空氣冷卻等過程快速斷裂成滴,自動凝成固體小顆粒,從而形成顆粒狀的尿素產品.而不同批次的熔融尿素在等待被注入泵內的過程中,其溫度會隨著等待時間的增加而降低.當其開始加工時因為在等待過程中的溫度變化其溫度可能不符合加工溫度要求.也就是說熱加工環境中工件的溫度會隨著其開工時刻的增大而降低,當溫度降到一定數值以后,將不再滿足加工要求,即工時惡化問題.此時需要對不滿足加工溫度要求批次的熔融尿素進行二次加熱,或者監控其溫度,當發現其溫度不滿足加工溫度要求時立即使用保溫設施對其進行保溫操作.二次加熱會增加此批次熔融尿素的加工時間和消耗額外的能量,從而增大產品拖期和能耗,造成產品延期交貨和增大生產成本;而使用保溫設施保溫雖然不會增加其加工時間但是會耗費更多的能耗成本.當造粒塔從一臺擴展到多臺,此時問題便擴展為考慮不同工作模式與工時惡化的并行機調度問題.及時交貨和能耗控制是生產成本控制的重要組成部分,因此,如何有效保證產品及時交貨以及精準的控制能耗是管理人員需要解決的關鍵決策問題[2].在此,本文以多臺尿素造粒塔的尿素生產過程為背景,從并行機加工環境出發,對上述調度問題進行建模并設計優化算法進行求解.

并行機調度問題長期以來吸引了大量學者的關注和研究[3],且節能調度方面的研究已有不少.孟磊磊等以能耗最小化為目標,提出了5 個考慮關機/重啟策略的不相關并行機調度模型[4].周炳海與顧佳穎提出了多目標免疫克隆選擇算法處理多資源約束下的非等效并行機節能調度問題[5].雷德明等提出了新型帝國競爭算法去處理多目標低碳并行機調度[6].與本文研究最為相關的則是在并行機調度問題中同時考慮節能與拖期最小化.Li 等基于分派規則提出了10 個啟發式算法去優化能耗與總拖期[7].王永琦等結合問題的性質,設計了適用于該問題的混合教學算法[8].然而上述研究均未考慮工件開工時間延誤造成額外能耗或二次加熱帶來的工時惡化.本文針對尿素廠造粒塔生產過程,采用階梯惡化函數對其生產過程進行描述[9],并盡量減少生產過程中發生的能耗.

關于工時惡化的并行機調度問題亦開始受到關注,Ji 和Cheng 考慮了工時線性惡化情況下的并行機調度問題,并給出了機器數確定的情況下多項式近似算法[10].Wang 等在此基礎上進行了擴展,考慮機器在開始部分不可用的情況,并設計了啟發式規則[11].Guo 等為工時階梯惡化的并行機設計了布谷鳥搜索算法,在考慮工件間調整時間的基礎上上最小化了總拖期[12],此外Guo等還比較了不同的建模方式對問題求解效率的影響[13].變鄰域搜索[14]與集劃分建模策略[15]也相繼被用于工時階梯惡化的并行機調度問題.在考慮處理成本和收益的階梯惡化并行機調度問題中,Pei 等提出了變鄰域搜索的混合算法去最大化凈收益[16].遺傳算法也被改進用于求解不相關并行機帶惡化工件的調度問題[17].關于工時惡化的并行機調度問題在潛在機器擾動、學習效益與維護活動等方面均有擴展[18-20],但文獻[18-21]尚未涉及節能調度方面的拓展.

基于以上分析發現,目前尚未出現同時考慮工時階梯惡化與能耗的并行機調度優化研究.現有并行機調度算法在處理實際約束時存在大規模算例計算時間過長、算法收斂速度慢、求解質量不高等問題,且難以將工作模式選擇考慮進去.本文針對有溫度要求的工件,在等待加工的過程中有保溫或者再加熱兩種方式,均需消耗一定能量.再加熱還會導致其加工時間發生惡化.以尿素廠造粒塔為研究背景,提出以加權總拖期與總能耗之和最小化為調度目標的工時階梯惡化并行機調度問題.通過分析問題構建了混合整數線性規劃模型,由于問題的NP-hard 特性,提出了遺傳變鄰域混合搜索算法(Genetic Algorithm-Variable Neighborhood Search,GA-VNS).通過集成遺傳算法(Genetic Algorithm,GA) 與變鄰域搜索(Variable Neighborhood Search,VNS)的優勢有效實現了對問題的求解.通過算例計算結果,驗證了該算法在解決較大規模算例時的效率.

1 問題描述與數學建模

給定機器集合M={1,···,m},其中M為包含所有機器的集合,m表示機器的總數,給定工件集合N={1,···,n},其中N為包含所有工件的集合,n為加工工件的總數.每個工件均可在任意一臺機器上加工.假設所有的工件在時刻0 都是可用的,即工件的準備時間為0.在加工過程中機器不會因其他因素而中斷.工件集N中的所有工件均需在機器上加工.每臺機器最多同時加工一個工件.每個工件j(j∈N)都有相應的基本加工時間aj,交貨期dj,惡化工期hj.如果工件j的開工時刻sj早于惡化工期hj,則其實際加工時間pj等于基本加工時間aj.在等待加工的過程中,工件的溫度會逐漸下降,其開工時刻sj也在逐漸增大.而當工件j的開工時刻sj晚于其惡化工期hj時,工件的溫度將不再符合加工要求,為了使工件溫度滿足加工要求,有兩種模式可以選擇:(1)對工件進行二次加熱,將發生額外的懲罰時間bj,使得pj=aj+bj,并且還會有消耗額外的能量(bj×qj),其中qj為工件j加工時的單位時間能耗.此時,工件j的實際加工時間pj是其開工時刻的階梯函數,額外消耗的能量為多出的加工時間內消耗的能量;(2)將工件放在保溫設施里對其進行保溫處理,等到其開始被加工時再取出(將工件放進和取出保溫設施的時間忽略不計).保溫模式可使工件j不增加額外的懲罰時間,但使用保溫設施對工件進行保溫操作將會發生額外的能量消耗.在保溫模式下,工件的加工時間仍等于其基本加工時間aj,額外的能量損耗ej則可表示為:

式中,e0表示使用保溫設備對工件進行保溫操作時單位時間發生的能耗.

調度決策就是指派工件到各臺機器,同時選擇恰當的工作模型以保證工件能夠順利完工,以求最小化總拖期時間與加工能耗.表1解釋了本文數學模型中的變量和符號.所提出的混合整數規劃模型如下:

目標函數為:

約束條件為:

上述模型中,目標函數(2)為最小化所有工件的加權總拖期與總能耗之和,其中 α 和 β表示所有工件在加工過程中的總拖期和總能耗的加權系數,在本文數學模型計算過程中,α 和 β均取1.因此該模型的優化目標為最小化所有工件的總拖期和總能耗之和.約束條件(3)確保每個工件只能指派給一臺機器.約束條件(4)強調如果工件i和工件j被分配到同一臺機器上加工,則它們不能同時加工.約束條件(5) 定義了工件的開工時刻并確保工件i的完工時刻ci、工件j的開工時刻sj和xij的取值保持一致,其中M為一個足夠大的數,取約束條件(6)定義了工件j的完工時刻cj.約束條件(7)給出了工件j的拖期Tj,Tj=max(cj-dj,0).約束條件(8)確定了工件j的實際加工時間pj的取值范圍.約束條件(9)強調若工件j的開工時刻sj早 于或等于其惡化工期hj(pj≤sj),則二進制變量zj=1,否則等于0.約束條件(10)確保當工件j的開工時刻sj早 于其惡化期hj時,不會再使用保溫設施進行保溫操作.即當zj=1時,uj=0.約束條件(11)確保當工件j使用保溫設施保溫時,其實際處理時間pj等 于aj.約束條件(12)定義了當工件j使用保溫設施時額外消耗的能量ej.約束條件(13)確定了工件j從時刻0 開始到加工完成消耗的總能量Ej.約束條件(14)和(15)為決策變量的取值約束.

表1 數學模型中的符號

2 遺傳變鄰域混合搜索算法

由于考慮工時階梯的單機總拖期問題已被證明為NP-hard 的[22],本文所考慮的問題為并行機加工環境且考慮能耗,因此其也是NP-hard 的.隨著工件數的增加,很難通過精確的算法獲得問題的最優解.在大規模問題求解尋找近優解時,群集智能優化算法求解效率明顯高于精確求解方法.遺傳算法能夠利用群集效應進行尋優,具有先天的并行搜索能力,故本文利用遺傳算法的這一特性進行大規模問題的求解.前期計算結果表明,若僅僅使用基本遺傳算法求解本文所提并行機調度問題,易陷入局部最優解且求解效率相對較差.在此采用混合變鄰域搜索策略來提高算法性能.使用遺傳算法經過一定迭代次數操作后的種群輸出的最優染色體做為初始解,進一步實施變鄰域搜索,以達到提高算法質量,提升運算效率的目的.因此,本文針對所提并行機調度問題的特性,集成考慮遺傳算法和變鄰域搜索的優勢,提出了基于遺傳算法框架的遺傳變鄰域混合搜索算法.

2.1 編碼和解碼方式

編碼是整個算法的第一步,對算法效果有巨大影響.本文的編碼方式必須滿足兩方面的需求,一是要確定機器的指派問題,另一個則是要確定每臺機器上工件的加工順序.本算法采用實數編碼方式.每個解序列為從1 到n+m-1隨機排序的序列.其中大小從1 到n的實數分別表示n個工件的編號.大小從n+1到n+m-1的數字為分隔符來區分不同機器,也就是說明其左邊和右邊的工件不在同一個機器上加工.例如6 個工件,3 臺機器的算例.染色體序列(1,5,7,6,3,8,4,2)表示機器一加工工件1、5 且加工先后順序為(1,5),機器二加工工件6、3,且加工先后順序為(6,3),依次類推,此序列解碼結果如圖1所示.關于當工件開始加工時其溫度不滿足加工溫度要求時的工作模式選擇問題.本文采取隨機的策略選擇其開工時刻超過惡化工期時的工作模式,即當工件的開工時刻大于其惡化工期時,其選擇施加懲罰時間和使用保溫設施保溫的概率均為50%.

2.2 遺傳算法

2.2.1 遺傳算法種群初始化

初始化種群是本文整個算法的開端,其組成結構對整個算法影響很大.本文采用隨機生成的方式生成初始種群,以保證染色體可取到所有的可能調度序列.

圖1 染色解碼方式甘特圖表示

2.2.2 適應度函數

模型目標是最小化所有工件的加權總拖期與總能耗之和,因此本文的適應度函數為目標函數的倒數:

其中,πi表示一個可行調度序列,αT(πi)+βE(πi)表示其目標值.

2.2.3 選擇策略以及精英保留

選擇的作用是可以從當前群體中選出優良個體,使得好的個體有更大的機會保留下來并將其優良的信息傳遞給下一代,因而可以逐步地向最優解逼近.本文的選擇操作選用輪盤賭選擇方法,染色體被選中的概率L為:

在式(17)中,pnum為遺傳算法部分的種群數量.為防止產生新個體的同時破壞已有的優良個體,本文采用了精英保留策略.精英保留就是在一次迭代過程中對種群進行選擇、交叉、變異等操作之后選出當前種群中適應值最大的個體,直接遺傳到下一代,下一次迭代時不對其進行遺傳操作.目的是保留最好的染色體,避免遺傳算子破壞其優良性.

2.2.4 交叉操作

交叉操作是種群中產生新個體的主要步驟,好的交叉方法對于遺傳算法的效果也有顯著影響.由于順序交叉能夠在保留原有排列的基礎上融合不同排列的有序結構單元,本文選用兩點順序交叉(類OX),順序交叉的具體流程(圖2)如下:

步驟1.父代1 和父代2 配對,從父代1 中隨機選擇一段連續的基因,并將這段基因按順序放在子代1的起始部分;

步驟2.去除父代2 中包含父代1 被選基因段的基因;

步驟3.將父代2 中去除父代1 備選基因段后剩余的基因按順序依次填入子代1 的剩余位置.此時,獲得了完整的子代1 的基因.

同理,按照以上步驟,可從父代2 中隨機選取一部分基因段和父代1 中的出去被選基因段部分,按照上述步驟插入得到子代2.

2.2.5 變異操作

當遺傳算法通過交叉算子已接近最優鄰域解時,利用變異操作可以提高其隨機搜索能力,且可以有效維持群體多樣性.本文選用隨機位置交換完成變異操作.隨機選中兩個元素進行位置調換即完成變異操作.如圖3示例:父代P1(5,8,7,1,3,4,6,2).選中第3 個元素7 和第6 個元素4 進行位置調換,即生成子代Q1(5,8,4,1,3,7,6,2).

圖3 隨機選擇變異示意圖

2.3 變鄰域搜索

變鄰域搜索算法[14]通過搜索多個鄰域結構能夠較好的避免陷入局部最優解,是一種改進型的局部搜索算法.本文對使用遺傳算法經過一定迭代次數操作后的最優染色體進行變鄰域搜索操作,以進一步改善解的質量.

變鄰域搜索算法的工作原理是通過各種鄰域結構對當前解實施變換,以產生可行解集合.目前關于調度問題的鄰域結構大多數是基于插入和交換操作.除了這些基本的鄰域結構,本文還引入了逆序操作.因此,本節使用插入和交換操作構造4 種鄰域結構,并使用逆序定義了一種鄰域結構.以下將分別對這5 種鄰域結構進行介紹.

鄰域搜索結構(Neighborhood Search) NS1 和NS2原理相似.兩者均是其中利用交換對當前解實施微小的變動.區別在于NS1 是從整個解序列的第一個元素開始到最后一個元素結束,依次隨機選擇一個與其不相等的元素進行交換,也就是把解序列內的所有元素都與其他不重復的隨機位置進行交換,而NS2 則是在解序列中隨機選擇一個元素,將其插入到另一個不重復的隨機選定的元素上.在NS1 和NS2 的操作過程中只要解的質量比原來的解好,立即接受其為當前解,并重新開始搜索;否則繼續搜索直至所有可能的組合均已完成.

鄰域搜索結構NS3 和NS4 有著類似的操作.兩者和NS1,NS2 不同的是NS3 和NS4 所進行的交換操作是兩兩交換,即同時交換的元素有4 個,成對交換.NS3 從解序列的前兩個元素開始到最后兩個元素結束,依次選擇兩個元素與另外隨機選擇的兩個不重復的元素分別進行交換.與NS1 和NS2 的區別一樣,NS4則是隨機的取兩個元素與另外一對兩個隨機的不重復的元素分別進行交換.其實施過程與NS3 相同.一旦發現給出的鄰域解有所改善,則將該鄰域解視為當前解,并再次開始搜索更好的解;否則繼續搜索直至搜索完成所有的鄰域結構.

為了進一步提高算法的性能,基于逆序操作的鄰域結構NS5 在上述4 個鄰域完成后實施.NS5 的具體操作為:從當前解序列中隨機選擇兩個元素,將兩者之間的工件全部逆序,以形成新的解.該步驟重復n+m-1次以尋找較好的解.與前4 個鄰域結構一樣,該鄰域結構只接受效果更好的解.

2.4 GA-VNS 算法框架

通過使用2.3 節的5 種鄰域搜索結構,再結合2.2 節的遺傳算法為VNS 算法提供初始解,即可對本文提出的問題實施GA-VNS 算法.GA-VNS 的終止條件為:(1)達到最大迭代次數Tp;(2)當前解連續nip次迭代沒有得到改善.若滿足上述兩個條件中的任意一個,則立即終止算法,并返回已求得的最好解.關于Tp和nip將在第3 節參數調試部分確定其具體取值.GA-VNS算法的程序架構如圖4所示.

圖4 GA-VNS 程序框圖

3 算例驗證

本章采用兩組算例驗證算法的性能,具體的參數取值見3.1 節.所提出的遺傳變鄰域混合搜索算法將在3.2 節對算法關鍵參數進行參數調試.本節對比了Gurobi、GA、VNS[14]和GA-VNS 對小規模和大規模算例的計算效果,以驗證所提算法性能.本節所涉及的所有算法均在Visual Studio 2013 平臺使用C#語言編程實現,在CPU (Intel 3.6 G)/RAM (8 GB)的個人計算機上運行.為了方便分析算法的性能,本節將求解得到的目標函數轉換成百分偏差,用R作為參數分析的響應變量,其值由式(18)決定.

式(18)中,Alg是 計算某算法R值時的當前算法,obj(Alg)則是當前算法計算10 次的平均目標值;Best是指在計算某一具體算例時本文所比較的包括Gurobi 在內的4 種算法中計算10 次平均目標值最小的算法,obj(Best)則是最好算法計算10 次的平均目標值.分析式(18)可知,R值越小,說明當前算法的效果越好.

3.1 算例設計

本節采用兩組算例來驗證算法性能.其中小規模算例的工件數n∈{4,6,8,10,12} 和m∈{2,3,4},大規模算例的 工件數n∈{20,40,60,80,100} 和m∈{4,6,8},共計30 個算例.同一組算例運算10 次,取平均值為最終運算結果.對于各個工件,設定工件j基本加工時間aj,懲罰加工時間bj,惡化工期hj,工件j開工時刻晚于惡化工期選擇使用保溫工作模式時單位時間能耗e0,加工時單位時間能耗qj,交貨期dj.此處需要說明的是,本文中所有工件在保溫時單位時間能耗e0都是相等的,在此設為5.由于所研究的問題沒有廣泛可用的基準實例集,因此本文測試實例的數據參考了文獻[14]中產生數據的方法.工件j的基本加工時間aj為[1,100]間均勻分布的隨機數;懲罰加工時間bj為[1,50]之間均勻分布的隨機數;惡化工期hj為(0,D]之間均勻分布的隨機數,其中其中w=0.5;工件在加工時單位時間能耗qj為[1,20]間均勻分布的隨機數;工件交貨期dj等于aj+(0,20],即工件j的交貨期等于其基本加工時間aj與(0,20]之間均勻分布的隨機數之和.本文在計算時目標函數的加權系數 α 和 β均取1,也就是本節所有算法計算的目標值都是總拖期與總能耗之和.

需要注意的是,Gurobi、GA 和VNS 實驗數據也是來源于此.GA 的算法結構采用本文遺傳算法部分的結構,VNS 的算法結構采用本文變鄰域搜索部分的內容.設定Gurobi 運算時間為3600 s,如果在給定的時間內沒有找到最優解,則返回當前已發現的最好整數解.關于GA 和VNS 算法的終止條件,它們的最大循環次數Tp和當前解連續沒有得到改善的迭代次數nip與GA-VNS 的相同.

3.2 參數調試

算法求解的質量和算法參數的選擇息息相關,本文所提GA-VNS 算法所涉及的主要參數為:用作GAVNS 算法初始解的遺傳算法的交叉概率Pc、變異概率Pm以 及GA-VNS 最大迭代次數Tp.基于初步測試,遺傳算法階段種群數量Pnum和最好個體連續未改善迭代次數nip分別設為50 和80.需重點調參的3 個關鍵參數的取值范圍如下:

Pc:0.6、0.7、0.8、0.9、0.99.

Pm:0.01、0.05、0.10、0.15、0.20.

Tp:100、200、300、400、500.

在GA-VNS 算法中,使用工件數為40 機器數為6 的大規模算例對每個參數都進行10 次求解運算,并對其求解結果實施單因素方差分析(ANOVA).為了方便分析不同取值水平下GA-VNS 算法的效果,圖5至圖7分別給出了3 個參數不同取值的均值圖和95% 置信水平下的Tukey 真實著性差異(Honestly Significant Difference,HSD)區間.

圖5 不同 Pc取值均值圖和TukeyHSD 區間

圖6 不同 Pm取值均值圖和TukeyHSD 區間

圖7 不同Tp取 值的均值圖和TukeyHSD 區間

從圖5可以看出,交叉概率Pc太小,會降低求解質量,而當Pc值太大時,求解質量也不是太理想.明顯得出當Pc取值為0.9 時,R值最小,算法效果最好;從圖6可以看出變異概率Pm過小對算法效果的影響并不大,當Pm的值為0.05 時,R有最小值,且隨著Pm越來越大,R值也越來越大.綜合來看,Pm設為0.05 最合適;圖7顯示當參數Tp取值水平為400、500 時,并未產生明顯差異,且二者擁有相近的均值,為保證更高的求解效率,400 是更好的選擇.故基于上述分析,交叉概率Pc=0.9,變異概率Pm=0.05,最大迭代次數Tp=400.

3.3 算例分析

在本節的計算中,同一組算例運算10 次,取平均值的整數部分,保留R值的小數后兩位與平均運行時間的小數后3 位為最終運算結果.對比了Gurobi、GA、GAVNS 和VNS 對小規模算例和大規模算例的運算結果.

表2列出了各個算法求解小規模算例的計算結果.從表2中可以看出,GA-VNS 和Gurobi 都能給出所有小規模算例的最好結果,且其解效果十分穩定.從計算時間上來看,GA-VNS 的平均計算時間為0.232 s,且只有工件數為12,機器數為4 的算例計算時間超過1 s,其余均低于1 s.而Gurobi 的平均計算時間為1.166 s,這說明在求解質量相同的情況下,GA-VNS 的求解效率要好于Gurobi.GA 和VNS 的計算時間比起GAVNS 來說相差無幾,但是兩者的求解質量卻不及GAVNS.由表2可以看到,在全部15 個小規模算例中,VNS 只給出了8 個算例的最優解,平均R值為0.804.與VNS 相比,GA 給出了13 個算例的最優解,平均R值為0.107,優于VNS,但還是不如GA-VNS 給出的解的質量好.從基于小規模算例的計算結果可以看出,GA-VNS 表現出了最好的求解性能.

使用Gurobi、GA、VNS 和GA-VNS 求解大規模算例,計算結果見表3.由于問題的難求解性,Gurobi 僅能給出機器數為6 工件數為20、機器數為8 工件數為20 以及機器數為8 工件數為40 的近似最優解.并且在求解所有大規模算例時,均耗光了計算時間都未找到最優解,且還有12 個算例未找到可行解.總體來講,Gurobi 求解大規模算例的效果并不理想.GAVNS 給出的平均R值為0.007,明顯優于Gurobi 和另外兩個啟發式算法.除了機器數為6,工件數為100 這一算例外,其余算例的最優值Best均由GA-VNS 給出.在3 種啟發式算法中,GA-VNS 由于引入GA 輸入初始解和變鄰域搜索結構,使得其平均計算時間最長,平均計算時間為3.142 s.但考慮到GA-VNS 優良的求解性能,付出的計算時間還是可以接受的.相比之下,GA 的運算時間是最短的,其平均計算時間為0.689 s.但從表3可明顯看出,雖然GA 的求解時間是最短的,但其求解效果在3 個啟發式算法中卻是最差的,平均R值達到了38.233,說明其求解精度還有很大的提高空間.VNS 的平均計算時間和GA-VNS 相差不大,為2.994 s,但在15 個大規模算例中,VNS 僅給出了一個最好的Best值,平均R值為5.24,且隨著工件數的增加,其R值也有逐漸增大的趨勢.總的來說,GA-VNS在較短的時間內給出了不錯的近似最優解,能夠有效解決同時考慮工時階梯惡化與能耗的并行機調度問題.

表2 小規模算例計算結果

表3 大規模算例計算結果

4 結論與展望

本文針對尿素造粒塔生產過程,提出了一類考慮工時惡化和能耗的并行機調度問題,建立了優化目標為加權總拖期與總能耗的混合整數線性規劃模型.由于問題的難求解性以及工作模式選擇的特殊性,本文提出了基于遺傳算法框架的改進的遺傳變鄰域混合搜索算法.采用了單因素方差分析確定關鍵算法參數,并基于隨機產生的兩組算例,分析了算法的性能.與數學求解器Gurobi、基本的遺傳算法與基本的變鄰域搜索算法的計算結果做了對比,結果驗證了本文所提算法的可行性與高效性.后續研究可引入動態規劃對兩類模式進行選擇,考慮結合更切合尿素造粒塔的實際生產情況的真實數據優化問題,同時設計多目標的求解算法,把兩個優化目標單獨研究.