基于可重生遺傳算法的大規(guī)模訂單調(diào)度問(wèn)題研究

0 前 言

本文研究的某風(fēng)機(jī)企業(yè)屬于多品種、小批量訂單型生產(chǎn)企業(yè)，產(chǎn)品特點(diǎn)為品種多、更新快、加工產(chǎn)量變化大、交貨周期短、工藝復(fù)雜、需求變動(dòng)頻繁；在此種背景下計(jì)劃與調(diào)度要具有敏捷性，能夠解決作業(yè)計(jì)劃與調(diào)度的動(dòng)態(tài)變更問(wèn)題，適應(yīng)企業(yè)動(dòng)態(tài)生產(chǎn)調(diào)度的需求，使企業(yè)適應(yīng)日益不確定的市場(chǎng)環(huán)境。

Job—Shop調(diào)度問(wèn)題是NP問(wèn)題，其研究的方向有兩大類：精確算法和近似算法。精確算法主要包括分支定界法、基于析取圖模型的枚舉方法、混合整數(shù)規(guī)劃模型和拉格朗日松弛法等。近似算法包括優(yōu)先權(quán)規(guī)則調(diào)度算法、瓶頸轉(zhuǎn)移啟發(fā)式算法、鄰域搜索算法和人工智能方法等。精確算法雖能保證得到全局最優(yōu)解，但只能解決小規(guī)模的調(diào)度問(wèn)題，無(wú)法實(shí)際應(yīng)用。近年來(lái)，用鄰域搜索算法，如模擬退火算法、禁忌搜索算法和遺傳算法等解決Job—Shop調(diào)度問(wèn)題，亦倍受關(guān)注。

當(dāng)前研究較多的應(yīng)用改進(jìn)的遺傳算法應(yīng)用于生產(chǎn)調(diào)度，如洪劉兵、楊艷麗[1]引入人工免疫機(jī)制克隆選擇算子和設(shè)計(jì)獨(dú)特的交叉算子，提高算法的收斂速度和種群的多樣性；曾益[2]采用的遺傳算法和模擬退火算法相結(jié)合使算法能夠趨于全局最優(yōu)，張超勇、饒運(yùn)清[3]等為克服傳統(tǒng)遺傳算法在求解車間作業(yè)調(diào)度問(wèn)題時(shí)的早熟收斂，設(shè)計(jì)了一種子代交替模式的交叉方式遺傳算法，傳統(tǒng)遺傳算法具有全局搜索能力，但易早熟收斂，而局部搜索善于微調(diào)，但常陷于局部最優(yōu)。

為了提高種群的多樣性，使其不被局部?jī)?yōu)解限制，本文運(yùn)用可重生思想對(duì)遺傳算法進(jìn)行改進(jìn)，在針對(duì)實(shí)際生產(chǎn)中訂單調(diào)度問(wèn)題調(diào)度規(guī)模大、調(diào)度復(fù)雜及計(jì)算時(shí)間長(zhǎng)等問(wèn)題，并結(jié)合企業(yè)實(shí)際建立了以最大流程時(shí)間最少為目標(biāo)的訂單調(diào)度模型予以優(yōu)化。從而提高全局搜索能力，避免早熟。

1 問(wèn)題描述及模型建立

一般的調(diào)度模型并不能應(yīng)用于MTO生產(chǎn)中，與一般靜態(tài)車間調(diào)度相比較，車間調(diào)度有如下特點(diǎn)： （1）產(chǎn)品的交付都是以訂單為基本單位； （2）訂單中產(chǎn)品種類多且數(shù)量不定，假設(shè)生產(chǎn)中共有μ個(gè)訂單，包含m種型號(hào)的產(chǎn)品，且每種型號(hào)產(chǎn)品數(shù)量為Nm，一般生產(chǎn)中μ,m,Nm＞1。模型假設(shè)： （1）產(chǎn)品的生產(chǎn)工藝具有唯一性。 （2）加工過(guò)程中不能中斷工序。 （3）零時(shí)刻訂單中所有工件都能開(kāi)始加工。根據(jù)其特點(diǎn)和模型假設(shè)建立如下數(shù)學(xué)模型：

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

