貪婪初始種群的遺傳算法求解柔性作業(yè)車間調(diào)度

屈新懷, 王 嬌, 丁必榮, 孟冠軍

(合肥工業(yè)大學(xué) 機(jī)械工程學(xué)院,安徽 合肥 230009)

柔性作業(yè)車間調(diào)度問(wèn)題突破了設(shè)備資源唯一性的限制,每道工序可由不同的機(jī)器加工,并且在不同機(jī)器所需的加工時(shí)間不同,其主要考慮機(jī)器選擇和工序排序這2個(gè)問(wèn)題,是作業(yè)車間調(diào)度的擴(kuò)展,更加符合生產(chǎn)實(shí)際[1]。柔性作業(yè)車間調(diào)度問(wèn)題是制造業(yè)信息化的重要內(nèi)容,也一直是國(guó)內(nèi)外學(xué)者研究的熱點(diǎn),是典型的NP難問(wèn)題。

目前,研究柔性作業(yè)車間調(diào)度問(wèn)題常用的算法是智能優(yōu)化算法,其中,遺傳算法因其全局搜索能力強(qiáng)、魯棒性好被廣泛地應(yīng)用于柔性作業(yè)車間調(diào)度問(wèn)題上,但是遺傳算法也存在收斂速度慢、易早熟等不足以及種群多樣性不足的缺陷[2]。為了提高算法性能,國(guó)內(nèi)外學(xué)者在求解柔性作業(yè)車間調(diào)度問(wèn)題時(shí),從各個(gè)方面對(duì)遺傳算法進(jìn)行改進(jìn)。文獻(xiàn)[3]針對(duì)柔性作業(yè)車間調(diào)度問(wèn)題特點(diǎn)提出主動(dòng)調(diào)度的插入式解碼機(jī)制;文獻(xiàn)[4]針對(duì)柔性作業(yè)車間調(diào)度問(wèn)題采用層次多空間競(jìng)爭(zhēng)遺傳算法進(jìn)行有效的層次優(yōu)化;文獻(xiàn)[5]提出自適應(yīng)交叉和變異概率;文獻(xiàn)[6]將遺傳算法與其他智能算法相結(jié)合求解柔性作業(yè)車間調(diào)度問(wèn)題。還有許多學(xué)者對(duì)初始化方法進(jìn)行了改進(jìn)。文獻(xiàn)[7]基于短用時(shí)策略的指派方法生成初始種群;文獻(xiàn)[8]提出一種全局搜索、局部搜索和隨機(jī)產(chǎn)生相結(jié)合的初始化方法;文獻(xiàn)[9]采用同時(shí)考慮處理時(shí)間和工作量的啟發(fā)式方法與隨機(jī)產(chǎn)生相結(jié)合的策略生成初始種群;文獻(xiàn)[10]提出基于全程檢索規(guī)則編碼的初始種群生成策略。以上初始化方法分別為每個(gè)工件選擇機(jī)器,卻沒有考慮不同工件工序之間的相互影響。

本文結(jié)合柔性作業(yè)車間調(diào)度問(wèn)題的特點(diǎn),提出貪婪初始化方法,隨機(jī)為工序排序,然后采用貪婪算法按工序的排序?yàn)槊總€(gè)工序選擇當(dāng)前加工時(shí)間最短的機(jī)器,從而生成較優(yōu)的初始種群,為了保證解的多樣性設(shè)計(jì)了貪婪初始化與隨機(jī)生成相結(jié)合的初始化方法;在進(jìn)行選擇操作時(shí)先篩選出機(jī)器染色體相同的種群,并通過(guò)初始化方法生成新的種群進(jìn)行替換,使得算法在求解過(guò)程中能有效地跳出局部最優(yōu)。

1 問(wèn)題描述

