基于多種云環(huán)境的任務(wù)調(diào)度算法綜述

陳紅華　崔翛龍　王耀杰

摘 要：任務(wù)調(diào)度算法是云計(jì)算資源分配部署的核心方法。針對(duì)當(dāng)前云計(jì)算發(fā)展面臨的任務(wù)需求和數(shù)據(jù)量指數(shù)級(jí)增長(zhǎng)的問(wèn)題，重點(diǎn)對(duì)任務(wù)調(diào)度算法進(jìn)行了系統(tǒng)的梳理和歸納，以云環(huán)境為分類依據(jù)，研究分析了單云、聯(lián)盟云、混合云、多云四類調(diào)度算法。在單云環(huán)境中，從傳統(tǒng)啟發(fā)式、元啟發(fā)式以及混合式任務(wù)調(diào)度算法角度進(jìn)行闡述。在聯(lián)盟云、混合云、多云環(huán)境中，從工作流和獨(dú)立任務(wù)調(diào)度算法角度進(jìn)行闡述。通過(guò)比較，總結(jié)了現(xiàn)有算法的優(yōu)點(diǎn)、缺點(diǎn)以及優(yōu)化性能，并形成結(jié)論性意見(jiàn)和開放性問(wèn)題，為未來(lái)對(duì)容器云、數(shù)據(jù)云以及兼顧資源分配與任務(wù)調(diào)度算法的研究奠定基礎(chǔ)。

關(guān)鍵詞：云計(jì)算； 任務(wù)調(diào)度； 單云； 聯(lián)盟云； 混合云； 多云

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2023）10-002-2889-07

doi：10.19734/j.issn.1001-3695.2023.02.0076

Summary of task scheduling algorithms based on multiple cloud environments

Chen Honghua1a，1b， Cui Xiaolong1a，2， Wang Yaojie3

（1.a.Anti-Terrorism Command Information Engineering Research Team， b.Postgraduate Brigade， Engineering University of PAP， Xian 710086， China; 2.Urumqi Campus of Engineering University of PAP， Urumqi 830000， China; 3.Construction & Development Research Institute of the Armed Police Research Institute， Beijing 100000， China）

Abstract：Task scheduling algorithms are the core method for resource allocation and deployment in cloud computing. To meet the current task demand of cloud computing while the amount of data grows exponentially， the paper focused on systematically sorting and summarizing of task scheduling algorithms. Categorized by cloud environment， it studied and analyzed four types of scheduling algorithms， namely single cloud， federated cloud， hybrid cloud， and multi-cloud. For single cloud environment， the paper elaborated from the perspectives of traditional heuristics， meta heuristics， and hybrid task scheduling algorithms. For federated cloud， hybrid cloud， and multi-cloud environments， the paper elaborate from the perspectives of workflow and independent task scheduling algorithms. Through comparisons， this paper summarized the advantages， disadvantages， and optimization performance of existing algorithms， and formed conclusive opinions and open questions， laying the foundation for future research on container clouds， data clouds， and algorithms that balanced resource allocation and task scheduling.

Key words：cloud computing; task scheduling; single cloud; federated cloud; hybrid cloud; multi-cloud

0 引言

2006年，在Google的搜索引擎會(huì)議上，云計(jì)算（cloud computing）［1］概念被正式提出。2008年BingoCloudOS產(chǎn)品的發(fā)布成為中國(guó)第一個(gè)獲得自主知識(shí)產(chǎn)權(quán)的基礎(chǔ)架構(gòu)云。我國(guó)高度重視云計(jì)算領(lǐng)域的發(fā)展，從“十二五”開始就將云計(jì)算作為專項(xiàng)計(jì)劃，并視為重點(diǎn)產(chǎn)業(yè)進(jìn)行建設(shè)。云計(jì)算領(lǐng)域的地位日益突顯，也迎來(lái)嶄新的發(fā)展。

發(fā)展至今，云計(jì)算在諸多領(lǐng)域有著重要運(yùn)用和廣泛研究，但仍沒(méi)有統(tǒng)一的定義。美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）［2］、Google維基百科［3］、中國(guó)云計(jì)算網(wǎng)［4］都對(duì)云計(jì)算有各自的定義，其最本質(zhì)的要素是以共享資源池的方式，通過(guò)調(diào)度算法，提供各種服務(wù)。從理論上來(lái)說(shuō)，云計(jì)算可以提供無(wú)限的存儲(chǔ)、計(jì)算能力和資源，但在現(xiàn)實(shí)運(yùn)用中，由于資源需求激增和調(diào)度策略發(fā)展的限制，極易導(dǎo)致資源爭(zhēng)用、服務(wù)中斷、缺乏互操作性、QoS降級(jí)和SLA違規(guī)等問(wèn)題［5］。從技術(shù)發(fā)展角度來(lái)看，從早期分布式系統(tǒng)到網(wǎng)格系統(tǒng)［6］進(jìn)而云計(jì)算技術(shù)出現(xiàn)，一定程度解決異構(gòu)網(wǎng)絡(luò)資源共享與利用問(wèn)題，但不同于集群系統(tǒng)與網(wǎng)格系統(tǒng)單一的調(diào)度目標(biāo)，現(xiàn)有云服務(wù)需要充分考慮多種用戶服務(wù)質(zhì)量需求，而且還要維持動(dòng)態(tài)變化的系統(tǒng)處于負(fù)載相對(duì)均衡的狀態(tài)，達(dá)到既提高資源利用率和最大化經(jīng)濟(jì)效益，又為用戶提供高質(zhì)量服務(wù)的目標(biāo)（兩個(gè)目標(biāo)呈相互制約關(guān)系）。總的來(lái)說(shuō)，云計(jì)算發(fā)展難點(diǎn)可以概括如下：a）計(jì)算節(jié)點(diǎn)資源處于不斷增減的動(dòng)態(tài)變化中，包括新計(jì)算節(jié)點(diǎn)的擴(kuò)展以及停止工作的計(jì)算節(jié)點(diǎn)的重新工作，從而需要對(duì)資源實(shí)時(shí)監(jiān)控與統(tǒng)計(jì)；b）云計(jì)算規(guī)模非常大，對(duì)計(jì)算節(jié)點(diǎn)的監(jiān)測(cè)需要占用大量計(jì)算資源［7］；c）在大規(guī)模的云計(jì)算中，常常發(fā)生節(jié)點(diǎn)失效與程序錯(cuò)誤的現(xiàn)象，從而需要充分保障任務(wù)執(zhí)行的可靠性與算法的魯棒性。

