[發明專利]一種基于果蠅算法的模糊批調度方法及系統

在審

• 申請號: 202011376058.8
• 申請日: 2020-11-30
• 公開（公告）號: CN112364526A
• 公開（公告）日: 2021-02-12
• 發明（設計）人: 賈兆紅;王銳;唐俊
• 申請（專利權）人: 安徽大學
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06F111/08;G06F119/12
• 代理公司: 合肥市浩智運專利代理事務所(普通合伙) 34124
• 代理人: 張景云

本發明提供一種基于果蠅算法的模糊批調度方法及系統，將工件的加工時間定義為模糊數，同時批的加工時間受到學習效應和惡化效應的影響，使得算法的結果更加接近實際結果，為企業的決策提供更加準確的理論支持。本發明使用同時考慮尺寸和時間的啟發式算法來生成初始解。同時考慮尺寸和時間去選擇工件加入批中，既減少了浪費空間，又減小整個工程的完工時間。本發明使用的搜索策略考慮了批在機器上處理位置的差異，可以很好搜索優秀的解空間。為了避免果蠅算法在搜索過程中陷入局部最優，滿足一定條件的果蠅種群將會被重新初始化。同時一個精英種群策略被設計，可以更好的探索優秀解空間，大大的提高了算法的運行效率。

技術領域

本發明涉及模糊批調度優化技術領域，具體來說是一種基于果蠅算法的模糊批調度方法及系統。

背景技術

近年來，生產調度問題越來越引起企業的重視，在資源有限的情況下，如何有效的對生產過程進行科學的調度成為企業發展的核心問題。由于生產過程中工件和機器都具有不同的屬性，使得問題的解決變得更加復雜，通過經驗很難去設計一個合理的調度方案。

當前基于平行機調度問題的研究都集中在確定的環境中，沒有考慮到機器的磨損以及操作工人具有學習能力的情況，因此在現實的生產環境下，工件的加工時間是模糊的。在確定的環境下得到的調度方案和實際結果存在較大的偏差，并不能很好的支持企業的決策。同時當前的算法普遍存在時間復雜度較高，極大的降低了企業的生產效率。

在傳統策略中通過對比候選工件尺寸和批的剩余容量，選擇具有較小差值的工件加入批中，使得批的浪費空間最小。但是會出現一個批中不同工件的加工時間差距較大，導致大量工件加工時間變長。

如申請號為CN201611042598.6公開的一種基于改進果蠅算法的作業車間調度方法，該方法根據作業車間的特點，建立作業車間的數學模型，構建出每個工件不同工序的加工順序的約束條件，以及每臺機器上不同工件的工序加工順序的約束條件。然后建立基于最大完工時間最小的作業車間調度目標函數，通過基于工序的編碼方式形成果蠅個體，采用了自適應步長的分類嗅覺隨機搜索法，使果蠅種群快速找到味道濃度判定函數的最小值，得出作業車間調度的最優解，即作業車間調度的最優方案。雖然該算法實現簡單，只需要設置兩個參數，并且全局尋優能力較強，能夠有效地解決作業車間調度問題。但該方案采用單一種群，全局搜索能力弱，且初始解為隨機生成，算法你收斂較慢，存在大量低效搜索，同時沒有篩除沒有潛力的種群解，解的多樣性差。

發明內容

本發明所要解決的技術問題在于提供一種充分考慮工件尺寸和加工時間的基于果蠅算法的模糊批調度方法。

本發明通過以下技術手段實現解決上述技術問題的：

一種基于果蠅算法的模糊批調度方法，包括以下步驟：

步驟1：根據模糊批調度問題的特點，建立模糊批調度問題的數學模型

步驟2：初始化最大迭代數T_max，果蠅種群數量NC，精英種群數量NE，果蠅種群中果蠅個體數S,令當前迭代數t＝0；

步驟3：根據問題設計啟發式信息，通過啟發式信息構建所有果蠅種群初始解；

步驟4：令t＝t+1，果蠅種群通過多種嗅覺搜索方案形成新的解，通過視覺搜索得到新的種群；

步驟5：對當前代所有的果蠅種群進行目標值比較，重新初始化部分擁有較劣解和陷入局優的果蠅種群；

步驟6：通過協作搜索更新精英種群，保留優秀的解空間，精英果蠅執行嗅覺和視覺搜索并更新種群解；

步驟7：從所有果蠅種群中獲取全局最優調度方案，如果t＜T_max，則返回步驟4，否則輸出最優調度方案。