云中截止時(shí)間動態(tài)分配的工作流調(diào)度成本優(yōu)化算法

摘要：現(xiàn)如今，如何在滿足截止時(shí)間約束的前提下降低工作流的執(zhí)行成本，是云中工作流調(diào)度的主要問題之一。三步列表調(diào)度算法可以有效解決這一問題。但該算法在截止時(shí)間分配階段只能形成靜態(tài)的子截止時(shí)間。為方便用戶部署工作流任務(wù)，云服務(wù)商為用戶提供了的三種實(shí)例類型，其中競價(jià)實(shí)例具有非常大的價(jià)格優(yōu)勢。為解決上述問題，提出了截止時(shí)間動態(tài)分配的工作流調(diào)度成本優(yōu)化算法（S-DTDA）。該算法利用粒子群算法對截止時(shí)間進(jìn)行動態(tài)分配，彌補(bǔ)了三步列表調(diào)度算法的缺陷。在虛擬機(jī)選擇階段，該算法在候選資源中增加了競價(jià)實(shí)例，大大降低了執(zhí)行成本。實(shí)驗(yàn)結(jié)果表明，相較于其他經(jīng)典算法，該算法在實(shí)驗(yàn)成功率和執(zhí)行成本上具有明顯優(yōu)勢。綜上所述，S-DTDA算法可以有效解決工作流調(diào)度中截止時(shí)間約束的成本優(yōu)化問題。

關(guān)鍵詞：云計(jì)算；工作流調(diào)度；截止期限；競價(jià)實(shí)例；成本優(yōu)化

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A文章編號：1001-3695（2023）01-028-0172-06

doi： 10.19734/j.issn.1001-3695.2022.06.0292

Cost optimization algorithm based on dynamic allocation of deadline for workflow scheduling in clouds

Pan Jikui1，2， Dong Xinyi1，2， Wang Zijian1， Lu Zhenghao1，2， Sun Fuquan1

（1.School of Mathematics amp; Statistics， Northeastern University at Qinhuangdao， Qinhuangdao Hebei 066000， China; 2. College of Information Science amp; Engineering， Northeastern University， Shenyang 110000， China）

Abstract：

Nowadays， how to reduce the execution cost of workflow under the premise of meeting the deadline constraint is one of the main problems of workflow scheduling in cloud. A three-step list scheduling algorithm can solve this problem effectively. However， the algorithm can only form static sub-deadline in deadline allocation stage. To provide convenience for users to deploy workflow tasks， cloud service providers provide users with three types of instances. Among them， spot instance has great price advantage and can greatly reduce the execution cost of workflow. To solve the above problems， this paper proposed a cost optimization algorithm based on dynamic allocation of deadline for workflow scheduling（S-DTDA）. This algorithm used particle swarm optimization to dynamically allocate the deadline， which made up for the defect of the three-step list scheduling algorithm. In the virtual machine selection stage， the algorithm added the spot instance to the candidate resources， which greatly reduced the execution cost. Experimental results show that compared with other classical algorithms， this algorithm has obvious advantages in experimental success rate and execution cost. In conclusion， S-DTDA algorithm can effectively solve the cost optimization problem of deadline constraint in workflow scheduling.

Key words：cloud computing; workflow scheduling; deadline; spot instance; cost optimization

0引言

工作流在生物信息學(xué)、天文學(xué)和物理學(xué)等大規(guī)模建模科學(xué)問題中應(yīng)用廣泛［1］。一個(gè)工作流由成百上千個(gè)任務(wù)和任務(wù)之間的依賴關(guān)系組成。通常使用有向無環(huán)圖（DAG）來描述工作流。工作流調(diào)度的目的是在滿足服務(wù)質(zhì)量約束（QoS）的同時(shí)為工作流中的任務(wù)找到合適的執(zhí)行資源［2］。云計(jì)算的出現(xiàn)和發(fā)展使得將大規(guī)模的工作流應(yīng)用程序部署到云環(huán)境中執(zhí)行成為一種更流行的方法［3］。云環(huán)境包含各種各樣無限的云資源。用戶采用按次付費(fèi)的模式租用云資源來執(zhí)行工作流［4］。更高性能的云資源擁有更快的執(zhí)行速度，同時(shí)也需要更高的租用費(fèi)用。因此同時(shí)考慮執(zhí)行成本和完工時(shí)間是工作流調(diào)度的主要問題之一。在滿足截止時(shí)間約束的前提下最小化執(zhí)行成本是一個(gè)已知的NP難問題［5］。在分布式社區(qū)中，這一問題一直是多年來的熱點(diǎn)［6］。

列表調(diào)度算法是用來解決工作流調(diào)度問題的常用算法。該算法一般包含兩個(gè)步驟：a）利用預(yù)先定義的啟發(fā)式信息設(shè)置各個(gè)任務(wù)的優(yōu)先級并利用優(yōu)先級構(gòu)建一個(gè)任務(wù)列表；b）按照任務(wù)列表中順序?yàn)槊總€(gè)任務(wù)配置合適的云資源。有些研究［7］在兩步列表調(diào)度之前增加了截止時(shí)間環(huán)節(jié)，形成了三步列表調(diào)度算法，并且通過實(shí)驗(yàn)驗(yàn)證了三步列表調(diào)度算法確實(shí)優(yōu)于兩步列表調(diào)度算法。然而現(xiàn)有截止時(shí)間分配策略智能形成靜態(tài)的子截止時(shí)間，所以還有進(jìn)一步優(yōu)化的空間。

在現(xiàn)實(shí)中，云服務(wù)商往往會提供過度的云資源以滿足用戶的峰值需求，從而導(dǎo)致了云數(shù)據(jù)中心的計(jì)算資源未得到充分利用。云服務(wù)商為了減少計(jì)算資源的浪費(fèi)，為用戶提供了更加經(jīng)濟(jì)的計(jì)算資源。Amazon于2009年提出了一種競價(jià)實(shí)例（spot instance）［8］，這是一種基于出價(jià)的實(shí)例類型。當(dāng)用戶的出價(jià)不低于市場價(jià)格時(shí)，用戶可以訪問競價(jià)實(shí)例；當(dāng)用戶出價(jià)低于市場價(jià)格時(shí)，將撤銷該實(shí)例。雖然競價(jià)實(shí)例具有較低的可靠性，但這類資源具有極大的價(jià)格優(yōu)勢。與配置相同的按需實(shí)例相比，競價(jià)實(shí)例可以享受50%～90%的折扣。這不僅為云服務(wù)商降低了資源閑置所帶來的操作和維護(hù)成本，也為用戶節(jié)省了運(yùn)行大規(guī)模工作所需要的成本。雖然如此，但競價(jià)實(shí)例存在可能被隨時(shí)中斷的問題，這會嚴(yán)重影響所提交應(yīng)用程序的性能。所以在使用競價(jià)實(shí)例時(shí)需要特別注意。