此外，云環(huán)境由單云環(huán)境發(fā)展到多個(gè)云的云間環(huán)境，單一的云環(huán)境實(shí)現(xiàn)簡(jiǎn)單，但單點(diǎn)故障能夠?qū)е聡?yán)重服務(wù)危機(jī)。2022年12月18日阿里云香港可用區(qū)C某機(jī)房設(shè)備異常，導(dǎo)致多個(gè)網(wǎng)站癱瘓，云服務(wù)器ECS、云數(shù)據(jù)庫(kù)PolarDB等云產(chǎn)品無(wú)法使用，造成不可估量的損失。多種云間環(huán)境解決了單云環(huán)境容易故障和受到DDoS攻擊問(wèn)題，但是云種類與數(shù)量的增加對(duì)任務(wù)調(diào)度算法提出更大的挑戰(zhàn)［8］?；谏鲜鰡?wèn)題，本文通過(guò)收集、整理、對(duì)比、分析目前主流云計(jì)算調(diào)度算法，采取從單云、多云、混合云、聯(lián)盟云等不同云間環(huán)境，對(duì)調(diào)度算法進(jìn)行分類闡述。在單云環(huán)境中，根據(jù)求解優(yōu)化問(wèn)題的技術(shù)，將任務(wù)調(diào)度算法分為傳統(tǒng)啟發(fā)式、元啟發(fā)式和混合式；云間環(huán)境的任務(wù)調(diào)度算法通常從單云調(diào)度算法的基礎(chǔ)上優(yōu)化發(fā)展而來(lái)，因此根據(jù)用戶請(qǐng)求任務(wù)的相互關(guān)系，分為工作流調(diào)度算法和獨(dú)立任務(wù)調(diào)度算法，并從算法策略、算法描述、優(yōu)化目標(biāo)、算法特征、存在問(wèn)題等角度進(jìn)行對(duì)比分析，為云計(jì)算調(diào)度算法未來(lái)研究重點(diǎn)提供理論支持。

1 云環(huán)境與任務(wù)調(diào)度

1.1 任務(wù)調(diào)度

任務(wù)調(diào)度旨在滿足用戶服務(wù)需求，提高資源的使用效率并且保持均衡的資源負(fù)載，降低整個(gè)數(shù)據(jù)中心的能耗，驅(qū)動(dòng)綠色發(fā)展。任務(wù)調(diào)度策略一般分為資源配置策略［9］和任務(wù)調(diào)度兩個(gè)部分。資源分配從服務(wù)提供商角度出發(fā)，按照規(guī)則拆分和配給資源；任務(wù)調(diào)度是從用戶提交的任務(wù)角度出發(fā)，把任務(wù)拆分并投放到合適的資源模塊的過(guò)程，但是對(duì)于任何一個(gè)具體場(chǎng)景來(lái)說(shuō)，資源往往是有限的，調(diào)度優(yōu)化問(wèn)題旨在實(shí)現(xiàn)任務(wù)請(qǐng)求與資源的最佳匹配。由于資源的重新分配與調(diào)度往往帶來(lái)巨大的系統(tǒng)開銷，所以本文主要從任務(wù)調(diào)度角度出發(fā)對(duì)算法進(jìn)行分析與討論。任務(wù)調(diào)度是一個(gè) NP-hard［10］優(yōu)化問(wèn)題，調(diào)度目標(biāo)函數(shù)為基于QoS參數(shù)的適應(yīng)度函數(shù)（FFQoS），進(jìn)行資源合理分配。資源分配與任務(wù)調(diào)度成正比，資源分配得越合理，任務(wù)調(diào)度實(shí)行的效率越高。而如何實(shí)現(xiàn)任務(wù)請(qǐng)求與資源的最佳匹配，即選擇最合適的資源對(duì)任務(wù)處理，是云算法發(fā)展面臨的最大難題。資源調(diào)配與調(diào)度（RPS）［11］過(guò)程如圖1所示。

資源供應(yīng)與調(diào)度（RPS）的目標(biāo)是最大程度地滿足用戶的QoS需求以及與資源提供商協(xié)定的SLA，進(jìn)行資源合理分配與均衡負(fù)載。具體流程為：首先根據(jù)任務(wù)實(shí)際，確定用戶的需求與目標(biāo)，結(jié)合工作負(fù)載情況分析用戶與云服務(wù)提供商定義服務(wù)級(jí)別協(xié)議（SLA）；其次，基于QoS來(lái)計(jì)算適應(yīng)度函數(shù)［12］（FFQoS）以及不考慮QoS參數(shù)的值（FFnonQoS），并進(jìn)行比較；再次，如果FFQoS

為了讓用戶獲得更好的服務(wù)體驗(yàn)并最大化提供商的利益，在資源有限的情況下設(shè)計(jì)更好的調(diào)度方案，通常通過(guò)設(shè)置不同的調(diào)度目標(biāo)［13］來(lái)描述云服務(wù)提供商的服務(wù)質(zhì)量和效果。常見(jiàn)調(diào)度目標(biāo)有完成時(shí)間（makespan）、成本、能源消耗量、吞吐量、負(fù)載平衡、服務(wù)質(zhì)量（QoS）、資源利用率。而對(duì)于云服務(wù)提供商提供的服務(wù)，用戶通常有不同的約束條件，主要有任務(wù)完成截止時(shí)間、預(yù)算、可靠性和任務(wù)執(zhí)行的具體優(yōu)先級(jí)以及整個(gè)過(guò)程的安全性。

1.2 單云與云間環(huán)境

云計(jì)算廣泛應(yīng)用于各個(gè)領(lǐng)域，其云環(huán)境也由單云逐漸發(fā)展到云間環(huán)境，單云主要包括彼此沒(méi)有關(guān)聯(lián)的單一公有云或私有云構(gòu)成。私有云和公共云在各自領(lǐng)域都有其特定運(yùn)用，能夠?qū)崿F(xiàn)有效資源利用，但是隨著日益復(fù)雜的云環(huán)境體系以及日益增長(zhǎng)的服務(wù)需求，需要更具體和更廣泛地共享信息和數(shù)據(jù)［14］。因此多種云間環(huán)境應(yīng)運(yùn)而生，實(shí)現(xiàn)了資源之間的跨云使用，降低了對(duì)單云的依賴性，提升應(yīng)對(duì)故障的能力。云間環(huán)境包括聯(lián)盟云環(huán)境［15］、混合云環(huán)境［16］和多云環(huán)境［17］。Gartner在《中國(guó)混合云運(yùn)營(yíng)的三個(gè)重要經(jīng)驗(yàn)》報(bào)告中指出，多云以及混合云的云策略得到了企業(yè)和市場(chǎng)的喜愛(ài)，并將逐步成為研究熱點(diǎn)。

云計(jì)算有各種類型的調(diào)度算法，可按靜態(tài)和動(dòng)態(tài)、集中和分布式、在線和離線（批處理模式）、搶占式和非搶占式和協(xié)作與非協(xié)作調(diào)度等進(jìn)行分類［18］。靜態(tài)調(diào)度算法需要預(yù)先獲取有關(guān)任務(wù)的相關(guān)信息，當(dāng)工作負(fù)載不頻繁變化且系統(tǒng)行為變化很小時(shí)，靜態(tài)算法的性能更好且易于實(shí)現(xiàn)。然而，在云環(huán)境中，資源實(shí)時(shí)變化，負(fù)載不斷波動(dòng)，因此動(dòng)態(tài)調(diào)度算法是應(yīng)對(duì)波動(dòng)需求的關(guān)鍵技術(shù)。當(dāng)任何節(jié)點(diǎn)發(fā)生增減變化時(shí)，算法會(huì)對(duì)任務(wù)進(jìn)行合理的轉(zhuǎn)移和再分配。事實(shí)上，所有元啟發(fā)式調(diào)度方法本質(zhì)上都是動(dòng)態(tài)的［19］。這也意味著，動(dòng)態(tài)算法和元啟發(fā)式算法更適用于目前云計(jì)算的復(fù)雜環(huán)境。

2 任務(wù)調(diào)度算法分類

