一种基于预测完成时间矩阵的异构云中心任务调度方法

1.本发明涉及云计算技术领域，更具体的说是涉及一种基于预测完成时间矩阵计算优先级(pmms)的方法。


背景技术：

2.云计算是一种通过计算机网络形成的计算能力极强的分布式计算，可存储、集成相关资源并按需配置，向用户提供个性化服务。云计算中心是一个能够部署大型工作流应用程序的优秀平台，它以其强大的计算系统向用户提供个性化的服务。异构云计算系统则是一个与高速网络互联的多组资源组成的计算平台。
3.异构云计算系统中的静态任务调度则是在任务开始执行前，任务的执行时间等信息已确定。异构云计算系统中的静态任务调度通常包含两个阶段：任务的优先级计算阶段和虚拟机选择阶段。云计算系统中的任务调度问题，本质上是为提交至云计算中心的工作流应用程序选择合适的虚拟机，将应用程序中的每个子任务按照一定的约束条件(如优先级约束、预算约束等)分配至选择的虚拟机，以期在较短的时间内(或在较低的开销等)完成整个应用程序的调度；在异构云计算系统中执行并行应用程序的效率严重依赖于所选择的调度方法，现有异构云计算系统中，当任务选择虚拟机时，现有的经典方法，如异构最早完成时间方法(heft)，往往不会考虑当前任务的后继任务的特点，且在优先级计算阶段，容易出现高优先级任务在低优先级任务之后调度的情况，产生低效率的任务调度列表，从而导致整个方法的效率低，因此使用此方法异构云计算系统中执行并行应用程序的效率低。
4.公开号为cn115391039a的一种发明创造专利公开了一种基于预测最早完成时间的分布式任务调度系统及方法，所述方法包括：任务存储模块：用于存储待调度的新任务；任务调度模块：用于获取训练好的任务完成时间预测模型，并根据任务完成时间预测模型；并发任务优化模块：用于优化任务处理节点集合中各个任务处理节点的最佳并发任务数；此发明能够为新任务选择出完成时间最早的执行器，并实时动态优化选择，但是往往不会考虑当前任务的后继任务的特点，且在优先级计算阶段，容易出现高优先级任务在低优先级任务之后调度的情况，产生低效率的任务调度列表，从而导致整个方法的效率低，因此使用此方法异构云计算系统中执行并行应用程序的效率低。


技术实现要素：

