基于遺傳算法的多目標生產車間調度研究

方　霞，曹　潔

（湖南文理學院，計算機科學與技術學院，湖南，常德　415000）

基于遺傳算法的多目標生產車間調度研究

方霞，曹潔

（湖南文理學院，計算機科學與技術學院，湖南，常德415000）

針對生產調度多目標動態復雜性，提出了一種基于AOE圖尋找關鍵路徑的改進遺傳算法。采用基于工件和機器相結合的編碼方法，根據多目標要求，設計了相應的交叉遺傳算子。實驗結果表明，改進的遺傳算法符合車間實際應用情況，對解決多目標動態車間調度問題有實際的應用意義。

遺傳算法；多目標；車間調度；關鍵路徑

1　概述

調度功能是車間管理的核心功能之一，它直接關系著車間能否在指定的時間段內合理利用有限的制造資源完成相應的加工任務。調度問題不但沖突多、求解過程相當復雜，而且在不同制造環境下所考慮的約束、達到的目的等均不相同，使得調度問題之間的差別很大［1］，特別是對于多目標問題，求解尤其困難。

組合優化問題通常具有大量的局部極值點，往往是不可微的、不連續的、多維的、有約束條件的、高度非線性的NP完全問題，因此，精確求解組合優化問題往往是不可能的。生產調度（JSP）問題是一類典型NP完全問題，隨著問題規模的擴大，會發生組合爆炸，算法復雜性呈指數增長［2-3］。各類混合遺傳算法是解決實際調度問題最有效的途徑和最有前途的調度方法［4］。在充分進行調查研究和比較各類優化搜索方法［5-9］的基礎上，提出一種混合遺傳算法來有效解決生產調度中的多目標問題。

2　JSP問題描述

JSP（Job-Shop）問題研究n個工件在m臺機器上的加工，已知各操作的加工時間和各工件在各機器上的加工次序約束，要求確定與工藝約束條件相容的各機器上所有工件的加工時間或完成時間或加工次序［10］。

使加工性能指標達到最優，具體滿足如下條件：

1）同一時刻同一臺機器只能加工一個工件；

2）每個工件在某一時刻只能在一臺機器上加工，不能中途中斷每一個操作；

3）不同工件的工序之間有部分聯系；

4）不同工件具有優先級的差別；

5）每個工件相鄰工序之間的間隔為零（準備時間可計入機器的加工時間）。

AOE帶權有向無環網模型是描述JSP調度問題的一種行之有效的方法，如圖1所示。

圖1　加工環節示意AOE網

頂點表示事件，弧aij表示工件i的某道工序j，權表示工序加工時間（為了簡化模型，準備時間包含于加工時間內視為整體）。

分析AOE網可以得到生產過程中的關鍵路徑，對于解決生產調度中的瓶頸問題有很強的現實意義。通過改善關鍵活動的工效，可以有效縮短整個工期，提高設備利用率。

車間調度分為靜態調度和動態調度兩種。靜態調度目標為在滿足生產任務交貨期的前提下，盡可能提高設備資源的利用率，減少調整時間，使生產周期最短。靜態調度是車間計劃進入執行階段的基礎和依據，遺傳算法（GA）在靜態調度問題中已經有成功的應用。動態調度指在車間實際的運行過程中，存在著不可預期的被稱為動態時間的隨機擾動，如機器故障、訂單的突然加入或取消等，因此往往需要不斷地進行動態重調度［11-13］。具體生產調度加工目標和解決策略如下：

1）企業成本最小化、降低庫存；

2）按期交貨訂單數量最大化。考慮縮短制造周期方面，則調用完工時間最早的工序；考慮不同交貨期方面，則計算不同完工提前期，根據事情緊急情況分別對待；

3）資源設備均衡利用。考慮減少機器負荷方面，則調用加工時間最小的工序；考慮設備能力方面，則涉及加班、外協等問題；

4）任務優先數的考慮。在上層決策時，充分關注市場銷售、機器生產、庫存等方面問題；而裝配完成情況與加工次序緊密聯系；動態調度事，對于缺件未能按時完工，需要優先加工，將其優先級增大；