不同的云環(huán)境適用于不同的場(chǎng)合，因此根據(jù)云環(huán)境的四種不同類型（單云環(huán)境、聯(lián)盟云環(huán)境、多云環(huán)境和混合云環(huán)境）進(jìn)行任務(wù)調(diào)度算法分類。在單云環(huán)境中，根據(jù)求解優(yōu)化問(wèn)題的技術(shù)，將任務(wù)調(diào)度算法分為傳統(tǒng)啟發(fā)式算法、元啟發(fā)式算法和混合式算法。由于云間環(huán)境的任務(wù)調(diào)度算法通常在單云調(diào)度算法的基礎(chǔ)上發(fā)展而來(lái)，并結(jié)合各自云環(huán)境特點(diǎn)，完成不同目標(biāo)并滿足各種約束，進(jìn)行優(yōu)化升級(jí)，因此從任務(wù)間的依賴關(guān)系分類工作流調(diào)度算法和獨(dú)立任務(wù)調(diào)度算法。圖2展示了云計(jì)算任務(wù)調(diào)度的分類。

2.1 單云環(huán)境

單云環(huán)境部署簡(jiǎn)單，是出現(xiàn)形式最早的云算法環(huán)境，其任務(wù)調(diào)度算法的發(fā)展也最悠久，有大量的研究。本文主要從傳統(tǒng)啟發(fā)式算法、元啟發(fā)式算法和混合式算法三個(gè)類別進(jìn)行分類比較分析。

2.1.1 傳統(tǒng)啟發(fā)式算法

啟發(fā)式算法是指在一個(gè)尋求最優(yōu)解的過(guò)程中能夠根據(jù)個(gè)體或者全局的經(jīng)驗(yàn)來(lái)解決問(wèn)題的方法。

min-min算法［20］的基本思想是先將小的任務(wù)分配到性能最好的機(jī)器上執(zhí)行，實(shí)現(xiàn)簡(jiǎn)單，但是容易出現(xiàn)饑餓現(xiàn)象與負(fù)載不均衡問(wèn)題。max-min算法改進(jìn)min-min算法，保證長(zhǎng)任務(wù)的執(zhí)行，但該算法面臨部分資源過(guò)度利用和部分未充分利用，無(wú)法改善參數(shù)等問(wèn)題。

HEFT算法［21］基于優(yōu)先級(jí)進(jìn)行任務(wù)的分配執(zhí)行，Dubey等人提出了改進(jìn)的HEFT算法，一定程度上緩解負(fù)載壓力，但該算法未能改善各種QoS參數(shù)。

先來(lái)先服務(wù)算法（FCFS）按照用戶的任務(wù)請(qǐng)求到達(dá)的先后順序執(zhí)行，導(dǎo)致短作業(yè)等待時(shí)間長(zhǎng)。Mondal等人（2015）提出最短作業(yè)優(yōu)先（SJF）調(diào)度算法，但節(jié)點(diǎn)負(fù)載不均勻，引發(fā)饑餓現(xiàn)象。因此，Devi等人［22］基于增強(qiáng)加權(quán)循環(huán)（WRR）進(jìn)行資源分配，改善了QoS，但頻繁的任務(wù)切換導(dǎo)致額外的開銷。

Sheikhalishahi等人［23］提出了多容量感知資源調(diào)度算法，減少等待時(shí)間，但未考慮任何QoS限制，算法的性能效低。為克服能效問(wèn)題，Sheikhalishahi等人［24］提出Bin Packing算法，改進(jìn)關(guān)鍵性能指標(biāo)。文獻(xiàn)［25］提出了最佳擬合算法（best fit algorithm），使得最快完成任務(wù)同時(shí)減少資源浪費(fèi)。傳統(tǒng)啟發(fā)式算法還包括最小完成時(shí)間（MET）、機(jī)會(huì)負(fù)載均衡（OLB）［26］ 、最小執(zhí)行時(shí)間（MCT）、爬山算法、sufferage算法、主成分分析［27］等。

傳統(tǒng)啟發(fā)式算法存在可行解與最優(yōu)解的偏離，即能夠求得可行解，但是并不一定是最優(yōu)解，并且多數(shù)算法依賴于某個(gè)特定問(wèn)題，從而在普適性上性能較差。

2.1.2 元啟發(fā)式算法

元啟發(fā)式是啟發(fā)式與隨機(jī)化的結(jié)合，它不借助于問(wèn)題的特定條件，生成或選擇啟發(fā)式（部分搜索算法）可行的解決方案。其優(yōu)勢(shì)在于用更少的計(jì)算量找到好的解決方案，主要從自然界中獲得靈感，并注重防止搜索陷入局部最優(yōu)解的問(wèn)題。由于元啟發(fā)式算法的優(yōu)勢(shì)，目前，元啟發(fā)式算法成為云環(huán)境任務(wù)調(diào)度算法的主流，這些算法用于在短時(shí)間內(nèi)獲得NP完全問(wèn)題的次優(yōu)（近似）解。通常將元啟發(fā)式調(diào)度算法基于具有簡(jiǎn)單通信和交互行為的大種群/群體的集體智能、生物進(jìn)化機(jī)制和物理過(guò)程分為群體智能優(yōu)化算法、進(jìn)化優(yōu)化算法和物理優(yōu)化算法，同時(shí)隨著技術(shù)發(fā)展，產(chǎn)生了新興算法和混合算法。

1）群體智能（swarm intelligence，SI）優(yōu)化算法

a）蟻群優(yōu)化（ACO）。該算法由“螞蟻系統(tǒng)”［28］發(fā)展而來(lái)。為了解決云計(jì)算中的瞬時(shí)峰值負(fù)載問(wèn)題，Duan等人［29］提出了基于ACO的改進(jìn)算法，稱為Pre-Ant Policy，該算法由預(yù)測(cè)模型組成，改進(jìn)了各種QoS參數(shù)。

b）人工蜂群（ABC）［30］。最初由Karaboga于2005年提出，其基本原理是通過(guò)觀察蜜蜂搜索和采蜜的行為，找到最優(yōu)采蜜路徑。Babu和Krishna提出了一種基于ABC算法的行為負(fù)載平衡算法，該算法不斷地平衡工作負(fù)載，并改進(jìn)各種關(guān)鍵性能指標(biāo)參數(shù)。

c）細(xì)菌飼料優(yōu)化（BFO）。其由Muller等人于2002年提出，主要原理是細(xì)菌覓食的集體行為，包括群居、趨化、繁殖和消除/擴(kuò)散四個(gè)過(guò)程。Tang等人［31］通過(guò)在線處理實(shí)時(shí)應(yīng)用程序，以少量資源來(lái)平衡負(fù)載，通過(guò)離線使用BFO算法進(jìn)行全局調(diào)度，增加整個(gè)系統(tǒng)的穩(wěn)定性和性能。

d）粒子群優(yōu)化（PSO）。由Eberhart等人［32］于1995年提出，其主要思想是利用粒子的集體行為找到食物。PSO發(fā)展迅速，如標(biāo)準(zhǔn)PSO、改良粒子群算法［33］和二元粒子群算法及其變體等。

2）進(jìn)化優(yōu)化算法

進(jìn)化算法（EA）是進(jìn)化計(jì)算的算法分支，最初由Holland［34］于1975年提出，通過(guò)開發(fā)一組初始候選解決方案來(lái)找到最佳解決方案。

