[發明專利]基于量子粒子群優化算法的多目標工作流動態調度方法

有效

• 申請號: 201310750460.1
• 申請日: 2013-12-31
• 公開（公告）號: CN103699446B
• 公開（公告）日: 2017-02-15
• 發明（設計）人: 馬廷淮;儲雅;田偉;鐘水明
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 南京眾聯專利代理有限公司32206
• 代理人: 顧進,葉涓涓

1.一種基于量子粒子群優化算法的多目標工作流動態調度方法，其特征在于，包括如下步驟：

步驟10，輸入用戶提交的工作流以及用戶的QoS請求，獲取各個任務、任務間的數據依賴關系以及每個任務對應的數據大小，獲取QoS請求中的{T_QoS，C_QoS，RA_QoS}，其中T_QoS，C_QoS，RA_QoS分別表示用戶對時間、成本和可靠性的QoS請求值，初始化任務執行的總時間T_total=0，總成本C_total=0以及總可靠性RA_total=0；

步驟20，廣播由步驟10所得的工作流中任務集V中各任務計算所需的資源R={r₁,r₂,…,r_n}，各個云提供商發布包含這些資源的虛擬機VM={VM₁，VM₂，…，VM_m}當前狀態信息VM_j（v_j,p_j,f_j），其中，v_j、p_j、f_j分別為VM_j的運行速度、運行價格和失效率；并提供VM與VM間的傳輸數據信息Tr_k1k2（v_trk1k2，p_trk1k2），其中v_trk1k2表示傳輸速度，p_trk1k2表示傳輸價格；

步驟30，設定一個待執行任務集合V’，將父任務已經執行完畢的子任務或沒有父任務的任務放入V’中，針對V’中的每個任務，根據虛擬機當前狀態信息以及虛擬機間的傳輸速度，利用任務需要執行的數據量，對V’中的任務調度設定時間、成本和可靠性的目標函數，所述目標函數中根據用戶對時間、成本和可靠性的偏好進行權重運算，所述任務需要執行的數據量包括父任務傳輸給當前任務的數據量和當前任務自身的數據量；

步驟40，根據步驟30中獲得的目標函數，采用QPSO優化算法為V’中的任務選擇當前最適宜的虛擬機；

步驟50，當經過步驟40的QPSO優化算法獲取當前最適宜虛擬機后，將V’中的任務分配到相應虛擬機上執行，并獲取V’中任務執行的實際總執行時間T、總成本C和總可靠性R，選取其中最大的執行時間作為這次V’中任務執行的總時間T，將每個任務的執行成本之和作為本次V’中任務執行的總成本C，將每個任務的可靠性之積作為本次V’中任務執行的總可靠性R，并將它們累計到T_total、C_total和RA_total中；

步驟60，根據步驟50得到的T_total、C_total和RA_total，判斷是否T_total≤T_QoS&&C_total≤C_QoS&&RA_total≥RA_QoS，如果不滿足上式，則記錄違反QoS請求的行為；

步驟70，獲取任務的完成狀態，如果有任務的父任務已經全部完成，則更新待執行集合V’；然后根據當前網絡負載更新虛擬機間的傳輸速度，并根據當前虛擬機的負載更新虛擬機的運行速度；

步驟80，當待執行集合V’中還有任務未完成時，根據最新的虛擬機當前狀態信息和虛擬機間的傳輸數據信息，再次執行步驟40直至V’中不存在待執行的任務。