解并行機(jī)模糊調(diào)度問(wèn)題的自適應(yīng)遺傳算法

劉文程，高家全

解并行機(jī)模糊調(diào)度問(wèn)題的自適應(yīng)遺傳算法

劉文程，高家全

針對(duì)家紡企業(yè)車(chē)間調(diào)度的實(shí)際情況，建立了一種產(chǎn)品優(yōu)先級(jí)約束的模糊車(chē)間調(diào)度模型。在模型中，完工時(shí)間和交貨期都是模糊的，交貨期平均滿(mǎn)意度最大為調(diào)度目標(biāo)。基于此模型，提出了一種自適應(yīng)的遺傳算法，該算法通過(guò)比例選擇及局部搜索保證種群的優(yōu)良特性，并通過(guò)自動(dòng)調(diào)節(jié)變異率和交叉率的方式保證種群的多樣性，有效跳出局部收斂。仿真結(jié)果表明，自適應(yīng)遺傳算法能有效求解，并優(yōu)于免疫遺傳算法。

并行機(jī)；模糊加工時(shí)間；模糊交貨期；模糊調(diào)度；遺傳算法

1 引言

家紡企業(yè)作為傳統(tǒng)的制造企業(yè)，在我國(guó)的制造業(yè)中具有舉足輕重的地位?，F(xiàn)有的一些研究成果主要集中在對(duì)家紡企業(yè)確定性車(chē)間生產(chǎn)調(diào)度問(wèn)題上[1-2]，但在家紡企業(yè)實(shí)際的生產(chǎn)過(guò)程中，不僅有確定性生產(chǎn)調(diào)度問(wèn)題，還具有不確定性生產(chǎn)調(diào)度問(wèn)題。不確定性的生產(chǎn)調(diào)度問(wèn)題一方面是由家紡企業(yè)特殊的性能造成的，比如原料的不同特性，操作工人熟練度的差異，機(jī)器設(shè)備不同程度老化等，這都將影響產(chǎn)品的加工進(jìn)度，并使得加工時(shí)間變得不確定；另一方面是由于同一批次的產(chǎn)品可能來(lái)自不同的訂單，不同的訂單的交貨期一般而言是不一樣的，這就將使得產(chǎn)品的交貨期不同。

現(xiàn)階段，在車(chē)間調(diào)度領(lǐng)域針對(duì)不確定的生產(chǎn)調(diào)度問(wèn)題的研究，已有一些研究成果[3-12]。這些研究一般針對(duì)模糊車(chē)間調(diào)度問(wèn)題，大部分是對(duì)模糊的加工時(shí)間或模糊的交貨期這種單一情況下的作業(yè)車(chē)間的模糊調(diào)度問(wèn)題進(jìn)行研究。盡管也有部分學(xué)者對(duì)模糊加工時(shí)間和模糊交貨期這種較為復(fù)雜的情況進(jìn)行研究，但是他們對(duì)滿(mǎn)意度函數(shù)的考慮存在一定的偏差，沒(méi)有考慮到對(duì)于企業(yè)而言，不同客戶(hù)的重要程度是不相同的，這樣將使得調(diào)度結(jié)果不合理。從而使得家紡企業(yè)的生產(chǎn)調(diào)度問(wèn)題無(wú)法應(yīng)用已有的研究成果，需要專(zhuān)門(mén)針對(duì)其生產(chǎn)特點(diǎn)進(jìn)行研究。

本文根據(jù)家紡企業(yè)在實(shí)際生產(chǎn)調(diào)度過(guò)程中所具有的特點(diǎn)，分別對(duì)加工時(shí)間和交貨期進(jìn)行模糊化處理，在此基礎(chǔ)上建立模糊化的生產(chǎn)調(diào)度模型，并提出一種改進(jìn)的自適應(yīng)遺傳算法。該算法能夠通過(guò)調(diào)整變異率和交叉的方式保證種群的多樣性，并能夠有效跳出局部收斂；仿真結(jié)果證實(shí)了該算法的有效性和可靠性。

2 模糊生產(chǎn)調(diào)度模型