本文提出了截止時(shí)間動態(tài)分配的工作流調(diào)度成本優(yōu)化算法（S-DTDA）。該算法利用粒子群算法對截止時(shí)間進(jìn)行動態(tài)分配，彌補(bǔ)了三步列表調(diào)度算法的缺陷。在配置虛擬機(jī)時(shí)，該算法將競價(jià)實(shí)例添加到候選資源池中，大大降低了執(zhí)行成本。

1相關(guān)研究

工作流調(diào)度最開始研究的是多處理器系統(tǒng)［9］和陣列系統(tǒng)［10］。這些系統(tǒng)都是免費(fèi)使用的，所以最開始的研究都是以最小化完工時(shí)間為目的。隨著云計(jì)算的出現(xiàn)和興起，云工作流調(diào)度成為了新的研究課題。用戶以租用的形式使用云資源，使減小執(zhí)行成本成為云中工作流調(diào)度必須要考慮的問題。為解決該問題，相繼出現(xiàn)了很多研究。文獻(xiàn)［11］使用了粒子群算法。文獻(xiàn)［12］改進(jìn)了傳統(tǒng)的粒子群算法，提出了免疫粒子群算法，改善了粒子群算法的收斂速度，提高了算法質(zhì)量。本文提出的S-DTDA算法也使用了粒子群算法，用粒子群中每一個(gè)粒子代表一個(gè)解決方案，則最優(yōu)的粒子代表最佳的解決方案。有些文獻(xiàn)利用了分治的思想進(jìn)行工作流調(diào)度。例如文獻(xiàn)［13］利用了關(guān)鍵路徑的概念，提出了PCP算法。該算法首先找到工作流圖中的關(guān)鍵路徑，并為關(guān)鍵路徑上的任務(wù)分配截止時(shí)間，然后以關(guān)鍵路徑上的任務(wù)為終點(diǎn)繼續(xù)反向查找關(guān)鍵路徑并分配最后期限。文獻(xiàn)［14］在PCP算法的基礎(chǔ)上提出了IC-PCP算法。該算法與PCP具有類似的關(guān)鍵路徑查找方案，然后直接進(jìn)行服務(wù)資源的配置。列表算法經(jīng)常被用于解決工作流調(diào)度問題。有些研究在傳統(tǒng)列表調(diào)度算法的基礎(chǔ)上增加了截止時(shí)間分配的步驟。文獻(xiàn)［7］提出的ProLis算法、文獻(xiàn)［15］提出的DCO/DUCO算法和文獻(xiàn)［16］提出的HAS算法都是按照自定義的啟發(fā)式信息進(jìn)行最后期限的分配。文獻(xiàn)［17］提出了HCDCW算法，該算法將優(yōu)先在私有云中調(diào)度執(zhí)行，當(dāng)任務(wù)執(zhí)行時(shí)間超出任務(wù)截止期約束時(shí)，使用公有云調(diào)度部分工作流。文獻(xiàn)［18］提出了HAPSO算法，該算法在工作流截止期約束下，有效權(quán)衡了完成時(shí)間與執(zhí)行成本。雖然這些方法的調(diào)度結(jié)果都很優(yōu)異，但其大多針對每個(gè)任務(wù)生成靜態(tài)子截止時(shí)間，還可以進(jìn)一步優(yōu)化。上述優(yōu)化算法都是將調(diào)度任務(wù)部署在按需實(shí)例上進(jìn)行。雖然按需實(shí)例工作可靠，但是相對于競價(jià)實(shí)例，其價(jià)格太過昂貴，需要更高的執(zhí)行成本。

當(dāng)競價(jià)實(shí)例作為一種新的資源類型出現(xiàn)后，相繼涌現(xiàn)了大量關(guān)于競價(jià)實(shí)例科研成果。由于競價(jià)實(shí)例的未來市場價(jià)格的不確定性，許多研究對競價(jià)實(shí)例的價(jià)格進(jìn)行預(yù)測并對其容錯(cuò)性進(jìn)行了研究。文獻(xiàn)［19］研究了AR、ETS、ARIMA和GARCH模型。GARCH能夠更好地動態(tài)預(yù)測競價(jià)實(shí)例的短期和中期實(shí)例價(jià)格，AR對GPU實(shí)例中長期價(jià)格預(yù)測具有較好的預(yù)測效果，ETS為基于平滑度的長期競價(jià)實(shí)例價(jià)格預(yù)測提供了較好的結(jié)果，ARIMA給出了基于長期競價(jià)實(shí)例價(jià)格波動的最佳預(yù)測結(jié)果。文獻(xiàn)［20］提出一種隨機(jī)森林回歸算法，能夠?qū)Υ稳占耙恢軆?nèi)的競價(jià)實(shí)例的價(jià)格進(jìn)行準(zhǔn)確預(yù)測。文獻(xiàn)［21］利用了競價(jià)實(shí)例的價(jià)格歷史，建立了K-nearest neighbors（KNN）回歸模型，該模型可以準(zhǔn)確預(yù)測競價(jià)實(shí)例未來的價(jià)格。文獻(xiàn)［22］提出了一個(gè)動態(tài)調(diào)度程序（burst-HADS），有效降低了資金成本，甚至在競價(jià)實(shí)例休眠場景下也滿足了應(yīng)用程序的截止日期。文獻(xiàn)［23］引入了一個(gè)稱為MASA-CUDAlign的新框架，即使多個(gè)實(shí)例被撤銷，也能保證滿足截止時(shí)間。文獻(xiàn)［24］提出了chaos-ANFIS模型，能夠?qū)Ω們r(jià)實(shí)例的未來價(jià)格進(jìn)行精準(zhǔn)預(yù)測。競價(jià)實(shí)例雖然可靠性較低，但其容錯(cuò)機(jī)制和價(jià)格預(yù)測研究已經(jīng)很成熟。利用競價(jià)實(shí)例進(jìn)行工作流調(diào)度任務(wù)能更加有效地降低執(zhí)行成本。

2問題描述

2.1工作流模型