柔性作業(yè)車間調(diào)度問(wèn)題可以描述為n×m問(wèn)題:n表示車間內(nèi)有n個(gè)待加工工件;m表示車間內(nèi)有m臺(tái)可選擇加工機(jī)器;n×m表示n個(gè)工件在m臺(tái)機(jī)器上加工的柔性作業(yè)車間調(diào)度問(wèn)題;J={J1,J2,…,Jn}表示工件集;M={M1,M2,…,mn}表示機(jī)器集;Oi={Oi1,Oi2,…,Oij}表示工件Ji的工序集;Mij?{M1,M2,…,Mm}為每道工序Oij的可選擇加工機(jī)器集,每道工序在不同機(jī)器上都有相應(yīng)的加工時(shí)間。柔性作業(yè)車間調(diào)度為工序安排最佳的加工順序和選擇最佳的加工機(jī)器,以達(dá)到優(yōu)化給定性能指標(biāo)的目標(biāo),其中3×3問(wèn)題見表1所列。

表1 3×3問(wèn)題

本文柔性作業(yè)車間調(diào)度問(wèn)題以最大完工時(shí)間最小為優(yōu)化目標(biāo),目標(biāo)函數(shù)可表示為:

minCmax=min(maxCi), 1≤i≤n

(1)

其中:Cmax為工件最大完工時(shí)間;Ci為工件Ji的完工時(shí)間。

對(duì)于柔性作業(yè)車間調(diào)度問(wèn)題,需滿足的約束條件[11]如下:

(1) 在零時(shí)刻,所有設(shè)備都是空閑的,所有工件都可以被加工。

(2) 不同工件之間具有相同的優(yōu)先級(jí),同工件的工序嚴(yán)格按照加工順序加工,每道工序必須在其前一道工序完成后才能進(jìn)行。

(3) 每道工序只能從可加工機(jī)器集中選擇一臺(tái)進(jìn)行加工。

(4) 每道工序一旦開始,加工過(guò)程不中斷。

(5) 同一時(shí)刻的各臺(tái)機(jī)器最多只能加工一道工序。

2 算法設(shè)計(jì)

2.1 編碼與解碼

柔性作業(yè)車間調(diào)度問(wèn)題要同時(shí)考慮工序排序和機(jī)器選擇2個(gè)方面,因此采用分段編碼方式:前段為工序排序染色體編碼,用來(lái)確定工序加工順序,數(shù)值i表示工件號(hào),而數(shù)值出現(xiàn)的次數(shù)j表示該工件的第j道工序,對(duì)應(yīng)的工序?yàn)镺ij;后段為機(jī)器選擇染色體編碼,機(jī)器編碼按順序?yàn)楣ぜ﨡1,J2,…,Jn的工序選擇的加工機(jī)器,用數(shù)值s表示選擇該工序可加工機(jī)器集合中的第s臺(tái)機(jī)器,如圖1所示。

圖1 染色體編碼

2.2 貪婪初始化

初始種群的質(zhì)量對(duì)遺傳算法的求解質(zhì)量和收斂速度有非常大的影響,求解柔性作業(yè)車間調(diào)度問(wèn)題是為工序排序及每道工序選擇最佳機(jī)器,各工序排序影響著機(jī)器的選擇。

根據(jù)柔性作業(yè)車間調(diào)度問(wèn)題的特點(diǎn),本文提出了貪婪初始化的初始化方法,生成局部最優(yōu)的初始種群,貪婪初始化工序排序部分采用隨機(jī)生成的方式,機(jī)器選擇部分按照工序排序順序?yàn)槊康拦ば蜻x擇當(dāng)前完工時(shí)間最短的機(jī)器。具體執(zhí)行步驟如下:

(1) 設(shè)置整數(shù)組tMP、tJP及參數(shù)k,tMP為機(jī)器{M1,M2,…,Mm}對(duì)應(yīng)的緊前工序完工時(shí)間,tJP為工件{J1,J2,…,Jn}對(duì)應(yīng)的緊前工序完工時(shí)間,初始化數(shù)組tMP、tJP中每個(gè)元素值為0,參數(shù)k=1。

(2) 隨機(jī)生成一條工序排序部分染色體OS。