2.1 問(wèn)題描述

家紡企業(yè)的模糊生產(chǎn)調(diào)度模型一般可以簡(jiǎn)單描述為：數(shù)量為n的產(chǎn)品在m臺(tái)機(jī)器上分別進(jìn)行加工，產(chǎn)品分別來(lái)自不相同的訂單，訂單來(lái)自不同的客戶(hù)，因此具有不同的優(yōu)先級(jí)。每個(gè)產(chǎn)品都具有模糊的加工時(shí)間及與客戶(hù)滿(mǎn)意度相關(guān)聯(lián)的模糊交貨期，產(chǎn)品的加工操作必須滿(mǎn)足一定的工藝約束，即不是所有的產(chǎn)品都可以在任何機(jī)器上進(jìn)行加工。每個(gè)產(chǎn)品在進(jìn)行加工時(shí)，只能在一臺(tái)機(jī)器上進(jìn)行一次加工并完成產(chǎn)品的加工操作。產(chǎn)品的加工操作在機(jī)器上開(kāi)始進(jìn)行后，直到產(chǎn)品完成加工之前不能停止產(chǎn)品的加工，中途機(jī)器不能對(duì)其他產(chǎn)品進(jìn)行加工，即機(jī)器同一時(shí)刻只能對(duì)一個(gè)產(chǎn)品進(jìn)行加工操作。家紡企業(yè)調(diào)度的目標(biāo)是尋找一種可行的方案，使得這種方案既能滿(mǎn)足企業(yè)特定的工藝要求，又能使得調(diào)度目標(biāo)獲得最優(yōu)解。

2.2 變量描述

為了方便敘述，引入下面的記號(hào)。

p?ij：模糊加工時(shí)間。即為產(chǎn)品 j在機(jī)器i上的加工時(shí)間，其中包括對(duì)產(chǎn)品配件進(jìn)行裝配的時(shí)間、傳輸產(chǎn)品的時(shí)間、卸載產(chǎn)品時(shí)間、加工產(chǎn)品時(shí)間及對(duì)產(chǎn)品進(jìn)行清洗的時(shí)間等，是在一定區(qū)間變化的模糊變量，用三角模糊數(shù)表示，為加工時(shí)間樂(lè)觀值，為加工時(shí)間可能值，為加工時(shí)間悲觀值。

Ωj：所有能加工產(chǎn)品 j的機(jī)器集合。

c?j：產(chǎn)品 j的模糊完工時(shí)間。這是由產(chǎn)品的加工時(shí)間的模糊性決定的，模糊的加工時(shí)間必然導(dǎo)致模糊的完工時(shí)間。

AI：平均面積滿(mǎn)意度。

t?ij：產(chǎn)品 j在機(jī)器i上的開(kāi)始加工時(shí)間。

λj：產(chǎn)品的優(yōu)先級(jí)系數(shù)。

設(shè)決策變量：

2.3 數(shù)學(xué)模型

平均滿(mǎn)意度最大模型：

圖1 模糊的完工時(shí)間和交貨期滿(mǎn)意度

式（1）是問(wèn)題的目標(biāo)平均滿(mǎn)意度最大；式（2）～（6）是滿(mǎn)足目標(biāo)函數(shù)的約束項(xiàng)，依次分別表示為：產(chǎn)品只能夠在一臺(tái)機(jī)器上進(jìn)行加工；機(jī)器同一時(shí)刻只能加工一個(gè)產(chǎn)品，即只有在完成一個(gè)產(chǎn)品的加工后，才能開(kāi)始下一產(chǎn)品的加工；產(chǎn)品在各機(jī)器上的加工時(shí)間均非負(fù)值；產(chǎn)品在各機(jī)器上的開(kāi)始加工時(shí)間均非負(fù)值；決策變量的取值范圍。

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

根據(jù)家紡企業(yè)的實(shí)際情況，建立了不確定性生產(chǎn)調(diào)度模型，為了對(duì)該模型進(jìn)行求解，設(shè)計(jì)了一種自適應(yīng)性的遺傳算法。算法基本流程如圖2，具體步驟如下：

