[發明專利]基于自適應遺傳和克隆選擇算法的模糊作業車間調度方法

在審

• 申請號: 201410502463.8
• 申請日: 2014-09-26
• 公開（公告）號: CN104281917A
• 公開（公告）日: 2015-01-14
• 發明（設計）人: 高尚策;陳貝貝;沈冬梅;侍倩;柴宏建;吳再新
• 申請（專利權）人: 東華大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 上海申匯專利代理有限公司 31001
• 代理人: 翁若瑩

技術領域

本發明涉及工業車間作業調度中加工工件和機器的調配方法。

背景技術

由于企業車間的生產計劃與控制問題在所有調度問題中最具典型性，所以對車間調度問題的研究一直在調度理論中占據主導地位。而生產過程中面臨的不確定因素，例如：機器故障、機器加工延誤、工件加工時間的不確定性、各工件交貨期的模糊性等，都會影響整個調度的安排和對調度結果的評估。而對于模糊車間調度問題的研究，更加符合實際生產，所以越來越多的學者開始研究模糊車間調度問題。

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

近年來研究模糊作業車間調度問題的方法有遺傳算法、模擬退火算法、啟發式算法等。算法基本原理都是基于一個初始解，按一定的方法搜索空間尋找最優解。這些研究存在一些缺陷：

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

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

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

發明內容

本發明要解決的技術問題是能夠合理調配車間調度生產計劃與控制問題。

為了解決上述技術問題，本發明的技術方案是提供了一種基于自適應遺傳和克隆選擇算法的模糊作業車間調度方法，其特征在于，包括以下步驟：

第一步、確定模糊車間調度的編碼方案為基于工序的編碼方式，每個基因代表一道工序，給同一工件的所有工序指定相同的符號，對于n個工件m臺機器的n×m模糊作業車間調度問題，每個染色體中包含n×m個基因，每個工件的符號將在染色體中出現m次；

第二步、隨機產生初始種群N，定義解空間；

第三步、定義并計算個體的適應度函數；

第四步、在第一次迭代時，每個個體初始的適應度值就是該個體的最優解，所對應的調度序列認為是初始最優序列使得模糊完工時間最小，在每一代最優解的附近，根據適應度值的大小進行克隆增殖操作，適應度越高，克隆出的個體數越多，反之，適應度越低，則克隆出的個體越少；

第五步、將繁殖之后的個體分別獨立的進行自適應交叉和自適應變異操作；

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

第七步、若滿足最大迭代次數，則結束；若不滿足，則返回到第三步繼續向下執行。

優選地，所述第二步具體為：

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

優選地，所述第三步具體為：

選擇一個函數使其能夠用函數值的大小較為準確地反映出解的優劣，該函數即為適應度函數；適應度函數根據優化問題的目標函數來確定，該適應度函數采用優化問題中的目標函數與一個常數c之和的倒數來表示。

優選地，所述第六步包括以下步驟：

步驟6.1、在進行遺傳操作后，計算每個個體的適應度值，每個父個體克隆得到的子個體中，適應度最高的個體Y_i易被優先選擇；

步驟6.2、利用爬坡更新規則，按一定的概率P挑選克隆的抗體Y_i來替換父抗體X_i，如果克隆體集合Y_i中最優個體的適應度比其父抗體X_i的適應度小，以概率1進行更新，如果最優子代的適應度大于它的父代，以指數型概率進行更新，以保持群體多樣性。

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

本發明不同于其它的單一方法，而是將自適應遺傳算法與克隆選擇算法相結合的一種新的混合算法，具有兩種算法的優點。本發明能夠合理分配資源，縮短車間調度模糊完工時間，提高作業車間模糊調度的效率，更加符合實際的生產調度。

附圖說明

圖1為本發明的算法流程圖；

圖2為6×6模糊調度問題的目標函數收斂曲線；

圖3為10×10模糊調度問題的目標函數收斂曲線。

具體實施方式