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

有效

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

1.一種云計算系統下多目標任務調度方法，其特征在于，包括：

以最小化最大完工時間、最小化最大設備工作量和最小化所有設備的總工作量為目標，將云計算系統下的任務調度構建為混合車間調度模型；

所述混合車間調度模型的約束條件是：

限制每個操作的釋放時間；

保證在任何設備中沒有操作重疊，即后續操作必須等待前置操作的完成；

確保對于一個操作只能選擇一個設備；

采用嵌入擾動結構的混合離散人工蜂群算法對混合車間調度模型進行求解，得到調度優化方案；

所述求解的具體過程包括：

采用初始化策略生成初始化種群；

在雇傭蜂階段，對初始化種群中每個解生成相應的鄰域解，評估新生成的鄰域解并初始化自適應鄰域結構；

在跟隨蜂階段，采用錦標賽選擇方法選擇當前較優解，對較優解生成相應的鄰域解，評估該鄰域解并更新自適應鄰域結構，并對當前較優解執行深度開發；

在偵查蜂階段，使用八種擾動結構生成八個鄰域解，選擇最優解并與跟隨蜂階段得到的鄰域解進行比較，若最優解優于跟隨蜂階段得到的鄰域解，則最優解取代后者；

在深度開發階段，基于當前最優解進行深度開發過程，以最優解取代最差解，具體地，

生成一個隨機數，將其與預設的系統參數進行比較，若隨機數小于系統參數，則基于當前解執行深度開發過程；

利用自適應擾動結構中獲勝的鄰域結構生成系統參數的鄰域解；

評估每個鄰域解，并且若其適應值優于前一個鄰域解，用所選擇的擾動結構更新自適應擾動結構，以及用鄰域解替換當前解；

所述擾動結構包括單交換結構、雙交換結構、單點互換結構、單插入結構、雙插入結構、頭尾插入結構和單點插入結構；

利用得到的調度優化方案對云計算系統下的任務進行調度。

2.如權利要求1所述的一種云計算系統下多目標任務調度方法，其特征在于，

所述最小化最大完工時間、最小化最大設備工作量和最小化所有設備的總工作量的目標函數，分別為：

其中，c_is是階段i中任務s的完成時間、c_max是所有任務的最大完成時間、W_k是設備k的工作負載、W_max是所有設備的最大工作負載、T_w是所有設備的總工作負載；m是設備數、n是作業數；

對三種目標函數進行加權得到加權目標函數：

F(c)＝w₁×F₁(c)+w₂×F₂(c)+w₃×F₃(c)

w₁+w₂+w₃＝1,0≤w₁,w₂,w₃≤1，

其中，w₁,w₂和w₃表示權重系數。