[發(fā)明專利]一種基于混合遺傳算法求解柔性作業(yè)車間調(diào)度的方法

在審

• 申請?zhí)枺?/td>: 202010731003.8
• 申請日: 2020-07-27
• 公開（公告）號: CN111967654A
• 公開（公告）日: 2020-11-20
• 發(fā)明（設計）人: 毋濤;賈培豪;齊琦;李科;崔璐;任永亮;潘華峰;陳莉媛;劉青青
• 申請（專利權(quán)）人: 西安工程大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06N3/00;G06Q50/04
• 代理公司: 西安弘理專利事務所 61214
• 代理人: 弓長

本發(fā)明公開了一種基于混合遺傳算法求解柔性作業(yè)車間調(diào)度的方法，具體按照以下步驟實施：1、定義柔性作業(yè)車間調(diào)度編碼方式為雙層編碼方式；2、定義適應度函數(shù)，以求解完成加工的最短時間為優(yōu)化目標；3、采用遺傳算法和鯨魚群算法對柔性車間調(diào)度問題中的參數(shù)以及種群初始化，隨機生成初始種群；4、通過遺傳算法求解柔性作業(yè)車間調(diào)度；5、通過鯨魚群算法求解柔性作業(yè)車間調(diào)度；6、通過編碼重組，實現(xiàn)鯨魚群算法對遺傳算法的迭代優(yōu)化，輸出最優(yōu)調(diào)度方案。本發(fā)明的方法提高了算法的搜索深度，增強了求解精度與求解穩(wěn)定性。

技術(shù)領域

本發(fā)明屬于柔性作業(yè)車間調(diào)度技術(shù)領域，涉及一種基于混合遺傳算法求解柔性作業(yè)車間調(diào)度的方法。

背景技術(shù)

傳統(tǒng)的作業(yè)車間調(diào)度問題(Job-shop Scheduling Problem，JSP)中，一道工序只存在一臺加工機器，但在企業(yè)實際車間生產(chǎn)過程中往往會出現(xiàn)并行機器的現(xiàn)象，這就導致傳統(tǒng)的作業(yè)車間調(diào)度不能很好地滿足企業(yè)實際需求，由此，柔性作業(yè)車間調(diào)度問題(Flexible Job-shop Scheduling Problem，F(xiàn)JSP)便應運而生了。FJSP是JSP的一種擴展，它相較于JSP而言更為靈活，在規(guī)定工序的同時，還需對每道工序分配加工機器，是復雜的NP(Non-deterministic Polynomial Complete，即多項式復雜程度的非確定性)的問題。正是由于FJSP具有較高的復雜性和解的靈活性，所以它更符合車間生產(chǎn)的實際需求，因此成為了車間調(diào)度領域的重點研究方向。

現(xiàn)有的多層次空間競爭性分布式遺傳算法的算法求解FJSP，雖然具有競爭優(yōu)勢，但是計算成本較高；改進模擬退火算法求解FJSP，該算法具有部分調(diào)度機制和冷卻機制，較之標準模擬退火算法有著更快的收斂速度；針對蟻群算法求解FJSP問題時計算效率低且容易陷入局部最優(yōu)解的情況提出了一種結(jié)合先驗知識、概率搜索和隨機搜索的新節(jié)點選擇方法，當搜索陷入局部最優(yōu)解中時，可以通過調(diào)整信息素并增加隨機選擇概率來進一步搜索解空間，從而實現(xiàn)對傳統(tǒng)蟻群算法的優(yōu)化；基于改進灰狼算法求解柔性車間調(diào)度問題提出一種改進灰狼算法求解FJSP，改進狼群初始化機制，通過結(jié)合遺傳算法和模擬退火算法提出一種哨兵狼機制，提高了種群多樣性，改進了灰狼優(yōu)化算法收斂慢、容易早熟的缺點。綜上所述，單一的智能算法在求解FJSP時或多或少存在著一些不足，如計算效率低下、求解穩(wěn)定性差等，因此對傳統(tǒng)智能算法進行改進亦或是將多種智能算法混合使用來優(yōu)化傳統(tǒng)智能算法的不足是研究的必然趨勢。

對1990年到2014年期間發(fā)表的191篇關(guān)于求解柔性作業(yè)車間調(diào)度問題的論文進行調(diào)查分析，發(fā)現(xiàn)34％的論文都是通過遺傳算法或混合遺傳算法來求解FJSP。由此可知，遺傳算法已經(jīng)是解決FJSP的主流方法，但遺傳算法在實際應用過程中往往容易陷入局部最優(yōu)陷阱。因此本文提出一種鯨魚群-遺傳混合算法，通過將鯨魚群算法與遺傳算法結(jié)合使用來提高標準遺傳算法求解FJSP時的搜索深度，進而改善遺傳算法容易陷入局部最優(yōu)陷阱的不足。

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

本發(fā)明的目的是提供一種基于混合遺傳算法求解柔性作業(yè)車間調(diào)度的方法，解決了現(xiàn)有技術(shù)中存在的柔性作業(yè)車間調(diào)度問題中求解結(jié)果不穩(wěn)定、求解精度低問題。

本發(fā)明所采用的技術(shù)方案是，一種基于混合遺傳算法求解柔性作業(yè)車間調(diào)度的方法，具體按照以下步驟實施：

步驟1、定義柔性作業(yè)車間調(diào)度編碼方式為雙層編碼方式；

步驟2、定義適應度函數(shù)，以求解完成加工的最短時間為優(yōu)化目標；

步驟3、采用遺傳算法和鯨魚群算法對柔性車間調(diào)度問題中的參數(shù)以及種群初始化，隨機生成初始種群；

步驟4、通過遺傳算法求解柔性作業(yè)車間調(diào)度；

步驟5、通過鯨魚群算法求解柔性作業(yè)車間調(diào)度；