混和進化算法求解具有分段惡化效應的并行機調度問題①

陳海潮,程文明,郭 鵬,王麗敏

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

1 引言

在傳統的調度理論中,通常工件的加工參數事先是完全確定的.然而在現實生產過程中,一些工件的實際加工時間會隨其開始加工的時間的延后而增長.這種情況經常發生在許多化學和冶金過程中.例如,在鋼軋機中,在軋制之前將錠加熱至所需溫度.加熱時間取決于錠的當前溫度(這取決于錠等待的時間).在等待期間,晶錠冷卻,因此在爐中需要更多的加熱時間.這會導致被加工工件的處理時間的延長,這種工件加工時間隨開始加工時刻變化的現象稱之為惡化效應.

本文研究的為帶惡化的生產調度問題,這個問題最早由Gupta 等[1]和Browne 等[2]提出,Gupta 等[1]在1988年引入了帶惡化的單機調度問題,他們認為任務的處理時間為多項式函數,1990年Browne 等[2]提出工件的作業處理時間是不間斷的,是具有與開始時間相關的線性函數.對于處理時間分段線性惡化的單機調度問題,Kunnathur 和Gupta[3]最早提出并給出了模型.Kubiak 等[4]比Kunnathur 和Gupta[3]多引入了惡化工期最大值H,如果H 趨近無窮大,則惡化造成的增加量就是無限的,否則增加量就是有限的.Hosseini 和Farahani[5]他們給定了一個規定的加工時刻h,提前加工會得到一個獎勵時間,延后會有一定的惡化時間從而提出了新的分段惡化模型.Wang 等[6]考慮了非線性惡化的單機調度問題.Wei 等[7]和Wang 等[8]考慮了具有時間和資源相關處理時間的單機調度.Jiang 等[9],Wang[10],Wang 等[11,12]和Wang 等[13]考慮了具有學習效果和惡化工作的單機調度問題.

在帶惡化并行機調度問題的求解方面,Rostami等[14]考慮了模糊環境下帶工件惡化和學習效應的異構并行機調度問題,提出了分支定界算法以最小化提前延誤和最大完工時間.Eduardo 等[15]考慮了帶階梯惡化工件的等同并行機調度,以最小化總完工時間為目標函數,提出了兩種基于集合劃分的數學模型.Bahalke等[16]考慮了具有一般線性惡化效應和順序依賴的調整時間的單機最大完工時間最小化調度問題,并利用遺傳算法進行求解.國內對帶惡化并行機調度的問題研究較少,軒華等[17]研究了以最小化最大完工時間為目標的不相關并行機環境下帶惡化工件的車間調度問題,假定工件在不同機器上有不同的惡化系數,并設計了兩段式編碼的改進遺傳算法.郭鵬[18]針對具有階梯惡化效應的并行機調度問題,構建了目標總完工時間最小化的混合整數規劃模型,并設計了基于工件排序的變領域搜索算法VNS.

就目前查閱的文獻而言,現有的研究大多假定工件具有固定的惡化率或者惡化效應為線性惡化以簡化問題,對分段線性惡化的并行機調度的研究還較少.本文研究具有分段線性惡化的并行機調度問題,其中工件加工時間 pj=aj+bjxjb,aj為工件j 在正常情況下的基本加工時間,bj為工件j 的懲罰時間,xjb為0-1 變量,如果工件j 在惡化工期 hj之前加工則 xjb=0,否則發生惡化 xjb=1.

2 問題描述

各參數符號定義如表1 所示,并給出以下問題假設:

表1 模型參數符號及其定義

(1)一臺機器不能同時加工多個工件,并且一個工件也不能被多次加工.

(2)工件沒有優先權.

(3)機器是連續可用的,即機器不會在有工件在等待加工時空閑.

(4)各工件正常情況下加工時間、惡化工期、惡化率已知.

基于以上假設,問題即是對于n 個在m 臺機器上加工,已知正常情況下基本加工時間,帶有不同惡化工期和惡化率的工件,尋找一個最優調度S,使最大完工時間這一優化目標最小.

