遺傳算法在考慮能耗的單機批調度中的應用①

吳 愁

(中國科學技術大學 管理學院,合肥 230026)

引言

能源消耗已經成為我們社會中的一個非常重要的問題,制造業中的能耗需求就占了總能耗的33%,釋放的占到總量的38%[1].同時隨著能源需求和價格的增加,實際生產過程產生大量與生產不直接相關的能源消耗,結合制造業中瓶頸工序的問題,引入批調度在提高生產管理水平和經濟效益方面有著十分重要的現實意義,而且對于批調度很早就開始研究,Ikura和Gimple[2]首次對批調度問題進行了研究,其中批的加工時間為常數;Uzsoy[3]首次提出并研究了目標為極小化完工時間(Cmax)的差異工件單機批調度問題,并證明為NP難問題.同時隨著對節能問題關注程度的日益提升,近來越來越多的學者對節能調度進行了研究,Pechmann和Scholer[4]通過減少熱量泄露來達到保溫效果,Yu等[5]應用多目標遺傳算法對建筑設計中的節能和熱舒適性進行優化,Gong等[6]使用一個通用的方法來對節能問題進行研究,以提高單元產品的生產性價比,但是,在批處理機調度中同時考慮時間和能耗的研究卻很有限,Melouk等[7]和Damodaran等[8]分別使用基本的模擬退火法和遺傳算法僅對完工時間進行求解,而Shrouf等[9]和Che[10]分別使用遺傳算法和混合的數學規劃法僅考慮能耗成本,沒有考慮與生產性能相關的完成時間,Oron[11]利用數學方法對能耗成本和總完成時間分開進行考慮.考慮到環境的壓力,降低車間能耗對制造商是很有吸引力的,不僅表現在環境方面,在經濟上也是如此,這也是為什么越來越多的科學家致力于節能和減少制造業中碳排放的原因[12],因此在同時考慮經濟和環境下采取有效的節能措施來減少能耗問題是很有必要的[13].

本論文應用的背景主要是眼鏡鏡片的加熱回火過程,因為鏡片毛坯通常由質地相對柔軟的玻璃制成,裝入鏡架前必須通過加熱進行回火,以增加強度,而不同規格的鏡片按照不同的固化曲線和控制程序進行加工,固化時間也存在差異.所以由于顧客產品尺寸不同,種類的差異導致的加熱時間不同,可以看成差異工件的問題,同時把加熱的熔爐看作資源,很多不同尺寸,不同種類的鏡片同時放入熔爐中進行加熱,可以把這些同時進行處理的鏡片看成一批工件,而所有工件尺寸和不能超過熔爐的容量,加熱過程中不允許中斷.在同時考慮生產效率和能源消耗下,把最小化完成時間(Cmax)和總能耗成本(TEC)作為調度的目標函數,使用偏好矩陣(ωc,ωe)在Cmax和TEC之間尋找平衡.在優化過程中,對分批引入左移調度進行批的局部改進,使用改進的選擇算子,同時能耗計算時考慮分時計價原則.

本文組織如下,第二部分為問題描述和數學建模;第三部分主要介紹遺傳算法在考慮能耗的單機批調度中的應用;第四部分為相關實驗;第五部為結論與展望.

1 問題描述

1.1 相關定義

本論文是遺傳算法在考慮能耗的單機批調度中的應用,目標為最小化完工時間(Cmax)和最小化能耗總成本(TEC).

為了方便目標解的計算,需要對調度過程中的機器狀態進行說明,加工狀態(processing),待機狀態(idl(e),關)機狀態(shutdown).各種狀態的轉換如圖1.其中表示t單位時間內消耗e單位能耗.加工與關機之間的轉化需要考慮,等待和關機之間可以通過加工狀態間接轉化,所以不需要考慮直接轉化,而加工與等待之間的轉化時間太短而不需要考慮.

圖1 狀態轉換過程

1.2 數學模型

1.2.1 假設和約束

(1)工件集合J={1,2,···,N},工件j的加工時間pj,尺寸sj,加工功率ej.

(2)J中工件分批加工,任一批中的工件集合Bb,其中工件總尺寸和不超過機器容量C.

(3)加工不允許中斷,批b的加工時間Pb為Bb中所有工件最大加工時間,批b的功率Eb為Bb中所有工件的最大加工功率.

(4)目標是如何安排生產,使得Cmax最小和TEC最少.

1.2.2 數學表達式形式

(1)集合

J:工件集合J={1,2,···,N}.

B:批次集合B={b1,b2,···,bm}.

T:單位時間集合T={t1,t2,···,tn}.

S:機器狀態集合,S={1,2,3},1表示加工,2表示待機,3表示關機.

(2)參數

ct:t時刻單位電價.

Es:機器為狀態s時的單位功率.

Ess′:機器狀態轉換的單位功率.

Tss′:機器狀態轉換的時間.

pj:工件加工時間.

Pb:批的加工時間.

Eb:批的加工功率.

stb:批的開始時間.

ctb:批的完成時間.

