[發明專利]一種新的混合算法求解柔性作業車間調度問題

在審

• 申請號: 201610109280.9
• 申請日: 2016-02-27
• 公開（公告）號: CN106611220A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 湯琴;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

所屬技術領域

本發明涉及作業車間調度技術領域，具體地涉及用算法求解柔性作業車間調度問題。

背景技術

柔性作業車間調度問題(FJSP)是經典的作業車間調度問題(JSP)的擴展。在JSP中，僅考慮工件具有唯一確定的加工工藝路線的情況。而在FJSP中，每道工序可以在多臺機器上加工，工件具有可選擇的加工路線，并且在不同的機器上加工所需的時間不同，因此FJSP比JSP更接近實際制造環境，是實際生產中亟需解決的一類調度問題。

FJSP不僅需要確定工件的加工順序，還要確定某道工序由哪臺機器加工。因此，FJSP是比JSP更為復雜的問題。現有的研究方法主要分為精確算法、啟發式規則和元啟發式算法(如模擬退火、遺傳算法等)。其中精確算法無法對大規模FJSP進行有效求解；啟發式規則求解速度快，但所得質量較差；遺傳算法具有通用性、魯棒性、隱含并行性等特點，在生產調度領域的應用非常廣泛，但其迭代迭代過程是沒有指導且完全隨機的自然選擇與遺傳操作，忽視了問題的特征信息在求解問題時的重要作用。

發明內容

針對上述不足，本發明將文化算法與遺傳算法結合，文化算法由主群體空間和信仰空間兩部分組成，是一種從種群中獲取有用的知識保存在信仰空間中，并利用這些知識指導搜索過程，是一種基于知識的多進化過程的全局優化搜索算法。本發明針對FJSP的特點，提出基于知識指導的遺傳算法，采用遺傳算法作為主群體空間，該算法在迭代過程中利用文化算法的尋優機制提取解的特征知識，指導遺傳算法的選擇操作，形成一種雙層進化結構。

本發明的目的是：提高算法的收斂速率和求解質量。

本發明為實現上述目的，所采用的技術方案是：一種新的混合算法求解柔性作業車間調度問題。該技術方案包括以下步驟：

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

步驟2：如果t≥Maxlter(最大迭代次數)則算法結束，否則轉到下一步驟；

步驟3：根據更新頻率f0，決定是否更新信仰空間，若f＝f0，則更新；否則轉步驟5；

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

步驟5：采用兩點交叉的方式進行交叉操作；

步驟6：自學習鄰域搜索變異，將進行變異的染色體與信仰空間A中最優染色體進行比較，根據基因取值不同的數量決定變異操作的方式；

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

本發明的有益效果是：本發明基于文化算法具有知識指導的特點，提出具有知識指導的遺傳算法，在迭代過程中利用文化算法的尋優機制提取解的特征知識，指導遺傳算法的選擇操作，形成雙層進化結構，使個體在搜索空間中加快了收斂速度，避免出現了早熟而收斂于局部最優解。同時，通過計算相似性指數來指導選擇操作確保優秀個體進入下一次迭代的子空間；通過在指定范圍的變異點進行自學習鄰域操作變異，保證個體在迭代過程中有效繼承父代的優良特征，從而加速搜索過程不斷向最優的方向逼近。

附圖說明：

圖1表示本算法的詳細流程圖

圖2表示本算法的重復置換工件號的編碼方式示例圖

具體實施方式：

本發明提出了一種新的混合算法求解柔性作業車間調度問題，該算法基于文化算法具有知識指導的特點，提出具有知識指導的遺傳算法，在迭代過程中利用文化算法的尋優機制提取解的特征知識，指導遺傳算法的選擇操作，形成雙層進化結構。

下面結合附圖，對本發明進一步的描述：

一、柔性作業車間調度問題

柔性作業車間調度描述如下：一個加工系統有m臺不同的機器M＝{M_j|j＝1，2，…m}要加工n個工件J＝{J_i|i＝1，2，…n}。FJSP包括兩個子問題：(1)為每道工序O_ik在對應的可用機器集合M_ik中選擇合適的機器M_j，即機器分配問題。

(2)為已經選定的機器集M安排n個工件集J的排列工序，并在滿足一定約束條件的同時優化一個或者多個給定的性能指標，即工件調度問題。

二、算法的關鍵內容說明

1、編碼方式，結合圖2