一個(gè)工作流由大量的任務(wù)與任務(wù)之間的依賴關(guān)系組成。工作流模型通常用有向無環(huán)圖DAG=（V， E）來表示。其中，V={t1，t2，…，tn}是有向無環(huán)圖中節(jié)點(diǎn)的集合，工作流中的每一個(gè)任務(wù)都用一個(gè)節(jié)點(diǎn)表示，wi表示任務(wù)ti的工作量。E是有向無環(huán)圖中邊的集合，E中的每一個(gè)元素eij={ti，tj}表示任務(wù)ti和tj的依賴關(guān)系，表示必須在任務(wù)ti執(zhí)行結(jié)束之后才能執(zhí)行任務(wù)tj，這時(shí)把任務(wù)ti和tj分別叫做父任務(wù)和子任務(wù)。如果任務(wù)ti向任務(wù)tj傳輸數(shù)據(jù)，傳輸?shù)臄?shù)據(jù)量用dij表示。本文把一個(gè)沒有父任務(wù)的任務(wù)叫做起始任務(wù)，把一個(gè)沒有子任務(wù)的任務(wù)叫做終止任務(wù)。由于大部分的調(diào)度算法不能適用于一個(gè)工作流存在多個(gè)起始任務(wù)或者多個(gè)終止任務(wù)的情況，所以需要對工作流模型進(jìn)行一般化處理。本文分別在工作流的起始處和終止處添加一個(gè)負(fù)載為零的任務(wù)來代表整個(gè)工作流的起始任務(wù)和終止任務(wù)，分別用tentry和texit表示。圖1展示了一個(gè)工作流模型。

2.2云資源模型

為了對云資源進(jìn)行統(tǒng)一管理和為用戶提供服務(wù)，云服務(wù)商將云資源虛擬化成資源池的形式。云服務(wù)商為用戶提供保留實(shí)例、按需實(shí)例和競價(jià)實(shí)例三種擁有不同計(jì)費(fèi)模式的實(shí)例。每一種資源實(shí)例都擁有多種類型，不同類型的資源擁有不同的處理速度和價(jià)格。越高性能的資源代表越快的處理速度和高昂的價(jià)格。本文基于Amazon EC2的實(shí)際產(chǎn)品建立了按需實(shí)例和競價(jià)實(shí)例兩種資源模型。除競價(jià)實(shí)例的可靠性低外，配置相同的按需實(shí)例和競價(jià)實(shí)例只有計(jì)費(fèi)模式不同，在其他方面沒有區(qū)別。集合R={r1，r2，…，rn}代表用戶可以租用的資源類型的集合。一個(gè)虛擬機(jī)就是一個(gè)具體的資源實(shí)例，用vmtypek表示。其中type∈{d，s}被用來區(qū)分按需實(shí)例和競價(jià)實(shí)例，k類型的按需實(shí)例和競價(jià)實(shí)例分別用vmdk和vmsk表示；k∈R表示虛擬機(jī)的資源類型。工作流中的任務(wù)是在虛擬機(jī)上執(zhí)行的，每一個(gè)虛擬機(jī)vmtypek都是集合VMS={vmd1，vmd2，…，vmdn，vms1，vms2，…，vmsn}中的一個(gè)元素。一個(gè)任務(wù)只能部署到一個(gè)虛擬機(jī)上執(zhí)行，而一個(gè)虛擬機(jī)可以按照既定的順序執(zhí)行多個(gè)任務(wù)。

虛擬機(jī)采用即付即用的收費(fèi)模式，以用戶租用的單元時(shí)間數(shù)量為標(biāo)準(zhǔn)進(jìn)行收費(fèi)。如果用戶沒有使用完一個(gè)完整的單元時(shí)間時(shí)，用戶也需要支付一個(gè)完整的單元時(shí)間的費(fèi)用。如圖2所示，T是虛擬機(jī)的單元時(shí)間長度。在0時(shí)刻虛擬機(jī)開始被租用，3.2 T時(shí)刻虛擬機(jī)結(jié)束租用，此時(shí)用戶需要支付4個(gè)單元時(shí)間的費(fèi)用。

競價(jià)實(shí)例的租用受市場價(jià)格和用戶出價(jià)的影響。當(dāng)市場價(jià)格低于用戶出價(jià)時(shí)，用戶才可以使用競價(jià)實(shí)例。如圖3所示，虛線表示用戶的出價(jià)，實(shí)線表示競價(jià)實(shí)例的市場價(jià)格。當(dāng)虛線高于實(shí)線時(shí)，用戶才可以使用競價(jià)實(shí)例。當(dāng)時(shí)間在Tb和Td之間時(shí)，競價(jià)實(shí)例的市場價(jià)格低于用戶的出價(jià)B。用戶在Tb時(shí)刻可以訪問競價(jià)實(shí)例，在Td時(shí)刻終止訪問。這段時(shí)間內(nèi)，用戶按照競價(jià)實(shí)例的市場價(jià)格支付租用費(fèi)用，而不是按照用戶的出價(jià)。

當(dāng)任務(wù)ti部署到虛擬機(jī)vmtypek上執(zhí)行時(shí)，假設(shè)虛擬機(jī)vmtypek的處理能力為P（vmtypek），那么任務(wù)ti的執(zhí)行時(shí)長為

ETtypei，k=wiP（vmtypek）（1）

假設(shè)所有虛擬機(jī)都在同一物理區(qū)域內(nèi)，而且虛擬機(jī)的平均帶寬基本相同。vm（ti）代表執(zhí)行任務(wù)ti的虛擬機(jī)，bw代表虛擬機(jī)的帶寬，那么任務(wù)ti與tj之間的數(shù)據(jù)傳輸時(shí)長為

TTi，j=di，jbwifvm（ti）≠vm（tj）0otherwise （2）

本文用RTtypei，k代表vmtypek可執(zhí)行ti的最早時(shí)刻，即vmtypek上排列在任務(wù)ti之前任務(wù)的完成時(shí)刻，當(dāng)任務(wù)ti是vmtypek上的第一個(gè)任務(wù)時(shí)，RTtypei，k為vmtypek的啟動完成時(shí)刻，則任務(wù)ti在vmtypek上的執(zhí)行開始時(shí)刻STtypei，k用式（3）計(jì)算，執(zhí)行完成時(shí)刻FTtypei，k用式（4）計(jì)算。

STtypei，k=max{RTtypei，k，maxtj∈ti′parents{FTtypej，k+TTj，i}}（3）

FTtypei，k=STtypei，k+ETtypei，k（4）

用LSTtypek代表虛擬機(jī)vmtypek的租用開始時(shí)刻，即虛擬機(jī)vmtypek上第一個(gè)任務(wù)開始接收數(shù)據(jù)的時(shí)刻。LSTtypek代表虛擬機(jī)vmtypek的租用結(jié)束時(shí)刻，即vmtypek上最后一個(gè)任務(wù)完成數(shù)據(jù)傳輸?shù)臅r(shí)刻。LSTtypek和LFTtypek分別為