(3)問題的數學模型

式(1)和(2)為目標問題;式(3)保證每個工件只屬于一個批;式(4)保證每個批中工件總尺寸不超過機器總容量;式(5)(6)說明批的加工時間為批中工件最長加工時間;批的加工功率為批中工件最大加工功率;式(7)給出總批數的取值范圍;式(8)保證每個時刻只能處理一個批;式(9)(10)保證處理不被打斷;式(11)保證加工批時機器處于加工狀態;式(12)保證機器的狀態;式(13)(14)保證只有前一個操作結束后才能進行下一個操作;式(15)保證批的順序.

2 遺傳算法在考慮能耗的單機批調度中的應用

2.1 編碼與初始種群的產生

本文采用基于工件序列的編碼方式,每個工件都用唯一的自然數表示,對于N個工件的調度問題,隨機產生1到N的一個排列,每個位置上的數字表示對應的工件號,個體就用這組數字串表示.而種群的大小根據研究問題的規模而定,本論文中初始種群大小為20,采用隨機方法產生一組初始種群.

2.2 目標的評估

本論文的目標問題為:最小化完成時間(Cmax),最小化能耗總成本(TEC).

Cmax為最后一批工件加工結束的時間,Cmax越小意味著機器的利用率越高.在生產過程中使用隨著時間變化的價格可能會給制造企業在成本上帶來一定程度的節約,Nghiem等[14]通過對減少峰值的能耗需求的控制系統的綠色調度進行研究,并證明抑制峰值能夠使成本和效率之間更加協調,所以本文最小化TEC主要是通過延長Cmax來降低能耗成本,比如在用電高峰(單位電價較高)時等待或者關閉機器,選擇單位電價比較合理時(用電低峰)進行工件加工.

機器是否等待的判斷標準是,對比當前和后一單位時刻電價,如果當前電價較低則不等待直接加工;反之,讓機器處于待機狀態或者關閉機器.PEidle/PEon/PEoff分別為單位待機能耗/開機能耗/關機能耗,Tidle、Ton、Toff為對應的時間,用公式表示如下:

令上一批的完工時間為t′?1,如果滿足條件公式(16),則等待加工并計算等待時間Tidle,反之繼續加工.當等待時間為Tidle時,如果滿足條件公式(17),則關閉機器,反之等待加工.

2.3 工件分批及其優化

本實驗采用BF分批規則,即工件j放入的批次為滿足機器容量要求且為當前加工時間最長的批.

在實驗中引入一種左移調度,即sch是Bh的剩余空間,Ph為Bh的加工時間,Bh在Bk前被加工,如果Bk中的工件i滿足si≤sch且pi≤Ph,則從Bk移到Bh中,直到Bk中沒有工件滿足si≤sch且pi≤Ph,大致過程描述如下:

(1)K為總批數,k=K.

(2)如果k＜2,程序結束,反之h=k-1.

(3)如果h≥1,找到Bk中加工時間最長的工件a,即pa=Pk,Bh的剩余空間sch,Bk的剩余空間sck,如果pa＞Ph,h=h?1;如果pa≤Ph且sa≤sch,把工件a從Bk移到Bh中,更新批次;如果pa≤Ph且sa≥sch,跳轉(4).反之k=k–1,跳轉(2).

(4)找到Bh中滿足pi＜pa的工件集合ω,ω={i∈Bh|pi＜pa},ω∈Bh計算ω中所有工件的尺寸s(ω).如果Bk中工件a滿足s(ω)≤sck+sa且sa≤sch+s(ω),工件a和集合ω中所有工件交換,否則刪除集合ω中最后一個工件直到集合ω=?.

2.4 適應度的計算

如果Cmiax≤Cmjax且TECi≤TECj,而且至少有一個嚴格成立,則個體i優于j,表示為j?i,個體j被個體i所支配.

因為每個決策者對最大完成時間和能耗總成本的關注程度不一樣,所以引入偏好矩陣ω=(ωc,ωe),其中ωc、ωe分別表示完成時間和能耗總成本的權重,且ωc+ωe=1,它反映調度中對Cmax和TEC的關注程度,系數值越大表示關注程度越大.令Cm′ax=ωcCmax,TEC′=ωeTEC,根據Cm′ax、TEC′計算適應度,結合文獻[15]等使用的適應度計算方法,本論文的適應度值表示為Fi=Si+di,Si和di具體定義如下.

用Gi表示個體i優于其它個體的數目,定義如下:

用Si表示嚴格優于自己的所有個體的長度值Gi之和,具體定義為:

所以Si的值越大,對應的個體越差,因為它被其它更多個體所支配.

為了區分沒有被其它解所支配的解的差異,我們引入密度估計.即根據、TEC′計算歐式距離,個體i,j之間的歐式距離定義如下:

2.5 最優解的選擇

決策者依據適應度值對目標值進行選擇,根據適應度值可以看出,當適應度值越小代表個體越優.

