[發(fā)明專利]一種基于矩陣編碼遺傳算法的作業(yè)調(diào)度方法

在審

• 申請?zhí)枺?/td>: 202110631876.6
• 申請日: 2021-06-07
• 公開（公告）號: CN113379225A
• 公開（公告）日: 2021-09-10
• 發(fā)明（設計）人: 楊開偉;張壯壯;趙雅楠;童一飛
• 申請（專利權）人: 南京理工大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/04;G06N3/12
• 代理公司: 常州易瑞智新專利代理事務所(普通合伙) 32338
• 代理人: 孫盼盼

本發(fā)明提出了一種基于矩陣編碼遺傳算法的作業(yè)調(diào)度方法，首先使用矩陣編碼，用一個n×m的矩陣來對種群中的個體進行編碼；然后進行種群初始化，在一定約束條件下，給種群中每個個體的元素隨機賦一個實數(shù)值；再計算適應度函數(shù)為使產(chǎn)品最大裝配完成時間最小的函數(shù)值。若滿足終止條件，則將適應度值最小的個體編碼矩陣進行解碼并輸出產(chǎn)品裝配方案；否則，進行選擇、交叉、變異等遺傳操作并生成新種群來重新計算適應度值，直到滿足終止條件。本發(fā)明可以得到合理、可靠的產(chǎn)品裝配方案，基于矩陣編碼的遺傳算法實現(xiàn)方法簡便、計算效率高，可改善目前作業(yè)調(diào)度方法實現(xiàn)復雜和效率低下等情況。

技術領域

本發(fā)明屬于車間作業(yè)調(diào)度領域，特別是一種基于矩陣編碼遺傳算法的作業(yè)調(diào)度方法。

背景技術

車間作業(yè)調(diào)度是企業(yè)實現(xiàn)資源合理分配、降低生產(chǎn)成本、提高生產(chǎn)效率和提升客戶滿意度的主要途徑，它對企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。車間作業(yè)調(diào)度負責根據(jù)訂單生產(chǎn)信息，在有限資源的前提下，為產(chǎn)品的生產(chǎn)制造制定計劃并分配必要的資源。隨著先進制造技術的普及和信息技術的發(fā)展，企業(yè)的生產(chǎn)正朝著多品種、變批量、有著不同完工時間和產(chǎn)品要求的方向發(fā)展，從而使得企業(yè)的生產(chǎn)作業(yè)計劃安排難度加大。因此選擇合理、高效的調(diào)度算法來進行作業(yè)計劃的制定，成為車間作業(yè)調(diào)度研究中的重要環(huán)節(jié)。

車間作業(yè)調(diào)度算法有很多，目前使用的比較多的有遺傳算法、蟻群算法和模擬退火算法等等。蟻群算法局部搜索能力強、搜尋結(jié)果穩(wěn)定，但是全局尋優(yōu)能力差、計算過程復雜。模擬退火算法局部尋優(yōu)能力強、收斂速度快，但是依賴參數(shù)設置、計算時間長。與上述兩種算法相比，遺傳算法具有明顯的優(yōu)勢。一方面，遺傳算法總體尋優(yōu)能力較強，解決車間調(diào)度問題時它可以從一種調(diào)度方案跳到另一種調(diào)度方案，從而可以解決其他算法易于陷入局部最優(yōu)的問題。另一方面，遺傳算法計算速度快且易與其他算法結(jié)合，這對于解決車間動態(tài)調(diào)度問題是十分有利的。但是目前遺傳算法的編碼方式、選擇操作、交叉操作和變異操作都較為復雜，這導致它實施起來很不方便。

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

本發(fā)明的目的在于提供一種基于矩陣編碼遺傳算法的作業(yè)調(diào)度方法，以幫助企業(yè)方便、高效地進行車間作業(yè)調(diào)度。

實現(xiàn)本發(fā)明目的的技術解決方案為：

一種基于矩陣編碼遺傳算法的作業(yè)調(diào)度方法，包括以下步驟：

步驟1、編碼：使用矩陣編碼，用一個n×m的矩陣來對種群P中的個體進行編碼。

步驟2、種群初始化：設定種群規(guī)模P_s，并在一定約束條件下給種群中每個個體的元素隨機賦一個實數(shù)值。

步驟3、計算適應度：適應度函數(shù)為使產(chǎn)品的最大裝配完成時間最小。分別計算當前種群中個體的適應度值。

步驟4、設置終止條件：終止條件為迭代次數(shù)T。當超過一定的迭代次數(shù)后，算法終止并輸出最小的適應度值和對應的個體矩陣編碼；否則，進行步驟6。

步驟5、解碼：根據(jù)矩陣編碼規(guī)則對適應度值最小的個體編碼矩陣進行解碼，輸出產(chǎn)品裝配方案。

步驟6、進行遺傳操作：設定交叉概率P_c和變異概率P_m。首先，根據(jù)當前種群中個體的適應度值來進行選擇操作，得到父代種群和母代種群。然后，在交叉概率P_c下將父代種群個體的編碼矩陣和母代種群個體的編碼矩陣進行交叉，來生成新種群。最后，在變異概率P_m下將新種群個體的編碼矩陣中的元素進行變異，得到變異后的新種群。以變異后的新種群來進行步驟3。

本發(fā)明與現(xiàn)有技術相比，其顯著優(yōu)點是：

(1)本發(fā)明的基于矩陣編碼遺傳算法的作業(yè)調(diào)度方法，相較于其他編碼復雜的遺傳算法，只需要通過一個矩陣即可進行編碼，大大降低了編碼和解碼過程的難度。