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

在審

• 申請?zhí)枺?/td>: 201610109280.9
• 申請日: 2016-02-27
• 公開（公告）號: CN106611220A
• 公開（公告）日: 2017-05-03
• 發(fā)明（設(shè)計(jì)）人: 湯琴;胡成華
• 申請（專利權(quán)）人: 四川用聯(lián)信息技術(shù)有限公司
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種新的混合算法求解柔性作業(yè)車間調(diào)度問題，該算法涉及作業(yè)車間調(diào)度技術(shù)領(lǐng)域，具體地涉及用算法求解柔性作業(yè)車間調(diào)度問題，其特征是：該算法的具體實(shí)施步驟如下：

步驟1：令群體進(jìn)化迭代次數(shù)t=0，更新頻率記錄次數(shù)f=0，并初始化算法的各種參數(shù)、主群體空間、信仰空間A和信仰空間B；

步驟2：如果tMaxlter(最大迭代次數(shù))則算法結(jié)束，否則轉(zhuǎn)到下一步驟；

步驟3：根據(jù)更新頻率f0,決定是否更新信仰空間，若f= f0，則更新；否則轉(zhuǎn)步驟5；

步驟4：采用k近鄰法，利用信仰空間B的知識指導(dǎo)，執(zhí)行相似性選擇算子操作；

步驟5：采用兩點(diǎn)交叉的方式進(jìn)行交叉操作；

步驟6：自學(xué)習(xí)鄰域搜索變異，將進(jìn)行變異的染色體與信仰空間A中最優(yōu)染色體進(jìn)行比較，根據(jù)基因取值不同的數(shù)量決定變異操作的方式；

步驟7：生成新一代種群，令t=t+1, f=f+1，返回步驟2，重復(fù)此程序。

2.根據(jù)權(quán)利要求1所述的一種新的混合算法求解柔性作業(yè)車間調(diào)度問題，其特征是：本發(fā)明采用重復(fù)置換工件號的編碼方式，即對一個規(guī)模為n×m的作業(yè)車間調(diào)度而言,一條染色體有n× m個基因,每個基因表示一個工件號,工件號在染色體中出現(xiàn)的位置表示其對應(yīng)的工序，這種編碼方式的優(yōu)點(diǎn)是不需要修復(fù)機(jī)制,因?yàn)樗M(jìn)行的遺傳操作不產(chǎn)生不可行解。

3.根據(jù)權(quán)利要求1所述的一種新的混合算法求解柔性作業(yè)車間調(diào)度問題，其特征是：本算法的解碼采用活動調(diào)度的方法，其所生成的調(diào)度方案一定包含最優(yōu)值。

4.根據(jù)權(quán)利要求1所述的一種新的混合算法求解柔性作業(yè)車間調(diào)度問題，其特征是：本算法的信仰空間由A和B兩部分構(gòu)成，分別由接受函數(shù)（）和來決定，假設(shè)主群體空間中共有L條染色體，令表示主群體空間中第條染色體，的適應(yīng)度值為其對應(yīng)調(diào)度方案的所有工件的最大完工時間，則信仰空間A為：

（）：A=

，

即由最優(yōu)染色體構(gòu)成信仰空間A，信仰空間B為：

QUOTE：B=

首先按照染色體的適應(yīng)度值的大小，依次排列為，然后取前x個個體存放到信仰空間B中，即，選擇既定數(shù)量為x的部分最優(yōu)染色體組成信仰空間B。

5.根據(jù)權(quán)利要求1所述的一種新的混合算法求解柔性作業(yè)車間調(diào)度問題，其特征是：本算法的信仰空間的更新方法是：每迭代既定的次數(shù)后，更新信仰空間，使信仰空間持續(xù)保存當(dāng)前最好的知識信息，因此，本算法采用當(dāng)前最好的部分調(diào)度方案作為學(xué)習(xí)對象，將信仰空間相鄰兩次更新之間的算法迭代次數(shù)稱為更新頻率，記住f0。

6.根據(jù)權(quán)利要求1所述的一種新的混合算法求解柔性作業(yè)車間調(diào)度問題，其特征是：本發(fā)明采用鄰域搜索變異，使變異操作在信仰空間A中知識的指導(dǎo)下以更寬的搜索區(qū)域進(jìn)行迭代，具體實(shí)現(xiàn)過程如下：

（1）確定變異點(diǎn)的選擇范圍，根據(jù)變異概率在子空間中隨機(jī)選擇一條染色體，與最優(yōu)染色體比較，并記錄基因取值不同的染色體位置pos和個數(shù)q（q為偶數(shù)）；（2）根據(jù)q的大小進(jìn)行不同的變異操作：

一種變異操作：當(dāng)q2時，隨機(jī)選擇變異點(diǎn)，進(jìn)行鄰域搜索變異；

另一種變異操作：當(dāng)q4時，則先產(chǎn)生一個由1到q之間的整數(shù)所組成的隨機(jī)序列P，令u表示進(jìn)行鄰域搜索變異的基因個數(shù)，v表示循環(huán)次數(shù)，w表示最大循環(huán)次數(shù)，且w為q/u向下取整，即w=，一般情況下，u=3，具體過程如下：1）令v=1；2）從左到右依次取隨機(jī)序列P上的3個元素P、P、P來決定pos上進(jìn)行鄰域搜索變異的基因位置；3）進(jìn)行鄰域搜索變異；4）將，若vw則轉(zhuǎn)到2），否則算法結(jié)束；

從中可以看出，q的數(shù)值越大，說明被變異染色體和最優(yōu)染色體之間的基因取值不同的位置越多；反之，則越少，該變異方式有自學(xué)習(xí)的特點(diǎn)，其時間復(fù)雜度為O(q)，其中q等于當(dāng)前染色體與信仰空間A中染色體之間基因位置取值相異點(diǎn)的個數(shù)，其偽代碼如下：

。

7.根據(jù)權(quán)利要求1所述的一種新的混合算法求解柔性作業(yè)車間調(diào)度問題，其特征是：本發(fā)明采用K近鄰法，利用信仰空間B中的知識指導(dǎo)選擇操作，具體過程如下：

（1）利用基于輪盤賭的選擇方式生成初始子群體空間；

（2）在子群體空間中選擇既定數(shù)量為k的優(yōu)良個體集合,根據(jù)k近鄰法將這些個體與信仰空間B中的染色體進(jìn)行相似性指數(shù)計(jì)算；

（3）查找k個相似性指數(shù)Sd最大的個體,并將這些個體插入到當(dāng)前子群體空間中,同時淘汰掉k個最差的個體，其相似性指數(shù)計(jì)算公式如下:

（1）

如果兩條染色體中對應(yīng)基因位置的取值相同，則返回值為1，否則為0，其計(jì)算公式如下：

其中，和分別表示兩條染色體，表示染色體中基因所處的位置，y表示染色體的長度，一般在規(guī)模為n× m的作業(yè)車間調(diào)度問題中其大小為y= nm；

本算法通過計(jì)算Sd相似性指數(shù)可以推出兩個解之間的相近程度，如果相似性指數(shù)Sd的取值越大，則兩條染色體就越相近,反之亦然。