混合遺傳算法求解車間作業(yè)調(diào)度問題

周海峰

（江蘇廣播電視大學(xué)，江蘇 南京 210017）

混合遺傳算法求解車間作業(yè)調(diào)度問題

周海峰

（江蘇廣播電視大學(xué)，江蘇 南京 210017）

所謂生產(chǎn)調(diào)度問題，其實(shí)質(zhì)如何分配資源使其更優(yōu)化.這里我們所講的資源指的是車間生產(chǎn)所需的設(shè)備資源.對(duì)車間生產(chǎn)作業(yè)調(diào)度問題進(jìn)行求解，其目的就是要找出一個(gè)能夠?qū)⒁唤M工件更為科學(xué)、合理的安排到機(jī)器上從而實(shí)現(xiàn)最優(yōu)化的生產(chǎn)作業(yè)方案.本文采用一種啟發(fā)式算法和遺傳算法相結(jié)合的混合遺傳算法，在運(yùn)用過程中給出其應(yīng)用方法.

啟發(fā)式算法；遺傳算法；車間作業(yè)調(diào)度

1 生產(chǎn)調(diào)度問題

調(diào)度就是指對(duì)共同使用的資源進(jìn)行統(tǒng)一的時(shí)間分配，其作用是為了實(shí)現(xiàn)某一目的.而本文所提出的車間作業(yè)生產(chǎn)調(diào)度，則是指利用一組機(jī)床在加工一組零件時(shí)，對(duì)每臺(tái)車床加工工件的順序進(jìn)行合理的安排，實(shí)現(xiàn)諸如總加工時(shí)長(zhǎng)、總加工成本或相對(duì)加工時(shí)長(zhǎng)等指標(biāo)的最優(yōu)化.通常若干不同工序組成了零件的整個(gè)加工過程，并且該過程要滿足對(duì)應(yīng)的約束關(guān)系.在車間作業(yè)調(diào)度過程中，約束條件的內(nèi)容與數(shù)量會(huì)隨著作業(yè)環(huán)境及作業(yè)要求的變化而變化，比如加工設(shè)備條件或者零件的加工工藝要求等等.

本文定義n個(gè)工件的集合為：P={P1,P2,…,Pn}；而m臺(tái)加工車床的集合則為：M={M1,M2,…,Mm}；工件Pi加工工序數(shù)目定義為Ki；則其加工工序定義為：Pi1(Ji1),Pi2(Ji2),…,PiKi(JiKi)(Ki∈Z+,i=1,2,…,n)這其中Z+為正整數(shù)，零件Pi在進(jìn)行第Ki道工序表示為JiKi，（JiKi∈M）；而被加工零件經(jīng)過第Ki道工序加工的開始時(shí)間表示為STiKi；被加工零件Pi在進(jìn)行第Ki道工序的加工的結(jié)束時(shí)間表示為ETiKi；TiKi為工件Pi加工第Ki道工序的時(shí)間.按照上文所述的定義，則車間作業(yè)調(diào)度的約束條件為以下幾個(gè)：第一，每個(gè)工序中均包含一個(gè)工序集合，該工序集合由多道工序組合而成，且要預(yù)先給定工件加工工序的順序；第二，某臺(tái)機(jī)器同時(shí)只可以加工一個(gè)零件的其中一道工序；再次，加工零件不一樣，其各工序間不存在先后的約束條件，工件相同，其工序需符合前后的約束關(guān)系；第四，工序PiKi(JiKi)和PiKi+1(JiKi+1)，二者的時(shí)間相距為零，即STiK-i+1-ETiKi=0；第五，每個(gè)零件在進(jìn)行每道工序加工時(shí)，其開始時(shí)間要大于等于零，即STiKi+1-ETiKi=0；第五，每個(gè)工件每道加工工序的開工時(shí)間必須大于或者等于零，即STiKi≥0；第六，所有的要件要在預(yù)定交期前全部完工，設(shè)Ti為加工工件Pi的總時(shí)間，即∑TiKi=Ti.

2 混合遺傳算法

