[發(fā)明專利]基于多色集合層次結(jié)構(gòu)的改進GA求解柔性車間調(diào)度的方法

有效

• 申請?zhí)枺?/td>: 201310737478.8
• 申請日: 2013-12-26
• 公開（公告）號: CN103729694A
• 公開（公告）日: 2014-04-16
• 發(fā)明（設(shè)計）人: 欒飛;曹巨江;傅衛(wèi)平;寶昱彤
• 申請（專利權(quán)）人: 陜西科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06N3/12
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 陸萬壽

技術(shù)領(lǐng)域

本發(fā)明屬于柔性車間調(diào)度技術(shù)領(lǐng)域，涉及一種改進的遺傳算法，具體涉及一種基于多色集合層次結(jié)構(gòu)的改進GA求解柔性車間調(diào)度的方法。

背景技術(shù)

柔性車間調(diào)度（Flexible?Job-Shop?Scheduling?Problem，F(xiàn)JSP），其核心思想是：多批次多種類零部件可以在同類別多型號設(shè)備上加工生產(chǎn)。在正式加工前，每個零部件的工藝是唯一確定的，但工藝路線卻是不定的，每道工序有多種加工設(shè)備的選擇，即每個待加工零部件有多條工藝路線可以選擇，且設(shè)備選擇要基于設(shè)備能力平衡。相比傳統(tǒng)的車間調(diào)度問題而言，F(xiàn)JSP問題是更加復雜的NP-hard問題，解決此類問題要求算法具有更高的復雜性，但由于其更接近生產(chǎn)的實際情況，使得其成為了目前內(nèi)外調(diào)度領(lǐng)域的研究重點。

近年來，學者們對柔性車間調(diào)度也展開了大量的研究；現(xiàn)有技術(shù)中，“周輝仁，鄭丕諤，安小會等.基于遺傳算法求解Job?Shop調(diào)度優(yōu)化的新方法[J].系統(tǒng)仿真學報，2009，21(11)：3295-3306”和“Pezzella?F.A?genetic?algorithm?for?the?flexible?Job-Shop?scheduling?problem[J].Computers?and?Operations?Research，2007，21(9)：54-61”為了提高GA的搜索速度，提出了改善編碼方式優(yōu)化染色體的方法，使GA算法的時間與空間復雜度大大降低，但其調(diào)度狀況過于理論化，未能考慮環(huán)境變化，不具柔性。

“張國輝，高亮，李培根等.改進遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機械工程學報，2009，45(7)：145-151”中，結(jié)合FJSP問題特點，采用適當?shù)牟呗愿倪M了染色體編碼方式、交叉算子和變異算子，大大提高了算法求解精度，但其求解速度且沒有提高。

“紀樹新，錢積新，孫優(yōu)賢.車間作業(yè)調(diào)度遺傳算法中的編碼研究[J].信息與控制，1997，26(5)：393-400”中，為了消除GA只能應(yīng)用于成組技術(shù)JSS的局限性，提出了JSS連鎖基因編碼法，雖然提高了求解效率，但其染色體的空間復雜度仍較高。

“潘全科，朱劍英.基于Petri網(wǎng)和混合算法的作業(yè)車間優(yōu)化[J].計算機集成制造系統(tǒng)，2007，13(3)：580-584”、“陳維民，王波，衛(wèi)玉柯.Petri網(wǎng)的遺傳算法在Job-Shop問題中的應(yīng)用研究[J].哈爾濱理工大學學報，2008，13(1)：59-62”和“鞠全勇，朱劍英.基于混合遺傳算法的動態(tài)車間調(diào)度系統(tǒng)的研究[J].中國機械工程，2007，18(1)：40-43”中，首先建立了JSP的賦時變遷Petri網(wǎng)模型，然后應(yīng)用遺傳算法（Genetic?algorithm，GA）、模擬退火（Simulated?Annealing，SA）、粒子群優(yōu)化（Particle?Swarm?Optimization?PSO）算法其中一種或者混合二種算法解決該問題，其所用求解算法依然具有很高的時間和空間復雜度，沒能有效地同時提高算法的求解速度和精度。

“傅衛(wèi)平，劉冬梅，來春為，王雯.基于多色集合的改進遺傳算法求解多品種柔性調(diào)度問題[J].計算機集成制造系統(tǒng)，2011，17(5)：1004-1011”和“劉冬梅，傅衛(wèi)平等.改進遺傳算法求解柔性車間調(diào)度問題[J].西北大學學報，2011，41(4)：611-616”中，采用了更易描述數(shù)據(jù)邏輯關(guān)系的多色集合理論，排除了不可行解，極大地縮小了GA搜索解域，同時提出了用單層編碼方式表示調(diào)度問題中的雙重約束，降低了算法的時間和空間復雜度。但是該文獻所述算法只能在簡單情況下（工序?qū)?yīng)設(shè)備二選一），生成染色體，與實際應(yīng)用差距較大；且染色體采用的分段編碼是以最大工序數(shù)為基準單位生成，這就導致了算法在實踐中處理大規(guī)模多工序調(diào)度問題時出現(xiàn)染色體太長，無效數(shù)據(jù)過多等現(xiàn)象，需要進一步改進。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服上述現(xiàn)有技術(shù)的缺點，提供一種基于多色集合層次結(jié)構(gòu)的改進GA求解柔性車間調(diào)度的方法，該方法引入了多層次的約束描述方法，將原來巨大的圍道矩陣切分，降低了約束模型的冗余數(shù)據(jù)量，增加算法實際應(yīng)用的可能性；此外還改進了染色體的編碼方式，去除了大量的無效基因，從空間復雜度角度進一步優(yōu)化算法，提高收斂速度。

為達到上述目的，本發(fā)明采用的技術(shù)方案包括以下步驟：

1）建立柔性車間調(diào)度問題的數(shù)學模型；

2）建立基于PST層次結(jié)構(gòu)的車間調(diào)度約束模型；