2 模型求解

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

遺傳算法[4]是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，非常適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性優(yōu)化問(wèn)題。在遺傳算法中，染色體對(duì)應(yīng)的數(shù)據(jù)或數(shù)組通常用串結(jié)構(gòu)數(shù)據(jù)來(lái)表示，遺傳算法處理的染色體成為基因型個(gè)體，一定數(shù)量的個(gè)體組成群體。各個(gè)個(gè)體對(duì)于環(huán)境的適應(yīng)程度叫適應(yīng)度。其主要內(nèi)容[5]包括：編碼方案、適應(yīng)度函數(shù)、選擇策略、遺傳算子等，其中交叉及變異概率分別為Pc和Pm。

2.2 可重生遺傳算法

對(duì)于大規(guī)模訂單調(diào)度問(wèn)題，由于訂單數(shù)量大及加工工藝復(fù)雜等原因，會(huì)導(dǎo)致運(yùn)算過(guò)程中涉及數(shù)據(jù)量大，過(guò)程復(fù)雜，穩(wěn)定性差，容易陷入早熟。為了提高種群的多樣性，使其不被局部?jī)?yōu)解限制，本文根據(jù)文獻(xiàn)[6]運(yùn)用可重生思想對(duì)遺傳算法進(jìn)行改進(jìn)。

（1）初始化種群大小和參數(shù)，設(shè)定種群數(shù)量為300，設(shè)置參數(shù)Pc=0.5， Pm=1。

（2）設(shè)定一個(gè)閾值ε。

（3）根據(jù)適應(yīng)值函數(shù)計(jì)算各條染色體的適應(yīng)值，求出每條染色體的歷史最優(yōu)值pbest以及歷史最優(yōu)值的平均值，種群在本次搜索中的最優(yōu)值 gbest。

圖1 重生遺傳算法流程圖

（4）將本次搜索中比歷史最優(yōu)平均值小的適應(yīng)值視為適應(yīng)值較小值個(gè)體，若本次搜索中的最優(yōu)值gbest與適應(yīng)值較小者之間的距離小于閾值ε，則適應(yīng)值較小者無(wú)需重新生成，否則，將適應(yīng)值較小者重新生成；除需重生的染色體外，其他染色體則進(jìn)行遺傳操作。

（5）判斷是否滿足終止條件，若滿足則停止迭代輸出最優(yōu)解，否則轉(zhuǎn)入步驟 （3）。

2.2.1 染色體編碼

在遺傳算法中，編碼方式的設(shè)計(jì)是其關(guān)鍵問(wèn)題，它決定了設(shè)計(jì)算法的求解精度及困難程度，必須考慮到 “個(gè)體”的可行性、有效性、合法性等，因此，應(yīng)用遺傳算法求解調(diào)度問(wèn)題的關(guān)鍵就是設(shè)計(jì)遺傳算法編碼方式。

由于本文研究訂單生產(chǎn)調(diào)度的特殊性，不同于一般的車間調(diào)度問(wèn)題，不僅要滿足一般調(diào)度問(wèn)題的解碼過(guò)程，而且需要考慮任何柔性設(shè)備的可交換加工特性，所以本文根據(jù)實(shí)際提出一種新的編碼方案。該編碼方案分為兩部分，總長(zhǎng)度為， 第一部分長(zhǎng)度為采用依據(jù)操作的編碼方式，主要是得到工件調(diào)度的先后順序方案；第二部分長(zhǎng)度同樣為采用基于機(jī)器的編碼方式，得到每個(gè)操作所在的加工設(shè)備。其中n為當(dāng)前所有訂單的工件數(shù)量，Ni為第i個(gè)工件所包含的操作數(shù)量。例如圖2所示為一條調(diào)度3個(gè)工件的染色體，第一部分中出現(xiàn)的3個(gè) “1”代表工件1的3道工序，工件2、3也同樣如此；第二部分代表設(shè)備，第1個(gè)工件的第1道工序在設(shè)備1上加工，其第2道工序在設(shè)備3上加工，以此類推。