本文所提出的混合遺傳算法的應(yīng)用為：將啟發(fā)式算法融入遺傳算法中，再利用該混合算法求解車間生產(chǎn)調(diào)度排序的問題.遺傳算法為一種群體優(yōu)化算法，其通過選擇和變異及交叉等不同操作，不斷的進(jìn)化解集性能，從而可以使搜索的速度得到進(jìn)一步提高.不過遺傳算法也存在不足，即難以控制早熟及收斂性等問題.作為傳統(tǒng)的啟發(fā)式算法，有著搜索速度快且結(jié)構(gòu)簡(jiǎn)單的優(yōu)點(diǎn)，但是其也存在搜索能力差且容易陷入局部最優(yōu)等不足.基于二者的優(yōu)勢(shì)與不足，將其進(jìn)行結(jié)合，將啟發(fā)式算法融入遺傳算法中，重新構(gòu)造出的混合遺傳算法能力更強(qiáng)，對(duì)于求解比較復(fù)雜的優(yōu)化問題有著積極的意義.該混合方法融合了遺傳算法的記憶功能和并行性，并將其與啟發(fā)式算法的快速搜索優(yōu)勢(shì)相結(jié)合，使得求解質(zhì)量得到了進(jìn)一步的提高.具體來講對(duì)遺傳算法進(jìn)行改進(jìn)的方法主要為以下幾點(diǎn)：第一，將啟發(fā)式嵌入初始化中，產(chǎn)生一個(gè)初始解群，且該初始解群要具備良好的適應(yīng)性能，這種方法可以使混合遺傳算法優(yōu)于啟發(fā)式算法；第二，把啟發(fā)式融入評(píng)估函數(shù)中，將染色體進(jìn)行解碼轉(zhuǎn)換為生產(chǎn)調(diào)度；第三，對(duì)個(gè)體變異及交叉率進(jìn)行自適應(yīng)設(shè)計(jì).上述幾點(diǎn)中，在進(jìn)行個(gè)體中全局搜索時(shí)主要采用遺傳算法；而對(duì)染色體部分搜索則利用啟發(fā)式算法.由于啟發(fā)式與遺傳算法二者存在相應(yīng)的互補(bǔ)性，所以二者相混合的算法更優(yōu)于兩種單獨(dú)算法.

3 利用混合遺傳算法進(jìn)行車間作業(yè)調(diào)度的求解

3.1 參數(shù)編碼

在進(jìn)行遺傳算法的求解過程中，要將問題所在空間的相關(guān)參數(shù)轉(zhuǎn)化為遺傳空間的參數(shù)，還要經(jīng)過基因依據(jù)所對(duì)應(yīng)的結(jié)構(gòu)組成染色體，這個(gè)將問題空間參數(shù)向著遺傳空間參數(shù)轉(zhuǎn)化的過程可以稱之為編碼.編碼的表達(dá)方法有很多，有基于工序的、基于工件的或者基于位置列表的以及基于機(jī)床的表達(dá)等等，本文所采用的是基于機(jī)床的表達(dá)方法.將染色體進(jìn)行編碼為設(shè)備序列，以該序列為基碼，編碼的具體實(shí)現(xiàn)為：

工件編號(hào)為1,2,3,…n；各工件的對(duì)應(yīng)的工序編號(hào)為1,2,3,…k；對(duì)應(yīng)的機(jī)床編號(hào)為1,2,3,…m.從而符號(hào)1.1.1則代表工件1的1工序在機(jī)床1上完成，以3（工件）×3（機(jī)床）為例：假如工件的加工工序最多為4，機(jī)床所對(duì)應(yīng)不存在的加工工序則定義為0.0.0，工件的各加工工序要能滿足工序先后關(guān)系的約束.

3.2 生成初始種群與設(shè)計(jì)適應(yīng)度函數(shù)

可以通過隨機(jī)產(chǎn)生的方法來產(chǎn)生初始種群，以便于達(dá)到解空間所有狀態(tài)的遍歷.對(duì)約束條件進(jìn)行檢驗(yàn)，判斷其是否為可行解，假如判斷結(jié)果為是，則將其加入初始種群，如果不是則淘汰.不過由于初始群體為隨機(jī)產(chǎn)生，因此進(jìn)化的代數(shù)有所加大，從而遺傳算法的計(jì)算時(shí)間也相應(yīng)大幅度增加.此處加入啟發(fā)式算法，將該算法局部搜索能力強(qiáng)的特點(diǎn)加以充分利用，從而優(yōu)良個(gè)體產(chǎn)生的速度就有所提高.個(gè)體適應(yīng)函數(shù)應(yīng)為工件總加工時(shí)間單調(diào)遞減函數(shù)，即個(gè)體適應(yīng)度的函數(shù)值隨著總工時(shí)的減小而增加，反之總工時(shí)越大，則個(gè)體適應(yīng)度的函數(shù)值就越小.個(gè)體i的適應(yīng)函數(shù)值可以進(jìn)行以下定義：