LSTtypek=STtypei，k－maxtj∈ti′sparents{TTj，i}（5）

LFTtypek=FTtypei，k+maxtj∈ti′schildren{TTi，j}（6）

云工作流調(diào)度成本通常包含執(zhí)行成本和傳輸成本。本文的數(shù)據(jù)傳輸時(shí)間包含在虛擬機(jī)的租用時(shí)間中，使用虛擬機(jī)的租用時(shí)間計(jì)算執(zhí)行成本，因此傳輸成本包含在執(zhí)行成本中。假設(shè)租用vmtypek一個(gè)單位時(shí)長T所需要承擔(dān)的租用費(fèi)用為UCtypek，則虛擬機(jī)vmtypek的租用費(fèi)用ECtypek為

ECtypek=「LFTtypek－LSTtypekTI×UCtypek（7）

2.3調(diào)度模型

調(diào)度的目的是將工作流中的任務(wù)部署到合適的虛擬機(jī)上，并使每一個(gè)任務(wù)都合理有序地進(jìn)行。將已經(jīng)被租用的虛擬機(jī)用集合I={vmd1，vmd2，…，vmdI，vms1，vms2，…，vmsJ}表示。一個(gè)映射m=〈ti，vmtypek，STtypei，k，F(xiàn)Ttypei，k〉表示將一個(gè)任務(wù)ti部署在vmtypek上執(zhí)行。其中，任務(wù)ti在vmtypek上執(zhí)行開始時(shí)刻用STtypei，k表示，任務(wù)ti在vmtypek上執(zhí)行結(jié)束時(shí)刻用FTtypei，k表示。用集合M表示所有任務(wù)到虛擬機(jī)的映射集合。如上所述，一次調(diào)度結(jié)果可以描述為〈I，M〉。整個(gè)虛擬機(jī)vmtypek的租用結(jié)束時(shí)刻用FTtypek表示。分別用makespan（I，M）和cost（I，M）代表一次調(diào)度結(jié)果的完工時(shí)間的執(zhí)行成本，并由式（8）和（9）計(jì)算。

makespan（I，M）=maxk∈I{FTtypek}（8）

cost（I，M）=∑|I|i=1ECdi+∑|J|j=1ECsj（9）

其中：∑|I|i=1ECdi表示租用的全部按需實(shí)例的執(zhí)行成本的和；∑|J|j=1ECsj表示租用的全部競價(jià)實(shí)例的執(zhí)行成本的和，兩部份相加得到執(zhí)行成本的總和。

一個(gè)工作流的截止時(shí)間用D表示，那么工作流調(diào)度問題可以表示為

mincost（I，M）

s.t.makespan（I，M）≤D（10）

3算法設(shè)計(jì)

如何確定每一個(gè)任務(wù)期限是本文所研究調(diào)度問題的關(guān)鍵。粒子群算法作為一種隨機(jī)優(yōu)化技術(shù)，非常適用于解決本文所面對的問題。文獻(xiàn)［25］提出了采用三步列表調(diào)度算法進(jìn)行云工作流調(diào)度，并提出一種基于粒子群的動態(tài)最后期限分配方法（DY-DD）。本文改進(jìn)了DY-DD算法，在之前算法的基礎(chǔ)上增加了競價(jià)實(shí)例，提出了一種表現(xiàn)更加優(yōu)異的算法（S-DTDA）。

粒子群算法中的每一個(gè)粒子的本質(zhì)是一個(gè)多維向量，通過漸進(jìn)式的計(jì)算求解后，得到最優(yōu)粒子。這一部分應(yīng)用列表調(diào)度算法計(jì)算了t-level、b-level與alap的值［9］，提出了一種基于粒子群的截止時(shí)間分配方法對截止時(shí)間進(jìn)行分配，并利用競價(jià)實(shí)例的價(jià)格優(yōu)勢提出了一種截止時(shí)間動態(tài)分配的工作流調(diào)度成本優(yōu)化算法。

3.1粒子群算法

粒子群算法在隨機(jī)優(yōu)化的基礎(chǔ)上，通過迭代的方法來獲得粒子的最優(yōu)位置。一個(gè)擁有size個(gè)粒子的粒子群用X={x1，x2，…，xsize}表示，粒子群中的第k個(gè)粒子xk={xk1，xk2，…，xkd}是一個(gè)d維向量，其物理含義是d維空間的一個(gè)點(diǎn)，同時(shí)也表示一個(gè)獨(dú)立的解決方案。粒子群的計(jì)算按照迭代的方式進(jìn)行，在每一輪迭代中需要移動所有的粒子，對粒子的位置進(jìn)行調(diào)整。當(dāng)滿足終止條件時(shí)，最終的解決方案就是當(dāng)前最優(yōu)的粒子。第k個(gè)粒子的移動速度vk={vk1，vk2，…，vkd}，記憶中粒子xk的最佳位置就是該粒子的局部最優(yōu)解，用lbk={lbk1，lbk2，…，lbkd}表示。記憶中粒子群的最佳位置就是該粒子群中所有粒子的全局最優(yōu)解，用gb={gb1，gb2，…，gbd}表示。粒子每個(gè)分量的最大值用xmax={xmax1，xmax2，…，xmaxd}表示，粒子每個(gè)分量的最小值用xmin={xmin1，xmin2，…，xmind}表示，粒子速度每個(gè)分量的最大值用vmax={vmax1，vmax2，…，vmaxd}表示，粒子速度每個(gè)分量的最小值用vmin={vmin1，vmin2，…，vmind}表示。假設(shè)xki（t）為粒子xk在第t輪迭代時(shí)第i個(gè)分量的值，那么可以用式（11）和（12）計(jì)算得到該粒子在第t+1輪迭代的更新方式。

xki（t+1）=xki（t）+vki（t）（11）

xki（t+1）=max（xmini，min（xki（t+1），xmaxi））（12）

其中：vki（t）的值通過式（13）和（14）計(jì)算得出。

vki（t+1）=wvki（t）+c1r1（lbki（t）－xki（t））+

c2r2（gbi（t）－xki（t））（13）

vki（t+1）=max（vmini，min（vki（t+1），vmaxi））（14）

其中：w代表慣性參數(shù)，其值取隨機(jī)數(shù)；c1和c2代表加速系數(shù)；r1和r2取隨機(jī)數(shù)。

