[發明專利]一種基于貓頭鷹搜索算法的計算密集型云工作流調度方法

有效

• 申請號: 201811336040.8
• 申請日: 2018-11-12
• 公開（公告）號: CN109710372B
• 公開（公告）日: 2020-10-13
• 發明（設計）人: 袁艷;李慧芳;韋琬雯;胡光政;鄒偉東;柴森春;夏元清
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/48;G06N3/00;G06F16/9535
• 代理公司: 北京正陽理工知識產權代理事務所(普通合伙) 11639
• 代理人: 唐華

1.一種基于貓頭鷹搜索算法的計算密集型云工作流調度方法，其特征在于，包括以下步驟：

步驟一、輸入用戶提交的待調度計算密集型云工作流模型及其所包含的依賴子任務集合、可供租賃的虛擬機集合；

步驟二、將各云工作流子任務調度至最合適虛擬機上執行的過程，建模為標準的最小值求解問題，其調度目標為：優化整個云工作流的執行跨度時間makespan，使所有云工作流任務執行完畢所花費的時間最短；

步驟三、利用基于聲強平方反比定律的貓頭鷹搜索算法，求解云計算環境下的任務-虛擬機調度問題，包括以下步驟：

步驟1、初始化算法的基本參數，包括步長參數β、調度方案個數M以及最大迭代次數Iteration、第一次出現最優解時的尋優迭代次數bestNum；

步驟2、使用均勻分布的隨機數來初始化每個調度方案；

步驟3、算法迭代過程中，當迭代次數t小于最大迭代次數Iteration時，t＝t+1，轉步驟4；當迭代次數t大于或等于最大迭代次數Iteration時，轉步驟8；

步驟4、根據云工作流模型，即子任務之間的依賴關系，計算當前代中所有調度方案的工作流執行跨度時間makespan；

步驟5、找到當前代中最佳的調度方案；如果最優解有更新，則bestNum＝t；對每個調度方案更新與當前最優解的距離信息同時更新的強度變化量

其中，V表示全局最優調度方案，makespan(V)表示最優調度方案對應的工作流執行跨度時間，random表示[0,1)的隨機數；

步驟6、判斷是否已經迭代l代而其最優解仍然沒有更新，若t-bestNuml，則使用遺傳變異的思想，隨機更改任一個體的任一位置的虛擬機映射關系，轉步驟7；否則，直接轉步驟7；

步驟7、根據強度變化量，對當前代的所有調度方案進行更新，并返回步驟3；

步驟8、找到最優調度方案，按照調度方案給出的任務與虛擬機映射關系，將工作流子任務與虛擬機進行綁定。

2.如權利要求1所述的一種基于貓頭鷹搜索算法的計算密集型云工作流調度方法，其特征在于，所述步驟一，具體將云工作流描述成一個有向無環圖G＝(T，E)，其中：T為有向無環圖中節點的集合，表示云工作流中的n個任務，T＝{T₁,T₂,……,T_n}；E是云工作流模型中有向邊的集合，E＝{(T_i,T_j)|T_i,T_j∈T}，有向邊T_i→T_j表示父任務T_i與子任務T_j之間的依賴關系，T_j只有在T_i完成后才可執行；用VM表示虛擬機，m表示可供用戶租賃的虛擬機總個數，虛擬機資源集合表示為VM＝{VM₁,VM₂,……,VM_k,……,VM_m}，其中k＝1,2,...,m；MIPS表示計算設備每秒可處理的百萬級機器語言指令數，則MIPS(VM_k)表示虛擬機VM_k的處理速度。