遺傳算法（GA）由約翰·霍蘭德于1960年提出，算法基于適應(yīng)度值選擇染色體，進(jìn)行交叉和突變產(chǎn)生新的解決方案，直到求得可行解。Shishido等人［35］提出的一種主要針對(duì)截止時(shí)間作為約束的遺傳算法，有效提升成本效益和確保安全方面。遺傳算法被證明是計(jì)算機(jī)科學(xué)中解決的NP難題的有效工具。Tsai等人［36］基于GA，使用差分策略實(shí)現(xiàn)變異操作，提出改進(jìn)的差分進(jìn)化算法（IDEA），以提升性能。

3）物理算法

物理算法是由物理學(xué)定律啟發(fā)而來(lái)。物理環(huán)境復(fù)雜多變，具有隨機(jī)性，算法混合全局和局部（基于鄰域的）搜索方法，使得在解決任務(wù)調(diào)度優(yōu)化問(wèn)題時(shí)表現(xiàn)得非常出色。

a）模擬退火（SA）。其由Kirk于1984年引入，主要原理是模擬了材料的退火過(guò)程，屬于無(wú)記憶算法，即在搜索過(guò)程中不存儲(chǔ)任何信息。Wang等人［37］提出了一種名為SA的高效物理資源分配算法，其性能優(yōu)于GA和PSO算法，并克服了具有成本意識(shí)的VNE問(wèn)題。

b）和諧搜索（HS）。Geem等人［38］提出HS進(jìn)化算法，通過(guò)模仿音樂(lè)即興創(chuàng)作，和聲即代表可能的解決方案。此外，還有引力搜索算法（GSA）和Tabu搜索算法等（TS）。

4）新興算法

近年來(lái)，許多新的元啟發(fā)式算法已經(jīng)被設(shè)計(jì)用于適應(yīng)復(fù)雜的云計(jì)算環(huán)境，以應(yīng)用于云計(jì)算中的不同復(fù)雜優(yōu)化問(wèn)題。如樹生長(zhǎng)算法（TGA）、飛餓撲火優(yōu)化算法（MFO）和珊瑚礁優(yōu)化［39］等。元啟發(fā)算法無(wú)須特定條件，但模塊聚合復(fù)雜，搜索易過(guò)早陷入局部最優(yōu)解。

2.1.3 混合式算法

單獨(dú)的調(diào)度算法對(duì)于特定領(lǐng)域的效果有著較好的反響，但面對(duì)實(shí)際任務(wù)調(diào)度中用戶需求動(dòng)態(tài)多變的現(xiàn)狀，產(chǎn)生了將不同算法融合的混合式算法，有效提高時(shí)間與效果方面的性能，成為目前重要的研究方向。Saravanan等人［40］提出了IWHOLF-TSC算法，改進(jìn)帶有Lévy飛行算法的野馬優(yōu)化。實(shí)驗(yàn)結(jié)果表明，該算法的性能優(yōu)于其他最先進(jìn)的調(diào)度算法。何婧媛等人［41］將布谷鳥搜索（CS）和粒子群優(yōu)化（PSO）兩種算法相結(jié)合，提出多目標(biāo)布谷鳥粒子群優(yōu)化算法（MO-CPSO）。CloudSim評(píng)估表明，與CS、ACO、和min-min算法相比，MO-CPSO算法使完成時(shí)間、開銷和截止時(shí)間違背率均最小。表1是單云環(huán)境下任務(wù)調(diào)度算法的對(duì)比總結(jié)。

對(duì)比發(fā)現(xiàn)，啟發(fā)式算法的研究與發(fā)展歷史最為悠久，其通常能夠?qū)崿F(xiàn)某一方面的性能最優(yōu)，如SJF算法在獨(dú)立性上表現(xiàn)出色。但是，相對(duì)于FCFS、RR、SJF等靜態(tài)調(diào)度算法，min-min、RR、OLB、MCT、MET等動(dòng)態(tài)算法更適應(yīng)于動(dòng)態(tài)變化的云環(huán)境。此外，傳統(tǒng)的調(diào)度算法無(wú)法找到多維調(diào)度問(wèn)題的最優(yōu)結(jié)果。因此，元啟發(fā)式任務(wù)調(diào)度算法成為解決云計(jì)算任務(wù)調(diào)度算法的主流選擇，但是往往實(shí)現(xiàn)更加復(fù)雜，難以廣泛應(yīng)用，實(shí)用性較差。而混合式算法通過(guò)保留傳統(tǒng)式啟發(fā)算法部署簡(jiǎn)單的特點(diǎn)與啟發(fā)式算法的高性能，實(shí)現(xiàn)算法優(yōu)化升級(jí)，實(shí)驗(yàn)數(shù)據(jù)表明，混合算法產(chǎn)生1+1>2的效果，在不同程度上獲得了較好的性能結(jié)果。但是也會(huì)導(dǎo)致額外開銷、利用率不高等現(xiàn)象。

2.2 聯(lián)盟云環(huán)境

聯(lián)盟云環(huán)境［15］是指各用戶獨(dú)立擁有自己的云服務(wù)提供商或私有云環(huán)境，同時(shí)在聯(lián)盟云中的每一個(gè)用戶彼此之間互聯(lián)基礎(chǔ)設(shè)施實(shí)現(xiàn)資源共享。在政府機(jī)關(guān)、教育機(jī)構(gòu)或?qū)W術(shù)組織中較為常見(jiàn)。通常分為對(duì)等聯(lián)盟和集中式聯(lián)盟兩種聯(lián)盟方式。對(duì)等聯(lián)盟是指聯(lián)合中的每個(gè)參與者云都是一個(gè)對(duì)等云，在沒(méi)有任何中介的情況下與其他人協(xié)作。在這種類型的云聯(lián)盟中，沒(méi)有中央組件，通常使用某個(gè)參與者云作為代理處理。集中式聯(lián)盟指聯(lián)合中的所有參與者云通過(guò)一個(gè)中央實(shí)體完成事物處理。本節(jié)從任務(wù)的依賴關(guān)系出發(fā)將任務(wù)調(diào)度算法分為工作流調(diào)度和獨(dú)立任務(wù)調(diào)度。

2.2.1 云聯(lián)盟中的工作流調(diào)度

文獻(xiàn)［42］提出一種基于QoS權(quán)重的聯(lián)盟云工作流的調(diào)度算法，在SmartFed的實(shí)驗(yàn)中，它為聯(lián)合DC、分配器、隊(duì)列管理和存儲(chǔ)添加所需的包，使用循環(huán)算法對(duì)DC中的VM進(jìn)行分配，并取得較好的效果。

Coutinho等人［43］提出了 GraspCC-fed，基于貪婪隨機(jī)自適應(yīng)搜索程序（GRASP），有效處理聯(lián)邦云中的工作流執(zhí)行，并與Sci-Cumulus工作流程引擎相結(jié)合。

文獻(xiàn)［44］提出了MOHEFT，算法擴(kuò)展了異構(gòu)最早完成時(shí)間（HEFT）工作流調(diào)度算法，處理多個(gè)沖突目標(biāo)并逼近帕累托前沿最優(yōu)調(diào)度。實(shí)驗(yàn)表明，當(dāng)具有幾個(gè)并行任務(wù)以及多個(gè)并行工作流時(shí)，MOHEFT性能最優(yōu)。

