基于改進的單倍體遺傳算法生產調度設計

趙錦東，張 婷，金 雁

（唐山學院，唐山 063000）

基于改進的單倍體遺傳算法生產調度設計

趙錦東，張 婷，金 雁

（唐山學院，唐山 063000）

0 引言

生產調度，作為制造執行系統的關鍵環節在企業信息化和管理一體化的進程中發揮著重要作用 ，良好的生產調度對企業生產健康高效的運轉具有重要的作用。生產調度技術在滿足車間內機械裝置生產能力、客戶訂單計劃和產品質量標準的條件下，參照當前的庫存狀況，以縮短時間為尺度，以市場需求為目標，評價生產數據和其他和生產密切相關的物性數據，實現產品結構、產品質量、生產車間組織結構和生產運作方式的優化。

市場競爭的日益激烈，對生產管理與生產調度提出了更高的要求。如何設計生產調度的方法、如何建立適合生產調度的優化算法對于加快企業對市場變化的快速反應、提高產品生產率、降低生產成本、節約能源的關鍵所在。

1 單倍體遺傳算法及其改進

1.1 單倍體遺傳算法

單倍體遺傳算法(Partheno Genetic Algorithm,PGA)是由日本學者KOJI M在將基本遺傳算法運用于調度問題時最先提出來的。該算法突破了基本遺傳算法選擇、交叉、變異三種遺傳算子的要求，取消了交叉操作，通過對變異操作進行不斷的研究與改進進行繁殖后代的。單倍體遺傳算法是一種新型的基于序號編碼的遺傳方式，具有與基本遺傳算法相似的遺傳、進化機制，與基本遺傳算法不同的是遺傳算子的種類、操作及對遺傳編碼的處理方式。單倍體遺傳算法的基因重組算子具有與基本遺傳算法交叉算子相同的功能，同時經過單倍體遺傳算法進化后的子代個體幾乎保留了父代個體所具備的全部遺傳特征。

1.2 改進的單倍體遺傳算法

對單倍體遺傳算法在搜索方式上提出改進，即對單倍體遺傳算法適應度函數的變換進行改進，采用改進的指數適應度函數，通過控制指數函數值的變化來改善單倍體遺傳算法的性能.改進前的指數變換方法如下：

1）式中指數函數的系數α一般取正數，f(x)為經過指數變換之前的適應度函數，f'(x)為變換后的適應度函數。

對原來的指數變換改進如下：

2）式中f(x)與f'(x)的含義與在改進前的指數變換中的意義相同。如問題自身性質是求解最小值，則f(x)直接取目標函數；如要求解的是目標函數的最大值，先將問題的目標函數進行線性變換，將求解最大值問題轉換為求解最小值的。改進后的指數變換中，指數α是一個動態變化的函數，而不再是一個常數，α隨個體進化代數的變化而逐漸變化的正數，根據單倍體遺傳算法的進化特點，將原來指數變換的指數系數α用一個自適應的動態調整函數表示。通常，遺傳進化初期favg的值較大，有時可達到進化迭代過程中出現的最大值，這樣α的值很小，甚至會達到進化過程中的最小值，隨著遺傳迭代的不斷進行，favg呈現減小的趨勢，此時進化代數t逐漸變大，總體來看α的取值逐漸變大。

2 基于改進的單倍體遺傳算法生產調度設計

2.1 生產調度問題描述

生產調度(Job-Shop Production Scheduling)問題可描述為：在技術、工藝等一系列約束條件下，對于某個可以被分解的任務，合理安排其組成部分所占有的加工時間、物料資源，在滿足用戶需求的前提下提高生產效率、降低生產成本、節約生產所耗能源。即研究在m臺機器上加工n個工件的過程，加工過程中的約束條件是工序的加工時間及工件工件的加工次序，有硬件約束又有技術約束，最終目的是求得與工藝約束條件相容的加工設備上的全部工件的加工次序，使加工性能達到預期目標或者接近預期目標。

2.2 生產調度問題建模

2.2.1 約束條件

在典型的Job-Shop調度問題中，除技術、工藝、資源約束外，通常還假定以下條件：待加工工件在不同機器設備上的加工順序必須以生產該工件的工藝流程為準則； 生產工件的初始加工時間定為0，且須保證一臺加工設備在同一時間內只能對一個工件進行加工操作，一個被加工工件在同一時間僅能夠在一臺加工設備上進行加工；工件在加工過程中，在一臺機器設備上完成一個生產任務以后，才能進行另一個生產任務；工件在前驅工序結束以后，才能進行后繼工序；待加工工件的優先權在生產調度中不予以考慮；同一臺機器設備不允許工件重復加工；工件在加工過程中不可以被中斷。

2.2.2 建模步驟

