[發(fā)明專利]基于自適應(yīng)遺傳和克隆選擇算法的模糊作業(yè)車間調(diào)度方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410502463.8
• 申請(qǐng)日: 2014-09-26
• 公開(kāi)（公告）號(hào): CN104281917A
• 公開(kāi)（公告）日: 2015-01-14
• 發(fā)明（設(shè)計(jì)）人: 高尚策;陳貝貝;沈冬梅;侍倩;柴宏建;吳再新
• 申請(qǐng)（專利權(quán)）人: 東華大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06N3/12
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 翁若瑩

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

本發(fā)明涉及工業(yè)車間作業(yè)調(diào)度中加工工件和機(jī)器的調(diào)配方法。

背景技術(shù)

由于企業(yè)車間的生產(chǎn)計(jì)劃與控制問(wèn)題在所有調(diào)度問(wèn)題中最具典型性，所以對(duì)車間調(diào)度問(wèn)題的研究一直在調(diào)度理論中占據(jù)主導(dǎo)地位。而生產(chǎn)過(guò)程中面臨的不確定因素，例如：機(jī)器故障、機(jī)器加工延誤、工件加工時(shí)間的不確定性、各工件交貨期的模糊性等，都會(huì)影響整個(gè)調(diào)度的安排和對(duì)調(diào)度結(jié)果的評(píng)估。而對(duì)于模糊車間調(diào)度問(wèn)題的研究，更加符合實(shí)際生產(chǎn)，所以越來(lái)越多的學(xué)者開(kāi)始研究模糊車間調(diào)度問(wèn)題。

到目前為止，Han?S等人研究了具有模糊交貨期的單機(jī)調(diào)度問(wèn)題；SAKAWA等人在1999年采用遺傳算法求解帶有模糊加工時(shí)間和模糊交貨期的模糊車間調(diào)度問(wèn)題，使得最小客戶滿意度最大。Ishibuchi?H等人對(duì)模糊作業(yè)車間調(diào)度問(wèn)題進(jìn)行了研究，并對(duì)模糊加工時(shí)間進(jìn)行了描述。Murata?T等人對(duì)具有模糊交貨期的多目標(biāo)調(diào)度問(wèn)題進(jìn)行了研究。Adamopulos?G?I用鄰域搜索方法對(duì)具有可變加工時(shí)間和模糊交貨期的單機(jī)調(diào)度問(wèn)題進(jìn)行了研究。

近年來(lái)研究模糊作業(yè)車間調(diào)度問(wèn)題的方法有遺傳算法、模擬退火算法、啟發(fā)式算法等。算法基本原理都是基于一個(gè)初始解，按一定的方法搜索空間尋找最優(yōu)解。這些研究存在一些缺陷：

(1)算法比較單一，尋找過(guò)程比較盲目。

(2)尋找最優(yōu)解容易陷入局部最優(yōu)，算法容易早熟收斂。

(3)更新種群比較隨機(jī)。

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

本發(fā)明要解決的技術(shù)問(wèn)題是能夠合理調(diào)配車間調(diào)度生產(chǎn)計(jì)劃與控制問(wèn)題。

為了解決上述技術(shù)問(wèn)題，本發(fā)明的技術(shù)方案是提供了一種基于自適應(yīng)遺傳和克隆選擇算法的模糊作業(yè)車間調(diào)度方法，其特征在于，包括以下步驟：

第一步、確定模糊車間調(diào)度的編碼方案為基于工序的編碼方式，每個(gè)基因代表一道工序，給同一工件的所有工序指定相同的符號(hào)，對(duì)于n個(gè)工件m臺(tái)機(jī)器的n×m模糊作業(yè)車間調(diào)度問(wèn)題，每個(gè)染色體中包含n×m個(gè)基因，每個(gè)工件的符號(hào)將在染色體中出現(xiàn)m次；

第二步、隨機(jī)產(chǎn)生初始種群N，定義解空間；

第三步、定義并計(jì)算個(gè)體的適應(yīng)度函數(shù)；

第四步、在第一次迭代時(shí)，每個(gè)個(gè)體初始的適應(yīng)度值就是該個(gè)體的最優(yōu)解，所對(duì)應(yīng)的調(diào)度序列認(rèn)為是初始最優(yōu)序列使得模糊完工時(shí)間最小，在每一代最優(yōu)解的附近，根據(jù)適應(yīng)度值的大小進(jìn)行克隆增殖操作，適應(yīng)度越高，克隆出的個(gè)體數(shù)越多，反之，適應(yīng)度越低，則克隆出的個(gè)體越少；

第五步、將繁殖之后的個(gè)體分別獨(dú)立的進(jìn)行自適應(yīng)交叉和自適應(yīng)變異操作；

第六步、對(duì)交叉和變異之后的個(gè)體進(jìn)行克隆選擇操作，生成新種群N*；

第七步、若滿足最大迭代次數(shù)，則結(jié)束；若不滿足，則返回到第三步繼續(xù)向下執(zhí)行。

優(yōu)選地，所述第二步具體為：

初始化染色體種群，參數(shù)至少包括：種群規(guī)模、克隆系數(shù)、自適應(yīng)交叉概率和變異概率、代溝、最大迭代次數(shù)。

優(yōu)選地，所述第三步具體為：

選擇一個(gè)函數(shù)使其能夠用函數(shù)值的大小較為準(zhǔn)確地反映出解的優(yōu)劣，該函數(shù)即為適應(yīng)度函數(shù)；適應(yīng)度函數(shù)根據(jù)優(yōu)化問(wèn)題的目標(biāo)函數(shù)來(lái)確定，該適應(yīng)度函數(shù)采用優(yōu)化問(wèn)題中的目標(biāo)函數(shù)與一個(gè)常數(shù)c之和的倒數(shù)來(lái)表示。

優(yōu)選地，所述第六步包括以下步驟：

步驟6.1、在進(jìn)行遺傳操作后，計(jì)算每個(gè)個(gè)體的適應(yīng)度值，每個(gè)父?jìng)€(gè)體克隆得到的子個(gè)體中，適應(yīng)度最高的個(gè)體Y_i易被優(yōu)先選擇；

步驟6.2、利用爬坡更新規(guī)則，按一定的概率P挑選克隆的抗體Y_i來(lái)替換父抗體X_i，如果克隆體集合Y_i中最優(yōu)個(gè)體的適應(yīng)度比其父抗體X_i的適應(yīng)度小，以概率1進(jìn)行更新，如果最優(yōu)子代的適應(yīng)度大于它的父代，以指數(shù)型概率進(jìn)行更新，以保持群體多樣性。

優(yōu)選地，在所述步驟6.2中，為了保存原始種群的信息，指數(shù)函數(shù)不用于X₁代，初代個(gè)體中的最佳抗體不能被替換。

本發(fā)明不同于其它的單一方法，而是將自適應(yīng)遺傳算法與克隆選擇算法相結(jié)合的一種新的混合算法，具有兩種算法的優(yōu)點(diǎn)。本發(fā)明能夠合理分配資源，縮短車間調(diào)度模糊完工時(shí)間，提高作業(yè)車間模糊調(diào)度的效率，更加符合實(shí)際的生產(chǎn)調(diào)度。

附圖說(shuō)明

圖1為本發(fā)明的算法流程圖；

圖2為6×6模糊調(diào)度問(wèn)題的目標(biāo)函數(shù)收斂曲線；

圖3為10×10模糊調(diào)度問(wèn)題的目標(biāo)函數(shù)收斂曲線。

具體實(shí)施方式