5）減少調整準備時間。充分考慮運輸時間的問題，其中涉及到設備地理位置情況、工件準備時間、刀具準備時間等方面。

3　混合遺傳算法描述

3.1混合遺傳算法

遺傳算法（GA）是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化算法，在許多領域中得到了成功的應用，如函數優化、旅行商問題等。利用遺傳算法已經成功解決靜態生產調度問題，本文重點針對動態調度中的多目標問題，采用以遺傳算法為基礎，結合AOE找尋關鍵路徑的混合遺傳算法來彌補遺傳算法的局部搜索能力的不足，根據適應度的變化采用相應的交叉變異算子，避免“早熟”收斂現象發生，對于生產調度中的動態多目標問題進行有效的解決［11-13］。

3.2編碼方案

編碼問題是算法設計的首要和關鍵問題，常見的有二進制編碼、格雷碼編碼、實數編碼、符號編碼、排列編碼、二倍體編碼、DNA編碼、多參數編碼、矩陣編碼等［14］。解決經典的工作車間調度問題有基于工序的編碼、基于機器編碼、基于操作的編碼等多種方法。采用基于工序和機器的編碼［15］，工序aij用Gi來表示工件i，其出現的次序表示工序加工順序；機器m用Jm表示某工序加工的機器。如染色體J1G1-J2G2-J1G1-J2G1表示工件1第1道工序在機器1上加工，工件2第1道工序在機器2上加工，工件1第2道工序在機器1上加工，工件1第3道工序在機器2上加工。

3.3種子選擇

首先對各工序生成的AOE網進行拓撲排序及逆拓撲排序判斷，在該前提下求得關鍵路徑，并對關鍵活動優先分配機器，保證關鍵活動的正常如期完成。將關鍵活動基因置前，后隨機生成一定數量的不完全染色體種子，結合工序要求對非關鍵路徑上的工序進行機器分配，形成最終的染色體。采用常用的輪盤賭方法進行選擇適應度高的個體，為了防止算法收斂于局部解，種群規模取30個。

為了保證所得到的最優個體不會被交叉、變異等遺傳操作所破壞，結合使用最優保存策略，若當前群體中最佳個體的適應度低于總的迄今為止的最好個體的適應度，用迄今為止的最好個體替換掉當前群體中的最差個體。

3.4適應度函數

多目標優化問題是指一個問題存在多個需要優化的性能指標，每個性能指標都有其不同約束條件，多目標優化就是要尋求一個在滿足各個約束條件下且能使各個需要優化的目標能得到優化解［11-12］。企業生產調度問題是一個典型的多目標優化問題，生產系統的效率取決于很多因素如生產周期 （市場銷售）、機器生產的利用率、庫存（成本）等，上層管理決策對各目標的考慮權重不同也直接決定著生產調度的結果發生變化。本文算法在交叉變異過程中使用相關參數α、β進行環境適應性調整，以達到多目標綜合決策要求。

3.5交叉變異操作

交叉算法直接決定著遺傳算法的全局搜索能力，基于關鍵路徑的交叉算子操作如下；首先根據交叉概率和適應度權重的配置選擇一對父母個體，僅對后續非關鍵基因部分進行交叉操作；隨機選擇非關鍵活動上的一個工件，其在父母個體中對應的x個操作不變，父母個體剩余其他操作按順序進行對應變換，分別得到新的兩個子代個體。

變異算子決定了遺傳算法的局部搜索能力，良好的算子可以有效的維持群體的多樣性，防止早熟現象的出現。為了保證關鍵活動的順利完成以及種群的多樣性，變異操作分為兩大步驟進行：首先根據變異概率對關鍵路徑上的工序進行機器配置變異，然后對非關鍵工序進行局部重新定位［16-18］。

3.6算法流程

1）調度任務數據初始化；

2）建立AOE網，求出關鍵路徑，隨機生成初始種群；

3）計算適應度，結合使用最優保存策略采用輪盤賭方法進行選擇；

