文/顧蕾

1 引言

目前，制造業(yè)雖然發(fā)展快速，但是很多制造業(yè)企業(yè)的生產(chǎn)車(chē)間還是在使用以人的經(jīng)驗(yàn)為主的生產(chǎn)調(diào)度方式。生產(chǎn)一線(xiàn)工人主要依靠自己日積月累的經(jīng)驗(yàn)來(lái)進(jìn)度產(chǎn)品生產(chǎn)的調(diào)度，在這種模式下很難實(shí)現(xiàn)生產(chǎn)的標(biāo)準(zhǔn)化，很容易產(chǎn)生生產(chǎn)設(shè)備使用不均衡、浪費(fèi)時(shí)間等問(wèn)題。這一系列文體的產(chǎn)生無(wú)形之中推動(dòng)了生產(chǎn)方式的創(chuàng)新，科學(xué)合理的基于人工智能化的生產(chǎn)調(diào)度方式由此產(chǎn)生。靜態(tài)流水車(chē)間是在開(kāi)始調(diào)度之前全部工件就已經(jīng)做好即將加工的準(zhǔn)備，假設(shè)不會(huì)發(fā)生突發(fā)故障，開(kāi)始加工后工件像流水一樣流入流出。在這種車(chē)間模式下所有的工件加工步驟都是一樣的。

Johnson[1]最先解決了兩臺(tái)機(jī)床的flowshop調(diào)度問(wèn)題，從此專(zhuān)家學(xué)者么開(kāi)始了對(duì)于不同類(lèi)型車(chē)間的調(diào)度問(wèn)題的研究。在此之前的生產(chǎn)調(diào)度問(wèn)題的解決全是依靠工人們積累的經(jīng)驗(yàn)來(lái)解決的，后來(lái)人們開(kāi)始使用運(yùn)籌學(xué)、線(xiàn)性規(guī)劃、拉格朗日松弛、分支定界法等應(yīng)用數(shù)學(xué)的方法來(lái)解決生產(chǎn)調(diào)度問(wèn)題。再后來(lái)人們開(kāi)始引入算法，依靠智能算法去解決生產(chǎn)中的調(diào)度問(wèn)題，例如啟發(fā)式算法，Rajendran和Ziegler[2],Wang等[3]就依靠啟發(fā)式算法解決了某些類(lèi)型車(chē)間的調(diào)度問(wèn)題。當(dāng)前情況下，相對(duì)來(lái)說(shuō)由Framinan和Leiste[4]給出的一種構(gòu)造型啟發(fā)式算法，算是最優(yōu)的啟發(fā)式算法。最近時(shí)間，人們對(duì)于遺傳算法的研究越來(lái)越深入，更多的學(xué)者開(kāi)始選擇使用遺傳算法來(lái)解決各種類(lèi)型車(chē)間的調(diào)度問(wèn)題[5-7]。但是標(biāo)準(zhǔn)的遺傳算法本身就存在一定的缺陷，例如容易出現(xiàn)早熟或者容易陷入局部最優(yōu)。這些缺點(diǎn)如果在算法實(shí)際執(zhí)行之前不解決的化，就會(huì)帶入到實(shí)際的應(yīng)用當(dāng)中，那么我們得出的所謂的最優(yōu)解很有可能并不是最優(yōu)解。本文針對(duì)GA的這些缺陷，對(duì)標(biāo)準(zhǔn)GA進(jìn)行交叉和變異上的改進(jìn)，提出一種改進(jìn)遺傳算法對(duì)靜態(tài)流水車(chē)間進(jìn)行求解，并驗(yàn)證改進(jìn)后的結(jié)果更優(yōu)。

2 問(wèn)題描述

靜態(tài)流水車(chē)間調(diào)度問(wèn)題研究就是在調(diào)度之前就做好準(zhǔn)備的n個(gè)工件逐個(gè)流入m臺(tái)機(jī)器中（假設(shè)機(jī)器不會(huì)發(fā)生故障），工件排成一隊(duì)在m臺(tái)機(jī)器上一次性流過(guò)，一臺(tái)機(jī)器一次只能加工一個(gè)工件，每個(gè)步驟的準(zhǔn)備時(shí)間和加工時(shí)間已知，求解此類(lèi)型車(chē)間最優(yōu)的調(diào)度方案。

