[發明專利]改良文化基因算法求解帶運輸時間柔性作業車間調度方法

在審

• 申請號: 201910885114.1
• 申請日: 2019-09-19
• 公開（公告）號: CN110598943A
• 公開（公告）日: 2019-12-20
• 發明（設計）人: 張國輝;孫靖賀;張海軍;閆瓊;劉星;賈佳;宋曉輝;張理濤
• 申請（專利權）人: 鄭州航空工業管理學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/04;G06N3/12
• 代理公司: 41178 鄭州豫鼎知識產權代理事務所(普通合伙)
• 代理人: 魏新培

1.改良文化基因算法求解帶運輸時間柔性作業車間調度方法，其特征在于，包括以下步驟：

步驟一：參數設置，設置文化基因算法求解帶運輸時間的FJSP的相關參數，包括：種群規模N_pop、完全隨機初始化概率P_A、優先最小加工時間初始化概率P_B、優先最大剩余加工時間初始化概率P_C、迭代次數N_iter、最優解保留代數N_re、交叉概率P_xovr、初始變異概率P_mutr0、初始溫度T₀、終止溫度T_f、擾動次數L_k、溫度衰減系數α、調整系數t、精英庫規模N_E；

文化基因算法的終止條件為：若在還未達到迭代次數N_iter時，當前最優解保留N_re代不發生變化，算法終止；否則，運行到迭代次數為止；

步驟二：結合柔性作業車間調度問題特點采用兩段式實數編碼方式；

步驟三：通過目標函數，計算所有個體的最大完工時間，并記錄最大完工時間最小的個體作為當前最優解；

步驟四：：判斷算法是否終止，依據參數中對算法停止條件的設定，判斷算法是否終止，若算法終止，則輸出當前最優解；反之，算法還沒有終止，繼續執行步驟五；

步驟五：根據個體最大完工時間，按照錦標賽選擇法挑出N_pop個個體作為父代，并以交叉概率P_xovr執行整體交叉算子，產生N_pop個子代；

步驟六：將子代依次進行局部搜索操作并得到N_pop個非劣個體，將得到的非劣個體與父代個體混合，按照錦標賽選擇法挑出N_pop個個體形成下一代種群，基于模擬退火算法設計一種局部搜索方法；

步驟七：計算種群個體的最大完工時間，將種群中的最優個體與當前最優解進行比較，若最大完工時間比當前最優解的小則替換當前最優解為種群最優個體，反之當前最優解不變，然后返回步驟四。

2.根據權利要求1所述的改良文化基因算法求解帶運輸時間柔性作業車間調度方法，其特征在于，在步驟二中，通過三種初始化方法產生初始種群，種群中每一個個體代表一組帶運輸時間的柔性作業車間調度方案。

3.根據權利要求2所述的改良文化基因算法求解帶運輸時間柔性作業車間調度方法，其特征在于，三種初始化方法及其對應的個體機器選擇部分與工序排序部分分別為：

完全隨機：個體機器選擇部分，每個位置的整數為對應工序的可選加工機器集中隨機選擇的機器序號，工序排序部分為所有工序加工順序隨機排列；

優先最小加工時間：個體機器選擇部分，每個位置的整數為對應工序在可選加工機器里加工時間最小的機器序號；工序排序部分為所有工序加工順序隨機排列；

優先最大剩余加工時間：個體機器選擇部分，每個位置的整數為對應工序的可選加工機器集中隨機選擇的機器序號；工序排序部分為優先排剩余加工時間最大的工件。

4.根據權利要求1所述的改良文化基因算法求解帶運輸時間柔性作業車間調度方法，其特征在于，在步驟五中，交叉操作同時對兩個個體的機器選擇部分和工序排序部分進行交叉互換，同時要保證交叉后的個體均為可行解。

5.根據權利要求1所述的改良文化基因算法求解帶運輸時間柔性作業車間調度方法，其特征在于，在步驟六中，加入變異算子增加種群多樣性，擴大搜索范圍；引入精英庫策略，將搜索后的較好解替換放入精英庫中，避免重復搜索。

6.根據權利要求5所述的改良文化基因算法求解帶運輸時間柔性作業車間調度方法，其特征在于，精英庫是一個有限存儲庫，初始精英庫為空集，將經過模擬退火算子輸出的個體視為較好個體，并將其存入精英庫中，若精英庫已被填滿，則替換其中的最劣個體，對后面將要執行局部搜索的個體進行篩選，當發現該個體已經存在于精英庫時，不再執模擬退火算子，轉而執行變異算子。

7.根據權利要求6所述的改良文化基因算法求解帶運輸時間柔性作業車間調度方法，其特征在于，變異算子的便于方法包括如下步驟：

對個體機器選擇部分和工序排序部分分別選取多個位置；

依次對機器選擇部分選取的位置所對應的工序的可選機器集中，隨機選取一個替換原機器；

將工序排序部分選取的位置隨機排列，按新順序放回到原來的位置上，完成變異。