2.2.2 初始種群的產(chǎn)生及適應(yīng)度函數(shù)

（1）初始種群的產(chǎn)生

圖2 染色體編碼方案實(shí)例

遺傳算法需要初始種群數(shù)據(jù)作為搜索起點(diǎn)，初始種群的產(chǎn)生不僅要符合編碼的合法性，而且關(guān)系著算法的計(jì)算效率等性能，本文根據(jù)種群編碼組成的特殊性，種群產(chǎn)生過(guò)程也分為兩個(gè)過(guò)程，首先，隨機(jī)生成第一部分的編碼，然后對(duì)根據(jù)工藝所要求設(shè)備的需要，再?gòu)目杉庸ぴ摰拦ば虻暮蜻x設(shè)備中隨機(jī)選取某臺(tái)設(shè)備編號(hào)作為相對(duì)應(yīng)第二部分的編碼。通過(guò)此方法產(chǎn)生的染色體能確保染色體的合法性，提高種群生成效率。

（2）適應(yīng)度函數(shù)及選擇

本文選擇以調(diào)度模型目標(biāo)訂單拖期和最小為適應(yīng)度函數(shù)，即fit（）F =1/f。

選擇操作采用蒙特卡羅法 （Monte Carlo），在該方法中，各個(gè)個(gè)體被選擇的概率和其適應(yīng)度值成比例。設(shè)種群規(guī)模大小為N，個(gè)體i的適應(yīng)度值為fi，則這個(gè)個(gè)體被選擇的概率為：

2.2.3 遺傳算法的交叉和變異操作

（1）交叉操作：本文中交叉操作采用基于位置的交叉，而且只對(duì)染色體的第一部分進(jìn)行，第二部分隨著與其相應(yīng)的第一部分的交叉而交叉。首先隨機(jī)選取位置，然后交換被選中的基因，并在原父代個(gè)體中刪除從另一父代個(gè)體交換過(guò)來(lái)的基因，接著從第一個(gè)基因位依次在未選中位置填入剩余基因。具體實(shí)例如圖3所示。

圖3 基于位置的交叉操作

（2）變異操作：由于調(diào)度中存在大量的工序都可在多臺(tái)機(jī)器上加工，所以變異操作僅對(duì)于染色體的第二部分進(jìn)行，即對(duì)某個(gè)工件的某道工序所加工的設(shè)備隨機(jī)更新。

3 實(shí)例驗(yàn)證及數(shù)值分析

為了驗(yàn)證模型的有效性，本文以某訂單企業(yè)為例，利用Visual Studio 2010軟件，在處理器為Intel Core i3@2.27GHz@2.27GHz，內(nèi)存為2GB的計(jì)算機(jī)上求解。遺傳算法參數(shù)選擇：種群500，交叉率為1，變異率為0.2。實(shí)驗(yàn)數(shù)據(jù)包括以下參數(shù)： （1）企業(yè)產(chǎn)品種類及在機(jī)器上的加工時(shí)間； （2）各個(gè)種類產(chǎn)品的加工工藝順序； （3）某時(shí)間段具體的訂單列表；數(shù)據(jù)見(jiàn)表1、表2、表3。

表1 調(diào)度問(wèn)題的加工時(shí)間表/min

表2 調(diào)度問(wèn)題加工順序表