其中,式(1)是目標函數,代表所需求的最小的最大完工時間,也就是所需要求出的最優工件排序的最后一個工件的完工時間.式(2)定義了工件的實際加工時間,如果工件在惡化工期前加工,那么加工時間為基本加工時間,否則增加一個懲罰時間.式(3)表示同一時間機器上只有一個工件在加工的.式(4)表示機器同一個加工位置只能分配一個工件,式(5)表示機器第一個的工件開始加工的時間非負.式(6)表示機器上l 位置工件的開工時刻是l-1 位置的完工時間.式(7)確定了機器k 在l 位置工件的完工時間.式(8)和式(9)表示工件的完工時刻和開始加工的時間.式(10)表示定義為0-1 變量.式(11)表明機器位置l 處工件開始加工的時刻和其完工時間是非負的.

3 混合進化算法設計

3.1 染色體編碼及適應度函數

染色體編碼用自然數序列表示工件加工的順序,解碼時,按照染色體編碼的順序依次將工件分配到最早可用的機器上.適應度函數即計算對應染色體調度分配后的工件完工時間總和的倒數.進化的目標是使適應度函數最大.例如,對于針對表2算例,并以2 臺機器6 個工件舉例.

表2 算例數據

若某一染色體編碼(根據SRF 規則生成)為:

則解碼后甘特圖如圖1 所示,且總完工時間為617.

圖1 解碼后甘特圖

3.2 種群初始化

對立學習(Opposition-Based Learning,OBL)[19]被應用于多種進化算法以提高性能,在進化過程中,不只考慮通常的解,還考慮其對立解,以提高收斂速度.而在種群初始化過程中采用對立策略能夠顯著增強初始解的質量.對立策略考慮當前點以及其對立點.對立點的定義如下:假設 p(x1,x2,···,xn)是N 維空間的一個點,x1,x2,···,xn,x ∈[ai,bi],i=1,2,···,N,則p 的對立點可表示為,其中,=ai+bi-xi.計算隨機生成的初始種群中每個個體的對立點并進行計較,將兩者中較好的解保留.此外根據問題的性質,基本加工時間較小的和懲罰時間較大的工件應先加工.因此,初始種群中的一個解可按照aj/bj的升序排列獲得.將其稱為最小比率優先(Smallest Rate First,SRF)規則.

3.3 選擇

采用輪盤賭選擇方式,若染色體 xi應 度值為 f(xi)個體被選中的概率,即適應度越高的個體被選擇的概率越大.

3.4 交叉

采用部分匹配交叉.如兩個父代個體為:

隨機選擇兩交叉點位并交換中間的染色體片段:

對于交叉點位外的區域出現的遍歷重復,根據匹配區域內的映射關系,逐一進行交換.比如,對于p1 交叉區域外重復的片段,存在來自p2 交叉區域內7 到4,2 到8 的映射.即對p1 匹配區外4 和8 分別以7 和2 替代.對于p2 同理.

即交叉后:

3.5 變異

變異采用兩點交換變異,隨機選擇兩交叉點并交換兩基因點位.如某個體p1 為:

隨機選擇兩交叉點位,如p1 中隨機選擇5 工件與6 工件,變異后得到個體:

3.6 種群多樣性

在遺傳算法不斷進行優化迭代的過程中,在進化的初期,種群擁有多種個體,而后由于適者生存,較高適應度的個體不斷被保留,種群的多樣性不斷下降,逐漸趨于成熟,遺傳算法的擇優基本依賴于種群中個體的變異,此時遺傳算法的搜索效率大大降低.因此本文在提出遺傳算法中加入種群多樣性指標 Np在種群多樣性不足,搜索效率不足時跳出遺傳算法,對目前得到的最優解進行變鄰域搜索.

其中,N 是種群中基因完全不同的個體,是種群規模.

3.7 變鄰域搜索VNS

變鄰域索算法(Variable Neighborhood Search,VNS)是1997年由Mladenovi 和Hansen[20]提出的一種局部搜索方法,主要包括

隨機擾動、局部搜索和鄰域變換等3 個過程.

本文采用5 種鄰域結構,單點交換,單點插入,兩點交換,兩點插入和逆序操作.具體操作如下所示.

單點交換.隨機選取染色體序列上的兩點進行交換.

單點插入.隨機選取染色體序列上一個基因,將其取出,插入到另外一個隨機點位中.

