[發明專利]基于多色集合的改進遺傳算法求解靜態車間調度的方法

在審

• 申請號: 201810090479.0
• 申請日: 2018-01-30
• 公開（公告）號: CN108364126A
• 公開（公告）日: 2018-08-03
• 發明（設計）人: 欒飛;陳夢瑤;石冰潔;李媛鳴;來春為;傅衛平;祝曉雪;張淼
• 申請（專利權）人: 陜西科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

本發明公開了一種基于多色集合的改進遺傳算法求解靜態車間調度的方法，該方法實現了遺傳算法與多色集合理論的柔性車間作業調度的方法，將遺傳算法與多色集合理論應用到了柔性車間作業調度中，目的是為了給車間調度問題提供一種合適的算法使作業時間最短，減少成本。本發明應用基于多色集合理論的改進遺傳算法，具體使用到了遺傳算法和多色集合理論，這些算法可以針對不同的機床與工序關系，推薦最優的車間調度安排。

技術領域

本發明屬于柔性車間調度安排技術領域，涉及一種基于多色集合的改進遺傳算法求解靜態車間調度的方法。

背景技術

傳統作業車間調度問題的實質就是合理、科學地安排任務與資源之間的關系，且預先確定每到工序的加工順序、加工機床和加工時間。柔性作業車間調度問題可以表述為：當多個工件在多個機床上進行加工時，其工藝路線再加工前不能完全確定，即每個工件的加工路線可能有幾條，每條路線的選擇狀況需根據機床的空閑狀況決定。因為FJSP增加了機床的不確定性，擴大了解域，增加了問題優化過程的難度，所以是更加復雜的NP-hard問題，即此類問題具有更高算法復雜性，但由于它更符合實際的生產狀況，是現有調度類問題的研究終點。

應用傳統遺傳算法對各類JSSP機型求解，其特點是簡單，容易實現，并能夠迅速求得一個較優解，說明了GA在求解調度問題中的潛力和有效性。通過改進GA的編碼提高問題求解的效率，是的GA編碼的時間與空間復雜度大大降低，但其研究的調度狀況過于單一，不舉辦生產柔性。結合JFSP的特點，恰當地改進了染色體編碼方式、交叉算子和變異算子，簡化了染色體的修復過程，提高了求解效率，但其染色體的空間復雜度仍較高。由此可以看出，采用GA來解決FJSP問題的關鍵在于改進染色體的編碼、交叉和變異方式，從而提高算法效率。

因為GA的優化過程并非直接應用于問題空間本身，而是再對應的碼空間上進行搜索，所以良好的編碼方式有助于提高GA的搜索小了和解的治理。利用多色集合理論中的圍道矩陣、同一顏色、個人顏色等概念，從功能分解和約束條件等多方面進行了數學形式的描述和推理，并證明了多色集合應用于模型建立的優越性，但它在對GA進行編碼是仍采用雙層編碼形式，無形中增加了算法的空間和時間復雜度。

傳統遺傳算法具有很強的全局搜索能力，從任意初始種群出發，最終都會找到全局。但當種群數量過大時，遺傳算法由于存在“早熟”的收斂問題，即算法由于收斂到局部最優解或是種群中不能再生成性能超過父代的個體，而不再進行進化的現象。

發明內容

本發明的目的在于克服上述現有技術的缺點，提供一種基于多色集合的改進遺傳算法求解靜態車間調度的方法，該方法通過圍道布爾矩陣的約束以及隱性染色體的交叉變異，得到最優的新染色體，找到靜態車間調度的最優方案。

為達到上述目的，本發明采用以下技術方案予以實現：

一種基于多色集合的改進遺傳算法求解靜態車間調度的方法，包括以下步驟：

步驟1：獲取車間加工任務、設備和工序的具體信息，使用對色集合理論來描述靜態車間調度任務中待加工工序所受到的工藝與機床的具體約束；

步驟2：確定靜態車間調度的具體約束，用調度約束表達式表示，用“1”和“0”分別表示指標變量x_ihk和指標系數a_ihk；

步驟3：根據具體的加工信息繪制加工任務信息表，進而創建圍道矩陣，來表達調度約束條件；

步驟4：根據工序－機床圍道布爾矩陣，生成工序隱性編碼序列表，由工序隱性編碼序列表，生成工藝-設備的邏輯圍道矩陣[A×F(A)]及其實數圍道矩陣[A×A(F)]；

步驟5：在模型約束下進行隱性染色體編碼；

步驟6：據染色體的隱性編碼信息獲取各工序對應機床所需加工時間，得出各工序的完工時間及機床的釋放時間；步驟7：按照柔性車間調度理論，創建目標函數；