[發明專利]一種云計算系統下多目標任務調度方法及系統

有效

• 申請號: 201911252905.7
• 申請日: 2019-12-09
• 公開（公告）號: CN110969362B
• 公開（公告）日: 2023-09-22
• 發明（設計）人: 李俊青;于輝
• 申請（專利權）人: 山東師范大學
• 主分類號: G06Q10/0631
• 分類號: G06Q10/0631;G06Q50/04;G06N3/006;G06F9/50
• 代理公司: 濟南圣達知識產權代理有限公司 37221
• 代理人: 李琳

本公開公開了一種云計算系統下多目標任務調度方法及系統，包括：以最小化最大完工時間、最小化最大設備工作量和最小化所有設備的總工作量為目標，將云計算系統下的任務調度構建為混合車間調度模型；采用嵌入擾動結構的混合離散人工蜂群算法對混合車間調度模型進行求解，得到調度優化方案；利用得到的調度優化方案對云計算系統下的任務進行調度。采用用混合離散人工蜂群算法，優化了云計算系統下的柔性任務調度問題，建模為HFS模型；嵌入8種擾動結構增強了算法的開發能力；自適應擾動結構平衡了開發和探索能力，改進的跟隨蜂機制具有深度挖掘功能，可以進一步增強局部搜索能力；設計良好的偵察蜂算法可以提高算法的收斂能力。

技術領域

本公開涉及多目標優化技術領域，特別是涉及一種云計算系統下多目標任務調度方法及系統。

背景技術

本部分的陳述僅僅是提供了與本公開相關的背景技術信息，不必然構成在先技術。

在云計算系統中，用戶提出的作業應該分配給有能力的設備，并且通常每個作業都包含幾個連續的任務，這些任務應該在不同或相同的設備上按一定的順序處理。整個過程可以建模為混合流水車間調度(HFS)問題。云系統中的任務調度近年來得到了研究，如Wang等人開發了用于異構計算和云調度的人工群智能的多學科方法。然而，已發表的文獻主要討論云系統中的任務分配，而沒有考慮云系統中的靈活能力。Li等人在Map/Reduce計算框架中開發了幾種周期性批處理作業調度啟發式方法，其中任務調度被建模為具有依賴于調度的設置時間的兩階段HFS。然而，考慮到實際應用中的多目標特征，該模型還需要進行擴展。

許多類型的優化問題都是NP-hard問題，許多類型的啟發式或元啟發式算法被提出來解決這些具有單目標和多目標的問題，在這些元啟發式算法中，人工蜂群(ABC)最近被開發出來，并且已經被證實對于許多類型的問題是有效的。

為了解決單目標優化問題，已經使用了多種類型的元啟發式算法。Pan等人針對分布式裝配排列流車間調度問題開發了構造啟發式和元啟發式。Li等人針對煉鋼系統中實際的HFS問題，設計了一種結合果蠅優化算法(FOA)和迭代貪婪(IG)算法的混合算法。在這些元啟發式算法中，具有三種類型的蜜蜂的ABC算法(即雇傭蜂、跟隨蜂和偵察蜂)也被廣泛用于解決優化問題，例如數值函數優化，具有動態操作跳過的混合柔性流水車間，以及分布式流水車間調度問題(DFSSP)。其他類型的元啟發式算法也被用于解決不同類型的優化問題，例如基于教學的優化(TLBO)、入侵雜草優化(IWO)和IG算法。通過關于元啟發式算法的文獻中，有許多類型的元啟發式算法可以用于解決具有單個目標的多種類型的優化問題。如何利用問題特征設計特定于問題的算子是改進元啟發式算法的關鍵問題。

大多數已發表的多目標優化算法可分為三個方面，即基于Pareto的方法，基于分解的方法，以及將多目標問題轉化為單目標問題的方法。通過應用基于Pareto的多目標優化算法，已經解決了許多類型的優化問題。為了解決多目標柔性作業車間調度問題(FJSSP)，已經提出了幾種元啟發式算法，如基于Pareto的禁忌搜索(TS)算法和基于Pareto的ABC算法。Yu等人針對乙烯裂解爐系統問題設計了一種多目標TLBO算法。文獻研究了多目標多周期逆向物流網絡設計問題。Yi等人為鋁電解生產過程開發了一種多目標細菌覓食優化算法。對于Hadoop中的任務調度問題，也開發了其他類型的多目標優化算法。

基于分解的多目標進化算法(MOEA/D)已經被證明是另一種有效的多目標優化算法。Yuan等人設計了一種啟發式方法來平衡基于分解的多目標優化器的收斂性和多樣性。Wang等人研究了MOEA/D的約束子問題處理方法。Wang等人通過使用Pareto自適應標量化方法開發了基于分解的算法?？梢园l現，MOEA/D算法主要用于連續優化問題，考慮MOEA/D算法求解調度問題的文獻較少。