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

趙錦東，張 婷，金 雁

（唐山學(xué)院，唐山 063000）

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

趙錦東，張 婷，金 雁

（唐山學(xué)院，唐山 063000）

0 引言

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

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

1 單倍體遺傳算法及其改進(jìn)

1.1 單倍體遺傳算法

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

1.2 改進(jìn)的單倍體遺傳算法

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

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

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

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

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

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

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

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

2.2.1 約束條件

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

2.2.2 建模步驟

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

1）建立任務(wù)所包含的工序和工序變遷之間的一對一關(guān)系；

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

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

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

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

6）建立資源庫與相應(yīng)資源間的一對一關(guān)系；7）給資源分配庫確定資源分配變遷；

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

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

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

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

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)絡(luò)協(xié)議：TCP/IP；瀏覽器：IE 6.0以上

2.3.2 主要功能設(shè)計(jì)

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

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

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

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

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

3 結(jié)論

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

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

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

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

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

[7]李茂軍,童調(diào)生,羅隆福.單親遺傳算法及其應(yīng)用研究[J].湖南大學(xué)學(xué)報(bào),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)度進(jìn)行建模和仿真的基礎(chǔ)上，基于改進(jìn)的單倍體遺傳算法設(shè)計(jì)實(shí)現(xiàn)車間生產(chǎn)調(diào)度系統(tǒng)。設(shè)計(jì)實(shí)現(xiàn)證明基于改進(jìn)后的單倍體遺傳算法設(shè)計(jì)的調(diào)度系統(tǒng)在算法的尋優(yōu)速度和收斂精度上有明顯提高。

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

趙錦東（1978 -），女，講師，碩士，主要從事計(jì)算機(jī)教學(xué)工作。

TP391

B

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

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

2010-10-15