[發明專利]移動云計算的多目標任務調度方法

有效

• 申請號: 201810531242.1
• 申請日: 2018-05-29
• 公開（公告）號: CN108762927B
• 公開（公告）日: 2022-01-14
• 發明（設計）人: 張小慶;胡亞捷
• 申請（專利權）人: 上海艾濤信息科技發展有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/48;G06N3/00
• 代理公司: 重慶創新專利商標代理有限公司 50125
• 代理人: 沈紅星

公開了一種移動云計算的多目標任務調度方法。該方法可以包括：步驟1：建立包含多個任務的有向無循環圖，設定迭代次數；步驟2：設定種群規模，建立包含多個初始種群個體的初始種群；步驟3：以初始種群個體為父代，通過進化方式獲得進化種群個體為子代，比較父代與子代的適應度函數，根據占優規則更新種群；步驟4：以初始種群個體為父代，重復步驟3，直至達到迭代次數，獲得優化種群，刪除適應度最小的N個種群個體，使優化種群的規模為種群規模，獲得最終種群。本發明可以在任務執行時間、執行代價和執行能耗三個目標上實現同步均衡的優化，形成多目標優化的調度解集合。

技術領域

本發明涉及移動云計算領域，更具體地，涉及一種移動云計算的多目標任務調度方法。

背景技術

移動云環境中的DAG任務調度問題不同于傳統的任務調度問題，需要考慮的因素更多更復雜，包括：1)用戶QoS需求的多樣性，如：服務響應時間、服務代價等；2)云服務具有異質性、動態性和彈性等特征；3)聯合云服務執行工作流任務的方式多樣；4)DAG任務調度時任務間的數據傳輸更為普遍。此時的任務調度問題本質上是聯合優化問題。

目前的研究中，一些工作主要集中于執行時間的優化，未考慮用戶的預算約束。然而，由于云計算的市場化特征，用戶必須對云資源使用進行付費，一些工作則考慮了用戶預算和截止時間約束，如文獻[W.Zheng and R.Sakellariou,Budget-deadline constrainedworkflow planning for admission control[J],Journal of Grid Computing,2013,11(4):633-651.]提出了一種基于預算約束的異構最快完成時間算法BHEFT，該算法是經典的異構最快完成時間工作流調度算法HEFT的改進，考慮了任務調度時的最優預算約束問題，文獻[H.Arabnejad,J.G.Barbosa,A budget constrained scheduling algorithm forworkflow applications[J],Journal of Grid Computing,2014,12(4):1-15.]提出了一種異構預算約束調度算法HBCS，通過定義代價因子調整可用預算與最低廉價格可能性的比例，實現調度優化，文獻[李克武,張功萱,朱昭萌,云環境中基于分解的多目標工作流調度算法[J],計算機工程與科學,2016,38(8):1588-1594.]提出了MOSC/D算法則是以工作流完成時間和費用作為優化目標，通過目標分解機制對單一目標求解近似最優解。

除了任務的調度時間和執行代價，能耗已經成為云計算中數據中心面臨的嚴峻問題。云服務的提供不僅需要滿足用戶的QoS需求，而且需要確保服務提供行為的收益保障，而這與資源方的高能耗是相互影響的。能效本身與其它QoS需求(時間或代價)是相互沖突的目標。相關研究中，文獻[Huang Q,Su S,Li J,et al.Enhanced Energy-EfficientScheduling for Parallel Applications in Cloud[C]//IEEE/ACM InternationalSymposium on Cluster,Cloud and Grid Computing,USA,IEEE,2013:781-786.]雖然考慮了能耗，但在任務調度時忽略了執行代價問題，優化目標有所減少。而文獻[ThanavanichT,Uthayopas P.Efficient energy aware task scheduling for parallel workflowtasks on hybrids cloud environment[C]//International Computer Science andEngineering Conference,USA,IEEE,2013:37-42]提出的加強HEFT算法EHEFT則僅是實現了調度時長與能耗的雙目標最優化。

綜合考慮相關已有的研究內容，多數工作集中于優化單一的或兩個目標，且沒有考慮不同目標間的相互影響，即執行時間與執行代價、或執行時間與執行能耗間的影響。因此，有必要開發一種移動云計算的多目標任務調度方法。