5.针对上述存在的技术问题，本发明提供一种基于预测完成时间矩阵的异构云中心任务调度方法。
6.本发明采用以下具体的技术方案：
7.一种基于预测完成时间矩阵的异构云中心任务调度方法，包括以下步骤：
8.s1：任务优先级阶段，其步骤如下：
9.s1.1：获取多个任务，计算每个任务的预测完成时间矩阵，预测完成时间矩阵中的行表示为任务，列表示为虚拟机，pm(ξi,prj)表示第i个任务ξi分配在第j个虚拟机prj上执
行的预测完成时间矩阵值；
10.s1.2：计算每个任务的优先级，并比较当前任务和后继任务的优先级，若当前任务优先级小于后继任务的优先级，则更新预测完成时间矩阵值和任务优先级，再根据更新后的任务优先级降序排列得到优先级队列；若当前任务优先级大于后继任务的优先级，则直接根据任务优先级降序排列得到优先级队列；
11.s2：虚拟机选择阶段，其步骤如下：
12.s2.1：计算每个任务的最早完成时间以及乐观调度长度值；
13.s2.2：为每个任务选择乐观调度长度值最小的虚拟机进行调度，
14.s2.3：完成优先级队列调度；
15.s3：计算整个应用程序的调度长度。
16.优选地，所述步骤s1.1中预测完成时间矩阵值pm(ξi,prj)的计算公式为：
[0017][0018]
succ(ξi)表示为任务ξi的直接后继节点集合，pm(ξ
γ
,prj)表示后继节点的预测完成时间矩阵值，ξ
exit
表示退出任务。
[0019]
优选地，所述步骤s1.2中优先级的计算公式如下：
[0020][0021]
其中rank
pm
(ξi)表示任务的等级值，由每个任务的平均预测完成时间矩阵值计算，|p|为虚拟机的台数。
[0022]
优选地，所述前任务优先级大于后继任务的优先级，则将任务按照rank
pm
(ξi)值降序排列，得到优先级队列。
[0023]
优选地，所述步骤s1.2中更新预测完成时间矩阵值时，进行比例缩小，其比例缩小的计算公式为：
[0024][0025]
其中rank
pm
(ξ
γ
)表示后继节点对应的优先级。
[0026]
优选地，所述比例缩小公式中θ是一个常数，取值为1。
[0027]
优选地，所述步骤s2.1中任务的最早完成时间的表达公式为：
[0028]
eft(ξi,prj)＝est(ξi,prj)+w(ξi,prj)
[0029]
其中eft(ξi,prj)为任务ξi在prj上的最早完成时间，est(ξi,prj)为任务ξi在prj上的最早开始时间，w(ξi,prj)为任务ξi分配在prj上所需的计算开销。
[0030]
优选地，所述步骤s2.1中乐观调度长度值的计算公式为：
[0031]
osl(ξi,prj)＝eft(ξi,prj)+pm(ξi,prj)
[0032]
osl(ξi,prj)表示为第i个任务ξi分配在第j个虚拟机prj的乐观调度长度值。
[0033]
优选地，所述步骤s2.3中优先级队列调度未完成，则返回到步骤s2.2。
[0034]
优选地，所述步骤s3中调度长度即退出任务的实际完成时间，其公式表达式为：
[0035]
makespan＝max{aft(ξ
exit
)}
[0036]
本发明的有益效果为：
[0037]
(1)本发明在满足优先级约束的条件下，最小化工作流应用程序的调度长度，本发明的预测完成时间矩阵在考虑当前任务的影响的同时预测其后继任务对整个工作流应用的影响，达到减少调度长度的目的；
[0038]
(2)本发明在优先级计算阶段，提出了任务优先级计算规则：任务的等级值等于每个任务在不同虚拟机上的预测完成时间矩阵值之和与虚拟机总数量的比值，即每个任务的平均预测完成时间矩阵值。由于预测完成时间矩阵“瞻前顾后”的特点，任务的优先级计算更加合理，不会出现高优先级任务在低优先级任务之后调度的情况，能够提高整个算法的效率。
附图说明
[0039]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。
[0040]
图1为基于预测完成时间矩阵计算优先级的方法流程示意图；
[0041]
图2为10个节点的dag并行应用程序示意图；
[0042]
图3为异构云计算系统模型。
具体实施方式
[0043]
下面结合实施例进一步解释和阐明，但具体实施例并不对本发明有任何形式的限定。
[0044]
实施例1
[0045]
本发明采用以下具体的技术方案：
[0046]
一种基于预测完成时间矩阵的异构云中心任务调度方法，包括以下步骤：
[0047]
s1：任务优先级阶段，其步骤如下：
[0048]
s1.1：获取多个任务，计算每个任务的预测完成时间矩阵，预测完成时间矩阵中的行表示为任务，列表示为虚拟机，pm(ξi,prj)表示第i个任务ξi分配在第j个虚拟机prj上执行的预测完成时间矩阵值；
[0049]
所述步骤s1中预测完成时间矩阵值pm(ξi,prj)的计算公式为：
[0050][0051]
succ(ξi)表示为任务ξi的直接后继节点集合，pm(ξ
γ
,prj)后继节点的预测完成时间矩阵值，ξ
exit
表示退出任务；
[0052]
s1.2：计算每个任务的优先级，并比较当前任务和后继任务的优先级，若当前任务
优先级小于后继任务的优先级，则更新预测完成时间矩阵值和任务优先级，再根据更新的任务优先级降序排列得到优先级队列；
[0053]
若当前任务优先级大于后继任务的优先级，则直接根据任务优先级降序排列得到优先级队列；
[0054]
所述步骤s1.2中优先级的计算公式如下：
[0055][0056]
其中rank
pm
(ξi)表示任务的等级值，由每个任务的平均预测完成时间矩阵值计算，|p|为虚拟机的台数。
[0057]
步骤s1.2中更新预测完成时间矩阵值时，进行比例缩小，其比例缩小计算公式为：
[0058][0059]
其中rank
pm
(ξ
γ
)表示后继节点对应的优先级，比例缩小的公式中θ是一个常数，取值为1。
[0060]
任务优先级阶段，在计算出所有任务的初始rank
pm
(ξi)后，从入口节点开始，依次比较当前任务节点ξi与其直接后继节点ξ
γ
(ξ
γ
∈succ(ξi))的rank
pm
值。若rank
pm
(ξi)≤rank
pm
(ξ
γ
)，把预测完成时间矩阵值按比例缩小，进而缩小该后继节点对应的rank
pm
(ξ
γ
)，直到满足优先约束条件rank
pm
(ξi)≥rank
pm
(ξ
γ
)。然后将任务按照rank
pm
(ξi)值降序排列，得到优先级列表；
[0061]
s2：虚拟机选择阶段，其的步骤如下：
[0062]
s2.1：计算每个任务的最早完成时间以及乐观调度长度值；
[0063]
步骤s2.1中任务的最早完成时间的表达公式为：
[0064]
eft(ξi,prj)＝est(ξi,prj)+w(ξi,prj)(4)
[0065]
其中eft(ξi,prj)为任务ξi在prj的最早完成时间，est(ξi,prj)为任务ξi在prj上的最早开始时间，w(ξi,prj)为任务ξi分配在prj上所需的计算开销。
[0066]
任务ξi在prj上的最早开始时间est(ξi,prj)的计算公式为：
[0067][0068]
其中，avail(prj)是prj准备就绪的最早时间，aft(ξk)是前驱节点实际完成时间，对于没有前驱的任务ξ
entry
，est(ξ
entry
,prj)＝0；
[0069]
s2.2：为每个任务选择乐观调度长度值最小的虚拟机进行调度；
[0070]
由步骤s2.1知，乐观调度长度值的公式为：
[0071]
osl(ξi,prj)＝eft(ξi,prj)+pm(ξi,prj)(6)
[0072]
osl(ξi,prj)表示为第i个任务ξi分配在第j个虚拟机prj的乐观调度长度值；
[0073]
在虚拟机vm选择阶段，首先计算每个任务ξi在prj上的osl。然后，pmms算法为任务选择osl值最小的vm来执行，从而使调度长度最小化。
[0074]
s2.3：完成优先级队列调度，若优先级队列调度未完成，则返回到步骤s2.2；
[0075]
s3：计算整个应用程序的调度长度。
[0076]
步骤s3中调度长度即退出任务的实际完成时间，其公式表达式为：
[0077]
makespan＝max{aft(ξ
exit
)}(7)
[0078]
综上所述，本发明在满足优先级约束的条件下，最小化工作流应用程序的调度长度；本发明的预测完成时间矩阵在考虑当前任务的影响的同时预测其后继任务对整个工作流应用的影响，达到减少调度长度的目的；
[0079]
本发明在优先级计算阶段，提出了任务优先级计算规则：任务的等级值等于每个任务在不同虚拟机上的预测完成时间矩阵值之和与虚拟机总数量的比值，即每个任务的平均预测完成时间矩阵值。由于预测完成时间矩阵“瞻前顾后”的特点，任务的优先级计算更加合理，不会出现高优先级任务在低优先级任务之后调度的情况，能够提高整个算法的效率。
[0080]
实施例2
[0081]
实施例2中，基于异构云计算系统模型，使用有向无环图(dag)描述的工作流应用程序，具体应用实施例1所提出的一种基于预测完成时间矩阵的异构云中心任务调度方法，工作流应用程序用g＝《n,e,c,w》表示，其中n为任务节点集合，每个任务节点ξi(ξi∈n)在不同虚拟机上执行时间不同，e为dag中直接相连两个任务节点的边集合，每条边e
i,j
(e
i,j
∈e)表示任务ξi和任务ξj的依赖关系，任务ξj不能先于任务ξi执行。c为直接连接两个任务节点之间通信边的集合，c
i,j
(c
i,j
∈c)表示e
i,j
的通信时间，当且仅当ξi和ξj分配给同一个虚拟机执行时，c
i,j
＝0。w为任务节点在不同虚拟机vm上的计算开销集合，实施例2中dag工作流应用程序的入口节点和退出节点有且仅有一个。
[0082]
如图2所示，这是一个典型的基于dag的并行应用程序的示例，其中包含了10个任务节点。
[0083]
基于dag的并行应用程序应用实施例1中所述方法的步骤如下：
[0084]
s1：任务优先级阶段，其步骤如下：
[0085]
s1.1：获取多个任务，计算每个任务的预测完成时间矩阵，预测完成时间矩阵中的行表示为任务，列表示为虚拟机，pm(ξi,prj)表示第i个任务ξi分配在第j个虚拟机prj上执行的预测完成时间矩阵值；
[0086]
所述步骤s1中预测完成时间矩阵值pm(ξi,prj)的计算公式为：
[0087][0088]
succ(ξi)表示为ξi任务的直接后继节点集合；
[0089]
s1.2：计算每个任务的优先级，并比较当前任务和后继任务的优先级，若当前任务优先级小于后继任务的优先级，则更新预测完成时间矩阵值和任务优先级，再根据更新后的优先级降序排列得到优先级队列；
[0090]
若当前任务优先级大于后继任务的优先级，则直接根据任务优先级降序排列得到优先级队列；
[0091]
所述步骤s1.2中任务优先级的计算公式如下：
[0092][0093]
其中rank
pm
(ξi)表示任务的等级值，由每个任务的平均预测完成时间矩阵值计算，|p|为虚拟机的台数。
[0094]
步骤s1.2中更新预测完成时间矩阵值，进行比例缩小，其比例缩小的计算公式为：
[0095][0096]
其中rank
pm
(ξ
γ
)表示后继节点对应的优先级，比例缩小的公式中θ是一个常数，取值为1。
[0097]
任务优先级阶段，在计算出所有任务的初始rank
pm
(ξi)后，从入口节点开始，依次比较当前任务节点ξi与其直接后继节点ξ
γ
(ξ
γ
∈succ(ξi))的rank
pm
值。若rank
pm
(ξi)≤rank
pm
(ξ
γ
)，则把预测完成时间矩阵值按比例缩小，进而缩小该后继节点对应的rank
pm
(ξ
γ
)，直到满足优先约束条件rank
pm
(ξi)≥rank
pm
(ξ
γ
)。然后将任务按照rank
pm
(ξi)值降序排列，得到优先级列表；
[0098]
s2：虚拟机选择阶段，其的步骤如下：
[0099]
s2.1：计算每个任务的完成时间以及乐观调度长度值；
[0100]
步骤s2.1中任务的最早完成时间的表达公式为
[0101]
eft(ξi,prj)＝est(ξi,prj)+w(ξi,prj)(4)
[0102]
其中eft(ξi,prj)为任务ξi在prj的最早完成时间，est(ξi,prj)为任务ξi在prj上的最早开始时间，w(ξi,prj)为任务ξi分配在prj上所需的计算开销。
[0103]
任务ξi在prj上的最早开始时间est(ξi,prj)的计算公式为：
[0104][0105]
其中，avail(prj)是prj准备就绪的最早时间，aft(ξk)是前驱节点实际完成时间，对于入口任务ξ
entry
，est(ξ
entry
,prj)＝0；
[0106]
s2.2：为每个任务选择乐观调度长度值最小的虚拟机进行调度；
[0107]
由步骤s2.1知，乐观调度长度值的公式为：
[0108]
osl(ξi,prj)＝eft(ξi,prj)+pm(ξi,prj)(6)
[0109]
osl(ξi,prj)表示为第i个任务ξi分配在第j个虚拟机prj的乐观调度长度值；
[0110]
在虚拟机选择阶段，首先计算每个任务ξi在prj上的osl。然后，pmms算法为任务选择osl值最小的虚拟机来执行，从而使应用程序的调度长度最小化。
[0111]
s2.3：完成优先级队列调度，若优先级队列调度未完成，则返回到步骤s2.2；
[0112]
s3：计算整个应用程序的调度长度。
[0113]
步骤s3中调度长度即退出任务的实际完成时间，其公式表达式为：
[0114]
makespan＝max{aft(ξ
exit
)}(7)
[0115]
实施例2中基于dag的并行应用程序应用实施例1中所述方法输出的结果如表1所示，表1为图1中各个任务节点在3组不同vm上的计算开销表。
[0116]
表1
[0117][0118]
以任务ξ3为例，仅当任务ξ3的直接前驱任务ξ1执行完，ξ3才有可能进入准备就绪状态。表1中第二行二列的计算开销值表示任务ξ1在pr1上的执行时间为54。若任务ξ1与任务ξ3不在同一个虚拟机上执行，那么从任务ξ1到任务ξ3的通信时间c
1,3
＝12。
[0119]
实施例3
[0120]
实施例3中，使用异构云计算系统模型来描述本发明的应用原理，具体应用实施例1所提出的一种基于预测完成时间矩阵的异构云中心任务调度方法。异构云计算系统模型由一个包含prj个异构虚拟机的集合p组成。云计算系统根据设计好的调度策略，在满足一定约束条件(如优先级约束、能耗约束)的情况下，完成任务到资源的映射。
[0121]
异构云计算系统主要由用户、资源部署、资源管理三个模块组成。用户模块是指云用户向云中心提交的各种应用和需求。资源部署模块则是用户与资源管理模块的桥梁，用户向云中心提交的请求经过资源部署模块进行预处理，包括对应用程序的处理、调度策略的设计等，最后经过资源管理器和任务调度器将用户提交的应用输送给资源管理模块。资源管理模块会根据不同的应用寻找合适的虚拟机vm以满足用户个性化的需求，以求节约资源，降低能耗等。实施例1中所述方法集成在资源部署模块的任务调度器中。异构云计算系统模型如图3所示。
[0122]
基于异构云计算系统模型，将实施例2应用实施例1中所述方法的步骤如下：
[0123]
s1：任务优先级阶段，其步骤如下：
[0124]
s1.1：获取多个任务，计算每个任务的预测完成时间矩阵，预测完成时间矩阵中的行表示为任务，列表示为虚拟机，pm(ξi,prj)表示第i个任务ξi分配在第j个虚拟机prj上执行的预测完成时间矩阵值；
[0125]
所述步骤s1.1中预测完成时间矩阵值pm(ξi,prj)的计算公式为：
[0126]
[0127]
succ(ξi)表示为ξi任务的直接后继节点集合；
[0128]
s1.2：计算每个任务的优先级，并比较当前任务和后继任务的优先级，若当前任务优先级小于后继任务的优先级，则更新预测完成时间矩阵值和任务优先级，再根据更新后的优先级降序排列得到优先级队列；
[0129]
若当前任务优先级大于后继任务的优先级，则直接根据任务优先级降序排列得到优先级队列；
[0130]
所述步骤s1.2中任务优先级的计算公式如下：
[0131][0132]
其中rank
pm
(ξi)表示任务的等级值，由每个任务的平均预测完成时间矩阵值计算，|p|为虚拟机的台数。
[0133]
步骤s1.2中更新预测完成时间矩阵值时，进行比例缩小，其比例缩小计算公式为：
[0134][0135]
其中rank
pm
(ξ
γ
)表示后继节点对应的优先级，比例缩小的公式中θ是一个常数，取值为1。
[0136]
任务优先级阶段，在计算出所有任务的初始rank
pm
(ξi)后，从入口节点开始，依次比较当前任务节点ξi与其直接后继节点ξ
γ
(ξ
γ
∈succ(ξi))的rank
pm
值。若rank
pm
(ξi)≤rank
pm
(ξ
γ
)，把预测完成时间矩阵值按比例缩小，进而缩小该后继节点对应的rank
pm
(ξ
γ
)，直到满足优先约束条件rank
pm
(ξi)≥rank
pm
(ξ
γ
)。然后将任务按照rank
pm
(ξi)值降序排列，得到优先级列表；
[0137]
s2：虚拟机选择阶段，其的步骤如下：
[0138]
s2.1：计算每个任务的完成时间以及乐观调度长度值；
[0139]
步骤s2.1中任务的最早完成时间的表达公式为
[0140]
eft(ξi,prj)＝est(ξi,prj)+w(ξi,prj)(4)
[0141]
其中eft(ξi,prj)为任务ξi在prj的最早完成时间，est(ξi,prj)为任务ξi在prj上的最早开始时间，w(ξi,prj)为任务ξi分配在prj上所需的计算开销。
[0142]
任务ξi在prj上的最早开始时间est(ξi,prj)的计算公式为：
[0143][0144]
其中，avail(prj)是prj准备就绪的最早时间，aft(ξk)是前驱节点实际完成时间，对于入口任务ξ
entry
，est(ξ
entry
,prj)＝0；
[0145]
s2.2：为每个任务选择乐观调度长度值最小的虚拟机进行调度；
[0146]
乐观调度长度值的公式为：
[0147]
osl(ξi,prj)＝eft(ξi,prj)+pm(ξi,prj)(6)
[0148]
osl(ξi,prj)表示为第i个任务ξi分配在第j个虚拟机prj的乐观调度长度值；
[0149]
在虚拟机选择阶段，首先计算每个任务ξi在prj上的osl。然后，pmms算法为任务选择osl值最小的虚拟机来执行，从而使应用程序的调度长度最小化。
[0150]
s2.3：完成优先级队列调度，若优先级队列调度未完成，则返回到步骤s2.2；
[0151]
s3：计算整个应用程序的调度长度。
[0152]
步骤s3中调度长度即退出任务的实际完成时间，其公式表达式为：
[0153]
makespan＝max{aft(ξ
exit
)}(7)
[0154]
实施例3基于实施例2应用实施例1中所述方法所得的计算开销表，得出实施例3输出的任务优先级结果如表2，表2为根据pmms方法得到的图1中各任务节点调度结果。
[0155]
表2
[0156][0157]
显然，本发明的上述实施例仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。