3.2截止時(shí)間動態(tài)分配的S-DTDA算法

三步列表調(diào)度算法通常先對截止時(shí)間進(jìn)行分配，將整個(gè)工作流的解釋時(shí)間D分配給各個(gè)子任務(wù)，使得每個(gè)子任務(wù)ti獲得一個(gè)子截止時(shí)間sdi；然后對任務(wù)進(jìn)行排序，得到一個(gè)任務(wù)隊(duì)列l(wèi)ist；最后按照隊(duì)列順序?yàn)槊恳粋€(gè)任務(wù)配置合適的虛擬機(jī)。本文提出了截止時(shí)間動態(tài)分配的工作流調(diào)度成本優(yōu)化算法（S-DTDA），對三度列表調(diào)度算法的執(zhí)行步驟進(jìn)行了調(diào)整。首先對任務(wù)進(jìn)行拓?fù)渑判蛏申?duì)列l(wèi)ist；然后利用粒子群算法找到近似最優(yōu)的截止時(shí)間分配結(jié)果；最后在虛擬機(jī)配置階段，利用競價(jià)實(shí)例的價(jià)格優(yōu)勢，在候選資源池中增加了競價(jià)實(shí)例，為每個(gè)任務(wù)分配合適的虛擬機(jī)。

在列表調(diào)度算法的應(yīng)用中，經(jīng)常需要計(jì)算并使用一個(gè)任務(wù)的t-level、b-level、alap值。從開始節(jié)點(diǎn)tentry到任務(wù)ti最長路徑長度為該任務(wù)的t-level值，t-level值的大小關(guān)系到該任務(wù)可以開始執(zhí)行的最早時(shí)刻。從任務(wù)ti到終止節(jié)點(diǎn)texit的最長路徑長度為該任務(wù)的b-level值。在整個(gè)工作流的關(guān)鍵路徑長度不受影響的前提下，任務(wù)ti開始執(zhí)行時(shí)刻可拖延的最大時(shí)間為該任務(wù)的alap值。已知每個(gè)任務(wù)的執(zhí)行時(shí)間是計(jì)算這些值對的前提。然而任務(wù)精確的執(zhí)行時(shí)間只有在調(diào)度結(jié)束后才能進(jìn)行計(jì)算。所以本文采取一種近似的方法來對任務(wù)ti的執(zhí)行時(shí)間ETi進(jìn)行計(jì)算，如式（15）所示。

ETi=wiP（r*）（15）

其中：r*表示云平臺能夠提供的處理速度最快的虛擬機(jī)類型。任務(wù)ti的t-level、b-level、alap值分別用tli、bli和alapi表示，通過式（16）～（18）計(jì)算。

tli=maxtj∈ti′sparent{tlj+ETj+dj，i/bw}tlentry=0（16）

bli=maxtj∈ti′schildren{blj+di，j/bw}+ETiblexit=0（17）

alapi=mintj∈ti′schildren{alapj－di，j/bw}－ETialapexit=blentry（18）

粒子群算法的使用需要解決兩個(gè)問題：a）怎樣按照粒子的模型確定結(jié)題解決方案的編碼方式；b）如何對兩個(gè)不同粒子的優(yōu)劣進(jìn)行比較。本文提出的S-DTDA算法將粒子定義為截止時(shí)間分配的結(jié)果，不同的截止時(shí)間分配結(jié)果表示為不同的粒子。工作流中任務(wù)的個(gè)數(shù)表示為粒子的維度d。參照隊(duì)列l(wèi)ist的順序確定粒子的各分量值與各任務(wù)的映射關(guān)系。例如，粒子k的第l個(gè)分量xkl的值表示第k種分配方案的第l個(gè)任務(wù)的子截止時(shí)間。判斷兩個(gè)粒子優(yōu)劣的方案如式（19）所示。

figt;fj≡costilt;costjif makespani，makespanj≤D

makespanilt;makespanjotherwise（19）

其中： fi、fj表示對粒子xi、xj進(jìn)行虛擬機(jī)配置后的最終調(diào)度結(jié)果。當(dāng)兩種調(diào)度方案的完工時(shí)間均滿足截止時(shí)間約束時(shí)，執(zhí)行費(fèi)用小的方案較優(yōu)，否則完工時(shí)間小的調(diào)度方案較優(yōu)。

為合理控制粒子的移動范圍，需要設(shè)置粒子各分量的最大值與最小值。因?yàn)槿蝿?wù)ti開始執(zhí)行的時(shí)間不會早于tli，最晚開始時(shí)間也不會晚于alapi。為了縮小搜索空間，粒子各分量的最大值與最小值的設(shè)置如式（20）和（21）所示。xmaxi和xmini分別表示粒子第i個(gè)分量的最大值和最小值。

xmaxi=（alapi+ETi）×Dblentry（20）

xmini=（tli+ETi）×Dblentry（21）

粒子移動速度的最大值與最小值如式（22）和（23）所示。

vmaxi=xmaxi－xminiθ（22）

vmini=－vmaxi（23）

其中：θ是一個(gè)常量。

為了加快粒子群的收斂速度，按照式（24）對t=0時(shí)刻的全局最優(yōu)解進(jìn)行設(shè)置。

gbi（t=0）=（blentry－bli+ETi）×Dblentry（24）

算法1動態(tài)截止時(shí)間分配方法

輸入：一個(gè)工作流 DAG=（V，E）。

輸出：調(diào)度方案 S=〈I，M〉。

list ←按照b_level 對工作流中的任務(wù)進(jìn)行降序排序

設(shè)置粒子群算法參數(shù)與全局最優(yōu)位置gb

初始化種群，設(shè)置每個(gè)粒子的局部最優(yōu)位置lb

while 不滿足迭代條件 do

for 每個(gè)粒子xk，k∈{1，2，…，size} do

計(jì)算并更新速度←通過式（13）和（14）

計(jì)算并更新位置←通過式（11）和（12）

按照list的順序?qū)k解碼為Sk←通過算法2

更新粒子xk的局部最優(yōu)位置lbk

end for

更新全局最優(yōu)位置gb←通過式（19）

end while

按照list的順序?qū)b解碼為調(diào)度方案S←通過算法2

return 調(diào)度方案S