4）基于關鍵路徑進行交叉變異操作；

5）滿足終止條件，轉步驟6，否則轉步驟3；

6）輸出最終解集。

4　計算應用實例與實驗仿真

系統演示使用VisualC++編程工具完成，如下是一個標準實例：已知實際工作環境及條件：5類機床，數量分別為2、1、1、1、1臺，編號i-j表示i類機床第j臺；工件號和工序號從1開始排列，交貨期均設為零值，具體數據見表1。

表1　加工工序相關數據

利用關鍵路徑的遺傳算法得到實驗結果仿真如圖2所示。圖中aij表示第i個工件第j工序。可以看出整體的加工順序安排合理，充分考慮了關鍵工件的加工工序，使得工期達到最短，成本最低。

圖2　實驗數據仿真

5　結論

針對制造企業生了車間生產調度系統框架。根據生產調度中動態多目標特征，使用相應的交叉變異算子改善了遺傳算法的搜索性能，在算法流程中考慮了同類型機床的負荷平衡優化問題，最后使用該算法對實例進行了調度仿真，通過分析比較，表明本文的調度算法性能良好，能夠較好的適應制造環境實際。

［1］ 熊銳，吳澄.車間生產調度問題的技術現狀與發展趨勢［J］.清華大學學報（自然科學版），1998，10（38）：55-60.

［2］ 徐俊剛，戴國忠，王宏安.生產調度理論和方法研究綜述［J］.計算機研究與發展，2004，41（2）：257-267.

［3］ 余建軍，張定超，周銘新.生產調度綜述［J］.中國制造業信息化，2009，38（17）：13-17.

［4］ 王東成，何衛平，王邦龍.基于混合遺傳算法的敏捷車間調度研究［J］.航空精密制造技術，2006，42（1）：43-47.

［5］ 石苓，竇延平.基于生產計劃排單的遺傳算法的優化與應用［J］.計算機仿真，2005，（4）.86-88.

［6］ 王展青，魏毅峰.求解JSP問題的改進遺傳算法［J］.武漢理工大學學報，2006，28（2）：40-42.

［7］ 周興斌，李平.基于優先數的智能生產調度系統［J］.計算機工程與應用，2003，（11）：199-201.

［8］ 劉紅軍，趙帥.一種基于混合遺傳算法的車間生產調度的研究［J］.制造業自動化，2011，33（9）：33-35.

［9］ 汪紅兵，徐安軍，姚琳等.應用改進遺傳算法求解煉鋼連鑄生產調度問題［J］.北京科技大學學報，2010，32（9）：1232-1237.

［10］莊新村，盧宇灝，李從心.基于遺傳算法的車間調度問題［J］.計算機工程，2006，（1）：193-194`

［11］谷峰，陳華平，盧冰原.基于遺傳算法的多目標柔性工作車間調度問題求解［J］.運籌與管理，2006，15（1）：134-139.

［12］趙建峰，朱曉春，汪木蘭，等.基于遺傳算法柔性制造系統生產調度的優化與仿真.制造業自動化，2010，32（5）：156-159.

［13］譚輝，張洪偉，朱麗.APS系統中基于改進的遺傳算法的分布式排產研究［J］.計算機應用研究，2005，（6）：76-78.

［14］余有明，劉玉樹，閻光偉.遺傳算法的編碼理論與應用［J］.計算機工程與應用，2006，（3）：86-89.

［15］韋勇福，曾盛綽.基于遺傳算法的車間生產調度系統研究［J］.2014，11：205-207.

［16］孫亮，王曉原，張運才.自適應超啟發式遺傳算法求解隨機型生產調度問題［J］.小型微型計算機系統，2013，34（9）：2158-2163.

［17］袁喜連，劉勇，肖翀.遺傳算法在銅板帶生產調度中的應用研究［J］.計算機工程與應用，2009，45（27）：213-215.

［18］高家全.遺傳算法在家紡企業生產調度中的應用［J］.哈爾濱工業大學學報，2009，41（6）：229-231.

TP18