步驟1將初始種群的規(guī)模設(shè)定為NG，根據(jù)約束條件隨機(jī)產(chǎn)生初始種群。

步驟2根據(jù)采用的適應(yīng)度函數(shù)來(lái)計(jì)算每個(gè)染色體的適應(yīng)度值。

步驟3運(yùn)用比例選擇機(jī)制以及最優(yōu)保存策略對(duì)下一代種群的染色體進(jìn)行選擇。

步驟4讓種群中的染色體兩兩進(jìn)行交叉，交叉率根據(jù)種群的收斂情況進(jìn)行調(diào)整，當(dāng)種群快速收斂時(shí)，適當(dāng)減小交叉率，當(dāng)種群趨于發(fā)散時(shí)，適當(dāng)增大交叉率，通過(guò)控制交叉率來(lái)實(shí)現(xiàn)對(duì)種群收斂速度的控制。

步驟5讓種群中的染色體進(jìn)行變異，變異率同樣根據(jù)種群的收斂情況進(jìn)行調(diào)整，當(dāng)種群快速收斂時(shí)，適當(dāng)提高變異率，當(dāng)種群趨于發(fā)散時(shí)，適當(dāng)減小變異率，通過(guò)控制變異率來(lái)保證種群的多樣性和染色體的優(yōu)良特性。

步驟6局部搜索算法對(duì)種群進(jìn)行優(yōu)化，使種群保持優(yōu)良特性。

步驟7重復(fù)步驟2到步驟6，當(dāng)滿(mǎn)足設(shè)定的終止條件時(shí)停止。

3.1 編碼設(shè)計(jì)及適應(yīng)度函數(shù)

向量組編碼方式解碼簡(jiǎn)單且能方便地執(zhí)行遺傳操作，更具有不會(huì)產(chǎn)生無(wú)效個(gè)體的優(yōu)點(diǎn)，因此本算法采用向量組的編碼方式進(jìn)行編碼。

適應(yīng)度函數(shù)是作為一種標(biāo)準(zhǔn)用來(lái)區(qū)分種群中染色體優(yōu)劣的，一般通過(guò)變換原適應(yīng)度間的比例關(guān)系來(lái)調(diào)節(jié)適應(yīng)度值。對(duì)于2.3節(jié)中模型的目標(biāo)函數(shù)，這里采用的適應(yīng)度函數(shù)為：

由式（7）可知，分母是固定的值，因此分子越大，則適應(yīng)度的值越大。

圖2 自適應(yīng)遺傳算法流程圖

3.2 選擇算子

采用比例機(jī)制選擇相應(yīng)個(gè)體，通過(guò)輪盤(pán)賭選擇方法對(duì)正比于個(gè)體適應(yīng)度的概率進(jìn)行計(jì)算。再經(jīng)過(guò)多輪選擇，選出需要進(jìn)行交配的個(gè)體。每一輪選擇時(shí)，首先均勻產(chǎn)生一個(gè)[0，1]的隨機(jī)數(shù)，然后將該隨機(jī)數(shù)作為選擇指針，對(duì)比各個(gè)染色體的相對(duì)適應(yīng)度來(lái)確定被選中的染色體。若種群的大小為N，染色體i的適應(yīng)度值為 fi，那么染色體i被選擇的概率Pf為：

本文算法不僅采用比例機(jī)制，同時(shí)將每代的最優(yōu)染色體進(jìn)行保存。通過(guò)用最優(yōu)的染色體替換掉適應(yīng)度值最低的染色體的方式，來(lái)提升種群的優(yōu)良特性。

3.3 交叉算子

本文算法針對(duì)向量組編碼方法，在部分匹配交叉的基礎(chǔ)上提出了一種隨機(jī)擴(kuò)展交叉算子。具體過(guò)程如下：

（1）產(chǎn)生一個(gè)正整數(shù)n，在染色體長(zhǎng)度的30%～50%之間進(jìn)行隨機(jī)選取。交叉的基因位數(shù)將由正整數(shù)n來(lái)決定，比如n的大小為3，那么染色體中將有三位基因進(jìn)行交叉。