技术特征：
1.一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述方法主要包括任务优先级阶段和虚拟机选择阶段，其方法的步骤如下：s1：任务优先级阶段，其步骤如下：s1.1：获取多个任务，计算每个任务的预测完成时间矩阵，预测完成时间矩阵中的行表示为任务，列表示为虚拟机，pm(ξ
i
,pr
j
)表示第i个任务ξ
i
分配在第j个虚拟机pr
j
上执行的预测完成时间矩阵值；s1.2：计算每个任务的优先级，并比较当前任务和后继任务的优先级，若当前任务优先级小于后继任务的优先级，则更新预测完成时间矩阵值和任务优先级，再根据更新后的任务优先级降序排列得到优先级队列；若当前任务优先级大于后继任务的优先级，则直接根据任务优先级降序排列得到优先级队列；s2：虚拟机选择阶段，其步骤如下：s2.1：计算每个任务的最早完成时间以及乐观调度长度值；s2.2：为每个任务选择乐观调度长度值最小的虚拟机进行调度；s2.3：完成优先级队列调度；s3：计算整个应用程序的调度长度。2.根据权利要求1所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述步骤s1.1中预测完成时间矩阵值pm(ξ
i
,pr
j
)的计算公式为：succ(ξ
i
)表示为ξ
i
任务的直接后继节点集合，pm(ξ
γ
,pr
j
)后继节点的预测完成时间矩阵值，ξ
exit
表示没有后继的任务。3.根据权利要求1所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述步骤s1.2中优先级的计算公式如下：其中rank
pm
(ξ
i
)表示任务的等级值，由每个任务的平均预测完成时间矩阵值计算，|p|为虚拟机的台数。4.根据权利要求3所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述当前任务优先级大于后继任务的优先级，则将任务按照rank
pm
(ξ
i
)值降序排列，得到优先级队列。5.根据权利要求1所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述步骤s1.2中更新预测完成时间矩阵值时，把后继节点的预测完成时间矩阵值pm(ξ
γ
,pr
j
)按比例缩小，其比例缩小的计算公式为：其中rank
pm
(ξ
γ
)表示后继节点对应的优先级。
6.根据权利要求5所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述比例缩小公式中θ是一个常数，取值为1。7.根据权利要求1所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述步骤s2.1中任务的最早完成时间的计算公式为：eft(ξ
i
,pr
j
)＝est(ξ
i
,pr
j
)+w(ξ
i
,pr
j
)其中eft(ξ
i
,pr
j
)为任务ξ
i
在pr
j
上的最早完成时间，est(ξ
i
,pr
j
)为任务ξ
i
在pr
j
上的最早开始时间，w(ξ
i
,pr
j
)为任务ξ
i
分配在pr
j
上所需的计算开销。8.根据权利要求1所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述步骤s2.1中乐观调度长度值的计算公式为：osl(ξ
i
,pr
j
)＝eft(ξ
i
,pr
j
)+pm(ξ
i
,pr
j
)osl(ξ
i
,pr
j
)表示为第i个任务ξ
i
分配在第j个pr
j
的乐观调度长度值。9.根据权利要求1所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述步骤s2.3中优先级队列调度未完成，则返回到步骤s2.2。10.根据权利要求1所述的一种基于预测完成时间矩阵的异构云中心任务调度方法，其特征在于，所述步骤s3中调度长度即退出任务的实际完成时间，其公式表达式为：makespan＝max{aft(ξ
exit
)}。

技术总结
本发明提供的一种基于预测完成时间矩阵的异构云中心任务调度方法，主要包括任务优先级阶段和虚拟机选择阶段，任务优先级阶段中的预测完成时间矩阵不仅能够在任务优先级阶段生成高效的任务调度列表，也能在虚拟机选择阶段正面影响任务对应的虚拟机分配，在满足优先级约束的条件下最小化工作流应用程序的调度长度。综上所述，本发明不仅考虑了直接后继任务的影响，也考虑了当前任务的重要性，任务和虚拟机的分配更加合理，本发明在不牺牲算法时间复杂度的前提下，实现工作流应用程序调度长度(最大完工时间)最小化。度(最大完工时间)最小化。度(最大完工时间)最小化。


技术研发人员：张龙信 艾明慧 曾文亮 万烂军 彭成 袁鑫攀 文志华
受保护的技术使用者：湖南工业大学
技术研发日：2023.03.29
技术公布日：2023/7/12