[發明專利]一種基于禁忌搜索遺傳算法的車間柔性作業調度方法

在審

• 申請號: 202110841603.4
• 申請日: 2021-07-26
• 公開（公告）號: CN115700647A
• 公開（公告）日: 2023-02-07
• 發明（設計）人: 胡毅;吳文江;李廉頗;周正;于皓宇;張曦陽
• 申請（專利權）人: 沈陽中科數控技術股份有限公司
• 主分類號: G06Q10/0631
• 分類號: G06Q10/0631;G06Q10/0633;G06N3/126;G06Q50/04
• 代理公司: 沈陽科苑專利商標代理有限公司 21002
• 代理人: 王倩

1.一種基于禁忌搜索遺傳算法的車間柔性作業調度方法，其特征在于，包括以下步驟：

全局搜索：將任意一種車間柔性作業的調度方案作為一條染色體，對每條染色體分別進行種群編碼，并對編碼后的染色體進行交叉操作和變異操作，得到最終表示工序排序的變異編碼的染色體種群；

局部禁忌搜索：基于染色體種群中的染色體構建柔性調度方案析取圖模型，尋找關鍵路徑，在關鍵路徑上對工序進行刪除和插入操作，完成對局部區域的一次搜索，為局部搜索設置禁忌表和禁忌長度，尋找滿足禁忌表和禁忌長度的所有染色體，完成車間柔性作業的調度方案的優化。

2.根據權利要求1所述的一種基于禁忌搜索遺傳算法的車間柔性作業調度方法，其特征在于，所述種群編碼為分段編碼形式，第一段為機床選擇編碼，第二段為工序編碼；所述機床選擇編碼給每個工件的每個工序指定機床，所述工序編碼在機床選擇編碼的前提下，指定每一個機床的加工的工序順序。

3.根據權利要求2所述的一種基于禁忌搜索遺傳算法的車間柔性作業調度方法，其特征在于，所述機床選擇編碼具體為：根據柔性工作調度表，得到某一工件的某一工序對應的可選加工機床的集合，在集合中選擇一臺機床作為完成該工序使用的機床，對其進行編碼a，其編碼含義為：某一工序在可選加工機床的集合中選擇了第a臺機床，機床選擇編碼的長度為所有工件工序的數目總和。

4.根據權利要求2所述的一種基于禁忌搜索遺傳算法的車間柔性作業調度方法，其特征在于，所述工序編碼具體為：設置一個長度為機床數的時間數組Time[m]，數組初始化為0，每一項對應已經安排在此臺機床上加工的所有工序的時間和，隨機選擇一個工件，從當前工件的第一道工序開始，將可選加工機床的集合中每臺機床的加工時間與時間數組Time[m]中的對應時間相加，從中選擇最短的加工時間所對應的機床k，更新Time[k]的值為所選的最短加工時間加上機床k的已有加工時間；依次選擇工件的每一道工序，選擇最短加工時間并迭代更新時間數組，直至為所有工件選定工序加工的機床，根據機床選擇編碼，按照同一工件之間的先后順序約束條件，篩選隨機生成工序排序的編碼，得到工序編碼。

5.根據權利要求1或2所述的一種基于禁忌搜索遺傳算法的車間柔性作業調度方法，其特征在于，所述染色體交叉操作為：將種群編碼中的所有機床選擇編碼作為初始種群，選擇初始種群的兩條父代染色體，按照機床選擇編碼的長度，隨機生成元素為0、1的數組序列，在父代染色體parent1中選擇與數組序列中元素為0相對應的機床選擇編碼，并從父代染色體parent2中選擇與數組序列中元素為1相對應的機床選擇編碼，用從兩條父代染色體選出的編碼，按照在父代染色體中的原相對位置，組成新的子代染色體child1；用兩條父代染色體剩下的編碼，同樣按照原父代染色體相對位置，得到子代染色體child2。

6.根據權利要求1或2所述的一種基于禁忌搜索遺傳算法的車間柔性作業調度方法，其特征在于，所述染色體變異操作為：對機床選擇編碼部分，在迭代過程中按照固定概率隨機選出的染色體上，選擇兩個基因位，分別從可選加工機床的集合上選擇加工時間最短的機床編碼作為兩個基因位上的變異值；對工序編碼部分，按照固定的概率隨機選出染色體，根據變異操作確定的機床編碼，對每臺機床所要加工的工件工序隨機排序，然后用工件自身的加工順序對工件排序進行篩選，作為最終工序排序的變異編碼。

7.根據權利要求1所述的一種基于禁忌搜索遺傳算法的車間柔性作業調度方法，其特征在于，所述對染色體種群中的染色體構建柔性調度方案析取圖模型，具體為：將每條染色體在其局部鄰域內定義鄰域結構，并使用局部搜索策略通過移動關鍵路徑上工序的方式改變鄰域結構，所述關鍵路徑的長度為調度最大完工時間。