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

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

1 引言

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

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

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

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

2 問題描述

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

表1 模型參數(shù)符號及其定義

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

(2)工件沒有優(yōu)先權(quán).

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

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

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

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

3 混合進化算法設(shè)計

3.1 染色體編碼及適應(yīng)度函數(shù)

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

表2 算例數(shù)據(jù)

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

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

圖1 解碼后甘特圖

3.2 種群初始化

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

3.3 選擇

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

3.4 交叉

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

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

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

即交叉后:

3.5 變異

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

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

3.6 種群多樣性

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

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

3.7 變鄰域搜索VNS

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

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

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

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

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

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

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

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

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

3.8 搜索擾動

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

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

3.9 混合進化算法流程

?

4 算例仿真及結(jié)果分析

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

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

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

算例中加工參數(shù)按以下規(guī)則隨機產(chǎn)生:

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

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

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

傳統(tǒng)GA算法參數(shù)設(shè)置:種群規(guī)模Np=60,最大連續(xù)非改進迭代數(shù)=60 ,最大迭代次數(shù)tmax=1000,交叉概率 pc=0.65,變異概率 pm=0.01.

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

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

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

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

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

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

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

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

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

表3 小規(guī)模算例對比

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

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

表4 大規(guī)模算例對比

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

5 結(jié)論與展望

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