（2）隨機(jī)產(chǎn)生數(shù)量為m的正整數(shù)作為需要交叉的基因點(diǎn)。

（3）假設(shè)需要將染色體A、B進(jìn)行交叉，選取染色體A中的基因放入染色體B中的前面，并刪除染色體B中相同的基因，從而產(chǎn)生基于染色體B的新染色體。同時(shí)，將染色體B中選取的基因放入染色體A中的前面，并刪除染色體A中相同的基因，從而產(chǎn)生基于染色體A的新染色體。

下面通過(guò)舉例說(shuō)明染色體的交叉過(guò)程，假設(shè)需要交叉的染色體A、B分別為：

假設(shè)n=3，隨機(jī)產(chǎn)生的基因位分別為4，8，2，那么經(jīng)過(guò)交叉后獲得的新染色體分別為：

將新染色體中相同的基因位分別進(jìn)行刪除后，便可獲得分別基于染色體A、B的后代染色體：

3.4 變異算子

本文算法的變異方式通過(guò)多點(diǎn)插入的形式來(lái)實(shí)現(xiàn)，這一方式適合向量組編碼的特性。下面對(duì)這一方式進(jìn)行說(shuō)明，先對(duì)要變異的基因位gi進(jìn)行隨機(jī)選擇，再變換gi中第二行的機(jī)器號(hào)，在每次變換機(jī)器后對(duì)染色體的適應(yīng)度值重新計(jì)算并做保留。當(dāng)完成對(duì)所有可選機(jī)器的插入計(jì)算后，選擇出最優(yōu)的染色體作為變異產(chǎn)生的染色體。這種變異方式在保留父代信息的同時(shí)，保證了變異后的染色體的質(zhì)量。

3.5 局部搜索算法

局部搜索算法一方面加快了種群搜索速度，另一方面提高了種群的質(zhì)量，優(yōu)化了算法性能。具體算法步驟如下所示。

對(duì)種群中的每一個(gè)染色體u進(jìn)行如下操作：

（1）對(duì)u進(jìn)行反轉(zhuǎn)變異，將產(chǎn)生的染色體記為u*；

（2）評(píng)價(jià)u和u*；

（3）若u*優(yōu)于u，則u=u*；

（4）若搜索次數(shù)達(dá)到設(shè)定的搜索次數(shù)，則停止搜索，否則重復(fù)（1）～（3）。

3.6 自適應(yīng)技術(shù)

動(dòng)態(tài)自適應(yīng)技術(shù)通過(guò)調(diào)整遺傳算法控制參數(shù)來(lái)控制種群的優(yōu)化，即在種群的進(jìn)化過(guò)程中根據(jù)種群收斂情況對(duì)Pc、Pm的數(shù)值進(jìn)行適當(dāng)調(diào)整。具體做法為：若種群趨于收斂，則在減小Pc的同時(shí)增大Pm，即通過(guò)將交叉的概率降低的同時(shí)將變異的概率提高來(lái)保證種群的多樣性，以避免種群早熟；若種群發(fā)散，在在增大Pc的同時(shí)減小Pm，即通過(guò)將交叉的概率提高的同時(shí)將變異概率降低來(lái)加快算法的收斂速度。

在種群的進(jìn)化過(guò)程中，σ為兩代種群最優(yōu)值的差值，通過(guò)讓交叉概率Pc和變異概率Pm跟隨σ的變換而變化來(lái)達(dá)到對(duì)種群優(yōu)化過(guò)程的控制，使種群的Pc、Pm值能根據(jù)σ動(dòng)態(tài)調(diào)整。數(shù)學(xué)描述如下：

4 仿真及實(shí)驗(yàn)分析

在型號(hào)為華碩X81SG的計(jì)算機(jī)上，操作系統(tǒng)為Windows XP，在C++Builder軟件環(huán)境下采用C++語(yǔ)言對(duì)全部算法進(jìn)行編寫(xiě)。隨機(jī)產(chǎn)生每種產(chǎn)品的機(jī)器集合、對(duì)應(yīng)加工時(shí)間和交貨期，使其滿(mǎn)足均勻分布的要求。