根據(jù)表1、表2、表3的數(shù)據(jù)分別采用標(biāo)準(zhǔn)遺傳算法和基于可重生遺傳算法進(jìn)行10次計(jì)算 （停止標(biāo)準(zhǔn)：成熟代數(shù)達(dá)到200代），得到以下數(shù)據(jù)結(jié)果 （見(jiàn)表4）。

3.1 不同算法對(duì)比尋優(yōu)過(guò)程

智能算法的尋優(yōu)收斂過(guò)程如圖4所示。從圖4中可以看出，在同樣的迭代數(shù)下，遺傳算法比粒子群算法初始解及最終的適應(yīng)值方面都要好，與標(biāo)準(zhǔn)遺傳算法相比，在解已經(jīng)基本穩(wěn)定的情況下，即迭代340代之后，可重生遺傳算法能利用其重生機(jī)制跳出原有循環(huán)，不斷更新，獲得更優(yōu)的解。

3.2 不同訂單規(guī)模下試驗(yàn)分析

表3 某風(fēng)機(jī)企業(yè)實(shí)際訂單 （訂單包含產(chǎn)品數(shù)）

表4 算法求解對(duì)比

如表5顯示在不同規(guī)模下分別標(biāo)準(zhǔn)遺傳算法、標(biāo)準(zhǔn)粒子群算法及可重生遺傳算法所得到的計(jì)算時(shí)間及訂單完成率的情況。在計(jì)算時(shí)間方面，隨著產(chǎn)品規(guī)模的增大，標(biāo)準(zhǔn)遺傳算法和可重生遺傳算法相差不多，但都比標(biāo)準(zhǔn)遺傳算法用時(shí)短。而訂單完成率方面，在產(chǎn)品規(guī)模較小的情況下，三種算法都可以得到很高的訂單完成率，隨著產(chǎn)品規(guī)模的增大，可重生遺傳算法明顯比另外兩種算法的結(jié)果更好。

表5 不同訂單產(chǎn)品規(guī)模下的試驗(yàn)結(jié)果

此實(shí)驗(yàn)也直接說(shuō)明了可重生遺傳算法在處理大規(guī)模訂單調(diào)度方面比一般智能算法具有更好的效果。

4 總 結(jié)

本文根據(jù)實(shí)際建立了訂單生產(chǎn)調(diào)度模型，針對(duì)遺傳算法在計(jì)算過(guò)程中的早熟問(wèn)題，基于種群可重生思想，提出了可重生遺傳算法。通過(guò)與標(biāo)準(zhǔn)遺傳算法及粒子群算法進(jìn)行對(duì)比表明，可重生遺傳算法在該問(wèn)題上具有更好地調(diào)度效果，且隨著訂單規(guī)模的增大其調(diào)度效果方面的優(yōu)勢(shì)更加明顯。

[1] 洪劉兵，楊艷麗.求解車間調(diào)度問(wèn)題的一種改進(jìn)遺傳算法[J].機(jī)床與液壓，2010,38(5):101-103.

[2] 曾益.一種基于改進(jìn)遺傳算法的車間調(diào)度問(wèn)題研究[J].機(jī)械設(shè)計(jì)與制造，2011(7):180-182.

[3] 張超勇，饒運(yùn)清，李培根,等.柔性作業(yè)車間調(diào)度問(wèn)題的兩級(jí)遺傳算法[J].機(jī)械工程學(xué)報(bào)，2007,43(4):119-124.

[4] 王萬(wàn)良.生產(chǎn)調(diào)度智能算法及其應(yīng)用[M].上海：科學(xué)出版社，2007:44-58.

[5] Zhenyuan Jia,Xiaohong Lu.Research on job-shop scheduling problem based on genetic algorithm[J].International Journal of Production Research,2011,49(12):3585-3604.

[6] 張捷，封俊紅.基于動(dòng)態(tài)距離閾值和重生機(jī)制的動(dòng)態(tài)微粒群優(yōu)化[J].計(jì)算機(jī)應(yīng)用研究，2009,26(12):4526-4529.