兩點交換.首先隨機選取染色體序列上的兩個基因點,再隨機選擇染色體上的另外兩個基因點,兩次選擇的基因點位上的基因進行互換.

兩點插入.隨機取出染色體序列上的兩個基因點,將其分別插入兩個隨機點位.

逆序操作.隨機選擇染色體上的兩個基因點位,將兩個基因點位之間的基因全部逆序.

其中,由于本文染色體解的形式為自然數序列,其中單點交換與單點插入是所有鄰域結構中對解產生的最微小的擾動,保證了每次搜索的精度,兩點交換與兩點插入是單點操作的延伸,相當于同時進行兩次單點操作但不評估首次交換后的結果,一定程度上防止陷入局部最優.逆序操作是為了進一步提升算法的性能加入的隨機搜索過程,在以上4 個領域結構完成后實施.

3.8 搜索擾動

為防止算法陷入局部最優,當算法連續多代沒有改善時,對當前的解進行擾動產生下一次迭代的初始解,以減少重復搜索的時間.本文采用3-opt 交換算子,具體實施過程為隨機選擇染色體上三個基因點位,將染色體分成4 段子序列,保持子序列的方向不變對4 段子序列重新進行連接,易知4 段子序列總共有4! =24種排列組合方式,本算法僅交換中間兩段子序列,首位子序列保持不變.例如某染色體為:

隨機選擇4,7,5 工件所在的位置,交換中間兩段子序列后得到:

3.9 混合進化算法流程

?

4 算例仿真及結果分析

根據數學模型,首先采用Gurobi 對小規模算例進行計算,驗證所提出算法的有效性,設定最大計算時間為1800 s.此外,為了驗證所以出的算法性能,同時在較大規模的算例中將其與傳統GA算法以及VNS算法進行比較.所有的算法均在處理器為Intel(R)Core(TM)i7-9750H CPU@2.60 GHZ,內存8.00 GB 微機Python 3.7 上實現.

為了確定算法的參數,根據文獻[21]提供的各項參數進行取值設置.

小規模算例工件數 n ∈{6,8,10,12} 和機器數m ∈{2,3);大規模算例工件數n ∈{30,50,100} 和機器數m ∈{5,10,20).

算例中加工參數按以下規則隨機產生:

基本加工時間為[1,100]之間均勻分布的隨機數;

懲罰加工時間為[1,100]之間均勻分布的隨機數;

惡化工期取來自不同區間 H1(0,D0.5] ,H2(D0.5,D],和 H3(0,D]的 均勻分布的隨機數,其中(0 ≤f ≤1).

傳統GA算法參數設置:種群規模Np=60,最大連續非改進迭代數=60 ,最大迭代次數tmax=1000,交叉概率 pc=0.65,變異概率 pm=0.01.

VNS算法參數設置:取最大迭代次數itermax=200,最大連續非改進迭代數=20.初始解由最小比率優先(SRF)規則生成.

OBGAVNS算法參數設置:為與傳統GA算法以及VNS算法形成有效對照,所采用的參數與對比參數大部分相同,即種群規模 Np=60,最大連續非改進迭代數=60 ,最大迭代次數tmax=1000,交叉概率pc=0.65 ,變異概率 pm=0.01.VNS 優化部分的最大迭代次數 i termax=200 ,最大連續非改進迭代數=20,此外另取種群多樣度閾值Ntmin=0.05.

為了方便分析算法的性能,本文將還目標值轉化為相對百分比偏差(Relative Percentage Deviation,RPD)[18],以這個值作為參數分析的相應變量.RPD 值由下式決定:

式(12)中Z(A)是算例計算目標值,Z(B)是算例在各種算法多次計算中所能獲得的最優目標值.

小規模算例對比結果如表3 所示,表中數據均為計算10 次后的平均值.但由于Gurobi 的性能限制,隨著算例規模的增大,Gurobi 逐漸無法在設定的時間內求問題的解,因此表中只列出Gurobi 在設定時間內能求得解的算例.同時將各算法在算例中得到的最小RPD 值加粗.