算法1描述了動態(tài)截止時(shí)間分配方法。算法的輸入是一個(gè)工作流，輸出是調(diào)度方案。首先對所有的任務(wù)按照b_level值進(jìn)行降序排序（第1行）。然后對粒子群算法的相關(guān)參數(shù)進(jìn)行初始化并對全局最優(yōu)位置和局部最優(yōu)位置進(jìn)行設(shè)置（第2、3行）。開始執(zhí)行粒子群算法（第4～12行）。利用算法2對每個(gè)粒子進(jìn)行解碼，生成解決方案。利用式（19）比較生成的解決方案，更新局部最優(yōu)位置和全局最優(yōu)位置（第9～11行）。粒子群算法迭代結(jié)束后，返回整個(gè)算法的最終調(diào)度方案（第13、14行）。

算法2虛擬機(jī)選擇算法

輸入：任務(wù)列表list；一個(gè)粒子x。

輸出：調(diào)度結(jié)果S=〈I，M〉。

I←，M←

for ti∈list do

for vmtypek∈I do

vmtypek←選擇增加ti后滿足xi并且租用費(fèi)用增量最小的虛擬機(jī)

end for

if 沒有找到合適的虛擬機(jī) then

for k∈R do

分別計(jì)算增加ti后按需實(shí)例和競價(jià)實(shí)例的費(fèi)用增量inCdk和inCsk

vmtypek←將inCdk和inCsk與上一次迭代的費(fèi)用增量進(jìn)行比較，選擇滿足xi且增量最小的虛擬機(jī)

end for

end if

if 仍舊未找到符合要求的虛擬機(jī) then

vmtypek←選擇能夠最早結(jié)束該任務(wù)的虛擬機(jī)

while 不能滿足xi amp;amp; vmtypek不是最快的虛擬機(jī) do

vmtypek←選擇一個(gè)更快類型的虛擬機(jī)并更新任務(wù)結(jié)束時(shí)間

end while

end if

vmtypek=（ECdkgt;ECsk？vmsk，vmdk）

M=M∪{〈ti，vmtypek，STtypei，k，F(xiàn)Ttypei，k〉}

if vmtypek I then

I= I∪{vmtypek}

end if

end for

return S=〈I，M〉

粒子群通過虛擬機(jī)選擇算法進(jìn)行解碼，具體如算法2所示。算法的輸入包括一個(gè)任務(wù)列表list和一個(gè)粒子x，輸出是由x解碼獲取的調(diào)度方案。算法首先對list中的所有任務(wù)進(jìn)行遍歷（第2行）。在已選擇的虛擬機(jī)中選擇增加ti后滿足xi并且租用費(fèi)用增量最小的虛擬機(jī)（第3～5行）。如果沒有找到合適的虛擬機(jī)，則遍歷所有的虛擬機(jī)類型，在競價(jià)實(shí)例和按需實(shí)例中選擇滿足xi且費(fèi)用增量最小的虛擬機(jī)（第6～11行）。如果仍舊未找到符合要求的虛擬機(jī)，則選擇能夠最早結(jié)束該任務(wù)的虛擬機(jī)。當(dāng)選擇的虛擬機(jī)不能滿足xi且不是最快的虛擬機(jī)時(shí)進(jìn)行迭代，選擇一個(gè)更快的虛擬機(jī)并更新任務(wù)時(shí)間，直到找到合適的虛擬機(jī)（第12～17行）。獲得選擇的虛擬機(jī)類型，計(jì)算執(zhí)行開始時(shí)刻和執(zhí)行結(jié)束時(shí)刻，把找到的任務(wù)到虛擬機(jī)的映射并入集合M中（第18、19行）。如果該虛擬機(jī)不在已選擇的虛擬機(jī)集合I中，則將該虛擬機(jī)并入集合I（第20～22行）。結(jié)束遍歷，返回最終的調(diào)度結(jié)果（第23、24行）。

4仿真實(shí)驗(yàn)

4.1實(shí)驗(yàn)設(shè)置

仿真實(shí)驗(yàn)部署在一臺Windows 10的操作系統(tǒng)PC機(jī)上。PC機(jī)使用Intel CoreTM i5處理器，內(nèi)存為8 GB。仿真程序使用Java語言編寫，在Eclipse開發(fā)環(huán)境下運(yùn)行。

仿真程序?qū)⑽墨I(xiàn)［7］提供的開源程序進(jìn)行修改，對競價(jià)實(shí)例重新建模并合并到原有程序中。表1給出了算法相關(guān)參數(shù)的設(shè)置方式。

仿真實(shí)驗(yàn)利用Bharathi等人提供的工作流生成器生成了四種適用于不同領(lǐng)域的工作流模型，它們分別為CyberShake、Epigenomics、LIGO和Montage。圖4展示了四種工作流的結(jié)構(gòu)特征。CyberShake一般在刻畫地震災(zāi)害領(lǐng)域中使用，是需要大量的CPU資源的數(shù)據(jù)密集型工作流；Epigenomics一般在信息生物學(xué)領(lǐng)域中使用，是一個(gè)用來自動執(zhí)行各種各樣的基因組排序操作的數(shù)據(jù)處理管道；LIGO一般在引力物理學(xué)領(lǐng)域中使用，也屬于CPU密集型工作流；Montage一般在天文學(xué)領(lǐng)域中使用，對CPU資源需求不高。四種工作流模型更加具體的描述可以參考文獻(xiàn)［1］。

本文對每個(gè)工作流模型都生成了50，100，200，…，900和1 000個(gè)任務(wù)，共11種不同規(guī)模的工作流，并將它們用于仿真實(shí)驗(yàn)。

在仿真實(shí)驗(yàn)中，本文選用了Amazon公司的r5.large、r5.xlarge、r5.2xlarge、r5.4xlarge和r5.8xlarge五種不同類型的虛擬機(jī)。參照Amazon EC2真實(shí)的收費(fèi)標(biāo)準(zhǔn)并按照r5.8xlarge按需實(shí)例的價(jià)格對每個(gè)虛擬機(jī)的租用費(fèi)用進(jìn)行了歸一化處理。表2展示了當(dāng)五種虛擬機(jī)按照按需實(shí)例類型進(jìn)行收費(fèi)時(shí)的處理能力和歸一化成本。

Amazon公司在2017年以來調(diào)整了競價(jià)實(shí)例的競價(jià)策略。近年來競價(jià)實(shí)例的價(jià)格已經(jīng)相對穩(wěn)定，對競價(jià)實(shí)例未來的價(jià)格預(yù)測也變得簡單。因此，本文假設(shè)競價(jià)實(shí)例在租用期間都是可靠的。五種虛擬機(jī)按照競價(jià)實(shí)例類型進(jìn)行收費(fèi)時(shí)的處理能力與它們按照按需實(shí)例類型收費(fèi)時(shí)的處理能力相同。五種競價(jià)實(shí)例的收費(fèi)標(biāo)準(zhǔn)參照了2021年12月6日到7日的48 h歷史價(jià)格進(jìn)行歸一化處理，詳情如圖5所示。