(3) 為OS[k]即工序Oij選擇機(jī)器。將工序可選擇加工機(jī)器集Mij對(duì)應(yīng)的機(jī)器緊前工序完工時(shí)間tMP分別與該工件緊前工序完工時(shí)間tJP[i]進(jìn)行比較,較大的為工序在對(duì)應(yīng)機(jī)器上開始時(shí)間,開始時(shí)間加上機(jī)器的加工時(shí)間為工序在機(jī)器上的完工時(shí)間;選擇完工時(shí)間最短的機(jī)器m作為當(dāng)前工序的加工機(jī)器;若最小完工時(shí)間不唯一,則在完工時(shí)間最小的機(jī)器中任選,然后按照編碼方式,記錄在染色體相應(yīng)位置。

(4) 將工序Oij完工時(shí)間作為被選擇機(jī)器m的緊前工序完工時(shí)間更新到tMP[m]上,作為對(duì)應(yīng)工件i的緊前完工時(shí)間更新到tJP[m]上。

(5) 循環(huán)執(zhí)行步驟(3)～步驟(4),直到按工序排序順序?yàn)樗泄ば蜻x擇加工機(jī)器。

貪婪初始化的流程如圖2所示。

圖2 貪婪初始化流程

2.3 遺傳算子

2.3.1 選擇算子

本文采用輪盤賭選擇策略比較個(gè)體的適應(yīng)度值,選擇適應(yīng)度值較小的個(gè)體作為交叉的對(duì)象,淘汰適應(yīng)度值低的個(gè)體。為了保留高質(zhì)量的解,提高收斂速度,在選擇操作中引入精英保留策略。考慮到保留的解的多樣性,在進(jìn)行選擇操作前,進(jìn)行種群多樣性篩選及初始化種群替換,將種群按照適應(yīng)度值從低到高進(jìn)行排序,按順序選擇第1個(gè)個(gè)體,將該個(gè)體機(jī)器選擇部分染色體每個(gè)基因位上的值與其他個(gè)體進(jìn)行比較,篩選出種群中機(jī)器部分染色體與其相同的個(gè)體,重復(fù)以上步驟按順序遍歷種群中所有個(gè)體,最后,采用初始化方法生成新的解對(duì)篩選出的個(gè)體進(jìn)行替換。

2.3.2 交叉算子

交叉操作是通過(guò)重組基因段產(chǎn)生新個(gè)體的。本文染色體編碼由2個(gè)部分組成,根據(jù)柔性作業(yè)車間調(diào)度問(wèn)題的特點(diǎn)對(duì)2段編碼采用不同的交叉方式。

工序排序染色體采用基于工序順序的交叉(precedence operation crossover,POX)能夠生成有效解,并繼承父代的優(yōu)良基因。在該操作中,將工件分為工件集1和工件集2,選取父代P1、P2并將P1、P2中工件集1的基因分別復(fù)制到C1、C2中的相同位置,然后將P1、P2中工件集2的基因分別按P1、P2中的順序依次填充到C1、C2中空余的基因位上,得到2個(gè)子代染色體C1、C2。

機(jī)器選擇染色體采用多點(diǎn)交叉,該操作為隨機(jī)生成一條與機(jī)器染色體長(zhǎng)度相同的基因?yàn)?、1的染色體C,選取父代P1、P2保留父代染色體與染色體C基因?yàn)?的位置相同的基因,交換父代與染色體C基因?yàn)?的位置相同的基因,得到2個(gè)子代染色體C1、C2。

2.3.3 變異算子

變異操作能維持種群多樣性,對(duì)2段編碼采用不同的變異方式。

工序排序染色體采用位置變異,選取父代P,隨機(jī)生成一條與工序染色體長(zhǎng)度l相同的的染色體a,其基因?yàn)?0,1)之間的實(shí)數(shù)。若a(i)