4.1 對(duì)模糊完工時(shí)間仿真

通過(guò)對(duì)產(chǎn)品為15，加工機(jī)器為4的家紡企業(yè)生產(chǎn)調(diào)度問(wèn)題進(jìn)行仿真示例，來(lái)驗(yàn)證本文提出的AGA算法的可行性。表1為算例的具體模糊加工時(shí)間，表中縱排為產(chǎn)品號(hào)，橫排為機(jī)器號(hào)，表格中的三個(gè)數(shù)字分別對(duì)應(yīng)樂(lè)觀值、最可能值和悲觀值。

表1 15工件4機(jī)器模糊加工時(shí)間表

表2為產(chǎn)品模糊交貨期和優(yōu)先級(jí)表。設(shè)定在提前交貨的情況下客戶(hù)的滿(mǎn)意度為1，即只要模糊完工時(shí)間能在模糊交貨期之前，那么不會(huì)對(duì)客戶(hù)的滿(mǎn)意度造成影響。不同優(yōu)先級(jí)的產(chǎn)品所具有的優(yōu)先級(jí)系數(shù)是不相同的，這里設(shè)定優(yōu)先級(jí)為1和優(yōu)先級(jí)為2的產(chǎn)品的優(yōu)先級(jí)系數(shù)分別為1和1.2。

表2 產(chǎn)品模糊交貨期和優(yōu)先級(jí)表

設(shè)置自適應(yīng)遺傳算法的參數(shù)，種群數(shù)量設(shè)為50，局部搜索交換次數(shù)設(shè)為20，參數(shù)k1設(shè)為300，k2設(shè)為0.1，交叉率和變異率的變化區(qū)間分別為0.5～1.0和0～0.05。

仿真可得最優(yōu)染色體為：

通過(guò)對(duì)最優(yōu)染色體分析可得，高優(yōu)先級(jí)客戶(hù)產(chǎn)品的交貨期能夠獲得高滿(mǎn)意度，一般能夠達(dá)到1；普通產(chǎn)品的交貨期也能獲得不低的滿(mǎn)意度，保證在0.95以上。這證明AGA算法能有效求解問(wèn)題模型。

4.2 對(duì)比實(shí)驗(yàn)

為驗(yàn)證本文提出的AGA算法的有效性，與文獻(xiàn)[4]提出的克隆選擇算法（CAS）和文獻(xiàn)[7]提出的人工免疫算法（AIS）進(jìn)行比較。以客戶(hù)滿(mǎn)意度最大為目標(biāo)，分別對(duì)模糊數(shù)據(jù)規(guī)模為30×10，60×10，80×15和100×10的數(shù)據(jù)進(jìn)行仿真，數(shù)據(jù)結(jié)果由算法進(jìn)行10次運(yùn)算，然后取其中的最優(yōu)值并計(jì)算出平均值。

表3 算法比較結(jié)果

由表3可知，AGA算法的性能要優(yōu)于CAS算法和AIS算法。針對(duì)不同規(guī)模的問(wèn)題，在迭代次數(shù)相同的情況下，AGA算法的最優(yōu)值要優(yōu)于CAS算法和AIS算法，而且隨著問(wèn)題規(guī)模的增加，AIS算法和CAS算法取得的最優(yōu)值跟全局最優(yōu)值的差距變大，而AGA算法依然能取得全局最優(yōu)值或接近全局最優(yōu)值，說(shuō)明算法能夠跳出局部最優(yōu)達(dá)到全局最優(yōu)值，從而說(shuō)明本文提出的AGA算法性能要優(yōu)于AIS算法和CAS算法。

5 結(jié)束語(yǔ)