3 求解靜態(tài)流水車(chē)間調(diào)度的改進(jìn)GA算法

3.1 求解思想

當(dāng)要解決實(shí)際生產(chǎn)當(dāng)中的問(wèn)題的時(shí)候，選取的算法的效率是否能滿(mǎn)足需求是解決問(wèn)題的關(guān)鍵。首先要做的就是選取具體的參數(shù)合集，然后通過(guò)使用GA算法去尋找此參數(shù)合集當(dāng)中的最優(yōu)解。我們?cè)谶x取參數(shù)的時(shí)候主要關(guān)注群體的規(guī)模、交叉率和變異率這幾項(xiàng)指標(biāo)。當(dāng)我們選取求解的參數(shù)不同時(shí)，GA算法的性能也會(huì)受到不同的影響，求解的結(jié)果也會(huì)不相同。綜上所述，要想體現(xiàn)GA算法的最優(yōu)性能，最先要做的就是選取合適的參數(shù)集。

當(dāng)通過(guò)算法去進(jìn)行問(wèn)題的優(yōu)化的過(guò)程中，如何去選擇合適的Pc和Pm，這是是需要不斷地試驗(yàn)反復(fù)的嘗試才能夠確認(rèn)的，這是一個(gè)相當(dāng)復(fù)雜繁瑣的過(guò)程，需要不斷地嘗試，嘗試過(guò)后確定最佳的Pc和Pm。

在改進(jìn)的CA算法中，要求Pc和Pm的值不是固定的，而是要隨著個(gè)體適應(yīng)度的變化二變化的。當(dāng)種群在進(jìn)行搜索的時(shí)候出現(xiàn)個(gè)體適應(yīng)度越來(lái)越靠近或出現(xiàn)局部最優(yōu)的時(shí)候，Pc和Pm的值會(huì)自動(dòng)增加，使種群的適應(yīng)度趨于分散然后跳出局部最優(yōu)的困境。當(dāng)種群在進(jìn)行搜索的時(shí)候出現(xiàn)個(gè)體適應(yīng)度越來(lái)越分散的時(shí)候，Pc和Pm的值會(huì)反方向變動(dòng)，通過(guò)減小概率來(lái)保證優(yōu)良的個(gè)體能夠不被淘汰。在交叉和變異的過(guò)程中，如果個(gè)體適應(yīng)度高于群體平均水平，Pc和Pm的值自動(dòng)降低，保證此個(gè)體能維持高適應(yīng)度然后進(jìn)入到下一代；如果個(gè)體適應(yīng)度低于群體平均水平， Pc和Pm的值自動(dòng)升高，使該個(gè)體在交叉或者變異的過(guò)程中被淘汰[8]。所以Pc和Pm在改進(jìn)后的GA算法當(dāng)中并不是固定的數(shù)值，而是隨著適應(yīng)度的變化而改變的。

3.2 求解步驟

3.2.1 編碼

該編碼方式選取以工件在機(jī)器上的加工順序來(lái)進(jìn)行編碼，即n道工序的編碼長(zhǎng)度就為n，基因數(shù)為n-1，以10道工序編碼為例，隨機(jī)產(chǎn)生一組編碼：σ7，σ6，σ8，σ10，σ9，σ4，σ3，σ5，σ2，σ1，該編碼用集合來(lái)表示：

T(ji,k)表示工件σi在機(jī)器k上的加工所需時(shí)間， n個(gè)工件在m臺(tái)機(jī)器上的加工所需要的時(shí)間為：

最大完成時(shí)間為：

求的是{σ1，σ2,…,σn}，使得Tmax的值最小，即求最小化最大完成時(shí)間。

3.2.2 生成初始種群

隨機(jī)生成初始種群，然后取適應(yīng)度高的個(gè)體，把它們放入隨機(jī)種群當(dāng)中，然后在隨機(jī)產(chǎn)生個(gè)體，如此反復(fù)進(jìn)行下去，直到達(dá)到需要的種群數(shù)后跳出循環(huán)。

3.2.3 個(gè)體適應(yīng)度函數(shù)

求解的目標(biāo)函數(shù)為適應(yīng)度函數(shù)，Ckmax為最大完成時(shí)間函數(shù)，表示第k個(gè)染色體的最大加工完成時(shí)間。用此公式來(lái)計(jì)算單個(gè)染色體的適應(yīng)度。適應(yīng)度函數(shù)為：

