趙錦東，張 婷，金 雁

（唐山學院，唐山 063000）

基于改進的單倍體遺傳算法生產(chǎn)調(diào)度設計

趙錦東，張 婷，金 雁

（唐山學院，唐山 063000）

0 引言

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

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

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

1.1 單倍體遺傳算法

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

1.2 改進的單倍體遺傳算法

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

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

對原來的指數(shù)變換改進如下：

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

2 基于改進的單倍體遺傳算法生產(chǎn)調(diào)度設計

2.1 生產(chǎn)調(diào)度問題描述

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

2.2 生產(chǎn)調(diào)度問題建模

2.2.1 約束條件

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

2.2.2 建模步驟

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

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

2）建立狀態(tài)庫所和變遷觸發(fā)后的狀態(tài)之間的一對一關系；

3）確定生產(chǎn)任務，并為每個任務建立一個起始狀態(tài)庫所；

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

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

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

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

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

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

2.3 生產(chǎn)調(diào)度系統(tǒng)主要功能設計

2.3.1 系統(tǒng)開發(fā)環(huán)境

操作系統(tǒng)：W I N D O W S X P；開發(fā)工具：.Net2.0, Microsoft Visual Studio 2005；開發(fā)語言：C# ；數(shù)據(jù)庫：Oracle 9i；網(wǎng)絡協(xié)議：TCP/IP；瀏覽器：IE 6.0以上

2.3.2 主要功能設計

該系統(tǒng)主要實現(xiàn)生產(chǎn)調(diào)度的任務的合理安排，使整個生產(chǎn)調(diào)度過程花費的時間最小。系統(tǒng)主要功能模塊如下：

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

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

圖1 調(diào)度結果顯示界面

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

3 結論

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

[1]馬正元,王偉玲,王玉生.生產(chǎn)調(diào)度問題的系統(tǒng)研究[J].成組技術與生產(chǎn)現(xiàn)代化,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]周嶺.車間作業(yè)調(diào)度與控制技術研究[J].械加工與自動化,2002,11(12):19-22.

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

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

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

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

Based on improved partheno genetic algorithm in enterprise production scheduling

ZHAO Jin-dong, ZHANG Ting, JIN Yan

在對車間生產(chǎn)調(diào)度進行建模和仿真的基礎上，基于改進的單倍體遺傳算法設計實現(xiàn)車間生產(chǎn)調(diào)度系統(tǒng)。設計實現(xiàn)證明基于改進后的單倍體遺傳算法設計的調(diào)度系統(tǒng)在算法的尋優(yōu)速度和收斂精度上有明顯提高。

生產(chǎn)調(diào)度；單倍體遺傳算法；設計

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

TP391

B

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

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

2010-10-15