本論文中采用優化的輪盤賭法與Metropolis準則相結合,當一個種群被選中超過種群的20%需要對選擇的個體進行修正,主要是根據個體被選中的順序對應原個體順序來進行替換,除了第一次出現的位置保持不變,其它位置根據Metropolis規則來進行替換,這樣可以防止陷入僵局.具體步驟如下:

(1)對種群中的所有個體計算適應度值,并將個體按從小到大的適應度值排列,記為S1.

(2)根據選擇概率輪盤賭選擇個體,并按選中的順序排好序,記為S2.

(3)根據S2的結果判斷哪些個體被選中的次數超過種群的20%,找到這些個體對應的原個體,即對應位置上的S1中的個體,除了第一次出現的位置不進行處理,其余的位置通過Metropolis準則來判斷該個體是被接受還是舍棄,處理過程為:

1)i為S1中的個體,j為S2中對應位置的個體.

2)當Fi＞Fj,產生隨機數r∈(0,1),當滿足條件r≤exp{(Fj?Fi)/T}時,保留S2中的個體j,否則用個體i代替個體j,其中T為控制參數.

3)當Fi＜Fj時,對S2中的個體j進行保留.

(4)S2為最后選中的個體.

3 仿真實驗與分析

3.1 實驗設計

本實驗采用文獻[7]提出的隨機產生方法獲得算例,算例的規模按如下4個標準進行劃分:工件數量N,工件的加工時間pj,工件尺寸sj,工件加工功率ej,其中,pj,sj,ej均服從離散均勻分布,算例生成的若干參數及范圍見表1.

表1 算例生成因素及等級

為了對每類問題的算例進行標記,用J1p1s1e1表示10個工件,工件尺寸服從[1,10],加工時間服從[1,10],加工功率服從[3,5],機器容量為10.

本文采用分時計價原則,分時電價由電網的不同時期提供,實驗中采用夏季計價標準,計價標準函數用c(t)表示,具體見公式(22),表2和表3為與加工過程相關的信息.

表2 加工相關的單位功率信息

表3 開關機所需時間信息

對于本論文的實驗結果,分別從解的質量和算法性能兩方面進行比較.

(1)解的質量用Pareto最優解集規模表示,Pareto最優解集規模為找到非支配解的數量,解的數目越多,選擇余地更多.

(2)用解集之間的覆蓋率來對算法性能進行衡量,覆蓋率C(A,B)表示算法B所求得的Pareto最優解集被算法A所生成解集支配的解的比例,按照下式計算:

其中,a?b表示解b被解a所支配.C(A,B)的值越接近1代表算法A的性能相對于算法B越好,但一般情況下C(A,B)≠C(B,A),當C(A,B)>C(B,A)時表示算法A的性能優于算法B.

3.2 實驗結果與分析

本實驗中的算法均在Matlab 2016a平臺下實現,每類問題隨機生成10個算例,每個算例各運行15次取平均值.

表4列出了在CEC和IEC下,使用遺傳算法在不同算例下找到的非支配解個數,從表中可以看出,CEC找到的非支配解個數要明顯優于IEC,反映了在工件規模較大的情況下CEC對非支配解的搜索效果要優于IEC.而且隨著問題復雜程度的提高,找到的非支配解個數呈現增加趨勢.

表4 非支配解的數量

表5列出了兩種情況下在不同算例下找到的非支配解的質量對,在J1類子問題中CEC的覆蓋率和IEC的差不多,但隨著工件規模的增大,CEC的優勢表現得更加明顯,說明在問題復雜度較高的情況下,CEC取得的非支配解在質量上要優于IEC.

為了更形象化了解在不同情況下,不同類型算例下非支配解的分布和算法的迭代優化情況,下面繪制了算例的非支配解部分分布圖和部分算例迭代尋優曲線.

表5 覆蓋率比較

圖2 10個工件問題的非支配解分布圖

圖3 20個工件問題的非支配解分布圖

圖4 50個工件問題的非支配解分布圖

圖5 算例J1p1s1e1的迭代優化圖

圖6 算例J2p1s2e2的迭代優化圖

圖7 算例J3p2s3e3的迭代優化圖

4 結論

本文研究了遺傳算法在考慮能耗的單機批調度中的應用,目標為最小化最大完工時間和最小化能耗成本,應用背景主要來源于眼鏡生產過程中鏡片的固化加熱過程.本文主要通過優化的遺傳算法找到帕累托最優解,在能耗成本計算中引入分時計價原則,并利用偏好矩陣來對完工時間和能耗成本之間進行權衡,同時結合非支配解來計算適應度值.從實驗結果來看,CEC下獲得的解集規模更大.另外,對生產調度中的問題考慮能耗成本后可以在得到比較合理的完工時間的同時大大節約能耗成本,這樣更能滿足實際生產過程中的需求.

這里還有很多方面可以在以后進行研究,比如對機器狀態轉換過程的判斷標準,分時計價中的時間周期和定價標準的影響等問題進行進一步分析與研究.另一方面可以想辦法提高遺傳算法對非支配解的搜索能力,更好的求解雙目標的差異工件單機批調度問題.