為評估S-DTDA算法的性能，仿真實(shí)驗(yàn)選擇ProLis［7］、PSO［11］和IC-PCP［14］三種經(jīng)典作為對比算法，采用了調(diào)度成功率和執(zhí)行成本兩個(gè)評估指標(biāo)。性能越好的算法，成功率越高并且執(zhí)行成本越低。截止時(shí)間的寬松程度對調(diào)度算法的結(jié)果有很大影響。截止時(shí)間越緊張，調(diào)度的成功率越低的同時(shí)成本越高。為了對本文算法作出更加合理的評估，引入以下兩個(gè)基準(zhǔn)對不同截止時(shí)間設(shè)置下的算法進(jìn)行驗(yàn)證：

a）廉價(jià)調(diào)度。使用HEFT［26］算法在一臺最廉價(jià)的虛擬機(jī)上進(jìn)行工作流調(diào)度。此時(shí)，完工時(shí)間用Mc表示，執(zhí)行成本用Cc表示。

b）快速調(diào)度。使用HEFT算法在一臺最昂貴的虛擬機(jī)上進(jìn)行工作流調(diào)度。此時(shí)，完工時(shí)間用Mf表示，執(zhí)行成本用Cf表示。

工作流截止時(shí)間的寬松程度用λ（λ∈［0，1］）表示，則工作流截止時(shí)間可表示為

D=MF+（MC－MF）×λ（25）

4.2實(shí)驗(yàn)結(jié)果

仿真實(shí)驗(yàn)先令λ從0.005變化至0.05，步長為0.005進(jìn)行實(shí)驗(yàn)；又令λ從0.1變化至0.5，步長為0.05再次進(jìn)行實(shí)驗(yàn)。分別觀察在相對緊張和相對寬松的截止時(shí)間設(shè)置下，各算法在調(diào)度成功率和執(zhí)行成本上的表現(xiàn)。

圖6給出了λ從0.005變化至0.05時(shí)各算法的平均成功率。四種算法的平均成功率基本都隨λ的增大而增大，直到增加到100%后穩(wěn)定。顯然，相對寬松的截止時(shí)間約束更容易找到調(diào)度方案。S-DTDA和ProLis表現(xiàn)最優(yōu)。只有在Montage模型下，當(dāng)λ為0.005時(shí)，S-DTDA的成功率約為91%，比ProLis的表現(xiàn)稍差一點(diǎn)。IC-PCP在CyberShake模型下表現(xiàn)最差，λ從0.005變化到0.05從未達(dá)到100%。PSO在四種模型下的表現(xiàn)都較差，但隨著λ的增大，成功率都能達(dá)到并穩(wěn)定在100%。

圖7給出了λ從0.005變化至0.05時(shí)各算法的歸一化執(zhí)行成本。由實(shí)驗(yàn)結(jié)果可知，受實(shí)驗(yàn)成功率的影響，PSO在Epigenomics和Montage下的成本先由低到低變化，等實(shí)驗(yàn)成功率達(dá)到100%后，成本由高到低變化。另外三個(gè)算法在四個(gè)模型下的成本都表現(xiàn)為隨λ的增加而降低。與PSO相比，其他三種算法都具有較大的優(yōu)勢。ProLis和IC-PCP基本相差不大，但是相對于S-DTDA，兩種算法一直存在劣勢。

圖8給出了λ從0.1變化至0.5時(shí)各算法的歸一化執(zhí)行成本。由實(shí)驗(yàn)結(jié)果可知，S-DTDA、ProLis和IC-PCP隨著λ的增加變化不大，但是S-DTDA比ProLis和IC-PCP具有明顯優(yōu)勢。PSO在Epigenomics和LIGO模型下的表現(xiàn)最差。隨著λ的增加，PSO在Cybershake和Montage模型下的成本逐漸低于IC-PCP，但是與S-DTDA和ProLis相比，PSO仍處于明顯劣勢。

5結(jié)束語

本文提出了截止時(shí)間動態(tài)分配的工作流調(diào)度成本優(yōu)化算法S-DTDA。該算法利用粒子群算法對截止時(shí)間進(jìn)行動態(tài)分配，彌補(bǔ)了三步列表調(diào)度算法的缺陷。在虛擬機(jī)選擇階段，該算法在候選資源中增加了競價(jià)實(shí)例，大大降低了執(zhí)行成本。對于一個(gè)給定的工作流、最后期限約束和云模型，該算法可以找到一個(gè)滿足截止時(shí)間約束且優(yōu)化了執(zhí)行成本的調(diào)度方案。本文利用Amazon EC2提供的真實(shí)數(shù)據(jù)建立了模型并進(jìn)行實(shí)驗(yàn)仿真。實(shí)驗(yàn)結(jié)果表明，相較于ProLis、PSO和IC-PCPC三個(gè)經(jīng)典算法，S-DTDA在實(shí)驗(yàn)成功率和執(zhí)行成本上具有明顯優(yōu)勢。

接下來，筆者會嘗試改進(jìn)本文算法或者探索新的算法解決本文所研究的問題，提高調(diào)度成功率并降低執(zhí)行成本。除此之外，還會將研究目標(biāo)擴(kuò)展到多目標(biāo)的工作流調(diào)度領(lǐng)域中。

參考文獻(xiàn)：

［1］Juve G，Chervenak A，Deelman E，et al. Characterizing and profiling scientific workflows［J］. Future Generations Computer Systems，2013，29（3）： 682-692.

［2］Wang Zijia，Zhan Zhihui，Yu Weijie，et al. Dynamic group learning distributed particle swarm optimization for large-scale optimization and its application in cloud workflow scheduling［J］. IEEE Trans on Cybernetics，2020，50（6）： 2715-2729.

［3］Zhan Zhihui，Liu Xiaofeng，Gong Yuejiao，et al. Cloud computing resource scheduling and a survey of its evolutionary approaches［J］. ACM Computing Surveys，2015，47（4）： article No.63.

［4］Su Sen，Li Jian，Huang Qingjia，et al. Cost-efficient task scheduling for executing large programs in the cloud［J］. Parallel Computing，2013，39（4-5）： 177-188.

［5］Wu Fuhui，Wu Qingbo，Tan Yusong. Workflow scheduling in cloud： a survey［J］.Journal of Supercomputing，2015，71（9）：3373-3418.

［6］Pinedo M. Scheduling： theory，algorithms，and systems［M］. Berlin： Springer，2012.