本文針對(duì)并行機(jī)模糊調(diào)度問(wèn)題，根據(jù)客戶(hù)滿(mǎn)意度最大這一生產(chǎn)目標(biāo)，建立了模糊生產(chǎn)調(diào)度模型，并構(gòu)建了自適應(yīng)遺傳算法對(duì)其進(jìn)行求解。該算法能夠克服一般遺傳算法趨于局部最優(yōu)的缺點(diǎn)，提高了全局尋優(yōu)能力。與AIS算法和CAS算法進(jìn)行對(duì)比實(shí)驗(yàn)，仿真結(jié)果表明該算法具有更優(yōu)的性能。

[1]高家全，趙端陽(yáng)，何桂霞，等.解特殊工藝約束拖后調(diào)度問(wèn)題的并行遺傳算法[J].計(jì)算機(jī)工程應(yīng)用，2007，43（27）：184-186.

[2]劉文程.家紡企業(yè)生產(chǎn)調(diào)度模型及優(yōu)化算法研究[D].杭州：浙江工業(yè)大學(xué)，2009.

[3]沈兵虎，柳毅.改進(jìn)微粒群算法求解模糊交貨期Flow-shop調(diào)度問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（34）：36-38.

[4]Ong Z X，Tay J C，Kwoh K C.Applying the clonal selection principle to find flexible job-shop schedules[C]//Proceedings of the 4th International Conference on Artificial Immunes Systems，2005：442-455.

[5]Masatoshi S.Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms[J].European Journal of Operational Research，2000，120（2）：393-407.

[6]雷德明，吳智銘.多目標(biāo)模糊作業(yè)車(chē)間調(diào)度問(wèn)題研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2006，12（2）：174-179.

[7]Agarwal R，Tiwari M K，Mukherjee S K.Artificial immune system based approach for solving resource constraint project scheduling problem[J].International Journal of Advanced Manufacturing Technology，2007，34：584-593.

[8]李富明，朱云龍.可變機(jī)器約束的模糊作業(yè)車(chē)間調(diào)度問(wèn)題研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2006，12（2）：169-174.

[9]柳毅，葉春明.模糊交貨期Flow-shop調(diào)度問(wèn)題的改進(jìn)微粒群算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2009，41（1）：145-148.

[10]Tang J，Zhang G，Lin B，et al.A hybrid algorithm for flexible job-shop scheduling problem[J].Procedia Engineering，2011，15：3678-3683.

[11]Wang L，Tang D.An improved adaptive genetic algorithm based on hormonemodulation mechanism forjob-shop scheduling problem[J].ExpertSystemswith Applications，2011，38（6）：7243-7250.

[12]Ren Q，Wang Y.A new hybrid genetic algorithm for job shop scheduling problems[J].Computer and Operations Research，2012，39（10）：2291-2299.

LIU Wencheng,GAO Jiaquan

浙江工業(yè)大學(xué) 之江學(xué)院，杭州 310024

College of Zhijiang,Zhejiang University of Technology,Hangzhou 310024,China

According to the practical job shop scheduling problem subject to priority constraint of products with fuzzy processing time and due time in textile manufacturing industry,a scheduling model with maximization of average satisfaction is proposed. Furthermore,an Adaptive Genetic Algorithm（AGA）is presented to solve the scheduling models.In this algorithm,besides the proportional selection,the self-adapting mutation and cross are proposed to enhance the diversity of the population.Simulation results show that AGA is effective and is advantageous to the artificial immune algorithm.

parallel machines;fuzzy processing time;fuzzy due-date;fuzzy scheduling;Genetic Algorithm（GA）

A

TP301

10.3778/j.issn.1002-8331.1210-0090

LIU Wencheng,GAO Jiaquan.Self-adapting genetic algorithm for solving fuzzy scheduling problem on parallel machines. Computer Engineering and Applications,2013,49（7）：60-63.

浙江省自然科學(xué)基金（No.LY12A01027）。

劉文程（1984—），男，碩士，研究領(lǐng)域?yàn)樯a(chǎn)調(diào)度優(yōu)化，算法優(yōu)化；高家全（1972—），男，博士，副教授，研究領(lǐng)域?yàn)橹悄軆?yōu)化算法及其應(yīng)用，高性能計(jì)算。E-mail：lwc198411@126.com

2012-10-10

2012-12-27

1002-8331（2013）07-0060-04