基于可重生遺傳算法的大規模訂單調度問題研究

0 前 言

本文研究的某風機企業屬于多品種、小批量訂單型生產企業，產品特點為品種多、更新快、加工產量變化大、交貨周期短、工藝復雜、需求變動頻繁；在此種背景下計劃與調度要具有敏捷性，能夠解決作業計劃與調度的動態變更問題，適應企業動態生產調度的需求，使企業適應日益不確定的市場環境。

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

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

為了提高種群的多樣性，使其不被局部優解限制，本文運用可重生思想對遺傳算法進行改進，在針對實際生產中訂單調度問題調度規模大、調度復雜及計算時間長等問題，并結合企業實際建立了以最大流程時間最少為目標的訂單調度模型予以優化。從而提高全局搜索能力，避免早熟。

1 問題描述及模型建立

一般的調度模型并不能應用于MTO生產中，與一般靜態車間調度相比較，車間調度有如下特點： （1）產品的交付都是以訂單為基本單位； （2）訂單中產品種類多且數量不定，假設生產中共有μ個訂單，包含m種型號的產品，且每種型號產品數量為Nm，一般生產中μ,m,Nm＞1。模型假設： （1）產品的生產工藝具有唯一性。 （2）加工過程中不能中斷工序。 （3）零時刻訂單中所有工件都能開始加工。根據其特點和模型假設建立如下數學模型：

目標函數：

2 模型求解

2.1 標準遺傳算法

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

2.2 可重生遺傳算法

對于大規模訂單調度問題，由于訂單數量大及加工工藝復雜等原因，會導致運算過程中涉及數據量大，過程復雜，穩定性差，容易陷入早熟。為了提高種群的多樣性，使其不被局部優解限制，本文根據文獻[6]運用可重生思想對遺傳算法進行改進。

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

（2）設定一個閾值ε。

（3）根據適應值函數計算各條染色體的適應值，求出每條染色體的歷史最優值pbest以及歷史最優值的平均值，種群在本次搜索中的最優值 gbest。

圖1 重生遺傳算法流程圖

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

（5）判斷是否滿足終止條件，若滿足則停止迭代輸出最優解，否則轉入步驟 （3）。

2.2.1 染色體編碼

在遺傳算法中，編碼方式的設計是其關鍵問題，它決定了設計算法的求解精度及困難程度，必須考慮到 “個體”的可行性、有效性、合法性等，因此，應用遺傳算法求解調度問題的關鍵就是設計遺傳算法編碼方式。

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

2.2.2 初始種群的產生及適應度函數

（1）初始種群的產生

圖2 染色體編碼方案實例

遺傳算法需要初始種群數據作為搜索起點，初始種群的產生不僅要符合編碼的合法性，而且關系著算法的計算效率等性能，本文根據種群編碼組成的特殊性，種群產生過程也分為兩個過程，首先，隨機生成第一部分的編碼，然后對根據工藝所要求設備的需要，再從可加工該道工序的候選設備中隨機選取某臺設備編號作為相對應第二部分的編碼。通過此方法產生的染色體能確保染色體的合法性，提高種群生成效率。

（2）適應度函數及選擇

本文選擇以調度模型目標訂單拖期和最小為適應度函數，即fit（）F =1/f。

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

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

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

圖3 基于位置的交叉操作

（2）變異操作：由于調度中存在大量的工序都可在多臺機器上加工，所以變異操作僅對于染色體的第二部分進行，即對某個工件的某道工序所加工的設備隨機更新。

3 實例驗證及數值分析

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

表1 調度問題的加工時間表/min

表2 調度問題加工順序表

根據表1、表2、表3的數據分別采用標準遺傳算法和基于可重生遺傳算法進行10次計算 （停止標準：成熟代數達到200代），得到以下數據結果 （見表4）。

3.1 不同算法對比尋優過程

智能算法的尋優收斂過程如圖4所示。從圖4中可以看出，在同樣的迭代數下，遺傳算法比粒子群算法初始解及最終的適應值方面都要好，與標準遺傳算法相比，在解已經基本穩定的情況下，即迭代340代之后，可重生遺傳算法能利用其重生機制跳出原有循環，不斷更新，獲得更優的解。

3.2 不同訂單規模下試驗分析

表3 某風機企業實際訂單 （訂單包含產品數）

表4 算法求解對比

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

表5 不同訂單產品規模下的試驗結果

此實驗也直接說明了可重生遺傳算法在處理大規模訂單調度方面比一般智能算法具有更好的效果。

4 總 結

本文根據實際建立了訂單生產調度模型，針對遺傳算法在計算過程中的早熟問題，基于種群可重生思想，提出了可重生遺傳算法。通過與標準遺傳算法及粒子群算法進行對比表明，可重生遺傳算法在該問題上具有更好地調度效果，且隨著訂單規模的增大其調度效果方面的優勢更加明顯。

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

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

[3] 張超勇，饒運清，李培根,等.柔性作業車間調度問題的兩級遺傳算法[J].機械工程學報，2007,43(4):119-124.

[4] 王萬良.生產調度智能算法及其應用[M].上海：科學出版社，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] 張捷，封俊紅.基于動態距離閾值和重生機制的動態微粒群優化[J].計算機應用研究，2009,26(12):4526-4529.