機(jī)器選擇染色體采用單點(diǎn)變異,選取父代P,隨機(jī)生成一條與工序染色體長(zhǎng)度l相同的的染色體a,其基因?yàn)?0,1)之間的實(shí)數(shù)。若a(i)

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法的可行性和有效性,本文選取文獻(xiàn)[7]提出的柔性作業(yè)車間調(diào)度3個(gè)基準(zhǔn)實(shí)例(8×8、10×10和15×10)進(jìn)行求解,利用Matlab R2016b實(shí)現(xiàn)上述算法,并與文獻(xiàn)[12]提出的改進(jìn)人工蜂群算法(artificial bee colony,ABC)、文獻(xiàn)[13]提出的改進(jìn)遺傳退火算法(enhanced genetic and simulated annealing,EGSA)、文獻(xiàn)[14]提出的混合蜂群算法和文獻(xiàn)[15]提出的結(jié)合DBR理論與改進(jìn)遺傳算法的DBRGA算法等對(duì)相同算例計(jì)算的結(jié)果進(jìn)行比較。比較結(jié)果見表2所列。其中：Cmax為文獻(xiàn)中求得的最大完工時(shí)間的最優(yōu)結(jié)果;Aver為運(yùn)行10次結(jié)果的平均值。

表2 文獻(xiàn)[7]算例優(yōu)化結(jié)果的對(duì)比

由表2可知：對(duì)于Cmax,本文提出的改進(jìn)遺傳算法與其他4個(gè)文獻(xiàn)算法求解8×8、10×10、15×10問(wèn)題都取得了的最優(yōu)結(jié)果;對(duì)于Aver,本文算法求解3個(gè)問(wèn)題的Aver比文獻(xiàn)[12]和文獻(xiàn)[13]算法求解的結(jié)果更優(yōu),本文算法求解的穩(wěn)定性較好;對(duì)于CPU時(shí)間,本文算法3個(gè)問(wèn)題運(yùn)行的CPU時(shí)間比文獻(xiàn)[13]、文獻(xiàn)[14]和文獻(xiàn)[15]算法給出了CPU運(yùn)行時(shí)間短,本文改進(jìn)算法在計(jì)算速度上更快。

測(cè)試本文中提出的改進(jìn)遺傳算法規(guī)避局部最優(yōu)的有效性。將本文算法與采用隨機(jī)產(chǎn)生和文獻(xiàn)[8]初始化方法的傳統(tǒng)遺傳算法進(jìn)行對(duì)比,8×8、10×10和15×10問(wèn)題迭代200次的收斂對(duì)比圖如圖3所示。其中：方法1為隨機(jī)初始化的遺傳算法;方法2為采用文獻(xiàn)[8]初始化方法的遺傳算法;方法3為本文提出的采用貪婪初始化的改進(jìn)遺傳算法。

(a) 8×8問(wèn)題

(b) 10×10問(wèn)題

(c) 15×10問(wèn)題圖3 8×8、10×10和15×10問(wèn)題的收斂對(duì)比結(jié)果

采用方法1與方法2求解3個(gè)問(wèn)題，經(jīng)過(guò)200次迭代運(yùn)算后未求得全局最優(yōu)解,算法陷入局部最優(yōu),而方法3能很快地跳出局部最優(yōu)求得全局最優(yōu)解。結(jié)果表明,本文提出的改進(jìn)遺傳算法可以有效地規(guī)避局部最優(yōu)。

4 結(jié) 論

作業(yè)調(diào)度是生產(chǎn)計(jì)劃實(shí)施過(guò)程中的重要環(huán)節(jié),本文以最小化最大完工時(shí)間為目標(biāo),提出一種貪婪初始種群的遺傳算法對(duì)柔性作業(yè)車間調(diào)度問(wèn)題進(jìn)行求解。采用了貪婪算法初始化,提高種群初始解的質(zhì)量;設(shè)計(jì)了一種結(jié)合種群多樣性篩選及初始化種群替換的選擇操作,有效地規(guī)避算法陷入局部最優(yōu);最后使用Matlab工具實(shí)現(xiàn)本文算法對(duì)文獻(xiàn)[7]基準(zhǔn)實(shí)例的求解,并將所得的結(jié)果與其他文獻(xiàn)的優(yōu)化結(jié)果進(jìn)行比較。結(jié)果表明,本文算法在求解柔性作業(yè)車間調(diào)度問(wèn)題上穩(wěn)定性高、收斂速度快,算法是可行的和有效的。