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

在審

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

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

步驟1、編碼：使用矩陣編碼，用一個(gè)n×m的矩陣來(lái)對(duì)種群P中的個(gè)體進(jìn)行編碼。

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

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

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

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

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

2.根據(jù)權(quán)利要求1所述的基于矩陣編碼遺傳算法的作業(yè)調(diào)度方法，其特征在于，步驟1使用矩陣編碼，用一個(gè)n×m的矩陣來(lái)對(duì)種群P中的個(gè)體進(jìn)行編碼，使用的矩陣表達(dá)式如下：

式(1)中：n為待裝配產(chǎn)品數(shù)量，m為待裝配產(chǎn)品的工序數(shù)量。每一行表示一個(gè)產(chǎn)品的所有工序，且工序是按照產(chǎn)品的工藝路線順序排列的；每一列表示每個(gè)產(chǎn)品的每道相同類型的工序；每個(gè)元素x_ij表示的是第i個(gè)產(chǎn)品在第j道工序選擇的工作臺(tái)編號(hào)和在工作臺(tái)等待裝配的序號(hào)，1≤i≤n，1≤j≤m。每個(gè)元素x_ij的值為一個(gè)隨機(jī)生成的實(shí)數(shù)，實(shí)數(shù)的整數(shù)部分a表示工作臺(tái)編號(hào)，實(shí)數(shù)的第一位小數(shù)b表示在該工作臺(tái)等待裝配的序號(hào)，c≤a≤d，0≤b≤9，且每個(gè)工作臺(tái)的b值不能重復(fù)，c表示每道工序第一個(gè)工作臺(tái)的編號(hào)，d表示每道工序最后一個(gè)工作臺(tái)的編號(hào)，需要說(shuō)明的是每道工序的工作臺(tái)總數(shù)相等，每個(gè)產(chǎn)品在每個(gè)工作臺(tái)進(jìn)行裝配的時(shí)間是固定的。

3.根據(jù)權(quán)利要求1所述的基于矩陣編碼遺傳算法的作業(yè)調(diào)度方法，其特征在于，步驟2進(jìn)行種群初始化，首先設(shè)定種群規(guī)模P_s并構(gòu)造相應(yīng)矩陣，然后在一定約束條件下隨機(jī)給每個(gè)個(gè)體編碼矩陣的元素賦一個(gè)實(shí)數(shù)值。