3.2.4 GA算子的設(shè)計(jì)

（1）選擇。錦標(biāo)賽選擇法：

每一輪里選擇一個(gè)選項(xiàng)后，在之前的選擇中再進(jìn)行選擇。通常最后的選擇就是錦標(biāo)賽的“獲勝者”。選取n個(gè)個(gè)體，個(gè)體i的適應(yīng)度用Fi表示，此時(shí)個(gè)體i可能被選中遺傳到下一代的概率為：

（2）交叉。

1.隨機(jī)選擇父本個(gè)體兩個(gè)；

2.隨機(jī)生成兩個(gè)自然數(shù)r1和r2，r1＜r2；

3.將r1至r2之間的片段互換位置，得到兩個(gè)新的子代，然后得到的兩個(gè)子代進(jìn)行修補(bǔ)，使其存在沖突

例如：取父本基因片段為[d,c,a,b,e][e,c,b,d,a]；r1=2,r2=4；

進(jìn)行交叉得到：[a,c,b,d,e][e,c,a,b,a]；

進(jìn)行修補(bǔ)后得到：[a,c,b,d,e][e,c,a,b,d]；

（3）變異。

1.隨機(jī)選擇父本個(gè)體兩個(gè)r1，r2

[a,c,b,d,e][e,c,a,b,d]；

2.逆轉(zhuǎn)變異

隨機(jī)從染色體中截一段基因，接著把該片段反序置換，然后插回?cái)嗔烟帯?/p>

例如：r1=2,r2=4；那么染色體的變異為[a,d,b,c,e][e,b,a,c,d]

3.3 算法實(shí)現(xiàn)

采用國(guó)際標(biāo)準(zhǔn)算例15×15來(lái)進(jìn)行標(biāo)準(zhǔn)GA算法和改進(jìn)GA算法的比較。

3.3.1 標(biāo)準(zhǔn)GA算法

例：種群數(shù)M=100，迭代次數(shù)T=150，代溝GGAP=1，交叉率Pc=0.3，變異率Pm=0.2；工件數(shù)n=15，工序數(shù)m=15。

3.3.2 改進(jìn)GA算法

例：種群數(shù)M=100，迭代次數(shù)T=150，代溝GGAP=1，交叉率Pc1=0.3，Pc2=0.5；變異率Pm1=0.1，Pm2=0.3；工件數(shù)n=15，工序數(shù)m=15。

3.4 結(jié)果比較

3.4.1 最優(yōu)工序發(fā)生變化

標(biāo)準(zhǔn)遺傳算法：

改進(jìn)遺傳算法：

3.4.2 最小最大時(shí)間改變

根據(jù)結(jié)果可知在40代時(shí)就已經(jīng)取得了最優(yōu)，出現(xiàn)早熟現(xiàn)象，對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jìn)從迭代曲線(xiàn)可以看出標(biāo)準(zhǔn)遺傳算法在迭代到40代的時(shí)候就達(dá)到了最優(yōu)，出現(xiàn)過(guò)早收斂現(xiàn)象，而改進(jìn)后的迭代結(jié)果現(xiàn)實(shí)在60代以后才開(kāi)始出現(xiàn)收斂，同時(shí)求解最小最大完成時(shí)間得出后者時(shí)間更短。

4 結(jié)論

本文從靜態(tài)流水車(chē)間著手解決其調(diào)度問(wèn)題，采用GA算法求解后發(fā)現(xiàn)出現(xiàn)早市現(xiàn)象，于是進(jìn)行算法改進(jìn)，引入可自我調(diào)節(jié)的交叉率和變異率，改進(jìn)后的GA算法，經(jīng)過(guò)標(biāo)準(zhǔn)算例認(rèn)證，明顯優(yōu)于標(biāo)準(zhǔn)GA算法得出的結(jié)果，改進(jìn)后的GA算法解決了標(biāo)準(zhǔn)GA算法出現(xiàn)過(guò)早收斂的問(wèn)題，從而達(dá)到要求的優(yōu)化效果，對(duì)于靜態(tài)流水車(chē)間的調(diào)度優(yōu)化提供了更多一種方法。