［7］Wu Quanwang，Ishikawa F，Zhu Qingsheng，et al. Deadline-constrained cost optimization approaches for workflow scheduling in clouds［J］. IEEE Trans on Parallel and Distributed Systems，2017，28（12）： 3401-3412.

［8］Cao Shujin，Deng Kefeng，Ren Kaijun，et al. An optimizing algorithm for deadline constrained scheduling of scientific workflows in IaaS clouds using spot instances［C］// Proc of IEEE International Confe-rence on Parallel amp; Distributed Processing with Applications，Big Data amp; Cloud Computing，Sustainable Computing amp; Communications，Social Computing amp; Networking. Piscataway，NJ： IEEE Press，2019： 1421-1428.

［9］Kwok Y K，Ishfaq A. Static scheduling algorithms for allocating directed task graphs to multiprocessors［J］. ACM Computing Surveys，1999，31（4）： 406-471.

［10］Jia Yu，Rajkumar B，Kotagiri R. Workflow scheduling algorithms for grid computing［J］. Studies in Computational Intelligence，2008，146： 173-214.

［11］Wu Zhangjun，Ni Zhiwei，Gu Lichuan，et al. A revised discrete particle swarm optimization for cloud workflow scheduling［C］// Proc of International Conference on Computational Intelligence and Security. 2010： 184-188.

［12］Wang Pengwei，Lei Yinghui，Promise R，et al. Makespan-driven workflow scheduling in clouds using immune-based PSO algorithm［J］. IEEE Access，2020，8： 29281-29290.

［13］Abrishami S，Naghibzadeh M，Epema D H J. Cost-driven scheduling of grid workflows using partial critical paths［J］. IEEE Trans on Parallel and Distributed Systems，2012，23（8）： 1400-1414.

［14］Saeid A，Mahmoud N，Dick H. Deadline-constrained workflow schedu-ling algorithms for infrastructure as a service clouds［J］. Future Generation Computer Systems，2013，29（1）： 158-169.

［15］Chen Weihong，Xie Guoqi，Li Renfa，et al. Execution cost minimization scheduling algorithms for deadline-constrained parallel applications on heterogeneous clouds ［J］. Cluster Computing，2021，24：701-715.

［16］Che Haiying，Wang Xiaolong，Wang Hong，et al. Scheduling with deadline constraint of healthcare applications on cloud-based workflow［J］. Journal of Medical Imaging and Health Informatics，2020，10（10）： 2430-2438.

［17］朱宇寧，何利力. 基于啟發(fā)式算法的混合云工作流調(diào)度算法［J］. 軟件工程與應(yīng)用，2021，10（6）： 746-756.（Zhu Yuning，He Lili. Hybrid cloud workflow scheduling algorithm based on heuristic algorithm［J］. Software Engineering and Applications，2021，10（6）： 746-756.）

［18］馬學(xué)森，許雪梅，蔣功輝，等. 混合自適應(yīng)粒子群工作流調(diào)度優(yōu)化算法［J/OL］.計(jì)算機(jī)應(yīng)用.（2022-04-07）. https：//kns.cnki.net/kcms/detail/51.1307.tp. 20220406.1232.010.html.（Ma Xuesen，Xu Xuemei，Jiang Gonghui，et al. Hybrid adaptive particle swarm optimization algorithm for workflow scheduling［J/OL］. Journal of Computer Applications.（2022-04-07）. https：//kns.cnki.net/kcms/detail/51.1307.tp.20220406.1232.010.html.）

［19］Khan M，Jehangiri A I，Ahmad Z，et al. An exploration to graphics processing unit spot price prediction［J］. Cluster Computing，2022，22（5）： 3499-3515.

［20］Veena K，Anand K C，Chandra P G. Amazon EC2 spot price prediction using regression random forests［J］. IEEE Trans on Cloud Computing，2020，8（1）： 59-72.

［21］Liu Wenqiang，Wang Pengwei，Meng Ying，et al. Cloud spot instance price prediction using KNN regression［J］. Human-Centric Computing and Information Sciences，2020，10： article No.34.

［22］Luan T，Luciana A，Pierre S，et al. Scheduling bag-of-tasks in clouds using spot and burstable virtual machines［J/OL］. IEEE Trans on Cloud Computing.（2021-11-08）. https：//doi.org/10.1109/TCC.2021.3125426.

［23］Brum R C，Sousa W P，Melo A C M A，et al. A fault tolerant and deadline constrained sequence alignment application on cloud-based spot GPU instances［C］// Proc of the 27th International Conference on Parallel and Distributed Computing. 2021： 317-333.

［24］Zohra A，Moulay Y H. Cloud spot price prediction approach using adaptive neural fuzzy inference system with chaos theory［J］. International Journal of Networking and Virtual Organisations，2022，26（1-2）： 23-46.

［25］王子健，盧政昊，潘紀(jì)奎，等. 最后期限動態(tài)分配的三步云工作流調(diào)度算法［J/OL］. 小型微型計(jì)算機(jī)系統(tǒng).（2022）. https：//kns.cnki.net/kcms/detail/21.1106.TP.20211213.1445.018.html.（Wang Zijian，Lu Zhenghao，Pan Jikui，et al. A three-step cloud workflow scheduling algorithm based on dynamic deadline distribution［J/OL］. Journal of Chinese Mini-Micro Computer Systems.（2022）. https：//kns.cnki.net/kcms/detail/21.1106.TP.20211213.1445.018.html.）

［26］Topcuoglu H，Hariri S，Wu Minyou. Performance-effective and low-complexity task scheduling for heterogeneous computing ［J］. IEEE Trans on Parallel and Distributed Systems，2002，13（3）： 260-274.

收稿日期：2022-06-01；修回日期：2022-08-05基金項(xiàng)目：國家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（2018YFB1402800）

作者簡介：潘紀(jì)奎，男，山東臨沂人，碩士研究生，主要研究方向?yàn)楣ぷ髁髡{(diào)度；董心儀，女，山東煙臺人，碩士研究生，主要研究方向?yàn)楣ぷ髁髡{(diào)度；王子健，男，河北秦皇島人，講師，碩士，主要研究方向?yàn)楣ぷ髁髡{(diào)度；盧政昊，男，遼寧本溪人，碩士研究生，主要研究方向?yàn)楣ぷ髁髡{(diào)度；孫福權(quán)，男（通信作者），遼寧大連人，教授，碩導(dǎo)，博士，主要研究方向?yàn)樵瀑Y源調(diào)度分配、大數(shù)據(jù)分析（panjikuidxy@163.com）.