2.2.2 云聯(lián)盟中的任務(wù)調(diào)度

文獻(xiàn)［45］提出了一種在聯(lián)邦云中執(zhí)行大規(guī)模分布式計(jì)算的通用框架，通過(guò)引入云計(jì)算能力（GWcloud）改進(jìn)的試點(diǎn)系統(tǒng)（GWpilot），可以根據(jù)可用資源實(shí)例化VM，允許用戶整合其資源調(diào)配，但模型不支持公共服務(wù)提供商。

文獻(xiàn)［46］提出一種基于FDMR（federated distributed Map-educe）的分布式算法，以在云聯(lián)盟中跨地理分布地調(diào)度作業(yè)。性能評(píng)估證明，F(xiàn)DMR解決方案非常接近精確方法，并提高了資源的利用率、數(shù)據(jù)傳輸性能、和資源可用性等因素，但是成本巨大。

Gouasmi等人［47］提出了一種分布式調(diào)度方案FedSCD，用于處理聯(lián)盟分布式集群中的MapReduce應(yīng)用程序。它通過(guò)減少空閑VM和防止資源浪費(fèi)來(lái)提供更好的資源管理和調(diào)度響應(yīng)時(shí)間，降低執(zhí)行成本，提高性能。表2對(duì)聯(lián)盟云環(huán)境下任務(wù)調(diào)度算法進(jìn)行總結(jié)歸納。

對(duì)比發(fā)現(xiàn)，聯(lián)盟云是學(xué)術(shù)與政府等機(jī)構(gòu)的常見(jiàn)形式，其中開發(fā)了大量科學(xué)技術(shù)結(jié)合任務(wù)調(diào)度算法，并通常將多目標(biāo)優(yōu)化作為目標(biāo)函數(shù)，主要針對(duì)完成時(shí)間和成本進(jìn)行優(yōu)化，同時(shí)也充分考慮了網(wǎng)絡(luò)帶寬資源利用率等。但是由于計(jì)算需求的激增以及云環(huán)境的特殊性，需要對(duì)各云用戶進(jìn)行規(guī)范，目前的聯(lián)盟云任務(wù)調(diào)度算法仍然無(wú)法滿足數(shù)據(jù)密集和計(jì)算密集型的需求，極大地制約了聯(lián)盟云任務(wù)調(diào)度算法的研究與發(fā)展。

2.3 混合云環(huán)境

混合云指包含公有云和私有云的兩個(gè)或兩個(gè)以上的云，用戶往往將其敏感工作流程分配給私有云，當(dāng)私有云缺乏執(zhí)行用戶任務(wù)所需的資源時(shí)，可以從公有云獲得共享資源，充分利用兩者優(yōu)勢(shì)，得到價(jià)格便宜又優(yōu)質(zhì)的服務(wù)，但對(duì)不同服務(wù)提供商以及云類型的統(tǒng)一納管和高效運(yùn)維難度加大?；旌显剖悄壳肮I(yè)市場(chǎng)主流的選擇，也是學(xué)術(shù)界的研究熱點(diǎn)。

2.3.1 混合云中的工作流調(diào)度

文獻(xiàn)［48］提出通信鏈路可用性的不確定性調(diào)度算法。在云中，由于通信鏈路中的并發(fā)性，很難獲得精確數(shù)據(jù)，導(dǎo)致制造時(shí)間和成本增加。Lin等人［49］提出HIAP，這是一種混合云上SWF的在線調(diào)度方法，將應(yīng)用程序劃分為一組相關(guān)任務(wù)，并考慮帶寬、數(shù)據(jù)傳輸成本和計(jì)算成本等約束，提升執(zhí)行時(shí)間的準(zhǔn)確。

2.3.2 混合云中的任務(wù)調(diào)度

Yuan等人［50］提出一種利潤(rùn)最大化算法（PMA），PMA提供的臨時(shí)任務(wù)調(diào)度可以動(dòng)態(tài)調(diào)度所有到達(dá)任務(wù)。通過(guò)混合啟發(fā)式優(yōu)化算法模擬退火粒子群優(yōu)化（SAPSO）來(lái)解決PMA每次迭代中的子問(wèn)題。大量的仿真實(shí)驗(yàn)表明，算法在保證服務(wù)延遲的同時(shí)，大大提高了私有云的吞吐量和利潤(rùn)。

文獻(xiàn)［51］提出TTSA調(diào)度算法，通過(guò)混合整數(shù)線性程序求解成本問(wèn)題，并通過(guò)混合模擬退火粒子群來(lái)優(yōu)化。實(shí)驗(yàn)結(jié)果表明，TTSA生成的最優(yōu)或次優(yōu)調(diào)度策略可以有效地提高私有CDC的吞吐量并降低成本，滿足任務(wù)響應(yīng)時(shí)間的要求。表3對(duì)混合云環(huán)境下任務(wù)調(diào)度算法進(jìn)行總結(jié)歸納。

對(duì)比發(fā)現(xiàn)，混合云環(huán)境的任務(wù)調(diào)度算法通常是對(duì)單云環(huán)境任務(wù)調(diào)度算法的優(yōu)化，主要集中于對(duì)完成時(shí)間與成本上的優(yōu)化，但總體仍是對(duì)多目標(biāo)的優(yōu)化。但目前多數(shù)任務(wù)調(diào)度算法無(wú)法在真實(shí)環(huán)境中進(jìn)行部署與測(cè)試，限制了算法的發(fā)展。

2.4 多云環(huán)境

多云環(huán)境是指由不同云服務(wù)提供商CSP（cloud service provider）提供的公有云的混合。多個(gè)公有云服務(wù)提供商的競(jìng)爭(zhēng)提供了更好的服務(wù)，但構(gòu)建復(fù)雜，管理困難。

2.4.1 多云中的工作流調(diào)度

Gupta等人［52］提出了一種基于傳輸時(shí)間意識(shí)的多云環(huán)境下的高效工作流調(diào)度算法。算法包括計(jì)算任務(wù)的優(yōu)先級(jí)和基于優(yōu)先級(jí)進(jìn)行虛擬機(jī)（VM）選擇兩個(gè)階段，仿真結(jié)果表明，算法在生成時(shí)間和利用率方面都優(yōu)于其他算法。文獻(xiàn)［53］提出一種基于多目標(biāo)PSO的調(diào)度方法，在PSO算法基礎(chǔ)上，對(duì)每個(gè)CSP應(yīng)用定價(jià)模型和一些性能指標(biāo)，進(jìn)行工作流調(diào)度。實(shí)驗(yàn)表明，算法性能優(yōu)于CMOHEFT和隨機(jī)調(diào)度算法。

2.4.2 多云中的任務(wù)調(diào)度

文獻(xiàn)［54］針對(duì)異構(gòu)多云環(huán)境提出了三種任務(wù)劃分調(diào)度算法，分別是CTPS、CMMTPS和CMAXMTPS，它包括預(yù)處理和處理步驟兩個(gè)程序，達(dá)到縮短調(diào)度時(shí)間并提高資源利用率的效果，但是對(duì)于預(yù)處理和處理階段之間的通信時(shí)間以及傳輸和執(zhí)行時(shí)間的成本考慮不夠。文獻(xiàn)［55］提出一種用于多云系統(tǒng)的自適應(yīng)調(diào)度方法（DSS），它結(jié)合了可分割負(fù)載理論和節(jié)點(diǎn)可用性預(yù)測(cè)方法，提出的多云架構(gòu)支持幾個(gè)地理分散的網(wǎng)關(guān)，具有各種計(jì)算和通信功能的資源池，可以使用具有各種容量的鏈路連接到所有節(jié)點(diǎn)。結(jié)果表明，算法能夠有效減少任務(wù)的處理時(shí)間。表4對(duì)多云環(huán)境下任務(wù)調(diào)度算法進(jìn)行總結(jié)歸納。

