[發明專利]基于改進果蠅算法的分布式流水車間調度方法

有效

• 申請號: 202110541129.3
• 申請日: 2021-05-18
• 公開（公告）號: CN113159642B
• 公開（公告）日: 2022-04-01
• 發明（設計）人: 桑紅燕;郭恒偉;潘全科;李俊青;韓玉艷
• 申請（專利權）人: 聊城大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/04;G06Q50/04;G06N3/00;G06F30/27
• 代理公司: 北京中創博騰知識產權代理事務所(普通合伙) 11636
• 代理人: 孫福嶺

1.一種基于改進果蠅算法的分布式流水車間調度方法，包括以下步驟：

步驟1：參數初始化；設置種群大小PSize、種群最優果蠅個體未更新次數的閾值G以及算法的停止時間T，其中，種群中包含的果蠅個體數量對應車間調度可選用的解決方案數量；閾值G表示最大完工時間最小的果蠅個體未改變的次數的上限值；停止時間T＝10*m*n(m為機器數量，n為工件數量)，其中，上述最大完工時間為每一個工廠中最后一個工件完成時間的最大值；

步驟2：果蠅種群的初始化；通過基于工件序列的表示方法進行編碼，使用構造性啟發式方法生成2個果蠅個體，使用隨機方法生成剩余PSize-2個果蠅個體，形成包含PSize個果蠅的初始種群P＝{π(1),π(2),...π(PSize)}，從種群P中選擇最大完工時間最小的果蠅個體，對最佳方案進行更新；

步驟3：利用嗅覺探索機制指導果蠅進行鄰域擾動，并形成新果蠅種群P₁＝{π(1),π(2),...π(PSize)}；

步驟4：利用差異飛行策略指導果蠅進行視覺飛行；

步驟5：更新最佳解決方案，判斷是否達到終止條件，若滿足，則進化結束，輸出當前最佳解決方案及其對應的最大完工時間，反之轉至步驟3；其特征在于，

所述的嗅覺探索機制包括一次交換擾動、二次交換擾動，其中：

一次交換擾動的具體步驟如下：從完工時間最大的工廠中隨機提取一個工件，記作J_cri，剩余的f-1個工廠，每間工廠隨機提取一個工件，記作J_tar，將J_cri與J_tar交換位置，產生f-1個新方案，從中選擇最大完工時間最小的方案；

二次交換擾動的具體步驟如下：在一次交換擾動得到的方案中，從完工時間最大的工廠中隨機選擇b個不重復的工件，其中，b的范圍設定為大于3，且小于完工時間最大的工廠中的工件數目的一半，從b個工件中隨機選擇一個工件記作J_ori，將J_ori與剩余b-1個工件進行交換，則產生b-1個新方案，從中選擇最大完工時間最小的方案，作為新果蠅種群；

所述的差異飛行策略包括以下步驟：

a.根據果蠅種群中最小的最大完工時間未發生變化的次數，判斷種群是否陷入局部最優，如果種群中最小的最大完工時間未發生變化的次數達到G次，則認為種群此時陷入局部最優，執行步驟b1，反之認為種群未陷入局部最優，執行步驟b2；

b1.若種群陷入局部最優，種群內的果蠅按照最大完工時間由小到大排序，排序后的種群中，前20％的果蠅因為有著較小的最大完工時間而被直接保留；剩余80％果蠅中，前50％果蠅通過相鄰工件互換方法，向當前種群中最大完工時間最小的果蠅進行學習，即對最大完工時間最小的果蠅執行相鄰工件互換方法；剩余50％果蠅使用隨機方法生成，最終生成一個包含PSize個果蠅的新種群P₂；從種群P₂中隨機選擇PSize/2個果蠅，更新種群P中最大完工時間較大的PSize/2個果蠅(即果蠅種群P中較差的一半個體向果蠅群P₂中的部分個體飛行)；

b2.若種群未陷入局部最優，則將嗅覺探索階段生成的種群P₁與嗅覺探索階段前的種群P組合，并從中選擇最大完工時間較小的PSize個果蠅進行下一次迭代(即果蠅個體向種群P₁和P中最好的PSize個果蠅飛行)；

其中，相鄰工件互換方法的具體步驟為：首先尋找完工時間最大的工廠為關鍵工廠,若關鍵工廠只有一個，則對該工廠內的工件執行相鄰工件互換操作，即每相鄰的兩個工件互換位置，從中選擇完工時間最小的一組互換，生成新方案；若關鍵工廠數量存在多個，則多個關鍵工廠中的每個工廠中的工件，均執行相鄰工件互換操作，從中選擇完工時間最小的一組互換，生成新方案。