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

有效

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

基于改進果蠅算法的分布式流水車間調度方法，涉及作業車間調度技術領域，特別是屬于一種基于差異飛行策略改進果蠅算法的分布式流水車間調度方法。包括：步驟1：參數初始化；步驟2：果蠅種群的初始化；步驟3：利用嗅覺探索機制指導果蠅進行鄰域擾動，步驟4：利用差異飛行策略指導果蠅進行視覺飛行；步驟5：更新最佳解決方案，判斷是否達到終止條件，若滿足，則進化結束，輸出當前最佳解決方案及其對應的最大完工時間，反之轉至步驟3。本發明解決了帶有設置時間的分布式置換流水車間調度問題，具有降低企業生產成本、提高效率的積極效果。

技術領域

本發明涉及作業車間調度技術領域，特別是屬于一種基于差異飛行策略改進果蠅算法的分布式流水車間調度方法。

背景技術

如今，經濟全球化和越來越激烈的市場競爭使現代企業更重視分布式的生產環境。企業憑借分布式生產環境高質量、低成本、低風險的優勢而更具有市場競爭力。作為現代制造系統的重要部分，生產調度在過去幾十年中受到了越來越多關注.特別是分布式置換流水車間調度問題(Distributed permutation flowshop scheduling problem,DPFSP)在現代企業中發揮著越來越重要的作用，吸引了諸多研究人員的注意力。

傳統的DPFSP通常假設加工某工件前的設置時間/啟動時間(setup time)是序列獨立的，即設置時間與工件的排列順序無關，一般將其包括在加工時間中或者忽略不計。但在實際環境中，處理下一個待加工的工件前需要執行一些額外的操作，如在印刷行業中，當下一項作業與正在加工的作業的尺寸、墨水顏色等屬性不同時，工人需要調整尺寸、更換墨水顏色，這些設置需要花費一定的時間且不容忽視，并且設置時間不僅與即將處理的工件有關，而且受到正在處理的工件的影響，即體現序列相關設置時間的特點(sequence-dependent setup time,SDST)。而且，當把設置時間包括在各種工業環境中的調度決策中時，可以實現巨大的節約。因此，研究高效的方法對帶有設置時間的分布式調度問題進行優化將會對現代企業產生巨大效益。

發明內容

本發明的目的即在于提供一種基于改進果蠅算法的分布式流水車間調度方法，解決了帶有設置時間的分布式置換流水車間調度問題，以達到降低企業生產成本、提高效率的目的。

本發明所提供的基于改進果蠅算法的分布式流水車間調度方法，其特征在于，包括以下步驟：

步驟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。