對(duì)比發(fā)現(xiàn)，多云環(huán)境越來(lái)越被應(yīng)用于實(shí)際中，但是不同云之間進(jìn)行大量的信息傳輸與共享，導(dǎo)致時(shí)間開銷加大，而任務(wù)調(diào)度算法容易時(shí)間復(fù)雜度過(guò)高，因此，大量算法對(duì)時(shí)間復(fù)雜度進(jìn)行優(yōu)化，但是對(duì)優(yōu)化目標(biāo)的優(yōu)化上沒(méi)有考慮多種優(yōu)化目標(biāo)。

綜合對(duì)任務(wù)調(diào)度算法的分類與評(píng)價(jià)發(fā)現(xiàn)，目前任務(wù)調(diào)度算法的發(fā)展逐步向更適用于復(fù)雜云環(huán)境與滿足多目標(biāo)的QoS優(yōu)化。但云計(jì)算通過(guò)資源虛擬化與容器等技術(shù)，能夠?qū)Ω黝愘Y源進(jìn)行統(tǒng)一管理，通常有基本資源分配算法（basic resource allocation，BRA）、公平調(diào)度算法（fair scheduler）、容量調(diào)度算法（capacity scheduker）以及基于用戶資源配額的資源彈性分配算法（QREA）等［55］，各類資源分配算法能夠提升多目標(biāo)優(yōu)化效果，此外，基于資源組合預(yù)測(cè)的云計(jì)算任務(wù)調(diào)度算法［56］綜合考慮資源的分布情況與任務(wù)的調(diào)度，避免盲目調(diào)度，但資源未能根據(jù)任務(wù)情況動(dòng)態(tài)改變。因此，目前算法中缺乏同時(shí)兼顧資源分配與任務(wù)調(diào)度的算法。

3 挑戰(zhàn)與展望

未來(lái)應(yīng)從以下四個(gè)方面進(jìn)行進(jìn)一步研究。

a）本文通過(guò)整理調(diào)度算法相關(guān)文章，發(fā)現(xiàn)現(xiàn)有算法都以單云任務(wù)調(diào)度算法改進(jìn)優(yōu)化為主，缺少對(duì)云間環(huán)境的架構(gòu)研究，導(dǎo)致算法的普適性差，無(wú)法適應(yīng)多種多樣的云間環(huán)境。下一步應(yīng)從云間環(huán)境本身出發(fā)，以統(tǒng)一的API屏蔽底層基礎(chǔ)設(shè)施導(dǎo)致的差異，設(shè)計(jì)更普適的算法。

b）通過(guò)整理發(fā)現(xiàn)，無(wú)論是單云環(huán)境還是云間環(huán)境，用戶對(duì)于云服務(wù)的需求快速增長(zhǎng)，不但要考慮多種優(yōu)化目標(biāo)，同時(shí)很多優(yōu)化目標(biāo)之間存在彼消此漲問(wèn)題，導(dǎo)致多目標(biāo)優(yōu)化無(wú)法兼顧的問(wèn)題，下一步應(yīng)綜合考量多種優(yōu)化目標(biāo)，并根據(jù)重要程度賦權(quán)重，提出滿足多個(gè)維度優(yōu)化目標(biāo)的任務(wù)調(diào)度算法。

c）隨著人工智能、物聯(lián)網(wǎng)、霧計(jì)算以及基于納米計(jì)算/量子、非傳統(tǒng)體系結(jié)構(gòu)等多種新興技術(shù)興起，今后的云計(jì)算環(huán)境將更加復(fù)雜多樣，下一步應(yīng)將新興技術(shù)與傳統(tǒng)云計(jì)算進(jìn)行融合，實(shí)現(xiàn)任務(wù)調(diào)度智能化、輕量化，推動(dòng)云計(jì)算實(shí)現(xiàn)跨越式發(fā)展。

d）目前的調(diào)度優(yōu)化算法主要從任務(wù)調(diào)度角度出發(fā)進(jìn)行優(yōu)化，往往忽略資源分配的重要性，但在現(xiàn)有系統(tǒng)中，對(duì)資源優(yōu)化分配所取得的微弱效果往往帶來(lái)巨大的系統(tǒng)開銷。容器技術(shù)的提出，其輕量化和彈性擴(kuò)縮容的性能，為兼顧資源分配與任務(wù)調(diào)度提供可行的方案。下一步應(yīng)從容器技術(shù)出發(fā)，對(duì)資源進(jìn)行更加有效的納管與彈性分配并實(shí)現(xiàn)資源根據(jù)任務(wù)量變化的動(dòng)態(tài)調(diào)度，同時(shí)將用戶提交的任務(wù)請(qǐng)求與資源進(jìn)行最佳映射，達(dá)到多QoS優(yōu)化，實(shí)現(xiàn)云環(huán)境下任務(wù)調(diào)度性能的進(jìn)一步優(yōu)化。

e）目前，大多數(shù)企業(yè)、政府、軍隊(duì)等機(jī)構(gòu)對(duì)于行業(yè)云、數(shù)據(jù)云的需求越來(lái)越大，位于Pass層的大量軟件下沉到Iass層，任務(wù)調(diào)度算法不再局限于傳統(tǒng)對(duì)算力、存儲(chǔ)、網(wǎng)絡(luò)等基礎(chǔ)資源調(diào)度，還要對(duì)應(yīng)用的資源進(jìn)行智能化調(diào)度，為數(shù)據(jù)云全域內(nèi)的虛擬化資源和容器化資源實(shí)現(xiàn)自動(dòng)及自主調(diào)度。目前，針對(duì)行業(yè)云、數(shù)據(jù)云的算法研究仍然存在大量空白，下一步應(yīng)基于行業(yè)云、數(shù)據(jù)云架構(gòu)，提出適用的任務(wù)調(diào)度算法。

4 結(jié)束語(yǔ)

本文主要完成了任務(wù)調(diào)度與云環(huán)境的概念明確。通過(guò)梳理現(xiàn)有的云計(jì)算任務(wù)調(diào)度算法，提出一種新的任務(wù)調(diào)度算法分類方法。根據(jù)云環(huán)境的不同，將云環(huán)境分為單云環(huán)境、聯(lián)盟云環(huán)境、混合云環(huán)境、多云環(huán)境，并基于不同環(huán)境進(jìn)行了分類和比較。對(duì)比發(fā)現(xiàn)，傳統(tǒng)啟發(fā)式任務(wù)調(diào)度算法對(duì)某一特定目標(biāo)優(yōu)化效果較好，但是用戶往往提出多種優(yōu)化目標(biāo)，因此提出元啟發(fā)式算法，但由于其實(shí)現(xiàn)復(fù)雜，難以應(yīng)用部署。混合式算法是傳統(tǒng)啟發(fā)式算法與混合式算法的結(jié)合，保留了兩者的優(yōu)勢(shì)，是目前主流的任務(wù)調(diào)度算法，但是存在額外開銷以及資源負(fù)載不均衡等問(wèn)題，因此仍值得進(jìn)一步研究?jī)?yōu)化。此外，云環(huán)境中任務(wù)復(fù)雜多樣，任務(wù)間的關(guān)系也相互交疊，獨(dú)立任務(wù)調(diào)度無(wú)法再適應(yīng)現(xiàn)有環(huán)境，目前，任務(wù)調(diào)度算法研究主要以工作流調(diào)度為主。

