[發明專利]基于集合型離散粒子群優化的云工作流調度方法

在審

• 申請號: 201811200809.3
• 申請日: 2018-10-16
• 公開（公告）號: CN109543875A
• 公開（公告）日: 2019-03-29
• 發明（設計）人: 張軍;詹志輝;陳偉能;余維杰;梁迪
• 申請（專利權）人: 華南理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06N3/00
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李斌

本發明公開了一種基于集合型離散粒子群優化的云工作流調度方法，該調度方法首先將待優化的云工作流調度問題建立數學模型，然后對建立的數學模型基于集合型離散粒子群優化實現云工作流調度。該發明針對帶有不同服務質量QoS需求的云工作流調度問題，采用了一類新型的集合型粒子群優化算法，通過將粒子群優化的速度、位置和相關的更新操作在離散的集合空間重定義，從而能夠滿足對離散空間的云工作流調度優化問題的應用需求，提高了云工作流調度的效率。

技術領域

本發明涉及云計算以及智能計算技術領域，具體涉及一種基于集合型離散粒子群優化的云工作流調度方法。

背景技術

云計算作為一種新興的資源使用和交付模式，可以讓用戶隨時隨地根據自己的需求來使用各種資源，已經逐漸為學界和產業界所認知。它提供了一個彈性的方法來實現一種基于交付模式計算密集型的工作流應用。在云系統中，由于用戶越來越關注服務質量(QoS)的滿意程度，滿足用戶自定義需求的云工作流動態調度問題已經逐漸變成一個亟待解決而且具有挑戰性的難題。

粒子群算法(PSO)是一種模擬自然界中鳥群和魚群捕食的隨機搜索算法。雖然PSO是一個非常適合于連續領域問題優化的算法，并且已經在很多連續空間領域獲得了相當成功的應用，但是還是有很多現實的問題都是定義在離散空間中的，例如典型的離散組合問題就有背包問題，旅行商問題，調度問題等。為了將PSO在離散優化空間中拓展，此前已經提出了集合型的粒子群優化算法(S-PSO)，成功地突破了粒子群優化在離散優化空間的應用瓶頸，在解決如旅行商和多重背包等經典組合優化問題中取得了很好的求解性能。以此為基礎，如果能實現基于S-PSO的云工作流調度方法，將可以為進一步提高云工作流調度的效率提供新的有效途徑。

發明內容

本發明的目的是為了解決現有技術中的上述缺陷，提供一種基于集合型離散粒子群優化的云工作流調度方法，提高云工作流調度的性能和效率。

本發明的目的可以通過采取如下技術方案達到：

一種基于集合型離散粒子群優化的云工作流調度方法，所述的調度方法包括下列步驟：

S1、將待優化的云工作流調度問題建立數學模型，過程如下：

S11、將云工作流調度問題所含有的元素的全集記為E，集合E被分為一個n元組(E¹,E²,…,Eⁿ)，其中E＝E¹∪E²∪…∪Eⁿ；

S12、將云工作流調度問題的一組候選解X∈PS分為一個n元組(X¹,X²,…,Xⁿ),其中X^j，j＝1,2,…,n是一個集合并且PS則是所有可行解的集合；

S13、當且僅當X滿足約束條件Ω，將X作為可行解；

S14、將云工作流調度問題的優化目標當成要找到一個合適的解X^*使得問題的目標函數f得到最優化；

S2、對建立的數學模型基于集合型離散粒子群優化實現云工作流調度，過程如下：

S21、初始化算法的各個參數，并建立第一代粒子群和初始速度，其中，粒子的編碼方式為：

X＝(X¹,X²,…,Xⁿ)

其中Xⁱ∈S_i，S_i表示能用于執行第i個任務T_i的所有云計算服務的集合，由于每個任務只能匹配到一個云計算服務中執行，因此Xⁱ僅僅只含一個元素K_i，表示任務T_i被安排云計算服務上執行，n是工作流中任務的總數量；