根據小規模算例測試結果,所采用來對比的OBGAVNS算法、傳統GA算法以及VNS算法是有效的并且與Gurobi 這類數學規劃求解器相比,在計算時間上具有明顯的優勢.同時OBGAVNS算法的計算結果與VNS算法以及傳統GA算法相比,在大部分算例中都具有最小的RPD 值,其中OBGAVNS算法的平均RDP 值為0.23%,而VNS算法平均RPD 值為0.53%,傳統GA算法平均RPD 值為0.58%,表現出較好的計算性能.

大規模算例如表4 所示,其中,RPDa 為所用算法計算結果平均值的相對百分比偏差,RPDm 為所用算法計算結果最小值的相對百分比偏差.對表格中OBGAVNS算法在對比中最優部分進行加粗.

通過對比3 種算法的RPD 值可知,所設計的OBGAVNS算法的所有算例的平均RDP 值為0.36%,最小RPD 值為0.04%,VNS算法的平均RPD 值為0.68%,最小RPD 值為0.21%,傳統GA 的平均RPD 值為3.37%,最小RPD 值為1.83%.從所有算例的平均RPD 值的計算結果看,OBGAVNS算法的計算性能效果優于傳統GA 與VNS.此外,在大部分的算例中,OBGAVNS算法在3 種算法中都取得了最優的計算結果.

這是由于,與VNS算法相比,OBGAVNS算法的VNS 部分初始解由遺傳算法提供,其初始解質量優于一般的VNS算法.此外,與一般的VNS算法不同,OBGAVNS算法給VNS 尋優部分提供的初始解帶有一定的隨機性,在每次重復搜索中都會有所不同,這為VNS算法提供了更大的搜索域,此外在OBGAVNS算法中還加入了3-opt 擾動算子能夠使算法在VNS 尋優部分能夠跳出局部最優解.

表3 小規模算例對比

隨著算例規模的增加,算法的計算時間也在同步增加,所提出的OBGAVNS算法中由于有更多的操作算子,因此較對比的算法而言需要更多的計算時間,從大規模算例統計的結果看,OBGAVNS算法平均計算時間是3 種算法中最長的,傳統GA 時間最短,這是由于傳統GA 雖然具有較好的全局搜索能力,但欠缺局部搜索能力,因此容易陷入局部最優過早收斂.OBGAVNS算法與VNS算法相比,除了初始解生成多花費的時間外,花費的時間主要是在擾動部分,每次擾動后都需要花費額外的一部分時間進行尋優,但與算法性能的提升來說,仍在可接受的范圍內,并且隨算例規模的增加,計算時間的百分比差距也有所減少.例如,S1算例中5 臺機器30 個工件OBGAVNS算法計算時間為VNS算法的5.52 倍,而增加到5 臺機器100 個工件時計算時間縮短為2.97 倍.

為了更直觀的展示算法的性能,以算例H1 區間5 臺機器50 個工件為例給出迭代中的個體分布圖如2 所示.根據程序計算結果,其中0 到152 代為遺傳算法部分,個體數為種大小,在152 代由于到達種群多樣性指標閾值因而進入變鄰域搜索部分,對單一個體進行VNS 優化,并在連續非改進次數達到時進行3-opt 擾動(在圖2 中表現為適應度值變差),開始重新搜索如此循環,最終到達設定的最大迭代次數或連續非改進次數停止搜索,輸出迭代中最好的解.

表4 大規模算例對比

圖2 OBGAVNS算法迭代個體分布圖

5 結論與展望

本文針對具有線性惡化的并行機調度問題,提出了一種混合進化算法OBGAVNS,該算法采用工件序號編碼以及機器先空閑先分配的解碼規則,用對立策略以及最小比率優先規則生成初始種群以提高初始種群的質量,并且引入種群多樣度指標加快算法的收斂;針對遺傳算法局部搜索能力不強的特點,加入帶有3-opt 擾動算子的VNS 變鄰域搜索算法對遺傳算法得到的結果進行優化.通過對不同規模的算例進行仿真實驗,結果表明了所提出OBGAVNS算法的有效性,并且其性能較傳統GA 與VNS算法均有所提升.接下來的研究工作將考慮更復雜的機器環境,如異速并行機、流水車間等,并添加考慮能耗與調整時間等約束使之更貼近生產實際.