總的來(lái)說(shuō)，本文提供了調(diào)度算法的全面理解，未來(lái)在數(shù)據(jù)云、行業(yè)云的調(diào)度算法研究中，應(yīng)注重對(duì)混合式工作流調(diào)度的研究。

參考文獻(xiàn)：

[1]許子明，田楊鋒.云計(jì)算的發(fā)展歷史及其應(yīng)用［J］.信息記錄材料，2018，19（8）：66-67.（Xu Ziming， Tian Yangfeng. The development history and applications of cloud computing［J］.Information Recor-ding Materials，2018，19（8）：66-67.）

［2]Mell P M， Grance T. The NIST definition of cloud computing， 800-145［R］.Gaithersburg，MD：National Institute of Standards and Technology，2011.

［3]Wikipedia.Cloud computing［EB/OL］.（2009-03-10）.http：//en.wikipedia.org/wiki/Cloud_computing.

［4]中國(guó)云計(jì)算網(wǎng).什么是云計(jì)算？［EB/OL］.（2008-05-14）［2009-02-27］.http：//www.cloudcomputing-china.cn/Article/ShowArticle.asp？ArticleID=1.（Cloud Computing Network of China.What is cloud computing？［EB/OL］.（2008-05-14）［2009-02-27］.http：//www.cloudcomputing-china.cn/Article/ShowArticle.asp？ArticleID=1.）

［5]Amin R， Kumar N， Biswas G P， et al. A light weight authentication protocol for IoT-enabled devices in distributed cloud computing environment［J］.Future Generation Computer Systems，2018;78：1005-1019.

［6]羅紅，慕德俊，鄧智群，等.網(wǎng)格計(jì)算中任務(wù)調(diào)度研究綜述［J］.計(jì)算機(jī)應(yīng)用研究，2005，22（5）：16-19.（Luo Hong， Mu Dejun， Deng Zhiqun， et al. A review of job scheduling for grid computing［J］.Application Research of Computers，2005，22（5）：16-19.）

［7]Juarez F， Ejarque J， Badia R M. Dynamic energy-aware scheduling for parallel task-based application in cloud computing［J］.Future Generation Computer Systems，2018，78：257-271.

［8]Madni S H H， Latiff M S A， Coulibaly Y， et al. Recent advancements in resource allocation techniques for cloud computing environment： a systematic review［J］.Cluster Computing，2017，20（3）：2489-2533.

［9]Mikavica B， Kostic＇-Ljubisavljevic＇ A. Pricing and bidding strategies for cloud spot block instances［C］//Proc of the 41st International Convention on Information and Communication Technology， Electronics and Microelectronics.Piscataway，NJ：IEEE Press，2018：0384-0389.

［10]Ullman J D. NP-complete scheduling problems［J］.Journal of Computer and System Sciences，1975，10（3）：384-393.

［11]Singh S， Chana I. Resource provisioning and scheduling in clouds： QoS perspective［J］.The Journal of Supercomputing，2016，72（3）：926-960.

［12]Wu Kaiyue， Lu Ping， Zhu Zuqing. Distributed online scheduling and routing of multicast-oriented tasks for profit-driven cloud computing［J］.IEEE Communications Letters，2016，20（4）：684-687.

［13]Hosseini Shirvani M， Rahmani A M， Sahafi A. An iterative mathema-tical decision model for cloud migration： a cost and security risk approach［J］.Software： Practice Experience，2018，48（3）：449-485.

［14]Zhang Bo， Zeng Zeng， Shi Xiupeng， et al. A novel cooperative resource provisioning strategy for multi-cloud load balancing［J］.Journal of Parallel and Distributed Computing，2021，152：98-107.

［15]Chauhan1 S S， Pilli E S， Joshi R C. A broker based framework for federated cloud environment［C］//Proc of International Conference on Emerging Trends in Communication Technologies.Piscataway，NJ：IEEE Press，2016：1-5.

［16]Linthicum D S. Emerging hybrid cloud patterns［J］.IEEE Cloud Computing，2016，3（1）：88-91.

［17]Li Xiaoyong， Ma Huadong， Yao Wenbin， et al. Data-driven and feedback-enhanced trust computing pattern for large-scale multi-cloud collaborative services［J］.IEEE Trans on Services Computing，2018，11（4）：671-684.

［18]Shi Yang， Chen Zhaoyun， Quan Wei， et al. A performance study of static task scheduling heuristics on cloud-scale acceleration architecture［C］//Proc of the 5th International Conference on Computing and Data Engineering.New York：ACM Press，2019：81-85.

［19]Xhafa F， Abraham A. Meta-heuristics for grid scheduling problems［M］//Xhafa F， Abraham A. Metaheuristics for scheduling in distri-buted computing environments.Berlin：Springer，2008：1-37.

［20]Liu Juefu， Liu Peng. The research of load imbalance based on min-min in grid［C］//Proc of International Conference on Computer Design and Applications.Piscataway，NJ：IEEE Press，2010：V4-1-V4-4.

［21]童釗，鄧小妹，陳洪劍，等.云環(huán)境下基于強(qiáng)化學(xué)習(xí)的多目標(biāo)任務(wù)調(diào)度算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2020，41（2）：285-290.（Tong Zhao， Deng Xiaomei， Chen Hongjian， et al. A multi-objective task scheduling algorithm based on reinforcement learning in cloud environments［J］.Journal of Chinese Computer Systems，2020，41（2）：285-290.）

［22]Devi D C. Load balancing in cloud computing environment using improved weighted round robin algorithm for non-preemptive dependent tasks［J］.The Scientific World Journal，2016，2016：article ID 3896065.

［23]Sheikhalishahi M， Wallace R M， Grandinetti L， et al. A multi-dimensional job scheduling[J].Future Generation Computer Systems， 2016，54：123-131.

［24]Sheikhalishahi M， Wallace R M， Grandinetti L， et al. A packing problem approaches to energy-aware load distribution in clouds［J］.Future Generation Computer Systems，2016，54：123-131.

［25]Shyam G K， Manvi S S. Resource allocation in cloud computing using agents［C］//Proc of IEEE International Advance Computing Confe-rence.Piscataway，NJ：IEEE Press，2015：458-463.

［26]Lavanya M， Shanthi B， Saravanan S. Multi objective task scheduling algorithm based on SLA and processing time suitable for cloud environment［J］.Computer Communications，2020，151：183-195.

［27]Al-Maytami B A， Fan P， Hussain A， et al. A task scheduling algorithm with improved makespan based on prediction of tasks computation time algorithm for cloud computing［J］.IEEE Access，2019，7：916-926.

［28]Dorigo M. Optimization， learning and natural algorithms［D］.Italy：Politecnico di Milano，1992.