上式中：Cmax是f(x)的最大值估計(jì).

3.3 交叉操作

交叉算子利用一點(diǎn)交叉運(yùn)算，參與交叉運(yùn)算的包括兩個(gè)個(gè)體母體M與父體F，按照自適應(yīng)交叉概率Pc進(jìn)行相應(yīng)的交叉運(yùn)算.記交叉運(yùn)算兩個(gè)體體母體M及父體F，其經(jīng)過交叉運(yùn)算所產(chǎn)生的子代個(gè)體記為D與S，L是染色體的長(zhǎng)度.整數(shù)p為隨機(jī)生產(chǎn)，且1

上式中：fmax：群體最大適應(yīng)度值

favg：每代群體平均適應(yīng)度值

f：要交叉的兩個(gè)個(gè)體比較大的適應(yīng)度值.

算法的收斂程度和自適應(yīng)調(diào)整為反向關(guān)系，因此防止算法收斂于局部最優(yōu)十分有效，并且可以保存更優(yōu)的進(jìn)化結(jié)果.

3.4 變異操作

利用互換變異進(jìn)行變異操作，即整數(shù)m先隨機(jī)生成，其取值范圍為機(jī)床的數(shù)量.在該機(jī)器中隨機(jī)選擇某一工序，將該工序和相臨的工序進(jìn)行互換.需要注意的是，在變異時(shí)要看相臨的工序是否為加工同一工件.其自適應(yīng)變異概率Pm進(jìn)行如下定義：

3.5 目標(biāo)函數(shù)

本文求解的目標(biāo)為工件完工時(shí)間的最小化，其目標(biāo)函數(shù)為：

其中 i=（1，2…n）

4 結(jié)論

生產(chǎn)調(diào)度問題為NP問題，即可用多項(xiàng)式時(shí)間算法對(duì)其猜測(cè)準(zhǔn)確性加以驗(yàn)證，因此最優(yōu)解確定算法相對(duì)較難確定.而且遺傳算法又具體備相應(yīng)的優(yōu)良特性，因此在車間生產(chǎn)調(diào)度問題方面，遺傳算法為后續(xù)的研究趨勢(shì).本文所提出將啟發(fā)式規(guī)則融入遺傳算法的混合遺傳算法，在進(jìn)行調(diào)度算法的求解過程中，即可以發(fā)揮遺傳算法的長(zhǎng)處，又可以充分利用啟發(fā)式算法快速搜索的特點(diǎn)，從而取得了更優(yōu)的分配效果，且通過實(shí)例可以證明，該方法所求解的調(diào)度結(jié)果相對(duì)較優(yōu).

〔1〕(日)玄光男,程潤(rùn)偉.遺傳算法與工程設(shè)計(jì)[M].北京:科學(xué)出版社,2007.

〔2〕鞠全勇,朱劍英.基于混合遺傳算法的動(dòng)態(tài)車間調(diào)度系統(tǒng)的研究[J].中國(guó)機(jī)械工程,2009(11).

〔3〕祁建程,楊建剛.并行混合遺傳算法在車間調(diào)度問題的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,2011(1).

〔4〕丁書斌,李啟堂,徐繼濤，等.混合遺傳算法求解經(jīng)典作業(yè)車間調(diào)度問題[J].煤礦機(jī)械,2007(1).

〔5〕楊開兵.多目標(biāo)混合遺傳算法求解流水車間調(diào)度問題[J].電腦與信息技術(shù),2008(6).

〔6〕張華,陶澤.基于混合遺傳算法的車間調(diào)度問題的研究[J].機(jī)械設(shè)計(jì)與制造,2005(3).

TP18

A

1673-260X（2011）09-0018-02