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

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

1 引言

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

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

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

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

2 問題描述

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

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

(1)一臺(tái)機(jī)器不能同時(shí)加工多個(gè)工件,并且一個(gè)工件也不能被多次加工.

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

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

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

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

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

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

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

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

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

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

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

圖1 解碼后甘特圖

3.2 種群初始化

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

3.3 選擇

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

3.4 交叉

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

隨機(jī)選擇兩交叉點(diǎn)位并交換中間的染色體片段:

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

即交叉后:

3.5 變異

變異采用兩點(diǎn)交換變異,隨機(jī)選擇兩交叉點(diǎn)并交換兩基因點(diǎn)位.如某個(gè)體p1 為:

隨機(jī)選擇兩交叉點(diǎn)位,如p1 中隨機(jī)選擇5 工件與6 工件,變異后得到個(gè)體:

3.6 種群多樣性

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

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

3.7 變鄰域搜索VNS

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

隨機(jī)擾動(dòng)、局部搜索和鄰域變換等3 個(gè)過程.

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

單點(diǎn)交換.隨機(jī)選取染色體序列上的兩點(diǎn)進(jìn)行交換.

單點(diǎn)插入.隨機(jī)選取染色體序列上一個(gè)基因,將其取出,插入到另外一個(gè)隨機(jī)點(diǎn)位中.

兩點(diǎn)交換.首先隨機(jī)選取染色體序列上的兩個(gè)基因點(diǎn),再隨機(jī)選擇染色體上的另外兩個(gè)基因點(diǎn),兩次選擇的基因點(diǎn)位上的基因進(jìn)行互換.

兩點(diǎn)插入.隨機(jī)取出染色體序列上的兩個(gè)基因點(diǎn),將其分別插入兩個(gè)隨機(jī)點(diǎn)位.

逆序操作.隨機(jī)選擇染色體上的兩個(gè)基因點(diǎn)位,將兩個(gè)基因點(diǎn)位之間的基因全部逆序.

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

3.8 搜索擾動(dòng)

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

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

3.9 混合進(jìn)化算法流程

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 OBGAVNS算法迭代個(gè)體分布圖

5 結(jié)論與展望

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