在對車間生產調度建模過程中，變遷集合中包含的元素不僅有資源變遷而且還有工序變遷。資源獲得庫所、設備庫所和狀態庫所構成了庫所的集合。

1）建立任務所包含的工序和工序變遷之間的一對一關系；

2）建立狀態庫所和變遷觸發后的狀態之間的一對一關系；

3）確定生產任務，并為每個任務建立一個起始狀態庫所；

4）將以上三個步驟中所確定的狀態庫所和工序變遷用有向弧連接起來；

5）建立資源獲得庫，在工序變遷與資源獲得庫間建立一對一的關系；

6）建立資源庫與相應資源間的一對一關系；7）給資源分配庫確定資源分配變遷；

8）起點為需要資源的變遷，終點為工序變遷對應的資源庫的有向弧的現實意義是將工序變遷所需要的資源釋放掉；

9）將確定的資源獲得庫所、資源庫所和資源分配變遷用有向弧連接起來；將工序變遷和相應的資源獲得庫所用有向弧連接起來；

10）資源庫著色，為有向圖中的有向弧標注權值，顏色默認值為-1，有向弧權值的默認值是0；以每道工序的加工時間為依據，給每一個工序變遷設置初始加工時間，其余變遷的加工時間默認為0。

2.3 生產調度系統主要功能設計

2.3.1 系統開發環境

操作系統：W I N D O W S X P；開發工具：.Net2.0, Microsoft Visual Studio 2005；開發語言：C# ；數據庫：Oracle 9i；網絡協議：TCP/IP；瀏覽器：IE 6.0以上

2.3.2 主要功能設計

該系統主要實現生產調度的任務的合理安排，使整個生產調度過程花費的時間最小。系統主要功能模塊如下：

1）資源管理模塊：實現對車間相關資源的系統管理與控制。包括設備管理、客戶信息管理、職工信息管理、物料管理和訂單管理五個子功能。

2）生產調度模塊：改進的單倍體遺傳算法在生產調度中的應用模塊。設計界面中輸入生產調度參數及改進的單倍體遺傳算法的相關參數，如初始種群數目、遺傳迭代次數、變異概率等數據。進行參數錄入以后，系統就將加工工件的加工時間及相應的約束條件篩選出來，根據工藝數據庫，將待加工的工件分解成相關工序的集合。再結合錄入的加工時間，轉化為算法中對應部分的相關參數。

圖1 調度結果顯示界面

由于車間生產調度系統從定單生成到代碼的下載，工藝、資源等之間存在的大量的數據流動，將車間生產調度的結果存儲到調度管理數據庫中，通過查看調度數據庫中的數據可以確定設備的詳細加工任務及加工流程。圖1為調度結果顯示界面。

3 結論

應用提出的改進的單倍體遺傳算法對建模后的車間生產調度模型進行優化，并給出了具體的優化步驟。使用改進的單倍體遺傳算法，進行車間生產調度系統設計，并通過對數據的采集、分析及模擬得出相應結果。設計實現證明基于改進后的單倍體遺傳算法設計的調度系統在算法的尋優速度和收斂精度上有明顯提高。

[1]馬正元,王偉玲,王玉生.生產調度問題的系統研究[J].成組技術與生產現代化,2005,34(6):10-14.

[2]AMIT K G,APPA I S.Job shop scheduling techniques in semiconductor Manufacturing[J].Int J Adv Manufacture Technology,2006,34(27):1163-1169.

[3]周嶺.車間作業調度與控制技術研究[J].械加工與自動化,2002,11(12):19-22.

[4]張鈴,張錢.遺傳算法機理的研究[J].軟件學報,2000,11(7):945-952.

[5]裴金勇,陳評,等.機組優化組合的改進遺傳算法[J].武漢大學學報,2001,34(l):73-76.

[6]李茂軍,等.單親遺傳算法在Flow shop問題中的應用[J].系統工程與電子技術,2000,22(6):84-89.

[7]李茂軍,童調生,羅隆福.單親遺傳算法及其應用研究[J].湖南大學學報,1998,25(6):164-179.

Based on improved partheno genetic algorithm in enterprise production scheduling

ZHAO Jin-dong, ZHANG Ting, JIN Yan

在對車間生產調度進行建模和仿真的基礎上，基于改進的單倍體遺傳算法設計實現車間生產調度系統。設計實現證明基于改進后的單倍體遺傳算法設計的調度系統在算法的尋優速度和收斂精度上有明顯提高。

生產調度；單倍體遺傳算法；設計

趙錦東（1978 -），女，講師，碩士，主要從事計算機教學工作。

TP391

B

1009-0134(2011)5(上)-0027-04

10.3969/j.issn.1009-0134.2011.5(上).10

2010-10-15