［29]Duan Hancong， Chen Chao， Min Geyong， et al. Energy-aware scheduling of virtual machines in heterogeneous cloud computing systems［J］.Future Generation Computer Systems，2017，74：142-150.

［30]Hajimirzaei B， Navimipour N J. Intrusion detection for cloud computing using neural networks and artificial bee colony optimization algorithm［J］.ICT Express，2019，5（1）：56-59.

［31]Tang Linlin， Li Zuohua， Ren Pingfei. et al. Online and offline based load balance algorithm in cloud computing［J］.Knowledge-Based Systems，2017，138：91-104.

［32]Eberhart R， Kennedy J. A new optimizer using particle swarm theory［C］//Proc of the 6th International Symposium on Micro Machine and Human Science.Piscataway，NJ：IEEE Press，1995：39-43.

［33]Kumar M， Sharma S C. PSO-COGENT： cost and energy efficient scheduling in cloud environment with deadline constraint［J］.Sustai-nable Computing：Informatics and Systems，2018，19：147-164.

［34]Holland J H. Adaptation in natural and artificial systems：an introductory analysis with applications to biology， control， and artificial intelligence［M］.Cambridge，MA：MIT Press，1992.

［35]Shishido H Y， Estrella J C， Toledo C F M， et al. Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds［J］.Computers & Electrical Engineering，2018，69：378-394.

［36]Tsai J T， Feng Jiacen， Chou J H， et al. Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm［J］.Computers & Operations Research，2013，40（12）：3045-3055.

［37]Wang Wenbo， Chang Xiaolin， Liu Jiqiang， et al. Simulated annealing based resource allocation for cloud data centers［C］//Proc of the 15th Annual Conference Companion on Genetic and Evolutionary Computation.New York：ACM Press，2013：81-82.

［38]Geem Z W， Kim J H， Loganathan G V. A new heuristic optimization algorithm：harmony search［J］.Simulation，2001，76（2）：60-68.

［39]Wan Shuzhen， Qi Lixin. An improved coral reef optimization-based scheduling algorithm for cloud computing［J］.Journal of Mathema-tics，2021，2021：article ID 5532288.

［40]Saravanan G， Neelakandan S， Ezhumalai P， et al. Improved wild horse optimization with Lévy flight algorithm for effective task scheduling in cloud computing［J］.Journal of Cloud Computing，2023，12（1）：1-14.

［41]何婧媛，孫乾坤.布谷鳥粒子群優(yōu)化算法的多目標(biāo)任務(wù)調(diào)度［J］.信息技術(shù)，2020，44（5）：37-40.（He Jingyuan， Sun Qiankun. Multi objective task scheduling of Cuckoo particle swarm optimization［J］.Information Technology，2020，44（5）：37-40.）

［42]Chudasama V， Shah J， Bhavsar M. Weight based workflow scheduling in cloud federation［M］//Satapathy S， Joshi A. Information and Communication Technology for Intelligent Systems.Cham：Springer，2017：405-411.

［43]Coutinho R D C， Drummond L M， Frota Y， et al. Optimizing virtual machine allocation for parallel scientifc workflows in federated clouds［J］.Future Generation Computer Systems，2015，46：51-68.

［44]Durillo J J， Prodan R， Barbosa J G. Pareto tradeoff scheduling of workflows on federated commercial clouds［J］.Simulation Modelling Practice and Theory，2015，58：95-111.

［45]Rubio-Montero A J， Huedo E， Mayo-García R. Scheduling multiple virtual environments in cloud federations for distributed calculations［J］.Future Generation Computer Systems，2017，74：90-103.

［46]Gouasmi T， Louati W， Kacem A H. Exact and heuristic MapReduce scheduling algorithms for cloud federation［J］.Computers & Electrical Engineering，2018，69：274-286.

［47]Gouasmi T， Louati W， Kacem A H. Cost-efficient distributed mapreduce job scheduling across cloud federation［C］//Proc of IEEE International Conference on Services Computing.Piscataway，NJ：IEEE Press，2017：289-296.

［48]Bittencourt L F， Madeira E R M， Da Fonseca N L S. Impact of com-munication uncertainties on workflow scheduling in hybrid clouds［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2012：1623-1628.

［49]Lin Bing， Guo Wenzhong， Lin Xiuyan. Online optimization scheduling for scientifc workflows with deadline constraint on hybrid clouds［J］.Concurrency and Computation，2016，28（11）：3079-3095.

［50]Yuan Haitao， Bi Jing， Tan Wei， et al. Temporal task scheduling with constrained service delay for profit maximization in hybrid clouds［J］.IEEE Trans on Automation Science and Engineering，2017，14（1）：337-348.

［51]Yuan Haitao， Bi Jing， Tan Wei， et al. TTSA： an effective scheduling approach for delay bounded tasks in hybrid clouds［J］.IEEE Trans on Cybernetics，2017，47（11）：3658-3668.

［52]Gupta I， Kumar M S， Jana P K. Transfer time-aware workflow sche-duling for multi-cloud environment［C］//Proc of International Confe-rence on Computing，Communication and Automation.Piscataway，NJ：IEEE Press，2016：732-737.

［53]Hu Haiyang， Li Zhongjin， Hu Hua， et al. Multi-objective scheduling for scientifc workflow in multicloud environment［J］.Journal of Network and Computer Applications，2018，114：108-122.

［54]Panda S K， Pande S K， Das S. Task partitioning scheduling algorithms for heterogeneous multi-cloud environment［J］.Arabian Journal for Science and Engineering，2018，43（2）：913-933.

［55]Kang S， Veeravalli B， Aung K M M. Dynamic scheduling strategy with efficient node availability prediction for handling divisible loads in multi-cloud systems［J］.Journal of Parallel and Distributed Computing，2018，113：1-16.

［56]劉曉東，趙曉芳，金巖，等.企業(yè)私有云環(huán)境下面向高性能計(jì)算的資源彈性分配算法［J］.高技術(shù)通信，2018，28（8）：669-676.（Liu Xiao-dong， Zhao Xiaofang， Jin Yan， et al. Resource elastic allocation algorithm for high performance computing in enterprise private cloud environment［J］.High Technology Letters，2018，28（8）：669-676.）

［57]程宏兵.基于資源預(yù)測(cè)的網(wǎng)格任務(wù)調(diào)度模型［J］.計(jì)算機(jī)應(yīng)用，2010，30（9）：2530-2534，2544.（Cheng Hongbing. Grid task sche-duling model based on resource prediction［J］.Journal of Computer Application，2010，30（9）：2530-2534，2544.）

收稿日期：2023-02-28；修回日期：2023-04-20

基金項(xiàng)目：軍委網(wǎng)信科研資助項(xiàng)目

作者簡(jiǎn)介：陳紅華（1998-），女，浙江桐鄉(xiāng)人，碩士研究生，主要研究方向?yàn)槊嫦蚨鄻踊蝿?wù)的云計(jì)算；崔翛龍（1973-），男（通信作者），安徽長(zhǎng)豐人，教授，博導(dǎo)，主要研究方向?yàn)橹悄芑笓]、任務(wù)大數(shù)據(jù)（xlspace@hotmail.com）；王耀杰（1990-），男，河南洛陽(yáng)人，博士，主要研究方向?yàn)榉纯诸A(yù)警、信息安全、深度學(xué)習(xí).